International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 4
Number 2
June 2010
227
1 INTRODUCTION
The trend in building very large passenger ships im-
poses a necessity for the safety systems of those ves-
sels to be constantly improved. Sea voyages offer an
attractive way of spending free time, therefore en-
suring safety of people on board should constitute an
ultimate goal to be pursued, also in case of emergen-
cy evacuation from a vessel. An analysis of factors
affecting the evacuation process should precede the
actual stage of designing a vessel so that the risks
can be, at least partially, eliminated during ship op-
eration. For buildings ashore the actual time of
evacuating counts till the moment the building is
left. For ships, this process should be divided into
the following stages: proceeding to muster stations,
abandoning vessel (embarkation on life–saving ap-
pliances and their launching or the same combined
with evacuation slide system). The time in case of
possible emergency evacuation of people should not
exceed the time available to carry out the evacua-
tion.
The analysis of evacuating people from a ship is
very complex because it involves a large number of
factors influencing the evacuation process and spe-
cific conditions related with the marine environment.
Models accounting for potentially greatest number
of factors affecting the evacuation process make it
possible to obtain results close to reality. However,
they are extremely difficult to verify. While con-
ducting full scale evacuation trials we cannot hurt
the volunteers, let them be affected by smoke, etc.
which makes the results of those trials different from
what can happen during the actual evacuation.
Theoretical analysis and actual trials of passenger
ship evacuation (in order to verify the models) are
carried out by research centres in collaboration with
maritime administration, industry and transport. The
development of evacuation analysis is coordinated
by the International Maritime Organization (IMO).
From the point of view of population of people
taking part in the evacuation, two approaches can be
distinguished. In the first one, referred to as the
global approach, people in motion are treated as a
liquid (hydraulic) medium. The process of move-
ment is described by a simple equation of flow kin-
ematics (e.g. models: EVACNET4 (Kisco & Francis
& Nobel, 1998), WAYOUT (Shestopal & Grubits,
1994)). In the individual approach the movement is
analysed, often in association with a defined pattern
of behaviour, separately for each participant of the
evacuation (e.g. models: Simulex ( Thompson &
Marchant, 1995), PedGo (Meyer- König & Klupfel
& Schreckenberg, 2001)).
The decision making process of people who take
part in the evacuation is presented in the model on
the basis of a relevant method for the simulation of
human behaviour. The classification of models ac-
cording to behavioural systems is as follows (Erica
& Kuligowski & Peacock, 2005):
− without behavioural principles (only the aspect of
movement is taken into consideration) e.g. mod-
els: EVACNET4, PathFinder (Cappuccio, 2000),
− alleged behaviour (models do not declare princi-
ples of behaviour, instead they assume them on
the basis of alleged behaviour), e. g. models:
PedGo, Simulex,
The Possibility of Application of Algorithms
Indicating Maximum Paths in Directed Graphs
for Modeling of the Evacuation Process
D. H. Lozowicka
Maritime University of Szczecin, Szczecin, Poland
ABSTRACT: In the introduction, ways of accounting geometrical, population, environment and procedure
parameters in the computer evacuation simulating programs have been shown. In the part to follow the meth-
od for graph theory based representation of the geometry of escape routes has been described. Besides,
means of indicating the longest time of emergency evacuation is proposed using a modified Warshall’s algo-
rithm to find the maximum weights in the directed graph. The use of the algorithm to indicate maximum es-
cape routes makes it possible to verify the arrangement of escape routes in newly designed or existing ships.
228
− behavioural system based on principles (system
“if, then”), e.g. models: EXITT (Levin, 1998), E-
SCAPE (Reisser-Weston, 1996),
− probabilistic behavioural system (principles in-
cluded in the model are stochastic), e. g. CRISP
(Fraser-Mitchell, 2001), ASERI models (Schnei-
der & Konnecke, 2001),
− behavioural system based on artificial intelli-
gence, e.g. models: Legion (Williams, 2005) Ve-
gas (Still, 1994).
Evacuation models differ according to the way
the movement of people is presented. In most types
of models people have their specific travel speed
(actual data). However, in the instances of a greater
density leading to queuing there are various methods
of describing the movements of people. In the situa-
tion of a restricted flow, the following approaches to
modeling can be distinguished:
− determining the speed and flow of people (indi-
viduals or populations) on the basis of the geome-
try of the analyzed space (density), e.g. WAY-
OUT, STEPS (Hoffman & Henson, 1998)
models,
− establishing individual distances between evacu-
ating people and possible obstacles, e.g. SIM-
ULEX, VEGAS models,
− calculating the undisturbed flow, then accounting
for disturbances using various coefficients, e. g.
ALLSAFE model (Heskestad & Meland, 1998).
In all models the surroundings of evacuation must
be presented, i.e. the geometry of the interior (corri-
dors, spaces layout). The space is divided into sub-
spaces and each subspace is attached to the neigh-
bouring ones. Usually two methods are employed:
− space is substituted for a network of polarized
spaces of different shapes and sizes, depending
on the model (e. g. PedGo, EGRESS models
(Ketchell & Cole & Webber, 1994)), making it
possible to locate an individual evacuated as well
as possible obstacles by the determination of the
exact position in the space (room),
− space is shown by means of fields which stand for
spaces (rooms) or corridors and are not consistent
with actual dimensions, giving the exact position
of an evacuated person in a given space (room) is
not possible; there is only a possibility to move
between the components of the analyzed structure
(e. g. EXODUS model (Gwynne & Galea & Law-
rence & Filippidis, 1998)).
2 THE REPRESENTATION OF THE
GEOMETRY OF SHIP’S ESCAPE ROUTES
BASED ON THE GRAPH THEORY
On the basis of ship evacuation plan it is possible to
present the layout of evacuation routes on the ship
(corridors, stairways and spaces) in the form of a
hydraulic network. In the next stage, utilizing the
graph theory and accounting for the movement of
passengers along escape routes, the layout of the es-
cape routes is brought down to the format allowing
for further use in the designed model of evacuation.
Particular stages of encoding the escape routes
layout in the form of the directed graph is shown in
Figure1.
When using this kind of record, it is suggested
that one of the ways of looking for the maximum
evacuation path be employed to form the most dis-
advantageous scenario of evacuation, that is, to cal-
culate the maximum weights of the graph. To this
end the modified Warshall’s algorithm was used
(Ross, 2005).
The devised method will be presented using a
chosen vessel as an example.
Figure 1. Algorithm of encoding the emergency escape routes
arrangement into the form of the directed graph.
In room PP there are 180 people, who split up the
moment the evacuation commences and proceed
through three exits: towards the staircase b and the
doors a and c. Figure 2 shows the escape routes ar-
rangement together with the direction of the evacua-
tion.
PP
b
a
e
g
c
d
h
DP
l
f
j
Figure 2. Escape routes arrangement together with the direc-
tion of the evacuation
The escape routes arrangement is represented as
a digraph in which a set of vertices represents the
particular sections of escape routes, while the edges
represent the connections among them (Fig 3). In the
229
digraph which represents escape routes, the weight
of the edge can be interpreted as the walking time of
a given evacuation group along this kind of path.
PP
c
b
a
d
f
e
j
MZ
h
i
g
Figure 3 The escape routes arrangement is represented as a di-
graph.
To calculate the time of evacuation T
c
, the meth-
od of calculating the flow of people through respec-
tive nodes of the arrangement was used.
The time of the transit of x passengers along a
given arc (passageway, space) is:
( )
csśr
c
WF
x
S
L
T
⋅
+=
(1)
where:
S
śr
- mean speed of people along the escape
routes can be assumed as ca. 0.5 m/s when the ship
is listing (Yoshida& Murayama & Itakaki, 2001),
(Ando& Ota & Oki, 1988),
L- the length of passageways
W
c
– the breadth, measured betwen the handrails,
for the passageways and stairways, and the door
breadth when fully open,
F
s
– specific flow is assumed to be 0.43 (per-
son/ms) (acc. SFPE Fire Protection Engineering
Handbook, 2
nd
edition, NFPA 1995),
The time obtained should be increased by coeffi-
cients accounting for: passenger age, passageways
inaccessibility, restricted visibility, flow of people in
the opposite direction and other factors which may
hinder the evacuation.
The increasing coefficients are assumed to be 2.3
(IMO, Circular MSC/Circ.1033).
The table of the weights of the analyzed exam-
ple has the following form:
−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−
357
428
204
556
361
147
147
357
312
357
363343363
The symbol ∞ indicates that in the graph there is no
path between given vertices.
3 WARSHALL ALGORITHM FOR FINDING
THE MAXIMUM PATHS
In connection with the intended adaptation of the
Warshall algorithm for finding the maximum paths
all cases of ∞ were replaced by values -∞, whilst -
∞+x = -∞ = x + (-∞) for a given x and -∞<a for all
real numbers a.
The maximum weight is called the largest weight of
path leading from one vertix to the other and is de-
noted as M.
The general formula of the Warshall algorithm to
form the table of the maximum weights of the graph
is as follows (Ross, 2005):
{Data: matrix W
0
of non-negative edge weights of
the directed graph without loops and multiple edges}
{Results: matrix M the weight of maximums of this
graph}
{ Auxiliary variables: matrix W}
W:=W
0
for k =1 n perform
for i =1 up to n perform
for j =1 up to n perform
if W[i,j]<W[i,k]+W[k,j], then
replace W[i,j] with the sum W[i,k]+W[k,j]
M:=W
The calculations of the maximum weights func-
tions table of the analysed example are as follows:
W=W
0
=
230
−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−
∞−∞−∞−∞−∞−∞−∞−∞−∞−
357
428
204
556
361
147
147
357
312
357
363343363
Due to the fact that we deal with a sequence of
events, the algorithm is to be simplified because we
focus only on the maximum paths coming out of the
vertix PP, that is, we assume that i=1.
W
1
=
[ ]
∞−∞−∞−∞−∞−∞−∞−∞−∞− 363343363
W
2
=
[ ]
363363363363363363720363363343363∞−
W
3
=
[ ]
363363363363363675720363363343363∞−
etc.
As a result, the following maximum weights from
the vertix PP are obtained.
M=
[ ]
2055137316271423867675720363363343363∞−
In the analyzed example of escape routes ar-
rangement the longest time of evacuation amounts to
2055 s (ca. 34 minutes). The longest evacuation time
there is for the following paths:
PP-a-e-g-h-i-MZ
PP-c-d-g-h-i-MZ
We assume that each of those paths is passed by 60
persons. Those groups of people achieve following
time of moving by analyzed edges of graph:
PP-a (PP-c) -343 seconds
c-d (a-e) – 357 seconds
d-g (e-g) – 147 seconds
g-h – 556 seconds
h-i – 204 seconds
i -MZ – 428 seconds
Alternative paths (PP-b-f-j-MZ) is definitely shorter
than above mentioned.
4 CONCLUSION
The purpose of the paper was to present an applica-
tion of the Warshall algorithm to calculate the long-
est time of evacuation on the ship.
The ship evacuation plan can be presented in the
form of a digraph with assigned weighted edges of
the graph. Then, by applying one of the algorithms
determining maximum paths, the longest evacuation
time can be set for assumed evacuation scenarios.
The analysed example was simplified by an as-
sumption that the evacuees would split up propor-
tionally to head for the available exits. However, it is
not seldom that everyone chooses one particular
egress (so called “herd instinct”), leaving the re-
maining ones unused. This can ultimately lead to
congestions or decelerating the evacuation. There-
fore this phenomenon is to be taken into account in
further studies.
The method of representing the evacuation routes
arrangement as a digraph and the application of the
algorithm to determine the maximum paths enables
the design solutions of escape routes to be verified
both for newbuildings and ships in operation.
At present it is mandatory to carry out an evacua-
tion analysis for passenger vessels of the ro-ro and
high speed craft type. However, in the future it is in-
tended to include all passenger vessels carrying
more than 1000 people. It shows that further studies
on modeling the evacuation process are needed,
which is justified by the fact that evacuation scenar-
ios recommended by the IMO are inaccurate and
have proved inadequate to real-life situations.
REFERENCES
Ando K.& Ota H. & Oki T. 1988. Forecasting the flow of peo-
ple, Railway Research Review, vol. 45, pp. 8-14.
Cappuccio J., 2000. Pathfinder: A Computer-Based Timed
Egress Simulation, Fire Protection Engineering, 8, pp.11-
12.
Erica D.& Kuligowski R. D. & Peacock A.,2005. Review of
Building Evacuation Models, National Institute of Stand-
ards and Technology Technical Note 1471, U.S. Govern-
ment Printing Office Washington.
Fraser-Mitchell J., 2001. Simulated Evacuations of an Airport
Terminal Building, using the CRISP Model, In 2nd Interna-
tional Symposium in Human Behaviour in Fire, pp. 89-100,
Boston, MA.
Gwynne S. & Galea E. R.& Lawrence P.& Filippidis L., 1998.
A Systematic Comparison of Model Predictions Produced
by the buildingEXODUS Evacuation Model and the Tsu-
kuba Pavilion Evacuation Data, Applied Fire Science, 7, pp.
235-266.
Heskestad A. W. & Meland O. J., 1998. Determination of
Evacuation Times as a Function of Occupant and Building
Characteristics and Performance of Evacuation Measures,
231
In Human Behaviour in Fire - Proceedings of the 1st Inter-
national Sympodium, pp. 673-680.
Hoffman N. A. & Henson D. A., 1998 Analysis of the Evacua-
tion of a Crush Loaded Train in a Tunel, In 3rd Interna-
tional Conference on Safety in Road and Rail Tunnels,
Nice, France.
International Maritime Organisation (IMO), 2002. Sub-
commiteee on Fire Protection, Recommendation on Evacu-
ation Analysis for New and Existing Passenger ships, FP
46/WP.10, FP 46/3, FP 46/3/1, FP 46/3/2, FP 46/INF.3,
FP46/UP2, 46-th session.
International Maritime Organisation (IMO), 2002. Interim
Guidelines for evacuation analysis for new and existing
passenger ships, MSC Circular n. MSC/Circ.1033, 26-th
June.
Ketchell N. & Cole S. S. &Webber D. M., 1996. The
EGRESS Code for Human Movement and Behaviour in
Emergency Evacuation, In R.A.Smith & J. F. Dickie (Eds.),
Engineering for Crowd Safety, pp. 361-370, London: Else-
vier.
Kisko T. M. & Francis R. L.& Nobel C. R., 1998. EVACNET4
User's Guide, Version 10/29/98, University of Floryda.
Levin B. M., 1998. EXITT: A Simulation Model of Occupant
Decisions and Actions In Residential Fires, (Rep. No.
NBSIR 88-3753), Natl. Inst. Stand. Techno.
Meyer- König T.& Klupfel H.& Schreckenberg M., 2001. A
microscopic model for simulating mustering and evacuation
process onboard passenger ships. In Proceedings of the In-
ternational Emergency Management Society Conference.
Reisser-Weston E. 1996. Simulating Human Behaviour in
Emergency Situations, In RINA, International Conference
of Escape, Fire, and Rescue.
Ross K.A,2005. Matematyka dyskretna. Wydawnictwo nauko-
we PWN, Warszawa.
Schneider V. & Konnecke R., 2001. Simulating Evacuation
Processes with ASERI, In Tagungsband International Con-
ference on Pedestrian Evacuation Dynamics (PED), Duis-
burg.
Shestopal V. O. & Grubits S. J.,1994. Evacuation Model for
Merging Traffic Flows In Multi-Room and Multi-Story
Buildings, In Fire Safety Science, Proceedings of the 4th
International Sympodium, pp. 625-632.
Still G. K., 1994. Simulating Egress using Virtual Reality - a
perspective view of simulation and design, IMAS Fire Safe-
ty on Ships sympodium.
Thompson P. A.& Marchant E., 1995., Testing and Application
of the Komputer Model 'SIMULEX', Fire Safety Journal,
24, pp.149-166.
Yoshida K. & Murayama M. & Itakaki T., 2001. Study on
evaluation of escape route in passenger ships by evacuation
simulation and full-scale trails, INTERFLAME.
Williams A., 2005. Go with the Flow, The Architect's Journal.
