Hybrid Ant Colony Optimization Algorithm applied to the Multi-Depot Vehicle Routing Problem

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="https://link.springer.com/article/10.1007/s11047-020-09783-6" target="_blank" >https://link.springer.com/article/10.1007/s11047-020-09783-6</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s11047-020-09783-6" target="_blank" >10.1007/s11047-020-09783-6</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Hybrid Ant Colony Optimization Algorithm applied to the Multi-Depot Vehicle Routing Problem

Popis výsledku v původním jazyce

The article deals with the hybrid Ant Colony Optimization (ACO) algorithm and its application to the Multi-Depot Vehicle Routing Problem (MDVRP). The algorithm combines both probabilistic and exact techniques. The former implements the bio-inspired approach based on the behaviour of ants in the nature when searching for food together with simulated annealing principles. The latter complements the former. The algorithm explores the search space in a finite number of iterations. In each iteration, the deterministic local optimization process may be used to improve the current solution. Firstly, the key parts and features of the algorithm are presented, especially in connection with the exact optimization process. Next, the article deals with the results of experiments on MDVRP problems conducted to verify the quality of the algorithm; moreover, these results are compared to other state-of-the-art methods. As experiments, Cordreau’s benchmark instances were used. The experiments showed that the proposed algorithm overcomes the other methods as it has the smallest average error (the difference between the found solution and the best known solution) on the entire set of benchmark instances.

Název v anglickém jazyce

Hybrid Ant Colony Optimization Algorithm applied to the Multi-Depot Vehicle Routing Problem

Popis výsledku anglicky

The article deals with the hybrid Ant Colony Optimization (ACO) algorithm and its application to the Multi-Depot Vehicle Routing Problem (MDVRP). The algorithm combines both probabilistic and exact techniques. The former implements the bio-inspired approach based on the behaviour of ants in the nature when searching for food together with simulated annealing principles. The latter complements the former. The algorithm explores the search space in a finite number of iterations. In each iteration, the deterministic local optimization process may be used to improve the current solution. Firstly, the key parts and features of the algorithm are presented, especially in connection with the exact optimization process. Next, the article deals with the results of experiments on MDVRP problems conducted to verify the quality of the algorithm; moreover, these results are compared to other state-of-the-art methods. As experiments, Cordreau’s benchmark instances were used. The experiments showed that the proposed algorithm overcomes the other methods as it has the smallest average error (the difference between the found solution and the best known solution) on the entire set of benchmark instances.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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

Natural Computing

ISSN

1567-7818

e-ISSN

1572-9796

Svazek periodika

19

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

463-475

Kód UT WoS článku

000515594600001

EID výsledku v databázi Scopus

2-s2.0-85078462338