Approximation algorithms for the bus evacuation problem

作者：Pedrosa Lehilton L C; Schouery Rafael C S^*

来源：Journal of Combinatorial Optimization, 2018, 36(1): 131-141.

DOI：10.1007/s10878-018-0290-x

• Bus evacuation
• Emergency planning
• Approximation algorithm

We consider the bus evacuation problem. Given a positive integer B, a bipartite graph G with parts S and in a metric space and functions and , one wishes to find a set of B walks in G. Every walk in B should start at r and finish in T and r must be visited only once. Also, among all walks, each vertex i of S must be visited at least times and each vertex j of T must be visited at most 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 shelter in T, and the objective is to evacuate the entire population in the minimum amount of time. In this paper, we prove that approximating this problem by less than a constant is -hard and present a 10.2-approximation algorithm. Further, for the uncapacitated BEP, in which is infinity for each j, we give a 4.2-approximation algorithm.

• 出版日期2018-7