A modified ant colony optimization algorithm to increase the speed of the road network recovery process

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F44994575%3A_____%2F18%3AN0000030" target="_blank" >RIV/44994575:_____/18:N0000030 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.sciencedirect.com/science/article/pii/S2212420917304120" target="_blank" >https://www.sciencedirect.com/science/article/pii/S2212420917304120</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ijdrr.2018.04.004" target="_blank" >10.1016/j.ijdrr.2018.04.004</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A modified ant colony optimization algorithm to increase the speed of the road network recovery process

Popis výsledku v původním jazyce

When a disaster strikes many roads are blocked and the affected network may break up into a number of isolated parts. The reconnection of the network is therefore necessary for both relief distribution and planning of construction work. Shortening the time during which the road network is separated into isolated parts helps decrease indirect losses from disasters. The obstacles usually faced during the process of reconstruction include both the large number of blocked links and extensive affected areas (road networks). A reduction of the network into a much smaller complete graph and metaheuristic based on an ant colony optimization has been introduced to overcome this issue. We demonstrate that, for small networks, the metaheuristic produces the same results as other deterministic algorithms. We further show that the method is still a viable approach for large networks (723 nodes and 974 links, where we artificially blocked 46 links) when the NP-hard nature of this problem began to affect the computational time of the deterministic algorithms. We demonstrate how the various scenarios can be included into the algorithm. We finally introduce a new ranking of feasible solutions which enables the algorithm to minimize the time of reconstructions for all repair units. Reasonable results were obtained after five minutes of computation. There is nevertheless an up-to-38% improvement of the initial solution. The algorithm can also be used for both relief distribution, when no roads were damaged, and for planning of construction work when damaged roads occur.

Název v anglickém jazyce

A modified ant colony optimization algorithm to increase the speed of the road network recovery process

Popis výsledku anglicky

When a disaster strikes many roads are blocked and the affected network may break up into a number of isolated parts. The reconnection of the network is therefore necessary for both relief distribution and planning of construction work. Shortening the time during which the road network is separated into isolated parts helps decrease indirect losses from disasters. The obstacles usually faced during the process of reconstruction include both the large number of blocked links and extensive affected areas (road networks). A reduction of the network into a much smaller complete graph and metaheuristic based on an ant colony optimization has been introduced to overcome this issue. We demonstrate that, for small networks, the metaheuristic produces the same results as other deterministic algorithms. We further show that the method is still a viable approach for large networks (723 nodes and 974 links, where we artificially blocked 46 links) when the NP-hard nature of this problem began to affect the computational time of the deterministic algorithms. We demonstrate how the various scenarios can be included into the algorithm. We finally introduce a new ranking of feasible solutions which enables the algorithm to minimize the time of reconstructions for all repair units. Reasonable results were obtained after five minutes of computation. There is nevertheless an up-to-38% improvement of the initial solution. The algorithm can also be used for both relief distribution, when no roads were damaged, and for planning of construction work when damaged roads occur.

Druh

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

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

<a href="/cs/project/VI20152019049" target="_blank" >VI20152019049: RESILIENCE 2015: Dynamické hodnocení odolnosti souvztažných subsystémů kritické infrastruktury</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

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

INTERNATIONAL JOURNAL OF DISASTER RISK REDUCTION

ISSN

2212-4209

e-ISSN

2212-4209

Svazek periodika

31

Číslo periodika v rámci svazku

October 2018

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

15

Strana od-do

1092-1106

Kód UT WoS článku

000446353300101

EID výsledku v databázi Scopus

—