An Optimal Approximation for the Renter Traveling Salesman Problem

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

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

Abstract

In the classical Traveling Salesman Problem (TSP), we want to find a route that visits each of n cities, minimizing the total traveled distance. An often considered generalization is the Traveling Car Renter Problem, in which the route is traveled by renting a set of cars. Every car has a distinct distance function, but each rented car incurs the payment of a return fee g ≥ 0. The objective is to minimize the sum of traveled distances plus return fees. In this work, we present a O(log n)-approximation for the problem. This algorithm is asymptotically optimal, since we show that there is no approximation with factor o(log n), unless P = NP.

References

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.