An Improved Ant Colony Optimization Algorithm for Vehicle Routing Problem with Time Windows
DOI:
https://doi.org/10.22219/JTIUMM.Vol23.No2.105-120Keywords:
VRPTW, Local Search, Mutation, Ant Colony Optimization , Distribution, Logistic, Supply ChainAbstract
Distribution plays an important role in the supply chain system. One of the critical problems in distribution is the vehicle routing problem. This research proposes the Improved Ant Colony Optimization (IACO) algorithm to solve the Vehicle Routing Problem with Time Windows (VRPTW). The main objective is to minimize the total vehicle mileage by considering the vehicle capacity and customer time windows. The proposed IACO algorithm is inspired by the conventional Ant Colony Optimization (ACO) algorithm by adding local search and mutation processes. Numerical experiments were conducted to test that the routes generated did not violate the customer's time window constraints. In addition, this study also compares the proposed IACO algorithm routes with other metaheuristic algorithms, namely ACO classic and Tabu Search. In addition, this investigation was carried out by experimenting with the number of iterations. The results of numerical experiments prove that the proposed IACO algorithm can minimize the total vehicle mileage without violating capacity constraints and time windows.
Downloads
References
S.-H. Huang, Y.-H. Huang, C. A. Blazquez, and C.-Y. Chen, "Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm," Advanced Engineering Informatics, vol. 51, p. 101536, 2022. https://doi.org/10.1016/j.aei.2022.101536.
C. Kunaka, "Logistics in the Developing World," in International Encyclopedia of Transportation, R. Vickerman, Ed. Oxford: Elsevier, 2021, pp. 150-156, doi: https://doi.org/10.1016/B978-0-08-102671-7.10235-0.
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.
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.
I. Litomin, I. Tolmachov, and A. Galkin, "Use of the Distribution Center in the Ukrainian Distribution System," Transportation Research Procedia, vol. 16, pp. 313-322, 2016. https://doi.org/10.1016/j.trpro.2016.11.030.
W. Huang and T. Zhang, "An improved genetic algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deliveries and Time Windows," in 2016 35th Chinese Control Conference (CCC), 2016, pp. 9639-9643. https://doi.org/10.1109/ChiCC.2016.7554885.
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.
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.
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.
P. Toth and D. Vigo, The vehicle routing problem. SIAM, 2002.
R. Pérez-Rodríguez and A. Hernández-Aguirre, "A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows," Computers & Industrial Engineering, vol. 130, pp. 75-96, 2019. https://doi.org/10.1016/j.cie.2019.02.017.
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.
C. Truden, K. Maier, and P. Armbrust, "Decomposition of the vehicle routing problem with time windows on the time dimension," Transportation Research Procedia, vol. 62, pp. 131-138, 2022. https://doi.org/10.1016/j.trpro.2022.02.017.
K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse, "The vehicle routing problem: State of the art classification and review," Computers & Industrial Engineering, vol. 99, pp. 300-313, 2016. https://doi.org/10.1016/j.cie.2015.12.007.
Y. Wang, L. Wang, Z. Peng, G. Chen, Z. Cai, and L. Xing, "A Multi Ant System based hybrid heuristic algorithm for Vehicle Routing Problem with Service Time Customization," Swarm and Evolutionary Computation, vol. 50, p. 100563, 2019. https://doi.org/10.1016/j.swevo.2019.100563.
W. Zhang, D. Yang, G. Zhang, and M. Gen, "Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence difference-based local search for VRPTW," Expert Systems with Applications, vol. 145, p. 113151, 2020. https://doi.org/10.1016/j.eswa.2019.113151.
M. Suppan, T. Hanne, and R. Dornberger, "Ant Colony Optimization to Solve the Rescue Problem as a Vehicle Routing Problem with Hard Time Windows," in Proceedings of International Joint Conference on Advances in Computational Intelligence, Singapore, 2022, pp. 53-65: Springer Nature Singapore. https://doi.org/10.1007/978-981-19-0332-8_5.
R. Elshaer and H. Awad, "A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants," Computers & Industrial Engineering, vol. 140, p. 106242, 2020. https://doi.org/10.1016/j.cie.2019.106242.
M.-Y. Cheng and D. Prayogo, "Symbiotic Organisms Search: A new metaheuristic optimization algorithm," Computers & Structures, vol. 139, pp. 98-112, 2014. https://doi.org/10.1016/j.compstruc.2014.03.007.
M. Dorigo, M. Birattari, and T. Stutzle, "Ant colony optimization," IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, 2006. https://doi.org/10.1109/MCI.2006.329691.
H. Liu, "Research on cloud computing adaptive task scheduling based on ant colony algorithm," Optik, vol. 258, p. 168677, 2022. https://doi.org/10.1016/j.ijleo.2022.168677.
Y. Wang, L. Wang, G. Chen, Z. Cai, Y. Zhou, and L. Xing, "An Improved Ant Colony Optimization algorithm to the Periodic Vehicle Routing Problem with Time Window and Service Choice," Swarm and Evolutionary Computation, vol. 55, p. 100675, 2020. https://doi.org/10.1016/j.swevo.2020.100675.
D. M. Utama, U. Fitriani, I. Amallynda, and R. D. Azmi, "A Novel Hybrid Yellow Saddle Goatfish Algorithm for Fuel Consumption Vehicle Routing Problem with Simultaneous Pick-up and Delivery Problem," Jurnal Teknik Industri, vol. 23, no. 1, pp. 43-66, 2022. https://doi.org/10.22219/JTIUMM.Vol23.No1.43-66.
D. M. Utama, W. O. N. Safitri, and A. K. Garside, "A Modified Camel Algorithm for Optimizing Green Vehicle Routing Problem with Time Windows," Jurnal Teknik Industri, vol. 24, no. 1, pp. 23-36, 2022. https://doi.org/10.9744/jti.24.1.23-36.
D. M. Utama, B. Widjonarko, and D. S. Widodo, "A novel hybrid jellyfish algorithm for minimizing fuel consumption capacitated vehicle routing problem," Bulletin of Electrical Engineering and Informatics, vol. 11, no. 3, pp. 1272-1279, 2022. https://doi.org/10.11591/eei.v11i3.3263.
Y. Li, H. Soleimani, and M. Zohal, "An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives," Journal of Cleaner Production, vol. 227, pp. 1161-1172, 2019. https://doi.org/10.1016/j.jclepro.2019.03.185.
Q. Ding, X. Hu, L. Sun, and Y. Wang, "An improved ant colony optimization and its application to vehicle routing problem with time windows," Neurocomputing, vol. 98, pp. 101-107, 2012. https://doi.org/10.1016/j.neucom.2011.09.040.
M. Huang and P. Ding, "An Improved Ant Colony Algorithm and Its Application in Vehicle Routing Problem," Mathematical Problems in Engineering, vol. 2013, p. 785383, 2013. https://doi.org/10.1155/2013/785383.
H. Jia, Y. Li, B. Dong, and H. Ya, "An Improved Tabu Search Approach to Vehicle Routing Problem," Procedia - Social and Behavioral Sciences, vol. 96, pp. 1208-1217, 2013. https://doi.org/10.1016/j.sbspro.2013.08.138.
Q. Fu, K. Zhou, H. Qi, and F. Jiang, "A modified tabu search algorithm to solve vehicle routing problem," J. Comput, vol. 29, pp. 197-209, 2018. https://doi.org/10.3966/199115992018062903019.
G. Li and J. Li, "An Improved Tabu Search Algorithm for the Stochastic Vehicle Routing Problem With Soft Time Windows," IEEE Access, vol. 8, pp. 158115-158124, 2020. https://doi.org/10.1109/ACCESS.2020.3020093.
H. Nazif and L. S. Lee, "Optimised crossover genetic algorithm for capacitated vehicle routing problem," Applied Mathematical Modelling, vol. 36, no. 5, pp. 2110-2117, 2012. https://doi.org/10.1016/j.apm.2011.08.010.
S. Zhong-yue, G. Zhong-liang, and W. Qin, "An improved adaptive genetic algorithm for vehicle routing problem," in 2010 International Conference on Logistics Systems and Intelligent Management (ICLSIM), 2010, vol. 1, pp. 116-120. https://doi.org/10.1109/ICLSIM.2010.5461457.
P. Toth and D. Vigo, Vehicle routing: problems, methods, and applications. SIAM, 2014.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Muhammad Faisal Ibrahim, M. I. Mustofa, P Meilanitasari, S. U. Wijaya
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
