571
1
INTRODUCTION
Nowadays,researchershavetwomainproblems.On
theonehandpeoplearedependentoncriticalsystems
such as transportation, electricity, water supply,
sewage,ICT.According totheofficialdefinition,the
criticalinfrastructureisatermusedtodescribeassets
thatareessentialforthefunctioningofasocietyand
economy.
The following facilities are related to this
subject[1]:
electricity and heating generation, transmission
anddistribution;
gasandoilproduction,transportanddistribution;
telecommunication;
watersupply;
agriculture,foodproductionanddistribution;
publichealth(hospitals,ambulances);
transportation systems (fuel supply, railway
network,airports,harbours,inlandshipping);
financialservices(banking);
securityservices(police,military).
There are several regional critical‐infrastructure
protectionprogrammes,whichmainaimsare:
toindentifyimportantassets,
to analyze a riskbased onmajor threat scenarios
andthevulnerabilityofeachasset,
to indentify, select and make prioritisation of
counter‐measuresandprocedures.
Thesegoalsarecommonforallfacilitiespresented
above.Itis very importantto keep these systemsin
goodconditions[8],[9].Thus,theriskandreliability
analyses is needed to understand the impact of
threatsandhazards [4],[5],
[8].Unfortunately,these
problems are more and more complex, because of
existing strong interdependencies both within and
betweeninfrastructuresystems.
Thesecondproblemisfindingoptimalsolutions.It
is met in many areas of modern science, technology
and economics. For example, the navigator’s main
aimisoptimizingtherouteof
theshipduetosafety,
timeofpassage,fuelandcosts[16],[21].Thesolving
of these real‐life problems is looking for a
mathematical model or function that best
approximates or fit to the data collected during the
operation process or experiment [11]. If we can
specifythreeelements:a
modelofthephenomenonof
Graph Theory Approach to Transportation S
y
stems
Design and Optimization
S.Guze
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT:Themainaimofthepaperistopresentgraphtheoryparametersandalgorithmsastooltoanalyze
and to optimise transportation systems. To realize these goals the 0‐1 knapsack problem solution by SPEA
algorithm,methodsandproceduresforfindingtheminimalspanningtreeingraphsanddigraphs,domination
parametersproblemsaccuratetoanalysethetransportationsystemsareintroducedanddescribed.Possibility
of application of graph theory algorithms and parameters to analyze exemplary transportation system are
shown.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 8
Number 4
December 2014
DOI:10.12716/1001.08.04.12
572
distinguished decision variables, objective function‐
also known as a quality criterion‐and limitations,
eachofthesecanbe(generally)formulatedstrictlyas
an optimization problem [3]. This approach can be
apply to reliability, safety and risk analysis [3], [4].
But,becauseofthecurrentcomplexityofthetechnical
systems [9]
the criteria for their safe and reliable
operations aremade importantmore and more [11],
[12].Thisimplies thatmore than one object is taken
into account for solving the optimization problems
([3], [5], [10], [12], [14], [16], [20], [22]‐[23]). Some
tools for solving the problems of complex technical
systemsoperation, reliability,availability,safetyand
cost optimization are presented in [10] – [12]. The
methodsofthereliabilitypredictionandoptimization
of complex technical systems related to their
operationprocessesareintroducedin[10].
The methods of operational research can be
classified as deterministic or non‐deterministic [15],
[18],[20],
[22].Therearemanypublicationsconcerns
into deterministic or non‐deterministic optimization
methodsforengineeringandmanagement[20]‐[23].
Themethodsforsolvingthemaritimetransportation
optimization problems, i.e. weather routing or
minimizingfuelconsumptionareintroducedin[14],
[21],respectively.
In this paper the review of known graph theory
algorithmsandparameters[2]–[7],[13],[15], [17]–
[19],[23]whichcanbeappliedtodesign,analyzeand
optimizeoftransportationsystemsisdone.
Whereas, the presented approach can be used to
anyoflistedabovefacilities.
2
MULTI‐CRITERIAOPTIMIZATIONMETHODS
REVIEW
Inthegeneralwords,thesingle‐objectedoptimization
problemisdefinedasfollowingmathematicalmodel
(minimizingormaximizingproblem):
ii
ji ji i
F(x ) min or F(x ) max,
l(x) 0,l(x) 0,x0,i, j 1,2,...,n
(1)
where
i
x
‐decisionvariables,
ni ,...,2,1
;
)(
i
xF
‐goalfunction;
)(
ij
xl
‐ limits function (low or high) for decision
variables,
nji ,...,2,1, .
Whereas, the multi‐objective (multi‐criteria)
optimization model can be described as a vector
function
f that maps a tuple of
m
decision
variables to a tuple of
n
objectives. The formal
notationisasfollows[12]:
12 n
12 m
12 n
y f( x) f (x),f ( x), ,f ( x) min/ max
subjectto
xx,x,,x X,
yy,y,,y Y,
(2)
where
x
‐decisionvariable,
X
‐parameter(variable)space,
y
‐objectivevector,
Y
‐objectivespace.
The set of multi‐objective optimization problem
solutionsconsistsofalldecisionvectorsforwhichthe
corresponding objective vectors cannot be improved
in any dimension without degradation in another.
These vectors are known as Pareto optimal, what is
relatedtotheconceptofdominationvectorbyvector.
It
is simple to explain after introduce following
definitions.
Definition1
Letus take intoaccount amaximization problem
andconsidertwodecisionvectors
,, Xba
then
a
issaidtodominate
b ifandonlyif
ii
jj
i {1,2,...,n} : f( ) f( )
j
{1,2,...,n}: f( ) f( ).
ab
ab
(3)
Definition2
All decision vectors which are not dominated by
anotherdecisionvectorarecallednon‐dominated.
When the decision vectors are non‐dominated
within the entire search space, they are denoted as
Paretooptimal(Pareto‐optimalfront).
These general formulations for single and multi‐
objective optimization problem are common for
differenttypes
ofengineeringproblems,whichcanbe
related to different optimizationproblems presented
onFigure1.
Figure1.Differenttypesofproblemrelatedtooptimization
problems[3],[15].
The basic classification of the optimization
methodsconsistsintheirdivisionduetothenumber
of criteria (one or multi‐criteria). As it is shown on
Figure2,thereispossibilitytodistinguishsevenmost
frequently used methods of multi‐criteria
optimizationandthreeforone‐criterion[3].
573
Figure2.Chosenoptimizationmethods[3].
Thesemethodsrepresentsomegeneralapproaches
foroptimization,i.e.:
deterministic,
non‐deterministic,
heuristic,
evolutionary/genetic.
The above approaches can provide general tools
forsolvingoptimizationproblems toobtainaglobal
optimum. In second case the best way is using the
evolutionary or genetic algorithms. The schema of
basicgeneticalgorithmispresentedonFigure3.
General operation of genetic or evolutionary
algorithms is based on
the following steps (see
Figure3)[3]:
1
Initialization.
2
Calculatefitness.
3
Selection/Recombination/Mutations (parents and
children).
4
Finished.
Figure3.Basicgeneticalgorithm[3],[22].
The each chromosome of the genetic or
evolutionary algorithm is represented as a string of
bits.
In the paper the Strength Pareto Evolutionary
Algorithm(SPEA)isconsidered[3],[23].
The basic notations for above algorithm are as
follows:
t‐numberofgeneration,
t
P
‐populationingenerationt,
t
P ‐externalsetingenerationt,
P
‐temporaryexternalset,
P
‐temporarypopulation.
Additionally, it is necessary to give following
inputparameters:
N ‐populationsize,
N ‐maximumsizeofexternalset,
T
‐maximumnumberofgenerations,
c
p
‐crossingprobability,
m
p
‐mutationprobability,
A
‐setofnon‐dominatedsolutions.
TheStrengthParetoEvolutionaryAlgorithmisas
follows[3],[23]:
Step1.Initialization:
The initial population
0
P
is generated according
toprocedure:
1
Togetitemi.
2
Toadditemitoset
0
P
.
Next, the empty external set
0
P is generated,
where
t=0.
Step2.Thecomplementoftheexternalsetisdone.
Let
P
=
t
P
1
To copy non‐dominated items from population
t
P
topopulation
P
.
2
Toremovedominateditemsfromset
P
.
3
To reduce the cardinalityof the set
P
to value
N
, using clustering and the solution give into
1t
P .
Step3.Determinationfitfunction.
ThevalueofthefitfunctionFforitemsfromsets
t
P
i
t
P can be found according to following
procedure:
Therealvalue
)1,0[
S isassignedforeveryitem
t
Pi (called power). This value is proportional to
number of items
t
Pj
, which represents the
solutionsdominatedbyitem
i.
Theadaptationofitem
jiscalculatedassumofall
items from external set, represents solution
dominatedbyitem
j,increasedby1.
Theaimofaddition1istoensurethatitems
t
Pi
willhavebettervalueoffitfunctionthanitemsfrom
set
t
P
,i.e.
n
S(i) ,
N1
(4)
where:
)(iS ‐powerofitemi,
n‐number of items in population dominated by
item
i.
Itisassumedthatvalueoffitfunctionforitemiis
equaltohispower,i.e.
)()( iSiF
. (5)
Step4.Selection
Let P
=Ø.
Fori=1,2,…kdo
1
Tochooserandomlytwoitems
tt
PPji , .
574
2
If )()( jFiF then
}{iPP
else
}{ jPP
,underassumptionthatvalueof
fitisminimizing.
Step4.Recombination.
Let P
=Ø.
Fori=1,2,…N/2do:
1
To choose two items
Pji
,
and to remove it
from
P
.
2
Tocreateitems:
lk,
bycrossingtheitems
j
i, .
3
Toadditems
lk,
toset
P
withprobability
c
p
,
elseadditems
j
i, toset
P
.
Step5.Mutation
Let P
=Ø.
Foreveryitem
Pi
do:
1
To create item j by mutation the item i with
probability
m
p
.
2
Toadditemjtoset
P
.
Step6.Finished
Let
PP
t
1
and 1 tt .
If
Tt thenreturnA–non‐dominatedsolution
frompopulation
t
P
andfinishelsebacktoStep2.
3
REVIEWOFGRAPHTHEORYTOPICS
Bellow chapter is showing general definitions,
parameters and algorithms of the domination in
graph theory and other related topics. Let
),( EVG
be a connected simple graph(Figure 1)
where
V
‐setofnvertices,
E
‐setofmedges.The
set of neighbors of vertex
v
in G is denoted
by
).(vN
G
3.1 Basicsondominationinundirectedgraphs
Inthefollowing,thedifferenttypeofdominationsets
and numbers’ definitions will be introduced, i.e.
general, connected and independent for undirected
graphs[4],[6],[7].
Definition1
Aset
)(GVD
isthedominating set of G if
for any
Vv either Dv or
DvN
G
)(
.
Thedominationnumber
)(G
ofagraph G isthe
minimumcardinalityofadominatingsetof
G .
Definition2
A set
)(GVD
C
is a connected dominating set
of
G if every vertex of
C
DV \
is adjacent to a
vertex in
C
D
and the subgraph induced by
C
D
is
connected. The minimum cardinality of a connected
dominating set of
G is the connected domination
number
).(G
c
Definition3
A set
)(GVD
I
is an independent dominating
set of
G if no two vertices of
I
D
are connected by
any edge of
G . The minimum cardinality of an
independent dominating set of
G is the
independentdominationnumber
).(G
I
Figure3.Theexemplaryundirectedgraph G .
Fortheexemplarygraph G presentedinFigure3
the particular domination sets and numbers
(Definitions1–3)areasfollows:
c
I
D{5,6}, (G) 2;
D{1,2,5}, (G) 2;
D{2,3}, (G) 2.
Theabovedefinitionsrefertothegeneralconcept
of undirected graphs. There are topics related to
weight functions, what allows defined the vertex‐
weightedgraph([4],[6],[7]).
Definition4
Avertex‐weightedgraph
),(
v
wG
isdefinedasa
graph
G together with a positive weight‐function
onitsvertexset
:
v
w
.0)( RGV
According to above definition we get next
definitions.
Definition5
The weighted domination number
)(G
w
of
),(
v
wG
is the minimum weight
Dv
vwDw )()(
of a set
)(GVD
such that
everyvertex
DDVx
)(
hasaneighborin
D
.
Definition6
The weighted connected domination number
)(G
Cw
of
),(
v
wG
is the minimum weight
C
Dv
C
vwDw )()(
of a set
)(GVD
C
such that
everyvertexof
C
DV \
isadjacenttoavertexin
C
D
andthesubgraphinducedby
C
D
isconnected.
Definition7
The weighted independent domination number
)(G
Iw
of
),(
v
wG
is the minimum weight
I
Dv
I
vwDw )()(
of a set
)(GVD
I
such that if
575
notwoverticesof
I
D
areconnectedbyanyedgeof
),( wG .
Similarly,itcanbedonefordirectedgraphs.
Taking into account the complexity of the
minimum dominating set, we should state, that in
generalisNP‐hardproblem.Efficientapproximation
algorithms do exist under assumption that any
dominating set problem can be formulated as a set
covering problem. Thus, the
greedy algorithm for
finding domination set is an analog of one that has
been presented in [4], [18]. This algorithms is
formulatedasfollows([4],[18]):
Algorithm1:
1 Let
V {1,...,n},
anddefine D
.
2
Greedy add a new node to D in each iteration,
until
D
formsadominatingset.
3
Anode
j
,issaidtobecoveredif
j
D orifany
neighborof
j
isin
D
.Anodethatisnotcovered
issaidtobeuncovered.
4
In each iteration, put into D the least indexed
node that covers the maximum number of
uncoverednodes.
5
Stopwhenallthenodesarecovered.
For graph in Figure 1, Greedy will return
}.2,1{D
Incaseoftheminimumconnecteddominationset,
theGreedyalgorithmisalsoused.However,todefine
themsomepreliminariesarenecessary[4],[19].
Weconsidergraph
G andsubset C ofvertices
in
G .Wecandividedallverticesintothreeclasses:
belongto C arecalledblack
b
v
;
not belong to C but adjacent to C are called
gray
g
v
;
notin C andnotadjacentto C arecalledwhite
w
v
.
Under assumption that
C is connected
dominatingsetifandonlyifthereisnowhitevertex
and the subgraph induced by black vertices is
connected.The sumofthe number of white vertices
and the number of connected components of the
subgraph induced by black vertices (black
components) equals 1. The greedy algorithm
with
potential function equal to the number of white
vertices plus number of black components is as
follows[4],[19].
Algorithm2:
Set
w: 1;
while 1w do
Ifthereexistsawhiteorgrayvertexsuchthat
coloringitinblackanditsadjacentwhite
verticesingraywouldreducethevalueof
potentialfunction
thenchoosesuchavertextomakethevalueof
potentialfunctionreduceinamaximumamount
elseset
w: 0;
3.2
Spanningtrees
The appropriate tool for the transportation system
analysisintermsofitsinfrastructureconnectingeach
nodethespanningtreeisproposed.Itcanbedonefor
bothundirectedanddirectedcases.
Definition8
The spanning tree T of a connected, undirected
graph
G is a tree composed of all the vertices and
some(orperhapsall)oftheedgesof
G.
Informally, a spanning tree of
G is a selection of
edgesof
Gthatform atree spanningevery vertex.It
means,thateveryvertexliesinthetree,butnocycles
(orloops)areformed[4].
According to Definition 5, the edge‐weighted
graphisintroduced.
Definition9
An edge‐weighted graph
),(
e
wG
is defined as a
graph graph
G together with a positive weight‐
functiononitsedgeset
:
e
w
.0)( RGE
Furthermore, for edge‐weighted graphs it is
possible to find minimum spanning tree, which is
definedasfollows.
Definition10
A minimum spanning tree (MST) of an edge‐
weightedgraphisaspanningtreewhoseweight(the
sumoftheweightsofitsedges)isnogreaterthanthe
weightofanyotherspanningtree.
It can be done according to two well‐known
algorithms:Kruskal’sandPrim’s.Theycanbeshown
asfollows[2],[4]:
Algortihm3(Kruskal’s)
1 Find the cheapest edge in the graph (if there is
morethanone,pickoneatrandom).Markitwith
anygivencolour,sayred.
2
Findthecheapestunmarked(uncoloured)edgein
the graph that doesnʹt close a coloured or red
circuit.Markthisedgered.
3
RepeatStep2untilyoureachouttoeveryvertexof
thegraph(oryouhave
n‐1colourededges).
The red edges form the desired minimum
spanningtree.
Algortihm4(Prim’s)
1 Pickanyvertexasastartingvertex‐
start
v
.Mark
itwithanygivencolour(red).
2
Find the nearest neighbor of
start
v
(call it P1).
Markboth P
1and the edge
start
v
P1red. Cheapest
unmarked (uncoloured) edge in the graph that
doesnʹt close a coloured circuit. Mark this edge
withsamecolourofStep2.
3
Find the nearest uncoloured neighbor to the red
subgraph(i.e.,theclosestvertextoanyredvertex).
Markitandtheedgeconnectingthevertextothe
redsubgraphinred.
4
RepeatStep3untilallverticesaremarkedred.
Theredsubgraphisaminimumspanningtree.
576
Theaboveknowledge(Sections3.1and3.2)canbe
applied to analyze transportation systems,
particularly its infrastructure (even critical). For
instance it is useful to choose the routes and nodes
classified as critical infrastructures [4], [8]. To show
possible applications of discussed methods, the
academicexampleisshownbellow.
Example
Let us consider the hypothetic map of road
connections, what is given by schema presented in
Figure4.Wechooseelevennodesanddescribethem
theconsecutivenumberandthetimeofredlight(in
seconds).Theedgesbetweenthenodesaredescribed
bythenumberofkilometers.
Figure4.Theexemplaryschemeofroad infrastructure.
Ourmaingoalistochoosetheminimalspanning
tree and minimal independent domination set, i.e.
findinganindependentdominationnumber.
According the Kruskal’s Algorithm, the minimal
spanningtreeisgiveninFigure5asthesetofdouble
edges.
Figure5.Minimalspanningtree(Kruskal’sAlgortihm)
Inthisway,theminimalnumberofkilometersis
equalto134[km].AccordingtoAlgorithm1,thetime
ofredlightsisequaledto430[seconds].Itisminimal
dominatingset,whatismarkedinFigure6withblack
nodes(vertices).
Figure6.Minimalweightedindependentdominationset.
3.3 Introductiontotheknapsackproblem
One of the most known problem in graph theory is
theknapsackproblem.Ithasbeenstudiedsince1897
and is combinatorial optimization problem. General
descriptionisbasedongivenasetofitems,eachwith
a mass and a value [3]. There is determined the
numberofeachitemto
includeinacollectionsothat
thetotalweightislessthanorequaltoagivenlimit
andthetotalvalueisaslargeaspossible(accordingto
(1)).Theknapsackproblemhasmanymodifiedforms,
i.e.toformofthe0‐1knapsackproblem.Inthiswayis
formulated as multi‐objective optimization
problem[3].
Generalassumptionabouta0‐1knapsackproblem
is it consists of a set of items, weight and profit
associated with each item, and an upper bound for
thecapacityoftheknapsack.Wewantfindasubsetof
items which maximizes the profits
and all selected
itemsfitintotheknapsack,i.e.,thetotalweightdoes
notexceedthegivencapacity[23].
Afterassuminganarbitrarynumberofknapsacks,
the single‐objective problem is extended directly to
themulti‐objectivecase.Formally,themulti‐objective
0‐1knapsackproblemcanbedefinedin
thefollowing
way[23]:
Given a set of
m
items and a set of
n
knapsacks,with
ji
p
,
profitofitem
j
accordingtoknapsack
i
,
ji
w
,
weightofitem
j
accordingtoknapsack
i
,
i
c
capacityofknapsack
i
,
findavector
,1,0,,,
21
m
m
xxx x
suchthat
m
i,j j i
j1
i {1,2,...,n} : wx c
(6)
and for which
)(,),(),()(
21
xxxx
n
ffff
is
maximum,where
m
ii,jj
j1
f( ) p x
x (7)
and
1
j
x
ifandonlyifwhenitem
j
ischosen.
Nowadays,thebestsolutionsofknapsackproblem
aredescribedintermsof ageneticmethods. Asitis
577
shown in [3] it can be very useful tool for multi‐
objectiveoptimizationoftransportationsystems.
3.4
Flowsintransportationsystems
The graph theoryis the basis for analyzing a traffic
flow in transportation systems and networks [13],
[17]. In section 3 the definition of undirected graph
was introduced. But, for more detailed analysis of
traffic flows, the digraphs should be defined. Thus,
thegraph
),( AVG
d
isdirectedgraphordigraph
with a set V, whose elements are called vertices or
nodes and set A of ordered pairs of vertices, called
arcs,directededges,orarrows(Figure7).
Figure7.Theexemplarydirectedgraph G .
ThemainreasonforthecreationofthisSubsection
is fact that transportation engineers need know the
trafficflowtheoryasatoolthathelpsunderstandand
express the problems of evaluating the capacity of
existing roadways or designing new ones. Thus, the
followingdefinitionsareimportant[17].
Definition11
Let
),,,( tsAVG
st
be a network with
Ats ,
being the source and the sink of
st
G
respectively.
Definition12
The capacity of an edge of network
st
G
is
mapping
,:
RAc
which represents the
maximum amount of flow that can pass through an
edge.Itisdenotedas
,
uv
c
where
., Avu
Definition13
A flow in network
st
G
is mapping
,:
RAf
uv
where
,, Avu
whichsubjectstothe
followingtwoconstrains:
1
,
),(
uvuv
Avu
cf
(capacity constraint: the flow of
anedgecannotexceeditscapacity)
2
Avuu
vu
Avuu
uv
tsVv
ff
),(:),(:
},{\
,
(conservation
of flows: the sum of the flows entering a node
must equal the sum of the flows exiting a node,
exceptforthesourceandthesinknodes).
Definition14
The value of flow
,
),(:
Avsv
svuv
ff
where
s
isthesourceof
st
G
.
Generally, the main problem in traffic flows is
maximize value of
uv
f
, which is called maximum
flowproblem.One ofthe solutionsis usingresidual
network,whichisdefinedasfollows[17].
Definition15
For given
st
G
and flow
uv
f
, we define the
residualnetwork
st
G
asfollows:
1
Thenodesetof
f
st
G
isthesameasthatof
st
G
;
2
Each edge
),( vue
of
f
st
G is with capacity
ee
fc
;
3
Each edge
),( uve
of
f
st
G is with capacity
.
e
f
Furthermore
}),(:min{ pvucc
f
uv
f
p
is
residualcapacityofpath
pinnetwork
f
st
G .
According to above definitions, the algorithm of
finding the maximal flow in network is given as
follows[13],[17].
Algorithm5(Ford‐Fulkerson)
For
eachedge
),( vue
do
Begin
uv
f
=0
vu
f
=0
End
Whileexistspath p from
s
do
t
in
f
st
G
do
Begin
}),(:min{ pvucc
f
uv
f
p
Foreach
pvue
),(
do
begin
uv
f
=
uv
f
+
f
p
c
vu
f
=‐
uv
f
End
End
Return
f.
Based on algorithm 5, the exemplary residual
networkisproposedinFigure8.
Figure8. Exemplary original and residual network, where
s:=1,t:=6.
578
4
CONCLUSION
Inthepaper,theconceptofcriticalinfrastructureshas
been presented. Some review and classifications of
well‐known information about optimization, graph
theoryandnetworkflowtheoryhavebeendone.The
SPEAalgorithmhasbeendescribedstep‐by‐stepand
the knapsack problem with its binary modification
has been presented.
It hasalso been used the SPEA
algorithm to solve the 0‐1 knapsack problem.
Furthermore,theselecteddefinitions,parametersand
algorithmsofgraphtheoryhavebeenintroducedand
applied to system transportation analysis. As the
example of possible application, the road
transportation system with the shortest time of red
lightinnodesandtheshortestkilometershavebeen
determined. The examples, from Section 3, are only
showing potential applications of methods,
algorithms and parameters, which are described in
thearticle.
REFERENCES
[1]COMMISSION OF THE EUROPEAN COMMUNITIES
(2006), Communication from the Commission on a
European Programme for Critical Infrastructure
Protection,Brussels.
[2]Cormen,T.H.&al.(2009).IntroductiontoAlgorithms,
Third Edition. MIT Press, ISBN 0‐262‐03384‐4. Section
23.2:ThealgorithmsofKruskalandPrim,pp.631–638.
[3]
Guze,S.(2014).Applicationoftheknapsackproblemto
reliability multi‐criteria optimization. Journal of Polish
Safety and Reliability Association, Summer Safety and
ReliabilitySeminars,Vol.5,No1,pp.85–90.
[4]Guze, S. (2014). The graph theory approach to analyze
criticalinfrastructuresoftransportationsystems.Journal
of
Polish Safety and Reliability Association, Summer Safety
andReliabilitySeminars,Vol.5,No2,pp.57‐62.
[5]Guze,S.Smolarek,L.(2011).Methodsforrisk minimizing
intheprocessofdecision‐makingunderuncertainty.Journal
ofPolishSafetyandReliabilityAssociation‐JPSRA,Vol.
2,Number1,123–128,
Gdańsk‐Sopot.
[6]Harary, F. (1969). Graph Theory. Addison‐Wesley,
Reading.
[7]Haynes T. W., Hedetniemi, S., Slater, P. (1988).
FundamentalsofDominationinGraphs.CRCPress.
[8]Kołowrocki, K. (2013). Safety of critical infrastructures.
JournalofPolishSafetyandReliabilityAssociation,Summer
SafetyandReliabilitySeminars,
Vol.4,No.1,pp.51‐74.
[9]Kołowrocki, K. (2004). Reliability of Large Systems.
Elsevier, Amsterdam‐Boston‐Heidelberg‐London‐
NewYork‐Oxford‐Paris ‐SanDiego‐SanFrancisco‐
Singapore‐Sydney‐Tokyo.
[10]Kołowrocki, K. & Soszyńska, J. (2010). Optimization of
complextechnicalsystemsoperationprocesses.Maintenance
Problems,
No1,31‐40,Radom.
[11]Kołowrocki,K.&Soszyńska‐Budny,J.(2011).Reliability
and Safety of Complex Technical Systems and Processes,
Modeling – Identification – Prediction – Optimization,
Springer‐Verlag.
[12]Kołowrocki, K. Soszyńska‐Budny, J. (2013). Reliability
predictionandoptimizationofcomplextechnicalsystems
with
applicationinporttransport.JournalofPolishSafetyand
Reliability Association, Summer Safety and Relibility
Seminars – SSARS 2013, Volume 3, Number1‐2, 263 –
279,Gdańsk‐Sopot.
[13]Leeuwen,Van,J.(1986).GraphAlgorithms.Book.
[14]Marie, S. & Courteille, E. (2009) Multi‐Objective
Optimization of
Motor Vessel Route. TransNav, The
International Journal on Marine Navigationand Safety
ofSeaTransportation,Vol.3,No.2,133‐141,Gdynia.
[15]Martello, S. & Toth, P. (1990). Knapsack Problems:
Algorithms and Computer Implementations. Chichester,
U.K.:Wiley.
[16]Ming‐Hua, L., Jung‐Fa, T. and Chian‐Son Y. (2012),
A
Review of Deterministic Optimization Methods in
Engineering and Management,Mathematical Problemsin
Engineering,Volume2012.
[17]Newell, G. F. (1980). Traffic flow on transportation
networks. MIT Press Series in transportation studies,
Monograph5.
[18]Parekh,A.K. (1991). Analysis ofGreedy Heuristic for
Finding Small Dominating Sets in Graphs.
Information
ProcessingLetters,Volume39,Issue5,pp.237–240.
[19]Ruan, L. & al., (2004). A greedy approximation for
minimum connected dominating sets. Theoretical
ComputerScience,Volume329,Issues1–3,pp325–330.
[20]Sun,W.andYuan,Y.‐X.(2006).Optimizationtheoryand
methods:nonlinearprogramming.Springer‐
Verlag.
[21]Szłapczyńska, J. (2013). Multicriteria Evolutionary
Weather Routing Algorithm in Practice. TransNav, the
International Journal on Marine Navigationand Safety
ofSeaTransportation,Vol.7,No.1,61‐65,Gdynia.
[22]Venter, G. (2010). Review of Optimization Techniques,
Encyclopedia of Aerospace Engineering, John Willey and
Sons,Ltd.
[23]Zitzler,E.&Thiele,L.(1999).MultiobjectiveEvolutionary
Algorithms: A Comparative Case Study and the Strength
Pareto Approach. IEEE Transactions on Evolutionary
Computation,VOL.3,NO.4.,257–271.
