A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem
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 routi...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2022-09-01
|
| Series: | Journal of King Saud University: Computer and Information Sciences |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1319157821001464 |
| _version_ | 1811310009667026944 |
|---|---|
| author | Lamees Mohammad Dalbah Mohammed Azmi Al-Betar Mohammed A. Awadallah Raed Abu Zitar |
| author_facet | Lamees Mohammad Dalbah Mohammed Azmi Al-Betar Mohammed A. Awadallah Raed Abu Zitar |
| author_sort | Lamees Mohammad Dalbah |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-13T09:52:15Z |
| format | Article |
| id | doaj.art-ad3c4eb4cb584f7e970918117a0e42d8 |
| institution | Directory Open Access Journal |
| issn | 1319-1578 |
| language | English |
| last_indexed | 2024-04-13T09:52:15Z |
| publishDate | 2022-09-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Journal of King Saud University: Computer and Information Sciences |
| spelling | doaj.art-ad3c4eb4cb584f7e970918117a0e42d82022-12-22T02:51:34ZengElsevierJournal of King Saud University: Computer and Information Sciences1319-15782022-09-0134847824795A modified coronavirus herd immunity optimizer for capacitated vehicle routing problemLamees Mohammad Dalbah0Mohammed Azmi Al-Betar1Mohammed A. Awadallah2Raed Abu Zitar3Artificial Intelligence Research Center (AIRC), College of Engineering and Information Technology, Ajman University, Ajman, United Arab EmiratesArtificial 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; Corresponding author at: Artificial Intelligence Research Center (AIRC), College of Engineering and Information Technology, Ajman University, Ajman, United Arab Emirates.Department of Computer Science, Al-Aqsa University, P.O. Box 4051, Gaza, Palestine; Artificial Intelligence Research Center (AIRC), Ajman University, Ajman, United Arab EmiratesSorbonne Center of Artificial Intelligence, Sorbonne University-Abu Dhabi, Abu Dhabi, United Arab EmiratesCapacitated 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.http://www.sciencedirect.com/science/article/pii/S1319157821001464OptimizationCoronavirus Herd Immunity Optimizer (CHIO)Vehicle routing problemCOVID-19Metaheuristics |
| spellingShingle | Lamees Mohammad Dalbah Mohammed Azmi Al-Betar Mohammed A. Awadallah Raed Abu Zitar A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem Journal of King Saud University: Computer and Information Sciences Optimization Coronavirus Herd Immunity Optimizer (CHIO) Vehicle routing problem COVID-19 Metaheuristics |
| title | A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem |
| title_full | A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem |
| title_fullStr | A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem |
| title_full_unstemmed | A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem |
| title_short | A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem |
| title_sort | modified coronavirus herd immunity optimizer for capacitated vehicle routing problem |
| topic | Optimization Coronavirus Herd Immunity Optimizer (CHIO) Vehicle routing problem COVID-19 Metaheuristics |
| url | http://www.sciencedirect.com/science/article/pii/S1319157821001464 |
| work_keys_str_mv | AT lameesmohammaddalbah amodifiedcoronavirusherdimmunityoptimizerforcapacitatedvehicleroutingproblem AT mohammedazmialbetar amodifiedcoronavirusherdimmunityoptimizerforcapacitatedvehicleroutingproblem AT mohammedaawadallah amodifiedcoronavirusherdimmunityoptimizerforcapacitatedvehicleroutingproblem AT raedabuzitar amodifiedcoronavirusherdimmunityoptimizerforcapacitatedvehicleroutingproblem AT lameesmohammaddalbah modifiedcoronavirusherdimmunityoptimizerforcapacitatedvehicleroutingproblem AT mohammedazmialbetar modifiedcoronavirusherdimmunityoptimizerforcapacitatedvehicleroutingproblem AT mohammedaawadallah modifiedcoronavirusherdimmunityoptimizerforcapacitatedvehicleroutingproblem AT raedabuzitar modifiedcoronavirusherdimmunityoptimizerforcapacitatedvehicleroutingproblem |