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

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

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 li vezes e cada vértice de T é visitado no máximo uj 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 uj é infinito para cada j.