An Effective Iterated Search for the Profitable Tour Problem With Simultaneous Pickup and Delivery

The Profitable Tour Problem with Simultaneous Pickup and Delivery (PTPSPD) is a practical and challenging variant of the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD), in which not all customers need to be served. This reflects real-world scenarios where fleet size is often limited and incurs significant costs. This study addresses the PTPSPD under realistic constraints and proposes an effective iterated local search algorithm that integrates complementary components to balance exploration and exploitation. A cluster-first, route-second heuristic is employed to generate high-quality initial solutions. The search process is intensified via a randomized variable neighborhood descent strategy. To enhance global exploration, a combination of random perturbation mechanisms and adaptive threshold acceptance criteria is employed. A dynamic tabu list further promotes diversification and prevents premature convergence. The proposed method is evaluated on a benchmark set of 117 PTPSPD instances involving 50 to 199 customers. Results highlight the effectiveness and robustness of the approach, establishing new best-known lower bounds for 64 instances. Additionally, the algorithm is tested on classical VRPSPD instances from the literature, further confirming its ability to consistently provide high-quality solutions within reasonable computational time.