A hybrid Tabu Search algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Maximum Tour Time Length

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. Deliveries are supplied from a single depot at the beginning of thevehicle's service, while pick-up loads are taken to the same depot at the end of the service. Also time of traversing of each route shouldnot encroach the specified limit. In this research, the aforesaid problem was introduced and a mixed integer programming modelwas developed for it. Because of being NP-Hard and theimpossibility of solving it in the large instances, a hybrid Tabu Search algorithm was developed to handle the problem. Forproducing the initial solution for this algorithm, two methods were built. Furthermore, five procedures for improving the solution weredeveloped, 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.

Keywords:

Vehicle Routing Problem , Simultaneous Pickup and Delivery , Maximum tour time length , Heuristic , Hybrid Tabu Search