Emergency routing using fishbone algorithm

Abstract

In 2002 the city of Prague was affected by a flooding of the river Vltava, caused by heavy rainfall in the Southwest area of the Czech Republic. Successive parts of the city were inundated and inhabitants have to be evacuated from areas threatened by the raising water. After breaching the dikes and upcoming water via caves and sewers, streets were flooded. A special Crisis App was designed to route people to safe areas via safe routes. The routing system is visualized by fishbone maps, commonly used in car routing systems. To compute the shortest path from current location to a safe area a hierarchical version of Dijkstra shortest path algorithm has been used. Fleeing citizens and special observation agents report about changing situations. If crossings and streets are flooded, new routes have to be computed or existing routes have to be adapted by applying Dijkstra again. The application is Prague specific but can be generalized to similar smart cities in case of flooding disasters. More details will be presented in the paper including a simulation study showing the adaptive routing of the Crisis App.