Approximation algorithms for the bus evacuation problem

Autor(es)

Pedrosa, Lehilton L. C. ^[1] ; Schouery, Rafael C. S. ^[1]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Inst Comp, Av Albert Einstein, 1251, Cidade Univ, BR-13083852 Campinas, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 36, n. 1, p. 131-141, JUL 2018.
• Citações Web of Science: 0

Resumo

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. (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático