Hybrid Coronavirus Herd Immunity Optimizer with Whale Optimization Algorithm for Vehicle Routing Problem with Soft Time Windows
Keywords:
Coronavirus Herd Immunity Optimizer, Whale Optimization Algorithm, Vehicle Routing Problem, Time WindowsAbstract
Vehicle Routing Problem with Time Windows (VRPTW) is one of the combinatorial optimization problems that objective is to find the optimal set of routes for a fleet of vehicles to service a set of customers, a given set of demands within time window. This paper presents the hybrid the Coronavirus Herd immunity Optimizer with Whale Optimization Algorithm (HCHIO-WOA) for solving VRPTW. The Coronavirus Herd Immunity Optimizer (CHIO) mimics the mechanism the social distancing in the herd immunity strategy. The parameters of CHIO are controlled by basic reproduction rate ( ) and maximum age of infected cases ( ). The Largest Rank Value (LRV) is used for generating the initial solution. In other case, the random number is larger than that WOA is used for selecting the new solution to avoid trapped in local optimal. The local search comprised 2-Operator, Lambda-Interchange method and Alternating Edges Crossover (AEX) for solution improvement. The proposed method has been tested in Solomon instance in different size problems and compared with other existing algorithms. The experiment result shows that the average gap of HCHIO-WOA is larger than Best Known Solution for small and medium problems which are 0.32% and 2.06%, respectively. The large problem found 9 out of 11 instances in Best Known Solution that is large value at 0.08%.
References
G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Management Science, vol. 6, no. 1, pp. 80–91, 1959.
S. Mouthuy, F. Massen, Y. Deville and P. Van Hentenryck, “A multistage very large-scale neighborhood search for the vehicle routing problem with soft time windows,” Transportation Science, vol. 49, no. 2, pp. 223–238, 2015, doi: 10.1287/trsc.2014.0558.
D. Taş, O. Jabali and T. Van Woensel, “A vehicle routing problem with flexible time windows,” Computers & Operations Research, vol. 52, pp. 39–54, 2014, doi: 10.1016/j.cor.2014.07.005.
M. Batsyn, I. Bychkov, L. Komosko and A. Nikolaev, “Tabu Search for Fleet Size and Mix Vehicle Routing Problem with Hard and Soft Time Windows,” in International Conference on Network Analysis, Nizhny Novgorod, Russia, May. 26–28, 2016, 2016, pp. 3–18.
P. Badeau, F. Guertin, M. Gendreau, J.-Y. Potvin and E. Taillard, “A parallel tabu search heuristic for the vehicle routing problem with time windows,” Transportation Research Part C: Emerging Technologies, vol. 5, no. 2, pp. 109–122, 1997, doi: 10.1016/S0968-090X(97)00005-3.
B. Ombuki, B. Ross, and F. Hanshar, “Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows,” Applied Intelligence, vol. 24, pp. 17–30, 2006, doi: 10.1007/s10489-006-6926-z.
W. C. Chiang and R. A. Russell, “Simulated annealing metaheuristics for the vehicle routing problem with time windows,” Annals of Operations Research, vol. 63, pp. 3–27, 1996, doi: 10.1007/BF02601637.
G. B. Alvarenga, G. R. Mateus and G. De Tomi, “A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows,” Computers & Operations Research, vol. 34, no. 6, pp. 1561–1584, 2007, doi:10.1016/j.cor.2005.07.025.
B. Yu, Z.-Z. Yang and B. Yao, “A hybrid algorithm for vehicle routing problem with time windows,” Expert Systems with Applications, vol. 38, no. 1, pp. 435–441, 2011, doi: 10.1016/j.eswa.2010.06.082.
Y. -J. Gong, J. Zhang, O. Liu, R. -Z. Huang, H. S. -H. Chung and Y. -H. Shi, “Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach,” IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 42, no. 2, pp. 254–267, 2011, doi: 10.1109/TSMCC.2011.2148712.
B. Yao, Q. Yan, M. Zhang and Y. Yang, “Improved artificial bee colony algorithm for vehicle routing problem with time windows,” PloS One, vol. 12, no. 9, 2017, Art. no. e0181275, doi: 10.1371/journal.pone.0181275.
D. Aggarwal and V. Kumar, “Performance evaluation of distance metrics on firefly algorithm for VRP with time windows,” International Journal of Information Technology, vol. 13, pp. 2355–2362, 2021, doi: 10.1007/s41870-019-00387-7.
Y. Shen, M. Liu, J. Yang, Y. Shi and M. Middendorf, “A hybrid swarm intelligence algorithm for vehicle routing problem with time windows,” IEEE Access, vol. 8, pp. 93882–93893, 2020, doi: 10.1109/ACCESS.2020.2984660.
M. A. Al-Betar, Z. A. A. Alyasseri, M. A. Awadallah and I. Abu Doush, “Coronavirus herd immunity optimizer (CHIO),” Neural Computing and Applications, vol. 33, pp. 5011–5042, 2021, doi: 10.1007/s00521-020-05296-6.
M. Alqarni, “Sodium sulfur batteries allocation in high renewable penetration microgrids using coronavirus herd immunity optimization,” Ain Shams Engineering Journal, vol. 13, no. 2, 2022, Art. no. 101590, doi:10.1016/j.asej.2021.09.017.
M. M. Refaat, S. H. A. Aleem, Y. Atia, Z. M. Ali and M. M. Sayed, “AC and DC Transmission Line Expansion Planning Using Coronavirus Herd Immunity Optimizer,” in 22nd International Middle East Power Systems Conference (MEPCON), Assiut, Egypt, Dec. 14–16, 2021, pp. 313–318, doi:10.1109/MEPCON50283.2021.9686191.
C. Kumar, D. Magdalin Mary and T. Gunasekar, “MOCHIO: a novel Multi-Objective Coronavirus Herd Immunity Optimization algorithm for solving brushless direct current wheel motor design optimization problem,” Automatika, vol. 63, no. 1, pp. 149–170, 2022, doi: 10.1080/00051144.2021.2014035.
S. N. Makhadmeh, M. A. Al-Betar, M. A. Awadallah, A. K. Abasi, Z. A. A. Alyasseri, I. A. Doush, O. A. Alomari, R. Damaševičius, A. Zajančkauskas and M. A. Mohammed, “A Modified Coronavirus Herd Immunity Optimizer for the Power Scheduling Problem,” Mathematics, vol. 10, no. 10, 2022, Art. no. 315, doi: 10.3390/math10030315.
A. Naderipour, A. Abdullah, M. H. Marzbali and S. A. Nowdeh, “An improved corona-virus herd immunity optimizer algorithm for network reconfiguration based on fuzzy multi-criteria approach,” Expert Systems with Applications, vol. 187, 2022, Art. no. 115914, doi: 10.1016/j.eswa.2021.115914.
Z. M. Ali, S. H. A. Aleem, A. I. Omar, and B. S. Mahmoud, “Economical-Environmental-Technical Operation of Power Networks with High Penetration of Renewable Energy Systems Using Multi-Objective Coronavirus Herd Immunity Algorithm,” Mathematics, vol. 10, no. 7, 2022, doi: 10.3390/math10071201.
L. M. Dalbah, M. A. Al-Betar, M. A. Awadallah, and R. A. Zitar, “A coronavirus herd immunity optimization (CHIO) for travelling salesman problem,” International Conference on Innovative Computing and Communications, 2022, pp. 717–729, 2022, doi: 10.1007/978-981-16-3071-2_58.
L. M. Dalbah, M. A. Al-Betar, M. A. Awadallah and R. A. Zitar, “A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem,” Journal of King Saud University-Computer and Information Sciences, vol. 34, no. 8, pp. 4782–4795, 2021, doi: 10.1016/j.jksuci.2021.06.013.
M. Alweshah, S. Alkhalaileh, M. A. Al-Betar, and A. A. Bakar, “Coronavirus herd immunity optimizer with greedy crossover for feature selection in medical diagnosis,” Knowledge-Based Systems, vol. 235, 2022, Art. no. 107629, doi:10.1016/j.knosys.2021.107629.
S. Mirjalili and A. Lewis, “The whale optimization algorithm,” Advances in Engineering Software, vol. 95, pp. 51–67, 2016, doi: 10.1016/j.advengsoft.2016.01.008.
S. Khalilpourazari, S. H. R. Pasandideh and A. Ghodratnama, “Robust possibilistic programming for multi-item EOQ model with defective supply batches: Whale Optimization and Water Cycle Algorithms,” Neural Computing and Applications, vol. 31, pp. 6587–6614, 2019, doi: 10.1007/s00521-018-3492-3.
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, doi: 10.1080/21642583.2020.1863276.
M. Abdel-Basset, G. Manogaran, D. El-Shahat and S. Mirjalili, “A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem,” Future Generation Computer Systems, vol. 85, pp. 129–145, 2018, doi: 10.1016/j.future.2018.03.020.
J. Zhang, L. Hong, and Q. Liu, “An improved whale optimization algorithm for the traveling salesman problem,” Symmetry, vol. 13, no. 1, 2021, Art. no. 48, doi: 10.3390/sym13010048.
P. Stephan, T. Stephan, R. Kannan and A. Abraham, “A hybrid artificial bee colony with whale optimization algorithm for improved breast cancer diagnosis,” Neural Computing and Applications, vol. 33, pp. 13667–13691, 2021, doi:10.1007/s00521-021-05997-6.
M. Abdel-Basset, V. Chang, and R. Mohamed, “HSMA_WOA: A hybrid novel Slime mould algorithm with whale optimization algorithm for tackling the image segmentation problem of chest X-ray images,” Applied Soft Computing, vol. 95, 2020, Art. no. 106642, doi: 10.1016/j.asoc.2020.106642.
G. -Y. Ning and D. -Q. Cao, “Improved Whale Optimization Algorithm for Solving Constrained Optimization Problems,” Discrete Dynamics in Nature and Society, vol. 2021, 2021, Art. no. 8832251, doi: 10.1155/2021/8832251.
M. M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Operations Research, vol. 35, pp. 254–265, 1987, doi: 10.1287/opre.35.2.254.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Faculty of Engineering, King Mongkut’s Institute of Technology Ladkrabang
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
The published articles are copyrighted by the School of Engineering, King Mongkut's Institute of Technology Ladkrabang.
The statements contained in each article in this academic journal are the personal opinions of each author and are not related to King Mongkut's Institute of Technology Ladkrabang and other faculty members in the institute.
Responsibility for all elements of each article belongs to each author; If there are any mistakes, each author is solely responsible for his own articles.
