A Branch-and-Cut Approach to the Vehicle Routing Problem with Simultaneous Delivery and Pick-up

The vehicle routing problem with simultaneous delivery and pickup (VRPSDP) is an extension of the capacitated vehicle routing problem in which products have to be transported from the depot to customer locations and other products have to be trucked from customer locations to the depot. Each customer requires a simultaneous delivery and pick-up of goods by the same vehicle. The VRPSDP is a basic problem in reverse logistics: In addition to the distribution process to the customers, re-usable goods have to be transported in the reverse direction. We implement a branch-and-cut approach and study how it can be applied to the solution of the VRPSDP. The computational tests have been performed on known benchmark instances. Some benchmark problems are solved to optimality for the first time