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

Journal of Advances in Computer Research

مقاله 6، دوره 3، شماره 4، بهمن 2012، صفحه 55-66   

نویسندگان

Majid Yousefikhoshbakht^{* 1}؛ Farzad Didehvar²؛ Farhad Rahmati²

¹Mathematics and Computer Science, Young Researchers club, Hamedan Branch, Islamic Azad University, Hamedan, Iran

²Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

چکیده

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.

کلیدواژه‌ها

Vehicle routing problem؛ Tabu Search؛ NP-hard Problems؛ Simultaneous Pickup and Delivery