ISBN 9783843930345

978-3-8439-3034-5, Reihe Mathematik

Philipp Heßler
Sink Location and Evacuation Planning

155 Seiten, Dissertation Technische Universität Kaiserslautern (2016), Hardcover, A5

Zusammenfassung / Abstract

Sink location problems can be used to model the choice of shelter locations in evacuation planning. These problems are formulated on graphs with capacitated edges and nodes. The aim of each sink location problem is to find a minimum cost set of sinks among the feasible nodes such that the supply of all nodes can be discharged as flows through the network to the chosen sinks. Sink location problems can be differentiated according to three criteria:

1. To how many sinks may the supply of one node be sent?

2. Are the flows from different nodes considered at the same time?

3. Is there a limit on the flow arriving at a sink and do the flows add up at the sinks?

Following these criteria, sink location problems can be divided into single and plural, simultaneous and non-simultaneous, and uncapacitated, independent, and additive sink location problems. The uncapacitated single non-simultaneous, plural non-simultaneous, and plural simultaneous sink location problems are equivalent to the single, plural, and simultaneous source location problems which have already been studied in literature. In this thesis, we prove relations among sink location problems showing that almost all plural sink location problems are equivalent. Several problems allow integral flows in an optimal solution. We show that each single simultaneous and the plural simultaneous independent sink location problem do not necessarily admit such flows in an optimal solution. The complexity of verifying feasibility and finding an optimal solution for the different problems is analyzed. Some problems can be solved to optimality in polynomial time while for others it is already strongly NP-hard to check whether a given instance is feasible. The main contributions are NP-hardness results and approximation algorithms for line, tree, cactus, and general graphs achieving the best possible performance guarantee.