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

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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).

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10300 - Physical sciences

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2020

Confidentiality

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

Name of the periodical

Entropy

ISSN

1099-4300

e-ISSN

1099-4300

Volume of the periodical

22

Issue of the periodical within the volume

8

Country of publishing house

CH - SWITZERLAND

Number of pages

28

Pages from-to

884

UT code for WoS article

000564172000001

EID of the result in the Scopus database

2-s2.0-85090048004