Vehicle routing problems with simultaneous pick-up and delivery service

Variations of the classical Vehicle Routing Problem (VRP) consider clients that require pick-up and delivery service, simultaneously or not. Each variation corresponds to a specific routing policy, applicable to a given context. Although several routing problems of this nature are defined in the literature, there are relationships among them that define one problem as a particular case of another, which allows transformation among problems. We classify these problems on the basis of the characteristics of the service required by the clients. We study in particular the Vehicle Routing Problem with Simultaneous Pickup and Delivery Service. This problem may be solved for example through a tour partitioning heuristic developed for the traveling salesman problem (TSP). The routing in each segment of the partitioned tour is achieved by solving capacitated TSP subproblems with simultaneous pick-up and delivery service. Computational results are given for a set of problems available in the literature.