An enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem
The capacitated vehicle routing problem (CVRP) is regarded as an NP-hard problem. Moreover, the CVRP is described as a model that can be used in many applications such as transport, logistics, and distribution. The exact algorithms can find exact optimal solutions on the small-sized problem instance...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI
2023
|
| Subjects: | |
| Online Access: | http://eprints.utm.my/107406/1/HabibollahHaron2023_AnEnhancedAntColonySystemAlgorithm.pdf |
| _version_ | 1811132532237795328 |
|---|---|
| author | Ahmed, Zakir Hussain Hameed, Asaad Shakir Mutar, Modhi Lafta Haron, Habibollah |
| author_facet | Ahmed, Zakir Hussain Hameed, Asaad Shakir Mutar, Modhi Lafta Haron, Habibollah |
| author_sort | Ahmed, Zakir Hussain |
| collection | ePrints |
| description | The capacitated vehicle routing problem (CVRP) is regarded as an NP-hard problem. Moreover, the CVRP is described as a model that can be used in many applications such as transport, logistics, and distribution. The exact algorithms can find exact optimal solutions on the small-sized problem instances; however, for large-sized instances it is difficult to find the exact optimal solutions in polynomial time. This reason motivated the researchers to present heuristic/metaheuristic algorithms to solve large-sized problem instances within a reasonable computational time. One of the good algorithms that deal with the CVRP is the ant colony optimization (ACO) algorithm. Several ACO algorithms have been suggested in the literature, such as the ant system (AS) algorithm, ant colony system (ACS) algorithm, and so on. On the other hand, ACO is designed to solve the path problem that finds the best way. However, this algorithm still lacks exploratory mechanisms, which results in premature convergence and stagnation issues. Therefore, we propose to develop an enhanced ACS (EACS) algorithm for solving the CVRP based on subpaths. In our proposed algorithm, we propose to utilize the K-nearest neighbour (KNN) algorithm for finding the best initial solution and then enhance the diversity mechanism of the proposed algorithm by avoiding the generation of the same solution using subpaths. This uses the diversity of the generated solution to find a better solution with a shorter route in a reasonable amount of computational time. Furthermore, we propose to apply the three-opt algorithm to the completed subtour and the k-opt algorithm to the subpath gained from the experience of the subpath. Finally, to verify the effectiveness of the proposed EACS algorithm, the algorithm is tested on some CVRP instances and is compared with one of the state-of-the-art methods, namely, the enhanced simulated annealing algorithm. The comparative study showed a better performance of our EACS compared to the enhanced simulated annealing algorithm. |
| first_indexed | 2024-09-24T00:05:47Z |
| format | Article |
| id | utm.eprints-107406 |
| institution | Universiti Teknologi Malaysia - ePrints |
| language | English |
| last_indexed | 2024-09-24T00:05:47Z |
| publishDate | 2023 |
| publisher | MDPI |
| record_format | dspace |
| spelling | utm.eprints-1074062024-09-11T04:43:57Z http://eprints.utm.my/107406/ An enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem Ahmed, Zakir Hussain Hameed, Asaad Shakir Mutar, Modhi Lafta Haron, Habibollah QA75 Electronic computers. Computer science The capacitated vehicle routing problem (CVRP) is regarded as an NP-hard problem. Moreover, the CVRP is described as a model that can be used in many applications such as transport, logistics, and distribution. The exact algorithms can find exact optimal solutions on the small-sized problem instances; however, for large-sized instances it is difficult to find the exact optimal solutions in polynomial time. This reason motivated the researchers to present heuristic/metaheuristic algorithms to solve large-sized problem instances within a reasonable computational time. One of the good algorithms that deal with the CVRP is the ant colony optimization (ACO) algorithm. Several ACO algorithms have been suggested in the literature, such as the ant system (AS) algorithm, ant colony system (ACS) algorithm, and so on. On the other hand, ACO is designed to solve the path problem that finds the best way. However, this algorithm still lacks exploratory mechanisms, which results in premature convergence and stagnation issues. Therefore, we propose to develop an enhanced ACS (EACS) algorithm for solving the CVRP based on subpaths. In our proposed algorithm, we propose to utilize the K-nearest neighbour (KNN) algorithm for finding the best initial solution and then enhance the diversity mechanism of the proposed algorithm by avoiding the generation of the same solution using subpaths. This uses the diversity of the generated solution to find a better solution with a shorter route in a reasonable amount of computational time. Furthermore, we propose to apply the three-opt algorithm to the completed subtour and the k-opt algorithm to the subpath gained from the experience of the subpath. Finally, to verify the effectiveness of the proposed EACS algorithm, the algorithm is tested on some CVRP instances and is compared with one of the state-of-the-art methods, namely, the enhanced simulated annealing algorithm. The comparative study showed a better performance of our EACS compared to the enhanced simulated annealing algorithm. MDPI 2023-11 Article PeerReviewed application/pdf en http://eprints.utm.my/107406/1/HabibollahHaron2023_AnEnhancedAntColonySystemAlgorithm.pdf Ahmed, Zakir Hussain and Hameed, Asaad Shakir and Mutar, Modhi Lafta and Haron, Habibollah (2023) An enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem. Symmetry, 15 (11). pp. 1-24. ISSN 2073-8994 http://dx.doi.org/10.3390/sym15112020 DOI:10.3390/sym15112020 |
| spellingShingle | QA75 Electronic computers. Computer science Ahmed, Zakir Hussain Hameed, Asaad Shakir Mutar, Modhi Lafta Haron, Habibollah An enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem |
| title | An enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem |
| title_full | An enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem |
| title_fullStr | An enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem |
| title_full_unstemmed | An enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem |
| title_short | An enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem |
| title_sort | enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem |
| topic | QA75 Electronic computers. Computer science |
| url | http://eprints.utm.my/107406/1/HabibollahHaron2023_AnEnhancedAntColonySystemAlgorithm.pdf |
| work_keys_str_mv | AT ahmedzakirhussain anenhancedantcolonysystemalgorithmbasedonsubpathsforsolvingthecapacitatedvehicleroutingproblem AT hameedasaadshakir anenhancedantcolonysystemalgorithmbasedonsubpathsforsolvingthecapacitatedvehicleroutingproblem AT mutarmodhilafta anenhancedantcolonysystemalgorithmbasedonsubpathsforsolvingthecapacitatedvehicleroutingproblem AT haronhabibollah anenhancedantcolonysystemalgorithmbasedonsubpathsforsolvingthecapacitatedvehicleroutingproblem AT ahmedzakirhussain enhancedantcolonysystemalgorithmbasedonsubpathsforsolvingthecapacitatedvehicleroutingproblem AT hameedasaadshakir enhancedantcolonysystemalgorithmbasedonsubpathsforsolvingthecapacitatedvehicleroutingproblem AT mutarmodhilafta enhancedantcolonysystemalgorithmbasedonsubpathsforsolvingthecapacitatedvehicleroutingproblem AT haronhabibollah enhancedantcolonysystemalgorithmbasedonsubpathsforsolvingthecapacitatedvehicleroutingproblem |