Anzeige
Erschienen in:
17.04.2018
Approximation algorithms for the bus evacuation problem
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2018
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We consider the bus evacuation problem. Given a positive integer B, a bipartite graph G with parts S and \(T \cup \{r\}\) in a metric space and functions \(l_i :S \rightarrow {\mathbb {Z}}_+\) and \({u_j :T \rightarrow \mathbb {Z}_+ \cup \{\infty \}}\), 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\) times and each vertex j of T must be 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 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 }\)-hard and present a 10.2-approximation algorithm. Further, for the uncapacitated BEP, in which \(u_j\) is infinity for each j, we give a 4.2-approximation algorithm.