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.

Download full text files

Export metadata

Author:Marc Goerigk, Bob Grün, Philipp Heßler
Document Type:Preprint
Language of publication:English
Date of Publication (online):2013/04/06
Year of first Publication:2013
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2013/06/05
Page Number:16
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012