Approximation algorithms for the bus evacuation problem

We consider the bus evacuation problem. Given a positive integer B, a bipartite graph G with parts S and $$T \cup \{r\}$$ T ∪ { r } in a metric space and functions $$l_i :S \rightarrow {\mathbb {Z}}_+$$ l i : S → Z + and $${u_j :T \rightarrow \mathbb {Z}_+ \cup \{\infty \}}$$ u j : T → Z + ∪ { ∞ } , 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 $$l_i$$ l i times and each vertex j of T must be visited at most $$u_j$$ 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 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 $$\text{ NP }$$ NP -hard and present a 10.2-approximation algorithm. Further, for the uncapacitated BEP, in which $$u_j$$ u j is infinity for each j, we give a 4.2-approximation algorithm.