Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem
The dynamic traveling salesman problem (DTSP) falls under the category of combinatorial dynamic optimization problems. The DTSP is composed of a primary TSP sub-problem and a series of TSP iterations; each iteration is created by changing the previous iteration. In this article, a novel hybrid metah...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-08-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/22/8/884 |
| _version_ | 1797558608001499136 |
|---|---|
| author | Petr Stodola Karel Michenka Jan Nohel Marian Rybanský |
| author_facet | Petr Stodola Karel Michenka Jan Nohel Marian Rybanský |
| author_sort | Petr Stodola |
| collection | DOAJ |
| description | The dynamic traveling salesman problem (DTSP) falls under the category of combinatorial dynamic optimization problems. The DTSP is composed of a primary TSP sub-problem and a series of TSP iterations; each iteration is created by changing the previous iteration. In this article, a novel hybrid metaheuristic algorithm is proposed for the DTSP. This algorithm combines two metaheuristic principles, specifically ant colony optimization (ACO) and simulated annealing (SA). Moreover, the algorithm exploits knowledge about the dynamic changes by transferring the information gathered in previous iterations in the form of a pheromone matrix. The significance of the hybridization, as well as the use of knowledge about the dynamic environment, is examined and validated on benchmark instances including small, medium, and large DTSP problems. The results are compared to the four other state-of-the-art metaheuristic approaches with the conclusion that they are significantly outperformed by the proposed algorithm. Furthermore, the behavior of the algorithm is analyzed from various points of view (including, for example, convergence speed to local optimum, progress of population diversity during optimization, and time dependence and computational complexity). |
| first_indexed | 2024-03-10T17:33:53Z |
| format | Article |
| id | doaj.art-bdb182c7dadc4c238308106056d2d6d5 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-10T17:33:53Z |
| publishDate | 2020-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-bdb182c7dadc4c238308106056d2d6d52023-11-20T09:56:55ZengMDPI AGEntropy1099-43002020-08-0122888410.3390/e22080884Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman ProblemPetr Stodola0Karel Michenka1Jan Nohel2Marian Rybanský3Department of Intelligence Support, University of Defence, Kounicova 65, 662 10 Brno, Czech RepublicDepartment of Intelligence Support, University of Defence, Kounicova 65, 662 10 Brno, Czech RepublicDepartment of Intelligence Support, University of Defence, Kounicova 65, 662 10 Brno, Czech RepublicDepartment of Military Geography and Meteorology, University of Defence, Kounicova 65, 662 10 Brno, Czech RepublicThe dynamic traveling salesman problem (DTSP) falls under the category of combinatorial dynamic optimization problems. The DTSP is composed of a primary TSP sub-problem and a series of TSP iterations; each iteration is created by changing the previous iteration. In this article, a novel hybrid metaheuristic algorithm is proposed for the DTSP. This algorithm combines two metaheuristic principles, specifically ant colony optimization (ACO) and simulated annealing (SA). Moreover, the algorithm exploits knowledge about the dynamic changes by transferring the information gathered in previous iterations in the form of a pheromone matrix. The significance of the hybridization, as well as the use of knowledge about the dynamic environment, is examined and validated on benchmark instances including small, medium, and large DTSP problems. The results are compared to the four other state-of-the-art metaheuristic approaches with the conclusion that they are significantly outperformed by the proposed algorithm. Furthermore, the behavior of the algorithm is analyzed from various points of view (including, for example, convergence speed to local optimum, progress of population diversity during optimization, and time dependence and computational complexity).https://www.mdpi.com/1099-4300/22/8/884dynamic traveling salesman problemcombinatorial dynamic optimization problemant colony optimizationsimulated annealinghybridizationmetaheuristic algorithm |
| spellingShingle | Petr Stodola Karel Michenka Jan Nohel Marian Rybanský Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem Entropy dynamic traveling salesman problem combinatorial dynamic optimization problem ant colony optimization simulated annealing hybridization metaheuristic algorithm |
| title | Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem |
| title_full | Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem |
| title_fullStr | Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem |
| title_full_unstemmed | Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem |
| title_short | Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem |
| title_sort | hybrid algorithm based on ant colony optimization and simulated annealing applied to the dynamic traveling salesman problem |
| topic | dynamic traveling salesman problem combinatorial dynamic optimization problem ant colony optimization simulated annealing hybridization metaheuristic algorithm |
| url | https://www.mdpi.com/1099-4300/22/8/884 |
| work_keys_str_mv | AT petrstodola hybridalgorithmbasedonantcolonyoptimizationandsimulatedannealingappliedtothedynamictravelingsalesmanproblem AT karelmichenka hybridalgorithmbasedonantcolonyoptimizationandsimulatedannealingappliedtothedynamictravelingsalesmanproblem AT jannohel hybridalgorithmbasedonantcolonyoptimizationandsimulatedannealingappliedtothedynamictravelingsalesmanproblem AT marianrybansky hybridalgorithmbasedonantcolonyoptimizationandsimulatedannealingappliedtothedynamictravelingsalesmanproblem |