A Genetic Algorithm for Solving Periodic Heterogeneous Vehicle Routing Problem
DOI:
https://doi.org/10.22219/JTIUMM.Vol23.No1.31-42Keywords:
Periodic Routing Problem, Heterogeneous Vehicles, Genetic Algorithm, Taguchi MethodAbstract
This paper addresses the periodic heterogeneous vehicle routing problem (PHVRP), an extension of the classical vehicle routing problems (VRP). This problem is known to be confined to various real-world instances where each customer's demand should be served within a specific time horizon and a maximum demand quantity that can be delivered at each visit. The heterogeneous capacitated vehicles are available to perform the services for each customer. This paper aims to minimize the total traveling time of routes for all vehicles over the time horizon so that the customers' demands can be delivered. Thus, a novel coding scheme is also proposed to directly convert a random sequence of integers into a feasible solution, which is then embedded into algorithms. Furthermore, this paper also compares the performance of the Genetic Algorithm (GA) with the particle swarm optimization algorithm (PSO). The numerical results of the experiments show that the proposed GA is superior to PSO. However, the computation time of PSO is faster than GA.
Downloads
References
D. M. Utama, B. N. I. Farida, U. Fitriani, M. F. Ibrahim, and D. S. Widodo, "Hybrid Henry Gas Solubility Optimization: An Effective Algorithm for Fuel Consumption Vehicle Routing Problem," Jurnal Ilmiah Teknik Industri, vol. 20, no. 2, pp. 141-152, 2021. https://doi.org/10.23917/jiti.v20i2.15640.
D. M. Utama, T. A. Fitria, and A. K. Garside, "Artificial Bee Colony Algorithm for Solving Green Vehicle Routing Problems with Time Windows," Journal of Physics: Conference Series, vol. 1933, no. 1, p. 012043, 2021. https://doi.org/10.1088/1742-6596/1933/1/012043.
D. M. Utama, D. S. Widodo, M. F. Ibrahim, and S. K. Dewi, "A New Hybrid Butterfly Optimization Algorithm for Green Vehicle Routing Problem," Journal of Advanced Transportation, vol. 2020, p. 8834502, 2020. https://doi.org/10.1155/2020/8834502.
P. Toth and D. Vigo, Vehicle routing: problems, methods, and applications. SIAM, 2014.
A. M. Campbell and J. H. Wilson, "Forty years of periodic vehicle routing," Networks, vol. 63, no. 1, pp. 2-15, 2014. https://doi.org/10.1002/net.21527.
D. M. Utama, S. K. Dewi, A. Wahid, and I. Santoso, "The vehicle routing problem for perishable goods: A systematic review," Cogent Engineering, vol. 7, no. 1, p. 1816148, 2020. https://doi.org/10.1080/23311916.2020.1816148.
S. K. Dewi and D. M. Utama, "A New Hybrid Whale Optimization Algorithm for Green Vehicle Routing Problem," Systems Science & Control Engineering, vol. 9, no. 1, pp. 61-72, 2021. https://doi.org/10.1080/21642583.2020.1863276.
E. J. Beltrami and L. D. Bodin, "Networks and vehicle routing for municipal waste collection," vol. 4, no. 1, pp. 65-94, 1974. https://doi.org/10.1002/net.3230040106.
I. M. Chao, B. L. Golden, and E. Wasil, "An improved heuristic for the period vehicle routing problem," Networks, vol. 26, no. 1, pp. 25-44, 1995. https://doi.org/10.1002/net.3230260104.
S. Baptista, R. C. Oliveira, and E. Zúquete, "A period vehicle routing case study," European Journal of Operational Research, vol. 139, no. 2, pp. 220-229, 2002. https://doi.org/10.1016/S0377-2217(01)00363-0.
P. Francis, K. Smilowitz, and M. Tzur, "The Period Vehicle Routing Problem with Service Choice," Transportation Science, vol. 40, no. 4, pp. 439-454, 2006. https://doi.org/10.1287/trsc.1050.0140.
A. R. Pourghaderi, R. Tavakkoli-Moghaddam, M. Alinaghian, and B. Beheshti-Pour, "A simple and effective heuristic for periodic vehicle routing problem," in 2008 IEEE International Conference on Industrial Engineering and Engineering Management, 2008, pp. 133-137. https://doi.org/10.1109/IEEM.2008.4737846.
A. C. Matos and R. C. Oliveira, "An Experimental Study of the Ant Colony System for the Period Vehicle Routing Problem," in Ant Colony Optimization and Swarm Intelligence, Berlin, Heidelberg, 2004, pp. 286-293: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-28646-2_26.
B. Yu and Z. Z. Yang, "An ant colony optimization model: The period vehicle routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, vol. 47, no. 2, pp. 166-181, 2011. https://doi.org/10.1016/j.tre.2010.09.010.
A. K. Garside and N. R. Laili, "A Cluster-First Route-Second Heuristic Approach to Solve The Multi-Trip Periodic Vehicle Routing Problem," Jurnal Teknik Industri, vol. 20, no. 2, pp. 172-181, 2019. https://doi.org/10.22219/JTIUMM.Vol20.No2.172-181.
G. Paletta, "The period traveling salesman problem: a new heuristic algorithm," Computers & Operations Research, vol. 29, no. 10, pp. 1343-1352, 2002. https://doi.org/10.1016/S0305-0548(01)00035-1.
L. Bertazzi, G. Paletta, and M. G. Speranza, "An improved heuristic for the period traveling salesman problem," Computers & Operations Research, vol. 31, no. 8, pp. 1215-1222, 2004. https://doi.org/10.1016/S0305-0548(03)00075-3.
R. A. Russell and D. Gribbin, "A multiphase approach to the period routing problem," Networks, vol. 21, no. 7, pp. 747-765, 1991. https://doi.org/10.1002/net.3230210704.
E. M. Panggabean, H. Mawengkang, Z. Azis, and R. Filia Sari, "Periodic Heterogeneous Vehicle Routing Problem With Driver Scheduling," IOP Conference Series: Materials Science and Engineering, vol. 300, no. 1, p. 012017, 2018. https://doi.org/10.1088/1757-899X/300/1/012017.
T. Vidal, T. G. Crainic, M. Gendreau, N. Lahrichi, and W. Rei, "A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems," Operations Research, vol. 60, no. 3, pp. 611-624, 2012. https://doi.org/10.1287/opre.1120.1048.
R. Cantu-Funes, M. A. Salazar-Aguilar, and V. Boyer, "Multi-depot periodic vehicle routing problem with due dates and time windows," Journal of the Operational Research Society, vol. 69, no. 2, pp. 296-306, 2018. https://doi.org/10.1057/s41274-017-0206-7.
B. Yao, P. Hu, M. Zhang, and S. Wang, "Artificial bee colony algorithm with scanning strategy for the periodic vehicle routing problem," Simulation, vol. 89, no. 6, pp. 762-770, 2013. https://doi.org/10.1177/0037549713481503.
B. M. Baker and M. A. Ayechew, "A genetic algorithm for the vehicle routing problem," Computers & Operations Research, vol. 30, no. 5, pp. 787-800, 2003. https://doi.org/10.1016/S0305-0548(02)00051-5.
M. A. Mohammed, M. K. Abd Ghani, R. I. Hamed, S. A. Mostafa, M. S. Ahmad, and D. A. Ibrahim, "Solving vehicle routing problem by using improved genetic algorithm for optimal solution," Journal of Computational Science, vol. 21, pp. 255-262, 2017. https://doi.org/10.1016/j.jocs.2017.04.003.
G. Zhenfeng, L. Yang, J. Xiaodan, and G. Sheng, "The Electric Vehicle Routing Problem with Time Windows using Genetic Algorithm," in 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), 2017, pp. 635-639. 10.1109/IAEAC.2017.8054093.
P. Li, J. He, D. Zheng, Y. Huang, and C. Fan, "Vehicle Routing Problem with Soft Time Windows Based on Improved Genetic Algorithm for Fruits and Vegetables Distribution," Discrete Dynamics in Nature and Society, vol. 2015, p. 483830, 2015. https://doi.org/10.1155/2015/483830.
Y. P. Anggodo, A. K. Ariyani, M. K. Ardi, and W. F. Mahmudy, "Optimization Of Multi-Trip Vehicle Routing Problem With Time Windows Using Genetic Algorithm," Journal of Environmental Engineering and Sustainable Technology; Vol 3, No 2 (2016)DO - 10.21776/ub.jeest.2017.003.02.4, vol. 3, no. 2, pp. 92-97, 2017. http://dx.doi.org/10.21776/ub.jeest.2017.003.02.4.
C. Yaw and C. Lin, "Solve the vehicle routing problem with time windows via a genetic algorithm," Conference Publications, vol. 2007IS - SpecialSP - 240, p. 249, 2007. https://doi.org/10.3934/proc.2007.2007.240.
M. Mirabi, "A novel hybrid genetic algorithm for the multidepot periodic vehicle routing problem," AI EDAM, vol. 29, no. 1, pp. 45-54, 2015. https://doi.org/10.1017/S0890060414000328.
P. K. Nguyen, T. G. Crainic, and M. Toulouse, "A hybrid generational genetic algorithm for the periodic vehicle routing problem with time windows," Journal of Heuristics, vol. 20, no. 4, pp. 383-416, 2014. https://doi.org/10.1007/s10732-014-9244-3.
R.-M. Chen, Y.-M. Shen, and W.-Z. Hong, "Neural-like encoding particle swarm optimization for periodic vehicle routing problems," Expert Systems with Applications, vol. 138, p. 112833, 2019. https://doi.org/10.1016/j.eswa.2019.112833.
M. F. Ibrahim, F. R. Nurhakiki, D. M. Utama, and A. A. Rizaki, "Optimised Genetic Algorithm Crossover and Mutation Stage for Vehicle Routing Problem Pick-Up and Delivery with Time Windows," IOP Conference Series: Materials Science and Engineering, vol. 1071, no. 1, p. 012025, 2021. https://doi.org/10.1088/1757-899X/1071/1/012025.
N. Choubey, "A Novel Encoding Scheme for Traveling Tournament Problem using Genetic Algorithm," International Journal of Computer Applications, vol. 2, no. 7, pp. 79-82, 2010. http://dx.doi.org/10.5120/1536-139.
S. Gholizadeh, "Structural Optimization for Frequency Constraints," Metaheuristic Applications in Structures and Infrastructures, pp. 389-417, 2013. http://dx.doi.org/10.1016/B978-0-12-398364-0.00016-4.
M. F. Ibrahim, M. M. Putri, D. Farista, and D. M. Utama, "An Improved Genetic Algorithm for Vehicle Routing Problem Pick-up and Delivery with Time Windows," Jurnal Teknik Industri, vol. 22, no. 1, pp. 1-17, 2021. https://doi.org/10.22219/JTIUMM.Vol22.No1.1-17.
S. S. Rao, T.-S. Pan, and V. B. Venkayya, "Optimal placement of actuators in actively controlled structures using genetic algorithms," AIAA Journal, vol. 29, no. 6, pp. 942-943, 1991. https://doi.org/10.2514/3.10683.
G. Taguchi, "Introduction to quality engineering (White Plains, NY: Asian Productivity Organization, Unipub/Kraus International Publications)," 1986.
M. S. Phadke, Quality engineering using robust design. Prentice Hall PTR, 1995.
J.-T. Tsai, W.-H. Ho, T.-K. Liu, and J.-H. Chou, "Improved immune algorithm for global numerical optimization and job-shop scheduling problems," Applied Mathematics and Computation, vol. 194, no. 2, pp. 406-424, 2007. https://doi.org/10.1016/j.amc.2007.04.038.
M. Hoogeboom, W. Dullaert, D. Lai, and D. Vigo, "Efficient Neighborhood Evaluations for the Vehicle Routing Problem with Multiple Time Windows," Transportation Science, vol. 54, no. 2, pp. 400-416, 2020. https://doi.org/10.1287/trsc.2019.0912.
R. F. Mansour, "Using Genetic Algorithm for Identification of Diabetic Retinal Exudates in Digital Color Images %J Journal of Intelligent Learning Systems and Applications," vol. 4, no. 4, pp. 188-198, 2012. http://dx.doi.org/10.4236/jilsa.2012.43019.
A. Ahmadi, F. E. Bouanani, H. Ben-Azza, and Y. Benghabrit, "A Novel Decoder Based on Parallel Genetic Algorithms for Linear Block Codes %J International Journal of Communications, Network and System Sciences," vol. 6, no. 1, pp. 66-76, 2013. http://dx.doi.org/10.4236/ijcns.2013.61008.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Amelia Khoidir, Annisa Kesy Garside
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
