A Hybrid Meta-heuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up

Document Type : Research Article

Authors

1 Assistant Professor, Faculty of Engineering (Department of Civil Engeineering), University of Zanjan

2 M.Sc. Student of Highway and Transportation Engineering, Faculty of Engineering, Imam Khomeini International University

Abstract

Vehicle routing problem (VRP) is an important issue that has much used for productivity and efficiency
of transportation systems in recent decades. One of the most popular and widely used developments
VRP is the vehicle routing problem with simultaneous delivery and pick-up (VRPSPD). In other words,
each customer simultaneously receives and sends goods. The proposed procedure is a combination of
the three heuristic: nearest neighbor algorithm, cheapest insertions, genetic algorithm. The first two
algorithms with a random method provided the initial solution for the third algorithm. A probability
function has been developed in the nearest neighbors and cheapest insertions to construct better solutions
as well as operations proposed for the genetic algorithm to increase the search space and avoiding local
optimizations. The proposed algorithms have implemented on forty different standard examples. By
comparing, the results obtained from the best available solutions than other algorithms, improvement
observed in some examples.

Keywords

Main Subjects

References

[1]Dantzig, G. B. and Ramser, R. H.; “The Truck Dispatching Problem,” Management Science, Vol. 6, No. 1, pp. 80–91, 1958.
[2]Min, H.; “The Multiple the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Points,” Transportation Research-Part A, Vol. 23, No. 5, pp. 377–386, 1989.
[3]Salhi, S. and Nagy, G.; “A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with Backhauling,” Journal of the Operational Research Society, Vol. 50, No. 10, pp. 1034–1042, 1999
[4]Dethloff, J.; “Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-up,” OR Spektrum, Vol. 23, No. 1, pp. 79–96, 2001.
[5]Montane, F. A. T. and Galvao, R. D.; “Vehicle Routing Problems with Simultaneous Pick-up and Delivery Service,” OPSEARCH, Vol. 39, No. 1, pp. 19–33, 2002.
[6]Angelelli, E. and Mansini, R.; “The Vehicle Routing Problem with Time Windows and Simultaneous Pick-up and Delivery,” Quantitative Approaches to Distribution Logistics and Supply Chain Management, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, pp. 249–267, 2002.
[7]Nagy, G. and Salhi, S.; “Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries,” European Journal of Operational Research, Vol. 162, No. 1, pp. 126–141, 2005.
[8]Chen, J. F. and Wu, T. H.; “Vehicle Routing Problem with Simultaneous Deliveries and Pickups,” Journal of the Operational Research Society, Vol. 57, No. 5, pp. 579–587, 2006.
[9]Tang-Montane, F. A. and Galvao, R. D.; “A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery Service,” Computers and Operations Research, Vol. 33, No. 3, pp. 595–619, 2006.
[10]Bianchessi, N. and Righini, G.; “Heuristic Algorithms for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery,” Computers and Operations Research, Vol. 34, pp. 2578–594, 2007.
[11]Zachariadis, E.; Tarantilis, D. and Kiranoudis, T.; “A Hybrid Metaheuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Service,” Expert Systems with Applications, Vol. 36, No. 2, pp. 1070–1081, 2009.
[12]Gajpal, Y. and Abad, P.; “An Ant Colony System (ACS) for Vehicle Routing Problem with Simultaneous Delivery and Pick-up,” Computers and Operations Research, Vol. 36, No. 12, pp. 3215–3223, 2009.
[13]Catay, B.; “A New Saving-based Ant Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery,” Expert Systems with Applications, Vol. 37, No. 10, pp. 6809–6817, 2010.
[14]Davis, L.; “Applying Algorithms to Epistatic Domains,” International Joint Conferences on Artificial Intelligence, Vol. 85, pp. 162–164, 1985.
[15]Zachariadis, E. E. and Kiranoudis, C. T.; “A Local Search Meta-heuristic Algorithm for the Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries,” Expert Systems with Applications, Vol. 38, No. 3, pp. 2717–2726, 2011.
Amirkabir Journal of Civil Engineering
Volume 48, Issue 4
December 2016
Pages 375-386

Files

Share

How to cite

Statistics