Abstract

The vehicle routing problem with simultaneous pick-up and delivery (VRPSPD) and maximum time limit for traversing of each tour is a variant of the classical vehicle routing problem (VRP) where customers require simultaneous delivery and pick-up. Delivery loads are taken from a single depot at the beginning of the vehicle’s service, while pick-up loads are delivered to the same depot at the end of the service. Also traversing time of each route should not encroach the specified limit. In this research, the aforesaid problem was introduced and a mixed integer programming model was developed for it. Because of being NP-Hard and the impossibility of solving it in the large instances, a hybrid tabu search algorithm was developed to handle the problem. For producing the initial solution for this algorithm, two methods were built. Furthermore, five procedures for improving the solution were developed, which three of them are being used for inter-route and the other two for intra-route improvement. Computational results were reported for 26 produced test problems of the size between 5 to 200 customers.

Key words: Vehicle routing problem, simultaneous pickup and delivery, maximum tour time length, heuristic, hybrid tabu search.