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.
Verfasser*innenangaben: | Marc Goerigk, Bob Grün, Philipp Heßler |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-35276 |
Dokumentart: | Preprint |
Sprache der Veröffentlichung: | Englisch |
Datum der Veröffentlichung (online): | 06.04.2013 |
Jahr der Erstveröffentlichung: | 2013 |
Veröffentlichende Institution: | Technische Universität Kaiserslautern |
Datum der Publikation (Server): | 05.06.2013 |
Seitenzahl: | 16 |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Lizenz (Deutsch): | Standard gemäß KLUEDO-Leitlinien vom 10.09.2012 |