Robust Flows with Losses and Improvability in Evacuation Planning

  • We consider a network flow problem, where the outgoing flow is reduced by a certain percentage in each node. Given a maximum amount of flow that can leave the source node, the aim is to find a solution that maximizes the amount of flow which arrives at the sink. Starting from this basic model, we include two new, additional aspects: On the one hand, we are able to reduce the loss at some of the nodes; on the other hand, the exact loss values are not known, but may come from a discrete uncertainty set of exponential size. Applications for problems of this type can be found in evacuation planning, where one would like to improve the safety of nodes such that the number of evacuees reaching safety is maximized. We formulate the resulting robust flow problem with losses and improvability as a mixed-integer program for finitely many scenarios, and present an iterative scenario-generation procedure that avoids the inclusion of all scenarios from the beginning. In a computational study using both randomly generated instance and realistic data based on the city of Nice, France, we compare our solution algorithms.

Volltext Dateien herunterladen

Metadaten exportieren

Verfasserangaben:Marc Goerigk, Ismaila Abderhamane Ndiaye
URN (Permalink):urn:nbn:de:hbz:386-kluedo-39474
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):12.10.2014
Jahr der Veröffentlichung:2014
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):10.12.2014
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 28.10.2014