Algoritmo de Aproximação para o Problema da Evacuação por Ônibus

• Lehilton L. C. Pedrosa UNICAMP
• Rafael C. S. Schouery UNICAMP

DOI: https://doi.org/10.5753/etc.2017.3197

Resumo

No Problema de Evacuação por Ônibus (BEP), dado um inteiro B, um grafo bipartido com partes S e T em um espaço métrico, e um vértice r, deseja-se encontrar um conjunto de B passeios, cada um começando em r e terminando em um vértice de T, de forma que cada vértice i de S é visitado no mínimo l_i vezes e cada vértice de T é visitado no máximo u_j vezes. O objetivo é encontrar uma solução que minimiza o comprimento da maior rota. Esse problema aparece em situações de planejamento para emergência, em que cada passeio corresponde à rota de um de B ônibus, que devem transportar cada grupo de pessoas em S para uma área segura em T. Neste trabalho, obtemos uma 5,2-aproximação para BEP sem capacidades, em que u_j é infinito para cada j.

Referências

Bish, D. R. (2011). Planning for a bus-based evacuation. OR Spectrum, 33(3):629–654.

Goerigk, M., Grün, B., and Heßler, P. (2013). Branch and bound algorithms for the bus evacuation problem. Computers & Operations Research, 40(12):3010 – 3020.

Sebő, A. (2013). Eight-fifth approximation for the Path TSP. In Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, pages 362–374.