Cost-efficient portfolios of reinforcement actions to secure the performance of transportation networks

Abstract

Transportation networks like public transport and highway systems are a critical part of modern society’s infrastructure. They enable the fast and reliable transportation of goods, people and information. Due to their critical nature, it is extremely important to secure their performance against disruptions caused by deterioration of the network’s components or external hazards like natural disasters or terrorist attacks for example. This motivates the decision makers to invest in reinforcement actions, which secure the network’s performance.

The decision makers need some help in identifying those reinforcement actions, which have the biggest positive impact on the performance of the network while also having minimal cost. A collection of such reinforcement actions is called a costefficient portfolio. This thesis presents an algorithm for identifying these portfolios. Transportation networks are modeled as undirected and unweighted graphs consisting of nodes and edges connecting them.

Two types of reinforcement actions are considered: Type I, which reinforce existing edges, and Type II, which add new edges to the network. We illustrate the algorithm with an example network with 10 nodes and 12 edges, where Type II reinforcement actions have a cost double the cost of Type I actions. There are 12 Type I actions and 13 Type II actions to consider. The results show us that it is far more beneficial to favor Type II reinforcement actions. However, there was one exception to this which was the reinforcement of a particular edge connecting one weakly connected node to the rest of the network, which was reinforced in most cost-efficient portfolios. The results infer that decision makers should favor Type II reinforcement actions when they are not unreasonably expensive.

One could support the decision makers with the cost-efficient portfolios given by the algorithm by recommending those portfolios or by recommending just some reinforcement actions, which have a high relative share amongst the cost-efficient portfolios. Additionally suggesting to avoid those reinforcement actions, which are not amongst any of the cost-efficient portfolios is possible.

Kuljetusverkot, kuten joukko- ja ilmaliikenne, ovat äärimmäisen tärkeä osa modernin yhteiskunnan infrastruktuuria. Ne mahdollistavat tavaroiden, ihmisten ja informaation nopean ja luotettavan liikkumisen paikasta toiseen. Niiden tärkeyden takia on ratkaisevaa turvata niiden toimintakyky olosuhteista riippumatta. Äärimmäiset sääilmiöt, komponenttien rappeutuminen ja muut ulkoiset uhat vahingoittavat verkon toimintakykyä, mikä motivoi päätöksentekijöitä investoimaan verkon vahvistamiseen.

Päätöksentekijät kaipaavat apua niiden vahvistustoimien identifioimiseen, joilla on isoin positiivinen vaikutus verkon toimintakykyyn, jotka ovat samalla mahdollisimman edullisia. Kokoelmaa tällaisia vahvistustoimia kutsutaan kustannustehokkaiksi portfolioiksi. Tässä kandidaatintyössä esitellään algoritmi, joka identifioi juuri tällaiset portfoliot.

Kuljetusverkkoja mallinnetaan suuntaamattomina ja painottamattomina verkkoina, jotka koostuvat solmuista ja niitä yhdistävistä kaarista. Vahvistustoimia on kahdenlaisia: ensimmäisen tyypin vahvistustoimessa vahvistetaan jo olemassa olevia kaaria ja toisen tyypin taas lisäävät uusia kaaria verkkoon. Kuvaamme algoritmin toimintaa esimerkkiverkolla, jossa on 10 solmua ja 12 kaarta, kun toisen tyypin vahvistustoimet olivat kustannukseltaan kaksinkertaisia ensimmäisen tyypin vahvistustoimiin verrattuna. Tulokset osoittavat, että on paljon kannattavampaa rakentaa uusia kaaria kuin vahvistaa jo olemassa olevia. Tästä poikkeuksena oli yksi kriittiseksi osoittautunut kaari, jota vahvistettiin lähes jokaisessa kustannustehokkaassa portfoliossa. Tästä päätellen uusien kaarien rakentaminen on lähes aina vanhojen vahvistamista kannattavampaa, kun niiden rakentaminen ei ole kohtuuttoman kallista.

Päätöksentekijöitä voi tukea algoritmin palauttamien kustannustehokkaiden portfolioiden avulla sekä suosittelemalla kokonaisia portfolioita että antamalla suosituksia yksittäisistä vahvistustoimista, joilla on suuri esiintyvyys kustannustehokkaissa portfolioissa. Lisäksi päätöksentekijöitä voi kehottaa välttämään niitä vahvistustoimia, jotka eivät esiinny lainkaan kustannustehokkaissa portfolioissa.