Sink location to find optimal shelters in evacuation planning

P. Heßler () and H. W. Hamacher ()
Additional contact information
P. Heßler: University of Kaiserslautern
H. W. Hamacher: University of Kaiserslautern

EURO Journal on Computational Optimization, 2016, vol. 4, issue 3, No 6, 325-347

Abstract: Abstract 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. A mixed integer programming formulation is given which is shown to have the integrality property. 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.

Keywords: Network location; Sink location; Network flows; 90B80; 90B10; 90C27; 90C35 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-015-0054-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:4:y:2016:i:3:d:10.1007_s13675-015-0054-7

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-015-0054-7

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().