Developing Genetic Algorithm to Solve Vehicle Routing Problem with Simultaneous Pickup and Delivery

Document Type : Original Article

Authors

1 Department of Civil Engineering, Faculty of Engineering, University of Zanjan, Zanjan, Iran

2 Transportation Engineering, Imam Khomeini International University, Qazvin,Iran.

3 Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran.

Abstract

One of the well-known and highly used extensions of vehicle routing problem (VRP) is Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD), in which delivery and pickup for each customer is carried out simultaneously. In this study, it is attempted to present an optimal method for solving VRPSPD using genetic algorithm. In this method, genetic algorithm is improved by modifying genetic parameters and presenting efficient and proper operators. Three Randomized, Nearest neighbor and Cheapest Insertion algorithms are utilized to create the initial population. Given the different structure used in each of these methods, the initial solutions are varied and include all feasible regions. In addition, by making modifications in these methods, the initial population was tried to be created through higher quality solutions to help genetic algorithm reach a better future generation. Also, 4 algorithms were invented for mutation operators, which prevented convergence in local optimums and helped finding better solutions by comparing the results. The proposed algorithm is executed on 40 different standard examples. After comparing the results by this algorithm and the best solutions by other algorithms, improvement is observed in 3 of the examples.

Keywords

Main Subjects


[1] Min H. The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General. 1989 Sep 1;23(5):377-86. [View at Google Scholar] ; [View at Publisher].
[2] Fu C, Zhang L, Wang X, Qiao L. Solving TSP problem with improved genetic algorithm. InAIP Conference Proceedings 2018 May 23 (Vol. 1967, No. 1, p. 040057). AIP Publishing LLC. [View at Google Scholar] ; [View at Publisher].
[3] Hussain A, Muhammad YS, Nauman Sajid M, Hussain I, Mohamd Shoukry A, Gani S. Genetic algorithm for traveling salesman problem with modified cycle crossover operator. Computational intelligence and neuroscience. 2017 Oct 25;2017. [View at Google Scholar] ; [View at Publisher].
[4] Salhi S, Nagy G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. Journal of the operational Research Society. 1999 Oct 1;50(10):1034-42. [View at Google Scholar] ; [View at Publisher].
[5] Dethloff J. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum. 2001 Feb 1;23(1):79-96. [View at Google Scholar] ; [View at Publisher].
[6] Montané FA, Galvão RD. Vehicle routing problems with simultaneous pick-up and delivery service. Opsearch. 2002 Feb 1;39(1):19-33. [View at Google Scholar] ; [View at Publisher].
[7] Nagy G, Salhi S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European journal of operational research. 2005 Apr 1;162(1):126-41. [View at Google Scholar] ; [View at Publisher].
[8] Chen JF, Wu TH. Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society. 2006 May 1;57(5):579-87. [View at Google Scholar] ; [View at Publisher].
[9] Montané FA, Galvao RD. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research. 2006 Mar 1;33(3):595-619. [View at Google Scholar] ; [View at Publisher].
[10] Bianchessi N, Righini G. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers & Operations Research. 2007 Feb 1;34(2):578-94. [View at Google Scholar] ; [View at Publisher].
[11] Zachariadis EE, Tarantilis CD, Kiranoudis CT. A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. Expert Systems with applications. 2009 Mar 1;36(2):1070-81. [View at Google Scholar] ; [View at Publisher].
[12] Gajpal Y, Abad P. An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Computers & Operations Research. 2009 Dec 1;36(12):3215-23. [View at Google Scholar] ; [View at Publisher].
[13] Çatay B. A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications. 2010 Oct 1;37(10):6809-17. [View at Google Scholar] ; [View at Publisher].
[14] Zachariadis EE, Kiranoudis CT. A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Systems with Applications. 2011 Mar 1;38(3):2717-26. [View at Google Scholar] ; [View at Publisher].
[15] Mukhopadhyay DM, Balitanas MO, Farkhod A, Jeon SH, Bhattacharyya D. Genetic algorithm: A tutorial review. International journal of grid and distributed computing. 2009 Sep 1;2(3):25-32. [View at Google Scholar] ; [View at Publisher].
[16] Mirjalili S, Dong JS, Sadiq AS, Faris H. Genetic algorithm: Theory, literature review, and application in image reconstruction. InNature-Inspired Optimizers 2020 (pp. 69-85). Springer, Cham. [View at Google Scholar] ; [View at Publisher].
[17] Donis-Díaz CA, Bello R, Kacprzyk J. Using ant colony optimization and genetic algorithms for the linguistic summarization of creep data. InIntelligent Systems' 2014 2015 (pp. 81-92). Springer, Cham. [View at Google Scholar] ; [View at Publisher].
[18] Schroeders U, Wilhelm O, Olaru G. Meta-heuristics in short scale construction: Ant colony optimization and genetic algorithm. PLoS One. 2016 Nov 28;11(11):e0167110. [View at Google Scholar] ; [View at Publisher].
[19] Zhao F, Yao Z, Luan J, Song X. A novel fused optimization algorithm of genetic algorithm and ant colony optimization. Mathematical Problems in Engineering. 2016 Jan 1;2016. [View at Google Scholar] ; [View at Publisher].
[20] Asadi AA, Naserasadi A, Asadi ZA. A new hybrid algorithm for traveler salesman problem based on genetic algorithms and artificial neural networks. International Journal of Computer Applications. 2011;975:8887. [View at Google Scholar] ; [View at Publisher].
[21] Kartheeswaran S, Durairaj DD. A hybrid genetic algorithm and back-propagation artificial neural network based simulation system for medical image reconstruction in noise-added magnetic resonance imaging data. In2015 Online International Conference on Green Engineering and Technologies (IC-GET) 2015 Nov 27 (pp. 1-6). IEEE. [View at Google Scholar] ; [View at Publisher].
[22] Fatyanosa TN, Sihananto AN, Alfarisy GA, Burhan MS, Mahmudy WF. Hybrid genetic algorithm and simulated annealing for function optimization. Journal of Information Technology and Computer Science. 2017 Feb 8;1(2):82-97. [View at Google Scholar] ; [View at Publisher].
[23] Chen PH, Shahandashti SM. Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints. Automation in Construction. 2009 Jul 1;18(4):434-43. [View at Google Scholar] ; [View at Publisher].
[24] Pomar LA, Pulido EC, Roa JD. A Hybrid Genetic Algorithm and Particle Swarm Optimization for Flow Shop Scheduling Problems. InWorkshop on Engineering Applications 2017 Sep 27 (pp. 601-612). Springer, Cham. [View at Google Scholar] ; [View at Publisher].
[25] Kuo RJ, Han YS. A hybrid of genetic algorithm and particle swarm optimization for solving bi-level linear programming problem–A case study on supply chain model. Applied Mathematical Modelling. 2011 Aug 1;35(8):3905-17. [View at Google Scholar] ; [View at Publisher].
[26] Cherki I, Chaker A, Djidar Z, Khalfallah N, Benzergua F. A Sequential Hybridization of Genetic Algorithm and Particle Swarm Optimization for the Optimal Reactive Power Flow. Sustainability. 2019 Jan;11(14):3862. [View at Google Scholar] ; [View at Publisher].
[27] DengWei L. Optimization design based on hierarchic genetic algorithm and particles swarm algorithm. Journal of Algorithms & Computational Technology. 2018 Sep;12(3):217-22. [View at Google Scholar] ; [View at Publisher].
[28] Melanie M. An introduction to genetic algorithms. Cambridge, Massachusetts London, England, Fifth Print 1999; 3: 62–75. [View at Publisher].
[29] Davis L. Applying adaptive algorithms to epistatic domains. InIJCAI 1985 Aug 18 (Vol. 85, pp. 162-164). [View at Google Scholar] ; [View at Publisher].
[30] Simsir F, Ekmekci D. A metaheuristic solution approach to capacitied vehicle routing and network optimization. Engineering Science and Technology, an International Journal. 2019 Jun 1;22(3):727-35. [View at Google Scholar] ; [View at Publisher].