535

1 INTRODUCTION

Given the current geopolitical situation and the

previous crisis related to the COVID pandemic, it is

reasonable to analyse transport and logistics networks

in terms of their criticality. In the case of transport,

this concept can be understood in various aspects.

For the proposed model, the criticality is analysed

in the context of connectivity/reliability of

vertices/edges, traffic flows in the transport network

and the impact of events blocking their nodes/edges.

The transport is one of the 8 Critical Infrastructures

(CI) – defined by the Act of 26 April 2007 on crisis

management (Journal of Laws 2007 No. 89 item 590).

In the case of the European Union, the establishment

of a critical infrastructure protection program was

preceded by terrorist attacks on four city trains in

Madrid in 2004, the subway in London in 2005 and an

airplane flying from Great Britain to the USA in 2006.

However, the functioning of this program made it

possible to respond appropriately in 2010 to the

paralysis of European air traffic caused by the

volcanic eruption in Iceland. The effects of this event

were felt not only on the old continent but all over the

world.

The events mentioned above, and the

consequences of their occurrence showed how much

the national and global economies depend on the

condition of transport (individual elements of the

transport system), regardless of the branch to which

these events are concerned.

The events of the last four years confirmed the

justification for introducing a critical infrastructure

protection policy. First, the COVID-19 pandemic

showed how much societies depend on global

transport. In turn, Russia's attack on Ukraine and the

sanctions adopted by EU countries aimed at, among

others, limiting oil and gas orders from Russia

showed that it is necessary to be able to quickly make

decisions about changing supply directions.

Unfortunately, this is not an easy and quick process,

so it is worth having prepared action scenarios in case

of such situations. This is where various analytical,

forecasting and decision-making models can be

useful, making the transport system more resilient.

The experience of the last several decades shows that

An Approach to the Analysis of Critical Elements

Transport and Logistics Networks Using Graph

Theory

. Strzelczyk & S. Guze

Maritime School Complex in Gdańsk, Gdańsk, Poland

Gdynia Maritime University, Gdynia, Poland

ABSTRACT: The article's primary purpose is to develop methods for determining critical nodes, arcs, and

routes of transport and logistics networks. One of the proposed algorithms resolves a problem in finding the

critical elements of the transport network. The second gives solutions to make alternative paths based on this

criticality of the network. These tools should be helpful for transport planners, especially for dangerous,

oversized, and important goods. The basis of the developed method is the domination in graphs. The proposed

analysis methodology is verified on the existing infrastructure in northeastern Poland.

http://www.transnav.eu

the

International Journal

on Marine Navigation

and Safety of Sea Transportation

Volume 18

umber 3

September 2024

DOI: 10.12716/1001.18.03.0

536

for the proper functioning of the economy and

society, it is essential that the transport system (all its

elements) is reliable and resistant to various

unfavourable external factors. Therefore, you should

work on methods that allow you to:

− finding weak links in the functioning of the

transport system,

− to identify potential threats,

− to reduce or even eliminate these threats,

− to mitigate the effects of threats.

Threats to critical infrastructures may be of natural

or anthropological origin; therefore, the methods of

identifying threats depend on the source of their

origin, and consequently, various methods are used to

mitigate the effects of these threats. However, the

most important thing seems to be finding weak links

in the transport system. In the technical part, they will

be related to means of transport or infrastructure and

less often to legal regulations or economic aspects. For

example, damage to a vehicle may result in blocking a

section of linear infrastructure. However, this will be

possible more often when there are bottlenecks in this

infrastructure or increased traffic intensity in this

section. When we find such elements of the transport

system or, more specifically, the transport network,

we can react in advance and counteract unfavourable

crises. Thus, we come to the need to solve problems

related to the reliability, resilience, vulnerability, or

sensitivity of transport networks as the most crucial

component in the transport system, allowing the

implementation of its main tasks.

Thus, the article aims to establish critical paths

(edges) and nodes (vertices), as well as their

modelling, depending on the situation in the region.

The tool can be used to determine new transport

networks, considering crises that affect the

determination of additional or other edges and

dominant vertices. So far, the mathematical analysis

models used have considered separately either the

vertices or the edges in the graph representing the

transport network. This article proposes a

comprehensive approach to modelling - simultaneous

consideration of vertices and edges - this is the

novelty of this article. For the tested model, the

criticality is analysed in the context of

coherence/reliability of vertices/edges, traffic flows in

the transport network, and the impact of events

blocking their nodes/edges.

The structure of the paper is as follows. The

Introduction section presents the main aspects of the

considered problem. The state-of-the-art section

shows the literature review. Further, the basic

notations are defined. Finally, the theoretical methods

and algorithms with real-world applications are

introduced.

2 STATE OF THE ART

The introductory considerations state that the

transport network is a "bloodstream" determining the

region's development, directly proportional to the

economic, development and military potential. The

network is a chain of interconnected vessels whose

opportunities and threats are replicated in other

elements.

According to the literature ([23], [64]), the

transport system is defined as a combination of

elements such as means of transport, infrastructure,

human resources and their interactions, which serve

to generate demand for travel in a given area and to

satisfy them by providing transport services. The

above definition is very general but, at the same time,

easy to adapt to various modes of transport. It allows

the use of a structure of connections between the

transport system elements adapted to the problem

being solved. It was assumed that the best and most

natural way of recording transport systems is a

network representing the infrastructure of this system

and making it possible to describe the flow of traffic

flows occurring in it ([59], [64]). We should agree with

this because the structure and traffic flows in the

transport network best reflect the relationships

between individual elements of the transport system

and thus determine it. There are three main types of

transport networks ([51], [64], [66]):

− All vertices of the same degree characterise regular

transport networks. The regularity of the number

of incident edges about the vertex indicates a high

level of spatial organisation, as in the case of a road

network [66].

− Small-world transport networks are characterised

by dense connections between nodes in the close

neighbourhood with a simultaneous small set of

crucial connections with nodes in the further

neighbourhood. A characteristic feature of this

type of transport network is high sensitivity to

failures around nodes with many close neighbours

(sometimes called hubs) ([29], [66], [73]}.

− Scale-free transport networks are characterised by

a hierarchical system with several vertices with

many neighbours and a small number of vertices

with a small set of neighbours (low vertex degree).

This type of network is characterised by ease of

evolution because adding new network nodes will

prioritise connecting them to larger nodes ([9 - 10],

[66]).

Due to the characteristics of transport

infrastructure, analysing transport networks at the

pre-design stage or assessing and improving them

during operation is best carried out using

mathematical modelling and optimization methods

([38],[45], [57-58], [77-78]).

The most common model for presenting the

structure of transport networks is graphs. They are

composed of two sets: V – vertices (nodes) and E –

edges (arcs). They are denoted as G(V, E). One of the

main applications of graph theory is the analysis of

transport networks and systems ([32], [36], [38-40],

[41], [44], [64], [57]). It was the attempt to solve the

problem of bridges in Königsberg by the famous

Swiss mathematician Leonhard Euler in 1736 that

gave rise to graph theory and thus determined the

meaning of the existence of this mathematical

construction used to model and solve problems of

transport networks ([3], [13-15], [30], [46], [60])

computer ([27], [29], [36], [66], [74]), and in recent

years also social ([51], [73]).

The most crucial transport problems solved using

graph theory include:

− the problem of the Chinese postman;

− travelling salesman problem;

− flows in networks;

537

− spanning tree.

Various ways of solving the Chinese postman

problem can be found, among others, in the literature

[32], [41]. In turn, various solutions to the travelling

salesman problem are presented, among others, in [4],

[5], [7], [37], [41], [55], [56], [57], [59], [64]. This

problem has also been solved in terms of dynamic

graphs, which take into account dynamic changes in

the networks they represent, such as

adding/removing edges or vertices ([2], [71], [76]).

Another problem of graph theory, which is

essential in the analysis of any networks, is the search

for the smallest or largest spanning tree [12], [36], [75]

or the search for maximum flow in networks [35], [59].

Graph domination is essential in analysing

transport networks ([19], [38 – 40], [44], [72]). It is used

to solve problems such as:

− location - for example, the problem of minimizing

the distance that a person must travel to reach the

nearest facility offering services that are critical

from the point of view of their life and health (e.g.

hospitals, police or fire stations), assuming their

constant number [43-44], [72];

− distance – for example, a problem in which the

maximum distance to an object is fixed and the

number of devices needed to serve all users should

be minimized (e.g. base stations of a cellular

network) [19], [43];

− related to the search for representative sets, for

example, to monitor communication or electrical

networks, as well as in geodetic measurements

(one should find the smallest number of places

where the surveyor must measure the height so

that they cover the entire surveyed area) [11], [72];

− vulnerability of transport networks [17], [40], [77].

Moreover, by using graph theory to describe

transport networks, Kansky proposed a series of

indicators describing transport networks in the 1960s

[69] at two levels of detail. The first refers to defining

parameters or indicators concerning the entire

network, while the second relates to the nodes. The

primary assumption of their applicability is the fact

that they provide methods allowing [69]:

− expressing the relationship between their values

and the network structure,

− comparing transport networks with each other at

specific moments in time,

− comparing the development of transport networks

at different times.

In the 1980s, scientists dealing with networks,

including transport and computer networks,

concluded that searching for the shortest path in a

network, the smallest spanning tree or the maximum

flow in networks is insufficient. They began to pay

attention to the connection problem between two

vertices of the transport network. They thus turned

their attention to network reliability issues, including

transport networks. Currently, research on the

reliability of transport networks is dominated by three

main types:

− connectivity reliability – understood as the

probability that network nodes will remain

connected – a measure describing the topological

structure of the transport network ([8], [13], [15-

17], [23], [46], [49]);

− travel time reliability – understood as the

probability that the journey between a given

source and sink will take place within a specific

period ([6], [14], [23], [50]);

− capacity reliability – understood as the probability

that the capacity of the transport network is equal

to or greater than the desired level when the

capacity of the arc is random [24], [25], [50].

A concept closely related to the reliability of

transport networks or, more broadly, transport

systems is their sensitivity. Unfortunately, this

concept is not clear. They can be understood in terms

of reliability and risk in some situations [14], [31], [65].

The sensitivity of the transport network may also be

expressed in terms of too low a level of services

provided and related problems [16-17], [49], [52], [63],

[68], as well as costs resulting from the unavailability

of this network [18], [61]. Moreover, some studies

point out that the sensitivity of the transport network

is its low resistance to natural threats or threats from

other sources [47-48]. In turn, other studies point to

sensitivity related to rare but high risk [16], which

correlates to the possibility of providing services and

maintaining continuity of operation [34], [40], [76].

This approach corresponds to the concept of critical

infrastructures [26], [28].

In particular, the last 25 years have made

governments of many countries around the world

aware that certain aspects of society's life are

particularly exposed to the negative impact of natural

factors, as well as those resulting from acts of

terrorism or vandalism [52], [64]. Depending on the

country, specific services, infrastructures, and, in a

broader sense, sectors have been identified, which

have been called critical because the lack of access to

them causes significant perturbations and problems in

the functioning of residents [20], [21], [22], [26], [28],

[69]. Specific infrastructures or critical sectors allow

for special attention to be paid to their safe and

reliable operation [20-22], [40], [53]. For this reason, it

is essential to have appropriate tools used when

analyzing the functioning of these infrastructures [20-

21], [31], [33], [40] and optimization [38], [53], [56].

A significant facilitation of the search for new,

effective methods of analysis and optimization is the

translation of the problem of transport network

reliability into the language of the theory of systems

and complex networks [1], [10], [51], [73]. Thanks to

this, it is possible to use methods of analysis,

modelling and optimization of the reliability and

sensitivity of complex technical systems [20-21], [53],

62] about transport networks [13], [38-40].

3 BASIC NOTATIONS

In further research, we consider the simple,

undirected (sometimes also weighted) graphs G(V, E)

constituted by nodes (vertices) set V (or V(G)) and arcs

(edges) set E (or E(G)). We adhere to the convention

that n=|V(G)| and m = |E(G)|. Let u, v ϵ V(G), then the

edge between these vertices in a simple graph is

denoted as {u, v}, which in shortened form is often

written as uv. According to the above definition, we

consider unordered pairs. It should be noted that

538

vertices are edge ends, i.e. they are adjacent to each

other and, at the same time, incident to the edge they

create.

The set of all vertices of the graph G(V, E) adjacent

to vertex v is called a neighbourhood and is denoted

by N

G(v) or N(v). The set NG(v)∪{v} is called the closed

neighbourhood of a vertex v in the graph G and

denoted by N

G[v]. For any subset of the set of vertices

in graph G, i.e. A⊆G the neighbourhood is defined as

G(A)=

⋃

∈

ANG(v). The degree of a vertex v in a graph

G is the number of vertices belonging to the set N

G(v)

and is denoted as deg

G(v)=|NG(v)|.

A line graph L(G) (also called an adjoint, conjugate,

covering, derivative, derived, edge, edge-to-vertex

dual, interchange, representative) of a simple graph G

is obtained by associating a vertex with each edge of

the graph and connecting two vertices with an edge if

and only if the corresponding edges of G have a

vertex in common.

3.1 Spanning trees

A spanning tree T

S(G) is a subset of a graph G, with all

the vertices covered with the minimum possible

number of edges. In other words, a spanning tree

contains all the vertices of the graph and only those

edges that do not form cycles in such a graph.

Regarding the topology of such a tree, the smallest

will mean the one whose set of edges is the smallest,

while the largest will mean the most extensive such

set of edges. When describing graph edges using

numerical weights, the smallest spanning tree is the

one for which the sum of the weights is the smallest.

Similarly, the largest spanning tree is the one in which

the sum of the edge weights is the largest.

The problem of finding a minimal spanning tree

(for weighted graphs) uses Kruskal’s algorithm as a

way to resolve this problem. The short description of

this algorithm is presented as algorithm 1. In case of

simple undirected graph, the Kruskal’s method [54] is

proper under assumption that every edge weight is

equal to 1. In this way, the minimal spanning tree is

the tree with the minimum number of edges that

constitute the spanning tree of graph G.

Algorithm 1 [Kruskal’s algorithm]

1: Input (,e) with fixed edge weighted function e;

2: Output Minimal spanning tree T

S(G);

3: Find the least weight of the edges in the graph (if there is

more than one, choose randomly). Mark as red colour;

4: Find the next smallest unlabeled (uncoloured) edge in the

graph that is not marked in red and colour it;

5: Repeat step 4 until you reach every vertex in the graph (or

until you have n-1 coloured edges)

6: The coloured edges form the desired minimum spanning

tree.

7: return T

S(G).

3.2 Domination in graphs

A dominating set for a graph G is a subset D of its

vertices, so any vertex of G is either in D or has

neighbours in D ([30], [35], [44]). The domination

number γ(G) is the number of vertices in the smallest

dominating set for G. An edge-dominating set for

graph G is a subset D

E⊆E such that every edge not in

E is adjacent to at least one edge in DE. A minimum

edge-

dominating number equals the power of the

smallest edge-dominating set [38-40], [70].

Based on this definition, algorithm 2 [40] is

presented. An important assumption for him is that

the input graph must be connected, simple, and non-

empty.

Algorithm 2 [Minimal-vertex-dominating-set]

1: Input =(,).

2: Output Minimal vertex-dominating set of graph G.

3: Fix :=0; all vertices are white.

4: while (white vertices exist) do

5: choose v∈{|()=



∈{()}} and it has the

maximal number of white neighbours.

6: :=∪{}; vertices in S are coloured by black; their

neighbours are grey.

7: end while.

8: return S.

9: if in S there are vertices, what dominates the same

vertices then

10: delete a vertex from S, which dominates only vertices

dominated by other vertices from S; return =\{}

11: else

12: =

13: end if

14: return D.

This algorithm is complemented by algorithm 3,

which finds the value of the weighted domination

number [45]. The pseudo-code is proposed below.

Algorithm 3 [Weighted-domination-number]

1: Input (,) with fixed vertex weighted function;

2: Output weighted domination number () of graph

(,);

3: for =1 to || do

4: find dominating set of G, starting from 



∈, and save it

as 



(



);

5: find total weight Wi(vi)=∑vi

∈

Diwi(vi) of dominating sets





(



);

6: end for;

7: find min{W

i(vi):vi∈V,i=1,...,|V|}→γw(G);

8: return 



().

The third algorithm introduced as the basis for

further theoretical and practical results is a

deterministic discrete-time model of fire spread on a

graph G. Hartnell introduces this concept in [42], and

call firefighting problem. This model of fire spread

considered how firefighters can act to stop a fire

outbreak. An outbreak of fire starts at a set of root

vertices of G at time t=0. In response, firefighters

defend f vertices at time t=1 [42]. The pseudo code of

proposed algorithms for finding solution of this

problem is presented as algorithm 4.

Algorithm 4 [Firefighting problem (or virus control)]

1: Input graph G(V,E);

2: Output the set of vertices under fire and non-fire;

3: A fire breaks out at a vertex of a graph.

4: The firefighter (or defender) then chooses any vertex not

yet on fire (or affected by the virus) to protect.

5: The fire and firefighter alternate moves on the graph due

to the fire can no longer spread.

6: The firefighter has chosen a vertex; it is protected or safe

from future fire moves.

7: After the firefighter’s step, the fire spreads to all vertices

adjacent to the ones on fire, except those protected.

539

4 THEORETICAL RESULTS

This part of the article presents new methods for

finding critical elements in transport networks. The

proposed algorithms are based on those shown in the

previous section. This analytical tool can be used to

establish critical paths (edges) and nodes (vertices)

and their modelling, depending on the situation in the

considered region. The criticality is analysed

regarding the consistency/reliability of nodes

(vertices) / arcs (edges), traffic flows in the transport

network, and the impact of events blocking their

nodes/arcs.

Before we propose new algorithms to identify the

critical elements of transport networks, some

preliminaries must be introduced to find the edge-

dominating set. The algorithm 5 presents a way to

find the minimal edge dominating set. It uses the

concept of line graphs.

Algorithm 5 [Minimal-edge-dominating-set]

1: Input =(,).

2: Output Minimal edge-dominating set of graph G.

3: Define line graphs L(G) of graph G;

4: use algorithm 1 for graph L(G);

5: return D

L(G)¬

6: D

E= DL(G).

7: return DE.

For simple, undirected graphs the edge-

domination number is the cardinality of the minimal

edge dominating set. The value of this number can be

found based on the result obtained from algorithm 5.

Because a transport network can be described by

weighted graph, the method for finding an edge

weighted domination number is proposed in

algorithm 6.

Algorithm 6 [Edge-weighted-domination-number]

1: Input (,

e) with fixed edge weighted function;

2: Output edge weighted domination number 



e() of

graph (,e);

3: Define weighted line graph L

w(G) of graph (,e);

4: use algorithm 3 for graph L

w(G);

5: return 



(Lw(G));

6: 



e():= 



(Lw(G));

7: return 



e().

The next step is defined critical components of the

transport or logistics networks. Referring here to the

fireman's algorithm (algorithm 4) is necessary. A

critical node (vertex) is the first node (vertex) in the

graph G that is not subject to the fire expansion of the

greedy algorithm 4, thus determining all vertices in

the further branches of the graph. Analogically, the

critical arc (edge) is the first free arc (edge) in the

graph that is not subject to the fire expansion of the

greedy algorithm 4, and thus determines all edges in

the further part of the graph branches.

Now, the new approach to identify the critical

elements of a transport network can be proposed. The

solution for this problem is algorithm 7.

Algorithm 7 [Identifying the critical elements of the

transport/logistic network]

1: Input G(V,E) or G(V,E,w

e) represents a transport/logistics

network;

2: Output sets of critical vertices (V

S) and edges (ES);

3: Find the minimum spanning tree of G - T

S(G)

(e.g. algorithm 1).

4: Find the dominating set of T

S(G) (greedy algorithms:

e.g. Algorithm 5 or 6).

5: Find the edge-dominating set of the T

S(G) started in

vertices from D(T

S(G)) (greedy algorithm and line

graphs).

6: For these vertices and edges, use the Firefighter’s

algorithm (algorithm 4).

7: Find the strategic vertices and edges.

This algorithm uses algorithms 1-6 depending on

what type of graph the transport network represents.

It should be emphasized that it is a greedy algorithm.

At the same time, the problem it solves is an NP-

complete problem. Therefore, it should be noted that

it is a tool supporting analysis and decision-making

but requires some caution in interpreting its results.

They may not always be optimal. However, based on

this algorithm, we get the following possibilities. We

can determine critical vertices that protect individual

tree arcs to prevent the graph's further atrophy. If fire

infects the graph, a „fireman” extinguishing fire at the

vertices and edges guarantees the graph's stability.

The first fire-free vertices and edges are called the

CRITICAL VEREX and the CRITICAL EDGE – in

these critical elements should be a logistical backup,

including sufficient tools to prevent the problem from

spreading (for example deals with congestion).

It is necessary to give a tool to reverse the "fire"

(congestion) spreading in the network. It means

finding alternatives for the "occupied" nodes and arcs

or possibly creating a separate path to distribute the

"fire". Therefore, we get new connections between

system-inefficient nodes and those that can "take

over" the additional “fire” (traffic flow). The proposed

solution is given as the algorithm 8.

Algorithm 8 [Identifying the alternative paths]

1: Input G(V,E) or G(V,E,we) as the result of the algorithm 7;

2: Output alternative paths P

3: Build an extended graph G

E=(VE,EE) for analysed area;

4: find domination set in G of vertices occupied by “fire”

with the highest degree D

F(G);

5: while ((D

F(G)≠∅) and (not all vertices from DF(G)

occupied by “fire” are connected)) do

6: select the highest degree vertex w∈D

F(G);

7: if there is a connection in G

E between the vertex w and the

vertex v occupied by the fireman in G then

8: connect them with via a new edge not occupied by the

“fire” (e∈E

E);

9: else

10: connect w with v through additional vertices from the set

E≠V (if there is a relationship in the real connection

network that allows the implementation of the transport

task);

11: add edges e to set of an alternative paths P

12: end while;

12: return P

5 APPLICATIONS

This section shows possible applications of the

methods introduced in section 4.

Let us consider a graph describing the model of

the map of Poland, the northeastern region. The graph

representing this region is on the figure 1. It is

necessary to mention that there are several elements

of the critical infrastructures in the considered region,

e.g.: the waterpower plant in Włocławek, the power

plant in Ostrołęka, the Dębe hydroelectric power

540

plant (on the barrage damming water in Zegrzyńskie

Lake), potential facilities in Pomerania: offshore and

the power plant in Żarnowiec, as well as bridges:

Zegrze, Serock, Pułtusk, Rozan.

Only the infrastructure that meets the

requirements for transporting oversized and

dangerous cargo was adopted for analytical purposes.

Thus, we consider only a mixture of the railroad and

roads, but we show graph representation for railways,

roads, and inland waterways.

Figure 1 shows railway connections with weights

corresponding to the speed achieved on a given route.

The Pan-European Railway (TEN – T) route receives

an additional weight of 5.

Figure 1. Selected railway connections. [own study]

The weights for figure 1 are defined according to

table 1.

Table 1. Weights for graph represents the railway.

________________________________________________

Velocity Weight

________________________________________________

to 80 km/h 1

81-100 km/h 2

101-120 km/h 3

121-140 km/h 4

141-160 km/h 5

161-200 km/h 6

Up to 200 km/h 7

________________________________________________

Additionally, figure 2 presents road connections,

with their weights corresponding to the road

numbers. The Pan-European Railway (TEN – T) route

receives an additional weight of 5.

Figure 2. Selected roads connections. [own study]

The weights for figure 2 are defined according to

table 2.

Table 2. Weights for graph represents the roads.

________________________________________________

Road Weight

________________________________________________

Number with 1 digit 1

Number with 2 digits 2

Number with 3 digits 3

________________________________________________

Finally, figure 3 presents inland connections, with

their weights corresponding to the classes of inland

waterways. The Pan-European Railway (TEN – T)

route receives an additional weight of 5.

Figure 3. Selected inland waterways. [own study]

The weights for figure 3 are defined according to

table 3.

Table 3. Weights for graph represents the inland waterways.

________________________________________________

Class 1 2 3 4 5

________________________________________________

Weight 1 2 3 4 5

________________________________________________

In the general case, a graph representing all the

modes of transport described above is presented in

Figure 4.

Figure 4. Summary of three modes of transport: rail, road,

inland waterways. [own study]

According to assumption, we consider only roads

and railways, as shown in figure 5.

541

Figure 5. Summary of two modes of transport: rail, road.

[own study]

For this graph (figure 5) we apply the algorithm 7

and get the minimal spanning tree (figure 6 – results

according to step 3).

Figure 6. Spanning tree of graph represented considered

transport network [own study]

Further we go to the step 4 of algorithm7. The

results is in figure 7.

Figure 7. Domination set in spanning tree.

The resulting domination set of TS is

D={Żarnowiec, Czeremcha, Łuków, Elbląg, Olsztyn,

Grudziądz, Malbork, Toruń, Warszawa, Augustów,

Zambrów, Białystok, Pilawa, offshore}.

This set is the base for procedure of the firefighting

algorithm. The fire is a congestion, and the

“firefighter” is a traffic supervision. The steps of this

are as follows.

Step 1 FIRE - vertices and edges coming from

Warsaw: Mińsk Mazowiecki, Wyszków, Ostrołęka,

Iława, Płock, Kutno.

Step 1a FIREFIGHTER - the occupied vertex with the

highest degree should be searched for and secured

(e.g. Mińsk Mazowiecki). From now on, both the top

of Mińsk Mazowiecki and all edges are determined by

the fireman and thus are not subject to fire expansion.

Step 2. FIRE - edges and vertices coming from

Wyszków, Ostrołęka, Iława, Płock, and Kutno, thus

occupying the vertices: Toruń, Augustów, Ostrów

Mazowiecki, Malbork.

Step 2a FIREFIGHTER - the occupied vertex with the

highest degree should be searched for and secured

(e.g. Ostrów Mazowiecki). From now on, the fireman

determines the top of Ostrów Mazowiecki and all

edges; thus, they are not subject to fire expansion.

Step 3. FIRE takes the next edge from Toruń, thus

occupying Bydgoszcz.

Step 3a FIREFIGHTER - the vertices and edges

extending from the Grudziądz should be protected,

thus securing the rest of the arc of the graph.

After this procedure, we get the results presented

in Figure 8.

Figure 8. Resulting graph after step 6. [own study]

This way, we get the sets of critical nodes and arcs.

Figure 9. Alternative paths. [own study]

542

To reverse the congestion process (fire) in the

network, it is necessary to look for an alternative to

the "occupied" vertices/edges or create a separate path

to distribute the congestion - following the theoretical

results (Section 4, algorithm 8). The new connections

between system-inefficient vertices and those that can

"hijack" the additional traffic flow is presented (black

in figure 9).

To summarize the practical part, it should be noted

that:

1 Dominating set of nodes in spanning tree for two

modes of transport: Warszawa, Zambrów/Łapy,

Białystok, Pilawa, Łuków, Czeremcha,

Augustów, Malbork, Olsztyn, Elbląg, Żarnowiec,

Grudziądz, Toruń, offshore.

2 Critical nodes (with arcs): Mińsk Mazowiecki,

Ostrów Mazowiecki, Grudziądz (with critical

edges) – it should be secured (according to be

critical for transport network).

6 CONCLUSIONS

The intended purpose of the article was achieved.

New algorithms were proposed for analysing the

criticality of transport and logistics networks. In

particular, new algorithms were introduced for

finding critical network elements (nodes and arcs) and

searching for alternative routes for these elements.

The resulting model should be particularly subject

to the Crisis Infrastructure Management Act because

each edge is a bridge, the breaking of which will cut

off strategic nodes in the operational management

system.

The models can be a tool for determining the

critical/strategic edges and vertices of the region,

considering the optimization of transport reliability

and costs.

Soon, the algorithms for strategic nodes and arcs

will be proposed. Then, all models will be constituting

the new decision support system for traffic flow

planners and managers.

ACKNOWLEDGMENTS

The paper presents the results developed in the scope of the

research project “Methods and algorithms of multicriteria

decision support for improving the safety and reliability of

transport and logistics systems”, WN/2024/PZ/06, granted

by GMU in 2024.

REFERENCES

[1] Albert, R., Baraba´ si, A.-L., 2002, Statistical mechanics of

complex networks. Reviews of Modern Physics 74, 47–

97.

[2] Akandwanaho S.M., Adewumi A.O., Adebiyi A.A., 2015,

Solving Dynamic Traveling Salesman Problem Using

Dynamic Gaussian Process Regression, Journal of

Applied Mathematics, vol. 2014, Article ID 818529, 10

pages.

[3] Appert M., Chapelon L., 2013, Measuring Urban Road

Network Vulnerability using Graph Theory: The Case of

Montpellier’s Road Network. Working Paper, halshs-

00841520, Version 1-8.

[4] Applegate D.L., Robert E., Bixby R.E., Vasek Chvátal V.,

Cook W.J., 2007, The Traveling Salesman Problem: A

Computational Study, Princeton Series in Applied

Mathematics.

[5] Arora S., 1998, Polynomial time approximation schemes

for Euclidean traveling salesman and other geometric

problems, Journal of the ACM, 45 (5): 753–782, CiteSeerX

10.1.1.23.6765, doi:10.1145/290179.290180.

[6] Asakura Y., 1996, Reliability measures of an origin and

destination pair in a deteriorated road network with

variable flows,” in Proceedings of the 4th Meeting of the

EURO Working Group in Transportation, pp.398–412,

University of Newcastle, UK.

[7] Babin G., Deneault S., Laporte G., 2007, Improvements

to the Or-Opt Heuristic for the Symmetric Travelling

Salesman Problem. The Journal of the Operational

Research Society, 58(3), pp. 402–407.

[8] Bai S., Zhu J., 2016, Connectivity Reliability Analysis of

Road Network of Multiple OD Pairs based on the

Structural Reliability of Joint Failure Modes, Journal of

Engineering Science and Technology Review 9 (6)

(2016s), pp. 69–75.

[9] Barab´asi A.L., 2009, Scale-free networks: a decade and

beyond,” Science, vol. 325, no. 5939, pp. 412–413.

[10] Barab´asi A.L., Albert R., 1999, Emergence of scaling in

random networks,” Science, vol. 286, no. 5439, pp. 509–

512.

[11] Barlow R.E., 1982, Set theoretic signed domination for

coherent systems, Operation Research Center Report No

82–1, Berkeley: University of California.

[12] Bazlamaccl C.F., Hindi K.S., 2001, Minimum - weight

spanning tree algorithms a survey and empirical study,

Computer & Operations Research, vol. 28, pp.767–785.

[13] Bell M.G.H., Cassir C., 2012, Reliability of transport

networks, Research Studies Press.

[14] Bell M.G.H., Iida Y., 1997. Transportation Network

Analysis. Wiley, Chichester, West Sussex.

[15] Bell M.G.H., Schmoker J.-D., 2002, Public transport

network reliability topological effects. In: Proceedings of

the 3rd International Conference on Transportation and

Traffic Studies, Guanxi People’s Press, Guilin, China.

[16] Berdica K., 2002a, An introduction to road vulnerability:

what has been done, is done and should be done.

Transp. Policy 9, 117–127

[17] Berdica K., 2002b, Vulnerability: a model-based case

study of the road network in Stockholm. In: TraVIS for

Roads: Examples of Road Transport Vulnerability

Impact Studies. PhD thesis, Department of

Infrastructure, KTH, Stockholm, TRITA-INFRA 02-029.

[18] Berdica K., Eliasson J., 2004, Regional accessibility

analysis from a vulnerability perspective. In: Nicholson,

A., Dantas, A. (Eds.), Proceedings of the Second

International Symposium on Transportation Network

Reliability (INSTR). Christchurch, New Zealand, pp. 89–

94.

[19] Berge C., 1962, The theory of graphs and its

applications, Translated by Alison Doig. Methuen & Co.

Ltd., London.

[20] Blokus, A. Multistate System Reliability with

Dependencies, 1st ed.; Elsevier Academic Press: London,

UK, 2020.

[21] Blokus A, Dziula P. Relations of Imperfect Repairs to

Critical Infrastructure Maintenance Costs. Sustainability.

2021; 13(9):4917. https://doi.org/10.3390/su13094917

[22] Bogalecka M. 2020. Consequences of Maritime Critical

Infrastructure Accidents. Environmental Impacts

Modeling—Identification—Prediction—Optimization—

Mitigation. Elsevier, Amsterdam, Oxford, Cambridge

(MA), (ISBN 9780128196755, DOI 10.1016/B978-0-12-

819675-5.00010-3).

[23] Cascetta E., 2001, Transportation Systems in

Transportation Systems Engineering: Theory and

543

Methods, E. Cascetta, Ed. Boston, MA: Springer US, pp.

1–22.

[24] Chen A., Yang H., Lo H.K., Tang W.H., 2002, Capacity

reliability of a road network: an assessment

methodology and numerical results, Transportation

Research Part B: Methodological, Volume 36, Issue 3,

2002, Pages 225–252, ISSN 0191-2615,

https://doi.org/10.1016/S0191-2615(00)00048-5.

[25] Chen A., Yang H., Lo H.K., Tang W. H., 2010, A

capacity Related Reliability for transportation Networks,

Journal of Advanced Transportation, vol. 33, no, 2, pp.

183–200.

[26] Commission of the European Communities, 2006,

Communication from the Commission on a European

Programme for Critical Infrastructure Protection,

Brussels.

[27] Cormen T.H., Leierson C.E., Rivest R.L., Stein C., 2009,

Introduction to Algorithms, Third Edition. MIT Press,

ISBN 0-262-03384-4. Section 23.2: The algorithms of

Kruskal and Prim, pp. 631–638.

[28] Council Directive 2008/114/EC of 8 December 2008 on

the identification and designation of European critical

infrastructures and the assessment of the need to

improve their protection. Official Journal of the

European Union L 345/75 (23.12.2008).

[29] Cui D., Gao Z.Y., Zhao X.M., 2007, Cascades in small-

world modular networks with ’CML’s method, Physica

B, vol. 17, pp. 1703–1710.

[30] Delavina E., Pepper R., Waller B., 2010, Lower bounds

for the domination number, Discussiones Mathematicae

Graph Theory 30 , pp. 475-487.

[31] D’Este G.M., Taylor M.A.P., 2003. Network

vulnerability: an approach to reliability analysis at the

level of national strategic transport networks. In: Bell,

M.G.H., Iida, Y. (Eds.), The Network Reliability of

Transport. Proceedings of the 1st International

Symposium on Transportation Network Reliability

(INSTR). Pergamon, Oxford, England, pp. 23–44.

[32] Diestel R., 2000, Graph Theory. Nowy Jork, ISBN 0-

387-95014-1.

[33] Du Z.P., Nicholson A., 1997, Degradable transportation

systems: Sensitivity and reliability analysis,

Transportation Research Part B: Methodological,

Volume 31, Issue 3, pp. 225-237, ISSN 0191-2615,

https://doi.org/10.1016/S0191-2615(96)00023-9.

[34] Einarsson S., Rausand M., 1998, An approach to

vulnerability analysis of complex industrial systems.

Risk Analysis 18 (5), pp. 535–546.

[35] Ford L.R., Fulkerson D.R., 1962, Flows in Networks,

Princeton University Press, Princeton, NJ.

[36] Gross J. L., Yellen J., 2004, Handbook of graph theory,

CRC Press. ISBN 978-1-58488-090-5.

[37] Gutin G., Punnen A.P., 2006, The Traveling Salesman

Problem and Its Variations, Springer US.

[38] Guze S., 2014, Graph Theory Approach to

Transportation Systems Design and Optimization.

TransNav, the International Journal on Marine

Navigation and Safety of Sea Transportation, vol. 8, no.

4, doi:10.12716/1001.08.04.12, pp. 571–578.

[39] Guze S., 2017, An application of the selected graph

theory domination concepts to transportation networks

modelling, Zeszyty Naukowe Akademii Morskiej w

Szczecinie, 52 (124), pp. 97–102.

[40] Guze S. Graph Theory Approach to the Vulnerability of

Transportation Networks. Algorithms. 2019; 12(12):270.

https://doi.org/10.3390/a12120270

[41] Harrary F., 1969, Graph Theory, Addison-Wesley,

Reading, MA.

[42] Hartnell B. L., Firefighter! an application of domination,

Presentation, in: 20th Conference on Numerical

Mathematics and Computing, University of Manitoba in

Winnipeg, Canada, September 1995.

[43] Haynes T.W., Hedetniemi M., Hedetniemi T., 2000,

Domination and independence subdivision numbers of

graphs, Discussiones Mathematicae Graph Theory 20 ,

pp. 271–280.

[44] Haynes T.W., Hedetniemi S., Slater P., 1998,

Fundamentals of Domination in Graphs. CRC Press.

[45] Hensher D.A., Button K., 2008, Handbook of transport

modelling, Elsevier.

[46] Hongwei M., Xizhao Z., 2015, An evaluation method for

the Connectivity Reliability Based on the Transportation

Network of Critical Links, International Journal of

Transportation vol.3, no.2, pp.45–52

http://dx.doi.org/10.14257/ijt.2015.3.2.04

[47] Holmgren A., 2004, Vulnerability analysis of electrical

power delivery networks. Licentiate thesis TRITA-LWR

LIC 2020, Department of Land and Water Resources

Engineering, KTH, Stockholm.

[48] Holmgren J., 2004. Efficient updating shortest path

calculations for traffic assignment. Master thesis LITH-

MAI-EX-2004-13, Department of Mathematics,

Linko¨ping Institute of Technology, Linko¨ping.

[49] Iida Y., 1999, Basic concepts and future directions of

road network reliability analysis, Journal of Advanced

Transportation, vol. 33, no2, 125–134.

[50] Immers L.H., Stada J.E., Yperman I., Bleukx A., 2004,

Robustness and resilience of transportation networks. In:

Proceedings of the 9th International Scientific

Conference MOBILITA, Bratislava, Slovenia, May 6–7.

[51] Jasny B.R., Zahn L.M., Marshall E., 2009, Connections,

Science, vol. 325, no. 5939, p. 405.

[52] Jenelius E., Petersen T., Mattsson L., 2006, Importance

and exposure in road network vulnerability analysis,

Transportation Research Part A 40 , 537–560.

[53] Kołowrocki K., Soszyńska-Budny J., 2011, Reliability

and Safety of Complex Technical Systems and Processes:

Modeling - Identification - Prediction - Optimization,

London, Dordrecht, Heildeberg, New York, Springer.

[54] Kruskal J. B., 1956, On the shortest spanning subtree of

a graph and the traveling salesman problem, Proc. Am.

Math. Soc., vol.7, pp.48–50.

[55] Leeuwen, Van, J., 1986, Graph Algorithms Book.

Handbook of Theoretical Computer Science, 1990, Pages

525, 527-631

[56] Ming‐Hua, L., Jung‐Fa, T., Chian‐Son Y., 2012, A

Review of Deterministic Optimization Methods in

Engineering and Management, Mathematical Problems

in Engineering, Volume 2012.

[57] Neumann T., 2016, The Shortest Path Problem with

Uncertain Information in Transport Networks. In

Challenge of Transport Telematics J. Mikulski, Ed.

Springer International Publishing.

[58] Neumann, T. Comparative Analysis of Long-Distance

Transportation with the Example of Sea and Rail

Transport. Energies 2021, 14, 1689.

https://doi.org/10.3390/en14061689.

[59] Newell G.F., 1980, Traffic flow on transportation

networks. MIT Press Series in transportation studies,

Monograph 5.

[60] Piña-Barcenas, J., Cedillo-Campos, M.G., Moreno-

Quintero, E. et al. Graph Theory to Achieve the Digital

Transformation in Managing Freight Transportation

Corridors. Mobile Netw Appl (2023).

https://doi.org/10.1007/s11036-023-02283-8

[61] Proag V., 2014, The Concept of Vulnerability and

Resilience, Procedia Economics and Finance, vol. 18,

pp. 369–376, ISSN 2212-5671,

https://doi.org/10.1016/S2212-5671(14)00952-6.

[62] Rausand M., Høyland A., 2004, System Reliability

Theory; Models, Statistical Methods and Applications,

Second Edt., Wiley Series in Probability and Statistics.

[63] Reggiani A., Nijkamp P., Lanzi D., 2015, Transport

resilience and vulnerability: The role of connectivity,

Transportation Research Part A: Policy and Practice, vol.

81, pp. 4–15.

[64] Rodrigue J.P., Comtois C., Slack B., 2017, The

geography of transport systems (4th Edition), Routledge,

Taylor & Francis Group, New York.

544

[65] Sarewitz D., Pielke R. Jr., Keykhah M., 2003,

Vulnerability and risk: some thoughts from a political

and policy perspective. Risk Analysis 23 (4), 805–810.

[66] Solé R.V., Valverde S., 2004, Information theory of

complex networks: on evolution and architectural

constraints, Complex networks. Springer, Berlin,

Heidelberg, pp. 189–207.

[67] Taylor M.A.P., 1999a, Dense network traffic models,

travel time reliability and traffic management. I: General

introduction. Journal of Advanced Transportation, vol.

33, no. 2, 218–233.

[68] Taylor M.A.P., 1999b, Dense network traffic models,

travel time reliability and traffic management. II:

application to network reliability. Journal of Advanced

Transportation, vol. 33, no. 2, 235–251.

[69] Taylor M.A.P., D’Este G.M., 2004, Critical infrastructure

and transport network vulnerability: developing a

method for diagnosis and assessment. In: Nicholson, A.,

Dantas, A. (Eds.), Proceedings of the Second

International Symposium on Transportation Network

Reliability (INSTR). Christchurch, New Zealand, pp. 96–

102.

[70] Thakkar D. K., Jamvecha N.P., 2018, Edge-Vertex

Domination in Graphs, Int. J. Math. And Appl., 6(1–C),

pp. 549–555.

[71] Tinós R., 2015, Analysis of the dynamic traveling

salesman problem with weight changes, 2015 Latin

America Congress on Computational Intelligence (LA-

CCI), Curitiba, pp. 1–6, doi: 10.1109/LA-

CCI.2015.7435936

[72] Walikar H.B., Acharya B.D., Sampathkumar E., 1979,

Recent developments in the theory of domination in

graphs. Allahabad, 1.

[73] Watts D. J., Strogatz S.H., 1998, Collective dynamics of

’small-world’ networks,” Nature, vol. 393, no. 6684, pp.

440–442.

[74] Willie R.R., 1978. Computer-Aided Fault Tree Analysis,

ORC 78-14, Operations Research Center, University of

California, Berkeley.

[75] Yamuna M., Karthika K., 2013, Minimal Spanning Tree

From a Minimum Dominating Set, WSEAS

TRANSACTIONS on MATHEMATICS, Issue 11, vol. 12,

pp. 1055– 1064.

[76] Yang M., Li C., Kang L., 2006, A new approach to

solving dynamic traveling salesman problems, in

Simulated Evolution and Learning, vol. 4247 of Lecture

Notes in Computer Science, pp. 236–243, Springer,

Berlin, Germany.

[77] Ziemska-Osuch, M.; Guze, S. Analysis of the Impact of

Road Traffic Generated by Port Areas on the Urban

Transport Network—Case Study of the Port of Gdynia.

Appl. Sci. 2023, 13, 200.

https://doi.org/10.3390/app13010200.

[78] Ziemska-Osuch M., Osuch D.: Analysis of the Capacity

of Intersections with Fixed-time Signalling Depending

on the Duration of the Green Phase for Pedestrians.

TransNav, the International Journal on Marine

Navigation and Safety of Sea Transportation, Vol. 18,

No. 2, doi:10.12716/1001.18.02.08, pp. 323-327, 2024