An Improved Modified Tabu Search Algorithm to Solve the Vehicle Routing Problem with Simultaneous Pickupand Delivery

The vehicle routing problem with simultaneous pickup and delivery (VRPSPD)is a well-known combinatorial optimization problem which addresses providedservice to a set of customers using a homogeneous fleet of capacitated vehicles. Theobjective is to minimize the distance traveled. The VRPSPD is an NP-hardcombinatorial optimization problem. Therefore, practical large-scale instances ofVRPSPD cannot be solved by exact solution methodologies within acceptablecomputational time. Our interest was therefore focused on meta-heuristic solutionapproaches. For this reason, a modified tabu search (PA) is proposed for solvingthe VRPSPD in this paper. tComputational results on several standard instances ofVRPSPD show the efficiency of the PA compared with other meta-heuristicalgorithms.

Keywords:

Vehicle Routing Problem , Tabu Search , NP-hard Problems , SimultaneousPickup and Delivery