A Branch-Cut-and-Price Approach to the Bus Evacuation Problem with Integrated Collection Point and Shelter Decisions

  • We consider the problem of evacuating a region with the help of buses. For a given set of possible collection points where evacuees gather, and possible shelter locations where evacuees are brought to, we need to determine both collection points and shelters we would like to use, and bus routes that evacuate the region in minimum time. We model this integrated problem using an integer linear program, and present a branch-cut-and-price algorithm that generates bus tours in its pricing step. In computational experiments we show that our approach is able to solve instances of realistic size in sufficient time for practical application, and considerably outperforms the usage of a generic ILP solver.

Volltext Dateien herunterladen

Metadaten exportieren

Verfasserangaben:Marc Goerigk, Bob Grün, Philipp Heßler
URN (Permalink):urn:nbn:de:hbz:386-kluedo-35276
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):06.04.2013
Jahr der Veröffentlichung:2013
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):05.06.2013
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012