New best solutions to VRPSPD benchmark problems by a perturbation based algorithm

Abstract

This paper discusses the vehicle routing problem with simultaneous pickup and delivery (VRPSPD), in which both pickup and delivery tasks simultaneously occur at various customer locations. The objective is to design a set of minimum distance routes with the minimum number of vehicles satisfying all the customers. This paper proposes a heuristic algorithm consisting of a route construction procedure, a route improvement procedure, and a solution perturbation procedure. A new sweep-based route construction method is developed to generate better initial solutions. In the route improvement procedure, a series of inter- and intra-route improvement algorithms are applied. The perturbation procedure perturbs a solution by removing some routes and stops from the solution and reinserting them into the solution. The last procedure is used to escape from local optima. Computational experiments on various benchmark instances are performed to evaluate our algorithm against the previously proposed approaches. New best solutions for many benchmark instances are found. (C) 2011 Elsevier Ltd. All rights reserved.