New Lower Bounds for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

The present work deals with the Vehicle Routing Problem with SimultaneousPickup and Delivery (VRPSPD). In this problem, the customershave both delivery and pickup demands. We propose undirectedand directed two-commodity flow formulations, which are based on theone developed by Baldacci, Hadjiconstantinou and Mingozzi for the CapacitatedVehicle Routing Problem. These new formulations are theoreticallycompared with the one-commodity flow formulation proposedby Dell’Amico, Righini and Salani. The three formulations were testedwithin a branch-and-cut scheme and their practical performance was measuredin well-known benchmark problems available in the literature. Theundirected two-commodity flow formulation obtained consistently betterresults. We also ran the three formulations in a particular case of theVRPSPD, namely the Vehicle Routing Problem with Mixed Pickup andDelivery (VRPMPD). Several optimal solutions to open problems with upto 100 customers and new improved lower bounds for instances with upto 200 customers were found.