A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem
The multi-compartment vehicle routing problem (MCVRP) has been applied in fuel or food delivery, waste collection, and livestock transportation. Ant colony optimization algorithm (ACO) has been recognized as an efficient method to solve the VRP and its variants. In this paper, an improved hybrid ant...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2020/8839526 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832566091149213696 |
|---|---|
| author | Ning Guo Bin Qian Rong Hu Huai P. Jin Feng H. Xiang |
| author_facet | Ning Guo Bin Qian Rong Hu Huai P. Jin Feng H. Xiang |
| author_sort | Ning Guo |
| collection | DOAJ |
| description | The multi-compartment vehicle routing problem (MCVRP) has been applied in fuel or food delivery, waste collection, and livestock transportation. Ant colony optimization algorithm (ACO) has been recognized as an efficient method to solve the VRP and its variants. In this paper, an improved hybrid ant colony optimization algorithm (IHACO) is proposed to minimize the total mileage of the MCVRP. First, a probabilistic model is designed to guide the algorithm search towards high-quality regions or solutions by considering both similar blocks of customers and customer permutations. Then, a heuristic rule is presented to generate initial individuals to initialize the probabilistic model, which can drive the search to the high-quality regions faster. Moreover, a new local search using the geometry optimization is developed to execute exploitation from the promising regions. Finally, two types of variable neighborhood descent (VND) techniques based on the speed-up search strategy and the first move strategy are devised to further enhance the local exploitation ability. Comparative numerical experiments with other algorithms and statistical analyses are carried out, and the results show that IHACO can achieve better solutions. |
| format | Article |
| id | doaj-art-b5048d47463944279047c065ca813380 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-b5048d47463944279047c065ca8133802025-02-03T01:05:11ZengWileyComplexity1076-27871099-05262020-01-01202010.1155/2020/88395268839526A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing ProblemNing Guo0Bin Qian1Rong Hu2Huai P. Jin3Feng H. Xiang4Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, ChinaFaculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, ChinaFaculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, ChinaFaculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, ChinaFaculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, ChinaThe multi-compartment vehicle routing problem (MCVRP) has been applied in fuel or food delivery, waste collection, and livestock transportation. Ant colony optimization algorithm (ACO) has been recognized as an efficient method to solve the VRP and its variants. In this paper, an improved hybrid ant colony optimization algorithm (IHACO) is proposed to minimize the total mileage of the MCVRP. First, a probabilistic model is designed to guide the algorithm search towards high-quality regions or solutions by considering both similar blocks of customers and customer permutations. Then, a heuristic rule is presented to generate initial individuals to initialize the probabilistic model, which can drive the search to the high-quality regions faster. Moreover, a new local search using the geometry optimization is developed to execute exploitation from the promising regions. Finally, two types of variable neighborhood descent (VND) techniques based on the speed-up search strategy and the first move strategy are devised to further enhance the local exploitation ability. Comparative numerical experiments with other algorithms and statistical analyses are carried out, and the results show that IHACO can achieve better solutions.http://dx.doi.org/10.1155/2020/8839526 |
| spellingShingle | Ning Guo Bin Qian Rong Hu Huai P. Jin Feng H. Xiang A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem Complexity |
| title | A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem |
| title_full | A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem |
| title_fullStr | A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem |
| title_full_unstemmed | A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem |
| title_short | A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem |
| title_sort | hybrid ant colony optimization algorithm for multi compartment vehicle routing problem |
| url | http://dx.doi.org/10.1155/2020/8839526 |
| work_keys_str_mv | AT ningguo ahybridantcolonyoptimizationalgorithmformulticompartmentvehicleroutingproblem AT binqian ahybridantcolonyoptimizationalgorithmformulticompartmentvehicleroutingproblem AT ronghu ahybridantcolonyoptimizationalgorithmformulticompartmentvehicleroutingproblem AT huaipjin ahybridantcolonyoptimizationalgorithmformulticompartmentvehicleroutingproblem AT fenghxiang ahybridantcolonyoptimizationalgorithmformulticompartmentvehicleroutingproblem AT ningguo hybridantcolonyoptimizationalgorithmformulticompartmentvehicleroutingproblem AT binqian hybridantcolonyoptimizationalgorithmformulticompartmentvehicleroutingproblem AT ronghu hybridantcolonyoptimizationalgorithmformulticompartmentvehicleroutingproblem AT huaipjin hybridantcolonyoptimizationalgorithmformulticompartmentvehicleroutingproblem AT fenghxiang hybridantcolonyoptimizationalgorithmformulticompartmentvehicleroutingproblem |