Dalbah Lamees Mohammad, Al-Betar Mohammed Azmi, Awadallah Mohammed A, Zitar Raed Abu
Artificial Intelligence Research Center (AIRC), College of Engineering and Information Technology, Ajman University, Ajman, United Arab Emirates.
Department of Information Technology, Al-Huson University College, Al-Balqa Applied University, P.O. Box 50, Al-Huson, Irbid, Jordan.
J King Saud Univ Comput Inf Sci. 2022 Sep;34(8):4782-4795. doi: 10.1016/j.jksuci.2021.06.013. Epub 2021 Jun 24.
Capacitated Vehicle routing problem is NP-hard scheduling problem in which the main concern is to find the best routes with minimum cost for a number of vehicles serving a number of scattered customers under some vehicle capacity constraint. Due to the complex nature of the capacitated vehicle routing problem, metaheuristic optimization algorithms are widely used for tackling this type of challenge. Coronavirus Herd Immunity Optimizer (CHIO) is a recent metaheuristic population-based algorithm that mimics the COVID-19 herd immunity treatment strategy. In this paper, CHIO is modified for capacitated vehicle routing problem. The modifications for CHIO are accomplished by modifying its operators to preserve the solution feasibility for this type of vehicle routing problems. To evaluate the modified CHIO, two sets of data sets are used: the first data set has ten Synthetic CVRP models while the second is an ABEFMP data set which has 27 instances with different models. Moreover, the results achieved by modified CHIO are compared against the results of other 13 well-regarded algorithms. For the first data set, the modified CHIO is able to gain the same results as the other comparative methods in two out of ten instances and acceptable results in the rest. For the second and the more complicated data sets, the modified CHIO is able to achieve very competitive results and ranked the first for 8 instances out of 27. In a nutshell, the modified CHIO is able to efficiently solve the capacitated vehicle routing problem and can be utilized for other routing problems in the future such as multiple travelling salesman problem.
容量受限车辆路径问题是一个NP难的调度问题，主要关注点是在车辆容量约束下，为若干服务多个分散客户的车辆找到成本最低的最佳路径。由于容量受限车辆路径问题的复杂性，元启发式优化算法被广泛用于应对这类挑战。冠状病毒群体免疫优化器（CHIO）是一种最近基于群体的元启发式算法，它模仿了新冠疫情群体免疫治疗策略。在本文中，对CHIO进行了修改以解决容量受限车辆路径问题。通过修改其算子来完成对CHIO的修改，以保持这类车辆路径问题的解的可行性。为了评估修改后的CHIO，使用了两组数据集：第一组数据集有十个合成CVRP模型，而第二组是ABEFMP数据集，它有27个不同模型的实例。此外，将修改后的CHIO所取得的结果与其他13种广受认可的算法的结果进行了比较。对于第一组数据集，修改后的CHIO在十个实例中的两个实例中能够获得与其他比较方法相同的结果，在其余实例中获得可接受的结果。对于第二组且更复杂的数据集，修改后的CHIO能够取得非常有竞争力的结果，在27个实例中的8个实例中排名第一。简而言之，修改后的CHIO能够有效地解决容量受限车辆路径问题，并且未来可用于其他路径问题，如多旅行商问题。
