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

Subject Areas : B. Computer Systems Organization

Majid Yousefikhoshbakht ¹ , Farzad Didehvar ² , Farhad Rahmati ³

1 - Mathematics and Computer Science, Young Researchers club, Hamedan Branch, Islamic Azad University, Hamedan, Iran
2 - Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
3 - Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

Received: 2013-05-14 Accepted : 2013-05-14 Published : 2012-11-01

Keywords: Tabu Search, NP-hard Problems, Vehicle routing problem, Simultaneous Pickup and Delivery,

Abstract :

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