An efficient heuristic for very large-scale vehicle routing problems with simultaneous pickup and delivery

The paper discusses two variants of the Capacitated Vehicle Routing Problem (CVRP), in which each customer to be visited can require both pickup and delivery, or only either pickup and delivery but not both. These problems are referred to, respectively, as the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) and as the Vehicle Routing Problem with Mixed Pickup and Delivery (VRPMPD). Both VRPSPD and VRPMPD are particularly relevant in practical logistics distribution scenarios, especially when dealing with a substantial number of pickup and delivery locations. The aim of this work is to provide an algorithm which extends, through a variety of specializations, the FILO framework, originally proposed and specifically designed for the CVRP. This variant, called FSPD, has been developed to accomplish two objectives: first, being competitive with the state-of-the-art algorithms for the VRPSPD and VRPMPD; second, efficiently solving new benchmark instances for these problems with a very large number of customers, while maintaining linear scalability of the computing time with respect to the problem size. The extensive computational study and detailed analysis of the algorithm components conducted in this paper demonstrate the successful achievement of both objectives.