A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service

The vehicle routing problem with simultaneous pick-up and delivery (VRP-SPD) is a variant of the classical vehicle routing problem (VRP) where clients require simultaneous pick-up and delivery service. Deliveries are supplied from a single depot at the beginning of the vehicle's service, while pick-up loads are taken to the same depot at the conclusion of the service. One important characteristic of this problem is that a vehicle's load in any given route is a mix of pick-up and delivery loads. In this paper we develop a tabu search algorithm to solve VRP-SPD. This algorithm uses three types of movements to obtain inter-route adjacent solutions: the relocation, interchange and crossover movements. A 2-opt procedure is used to obtain alternative intra-route solutions. Four types of neighbourhoods were implemented, three of them defined by the use of each of the single inter-route movements and the fourth by using a combination of these movements. Two different search strategies were implemented for selecting the next movement: first admissible movement and best admissible movement. Intensification and diversification of the search were achieved through frequency penalization. Computational results are reported for a set of 87 test problems with between 50 and 400 clients. (c) 2004 Elsevier Ltd. All rights reserved.