Uma Aproximação Ótima para o Problema do Caixeiro Alugador

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

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

Resumo

No clássico Problema do Caixeiro Viajante (TSP), queremos encontrar uma rota que passa por um conjunto de n cidades e que minimize a distância total percorrida. Uma generalização conhecida é o chamada Problema do Caixeiro Alugador, em que a rota pode ser percorrida alugando-se um subconjunto de veículos. Cada veículo tem uma função de distância distinta, mas para cada veículo alugado, paga-se uma taxa de retorno g ≥ 0. O objetivo é minimizar a soma das distâncias percorridas mais as taxas de retorno. Neste trabalho, apresentamos uma O(log n)-aproximação para o problema. Esse algoritmo é assintoticamente ótimo já que também mostramos que não há aproximação com fator o(log n), a não ser que P = NP.

Referências

da Silva, A. R. V. and Ochi, L. S. (2016). An efficient hybrid algorithm for the traveling car renter problem. Expert Systems with Applications, 64:132 – 140.

Dias, S. S., Ochi, L. S., Machado, V. M. C., Simonetti, L. G., and da Silva, A. R. V. (2016). Uma heurística baseada em ils para o problema do caixeiro alugador. In Anais do XLVIII SBPO Simpósio Brasileiro de Pesquisa Operacional.

Garg, N., Konjevod, G., and Ravi, R. (2000). A polylogarithmic approximation algorithm for the group steiner tree problem. Journal of Algorithms, 37(1):66 – 84.

Goldbarg, M. C., Asconavieta, P. H., and Goldbarg, E. F. G. (2012). Memetic algorithm for the traveling car renter problem: an experimental investigation. Memetic Computing, 4(2):89–108.

Guha, S. and Khuller, S. (1999). Greedy Strikes Back: Improved Facility Location Algorithms. Journal of Algorithms, 31(1):228–248.

Rios, B. H. O., Goldbarg, E. F. G., and Quesquén, G. Y. O. (2017). A hybrid metaheuristic using a corrected formulation for the traveling car renter salesman problem. In 2017 IEEE Congress on Evolutionary Computation (CEC), pages 2308–2314.