Approximation Algorithm for the Bus Evacuation Problem

• Lehilton L. C. Pedrosa UNICAMP
• Rafael C. S. Schouery UNICAMP

DOI: https://doi.org/10.5753/etc.2017.3197

Abstract

We consider the Bus Evacuation Problem (BEP) in which, given a number B, a bipartite graph with parts S and T in a metric space, and a vertex r, one wishes to find a set of B walks, each starting in r and finishing in T so that each vertex i of S is visited at least l_i times, and each vertex j of T is visited at most u_j times. The objective is to find a solution that minimizes the length of the longest walk. This problem arises in emergency planning situations where the walks correspond to the routes of B buses, that must transport each group of people in S to a safe zone in T. In this paper, we give a 5.2-approximation algorithm for the uncapacitated BEP, where u_j is infinity for each j.

References

Bish, D. R. (2011). Planning for a bus-based evacuation. OR Spectrum, 33(3):629–654.

Goerigk, M., Grün, B., and Heßler, P. (2013). Branch and bound algorithms for the bus evacuation problem. Computers & Operations Research, 40(12):3010 – 3020.

Sebő, A. (2013). Eight-fifth approximation for the Path TSP. In Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, pages 362–374.