Approximation algorithms for the bus evacuation problem

Lehilton L. C. Pedrosa () and Rafael C. S. Schouery ()
Additional contact information
Lehilton L. C. Pedrosa: University of Campinas
Rafael C. S. Schouery: University of Campinas

Journal of Combinatorial Optimization, 2018, vol. 36, issue 1, No 13, 141 pages

Abstract: Abstract 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.

Keywords: Bus evacuation; Emergency planning; Approximation algorithm (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0290-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:1:d:10.1007_s10878-018-0290-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0290-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().