Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries

The Vehicle Routing Problem with Pickups and Deliveries (VRPPD) is an extension to the classical Vehicle Routing Problem (VRP), where customers may both receive and send goods. We do not make the assumption common in the VRPPD literature, that goods may only be picked up after all deliveries have been completed. We also eschew the concept of insertion and propose a method that treats pickups and deliveries in an integrated manner. This method finds a solution to the corresponding VRP problem and modifies this solution to make it feasible for the VRPPD. Such modification is achieved mainly by heuristic routines taken from VRP methodology but modified such that their aim becomes the reduction of infeasibilities, although a number of problem-specific routines are also constructed. To render our procedures efficient when checking feasibility, we built appropriate mathematical relationships to describe changes in the maximum load of routes. Furthermore, several enhancements are introduced. Our methodology is also capable of solving multi-depot problems, which has not been done before for this challenging general version of the VRPPD. The methods are tested for single and multiple depot problems with encouraging results.