A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem.

ABSTRACT

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.