A reactive greedy randomized adaptive search procedure algorithm for solving the vehicle routing problem with simultaneous pickup and delivery

Abstract This study proposes a novel reactive greedy randomized adaptive search procedure (RGRASP) algorithm to tackle the vehicle routing problem with simultaneous pickup and delivery (VRPSPD), which is an NP‐hard optimization problem with a wide range of applications in reverse logistics management. Efficiently planning routes for simultaneous pickup and delivery activities while ensuring the feasibility of truckload capacity presents significant challenges. To address these complexities, we devise an RGRASP metaheuristic to provide solutions for scalable instances. The strength of our proposed RGRASP lies in its ability to generate new solutions from a dynamically updated solution space in each iteration, ultimately maximizing vehicle utilization and reducing overall routing costs. Computational experiments on 68 publicly available VRPSPD instances show that our algorithm outperforms state‐of‐the‐art methods, achieving better average solutions and finding 14 new best‐known solutions. We also identified and rectified infeasibilities in previously reported best‐known solutions, providing a reliable reference for future research.