Groupwise evacuation with genetic algorithms
Master thesis
Permanent lenke
http://hdl.handle.net/11250/137575Utgivelsesdato
2013Metadata
Vis full innførselSamlinger
Sammendrag
In a crisis situation on board a ship, it can be of the utmost importance to have the
passengers safely evacuate to the lifeboats in an efficient manner. Existing methods
such as marked escape routes, maps and so on are not optimal as pre-planned
escape routes may become heavily congested by passengers. The closest lifeboat
is not always feasible as lifeboat capacity can be exceeded. Considering that some
evacuees are strongly affiliated and would like to evacuate together as a group, it
all becomes a very difficult problem to solve. Sub-problems have been modelled,
but no existing model combines all of these aspects into account.
We proceed by modelling the area to be evacuated as a time-expanded graph,
assuming that future development in hazard severity is known in the form of a
survivability percentage for each node. Then we apply a multi-objective genetic
algorithm with five different fitness functions that use heuristics to maximize
overall survivability and reduce the total egress time if possible. A method has been
developed to pick the best evacuation plan out of the pool of potential solutions
returned by the genetic algorithm. The solution is compared with Dijkstra’s
algorithm and randomly generated paths.
Experiments are conducted using these algorithms for both predefined and randomly
generated graphs using different parameters. In the tested random graph,
the genetic algorithm gives on average 24% better survivability and 3 times better
grouping Random algorithms. A fixed network with a known solution was solved
100%.
This genetic algorithm can be used to generate better routing plans that utilizes
multiple evacuation routes and lifeboats while taking into account groups, resulting
in smoother evacuations which can save more lives.
Beskrivelse
Masteroppgave i informasjons- og kommunikasjonsteknologi IKT590 2013 – Universitetet i Agder, Grimstad