Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F60162694%3AG42__%2F20%3A00555978" target="_blank" >RIV/60162694:G42__/20:00555978 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.mdpi.com/1099-4300/22/8/884" target="_blank" >https://www.mdpi.com/1099-4300/22/8/884</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/e22080884" target="_blank" >10.3390/e22080884</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem

Popis výsledku v původním jazyce

The Dynamic Travelling 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 behaviour of the algorithm is analysed 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).

Název v anglickém jazyce

Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem

Popis výsledku anglicky

The Dynamic Travelling 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 behaviour of the algorithm is analysed 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).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10300 - Physical sciences

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Entropy

ISSN

1099-4300

e-ISSN

1099-4300

Svazek periodika

22

Číslo periodika v rámci svazku

8

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

28

Strana od-do

884

Kód UT WoS článku

000564172000001

EID výsledku v databázi Scopus

2-s2.0-85090048004