Sink Location to Find Optimal Shelters in Evacuation Planning

  • The sink location problem is a combination of network flow and location problems: From a given set of nodes in a flow network a minimum cost subset \(W\) has to be selected such that given supplies can be transported to the nodes in \(W\). In contrast to its counterpart, the source location problem which has already been studied in the literature, sinks have, in general, a limited capacity. Sink location has a decisive application in evacuation planning, where the supplies correspond to the number of evacuees and the sinks to emergency shelters. We classify sink location problems according to capacities on shelter nodes, simultaneous or non-simultaneous flows, and single or multiple assignments of evacuee groups to shelters. Resulting combinations are interpreted in the evacuation context and analyzed with respect to their worst-case complexity status. There are several approaches to tackle these problems: Generic solution methods for uncapacitated problems are based on source location and modifications of the network. In the capacitated case, for which source location cannot be applied, we suggest alternative approaches which work in the original network. It turns out that latter class algorithms are superior to the former ones. This is established in numerical tests including random data as well as real world data from the city of Kaiserslautern, Germany.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Philipp Heßler, Horst W. Hamacher
URN (permanent link):urn:nbn:de:hbz:386-kluedo-39344
Document Type:Preprint
Language of publication:English
Publication Date:2014/11/24
Year of Publication:2014
Publishing Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2014/11/24
Tag:network flow; network location; sink location
Number of page:25
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 28.10.2014