Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Approximation algorithms for the bus evacuation problem

Texto completo
Autor(es):
Pedrosa, Lehilton L. C. [1] ; Schouery, Rafael C. S. [1]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Av Albert Einstein, 1251, Cidade Univ, BR-13083852 Campinas, SP - Brazil
Número total de Afiliações: 1
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
Linha de fomento: Auxílio à Pesquisa - Temático