Document Open Access Logo

An Asymptotically Optimal Approximation Algorithm for the Travelling Car Renter Problem

Authors Lehilton L. C. Pedrosa , Greis Y. O. Quesquén , Rafael C. S. Schouery

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2019.14.pdf
  • Filesize: 442 kB
  • 15 pages

Document Identifiers

Author Details

Lehilton L. C. Pedrosa
  • Institute of Computing, University of Campinas, SP, Brazil
Greis Y. O. Quesquén
  • Institute of Computing, University of Campinas, SP, Brazil
Rafael C. S. Schouery
  • Institute of Computing, University of Campinas, SP, Brazil

Funding

Supported by grant #2015/11937-9, São Paulo Research Foundation (FAPESP), and grants #425340/2016-3, #313026/2017-3, #308689/2017-8, #425806/2018-9, #422829/2018-8, National Council for Scientific and Technological Development (CNPq).

Cite As Get BibTex

Lehilton L. C. Pedrosa, Greis Y. O. Quesquén, and Rafael C. S. Schouery. An Asymptotically Optimal Approximation Algorithm for the Travelling Car Renter Problem. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.ATMOS.2019.14

Abstract

In the classical Travelling Salesman Problem (TSP), one wants to find a route that visits a set of n cities, such that the total travelled distance is minimum. An often considered generalization is the Travelling Car Renter Problem (CaRS), in which the route is travelled by renting a set of cars and the cost to travel between two given cities depends on the car that is used. The car renter may choose to swap vehicles at any city, but must pay a fee to return the car to its pickup location. This problem appears in logistics and urban transportation when the vehicles can be provided by multiple companies, such as in the tourism sector. In this paper, we consider the case in which the return fee is some fixed number g >= 0, which we call the Uniform CaRS (UCaRS). We show that, already for this version, there is no o(log n)-approximation algorithm unless P = NP. The main contribution is an O(log n)-approximation algorithm for the problem, which is based on the randomized rounding of an exponentially large LP-relaxation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Routing and network design problems
Keywords
  • Approximation Algorithm
  • Travelling Car Renter Problem
  • LP-rounding
  • Separation Problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Fleura Bardhi and Giana M. Eckhardt. Access-Based Consumption: The Case of Car Sharing. Journal of Consumer Research, 39(4):881-898, December 2012. URL: http://dx.doi.org/10.1086/666376.
  2. John Black. Urban Transport Planning. Routledge, May 2018. URL: http://dx.doi.org/10.4324/9781351068604.
  3. Chandra Chekuri, Guy Even, and Guy Kortsarz. A greedy approximation algorithm for the group Steiner problem. Discrete Applied Mathematics, 154(1):15-34, January 2006. URL: http://dx.doi.org/10.1016/j.dam.2005.07.010.
  4. V. Chvatal. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research, 4(3):233-235, 1979. URL: http://dx.doi.org/10.1287/moor.4.3.233.
  5. André Renato Villela da Silva and Luiz Satoru Ochi. An efficient hybrid algorithm for the Traveling Car Renter Problem. Expert Systems with Applications, 64:132-140, December 2016. URL: http://dx.doi.org/10.1016/j.eswa.2016.07.038.
  6. André Renato Villela da Silva and Luiz Satoru Ochi. Um Algoritmo Evolutivo para o Problema do Caixeiro Alugador. In Proceeding Series of the Brazilian Society of Applied and Computational Mathematics, volume 5, 2017. URL: http://dx.doi.org/10.5540/03.2017.005.01.0460.
  7. Kenan Degirmenci and Michael H. Breitner. Carsharing: A literature review and a perspective for information systems research. In Lars Beckmann, editor, Multikonferenz Wirtschaftsinformatik (MKWI), Paderborn, Germany, February 2014. URL: https://eprints.qut.edu.au/105684/.
  8. Sávio S. Dias, Luiz Satoru Ochi, Victor M. C. Machado, Luidi Gelabert Simonetti, and André Renato Villela da Silva. Uma Heurística Baseada em ILS Para o Problema do Caixeiro Alugador. In Anais do XLVIII SBPO Simpósio Brasileiro de Pesquisa Operacional, pages 1625-1636, 2016. Google Scholar
  9. Irit Dinur and David Steurer. Analytical Approach to Parallel Repetition. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 624-633, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2591796.2591884.
  10. Jittat Fakcharoenphol, Satish Rao, Satish Rao, and Kunal Talwar. A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 448-455, New York, NY, USA, 2003. ACM. URL: http://dx.doi.org/10.1145/780542.780608.
  11. Denis Felipe, Elizabeth Ferreira Gouvêa Goldbarg, and Marco César Goldbarg. Scientific algorithms for the Car Renter Salesman Problem. In 2014 IEEE Congress on Evolutionary Computation (CEC), pages 873-879. IEEE, July 2014. URL: http://dx.doi.org/10.1109/cec.2014.6900556.
  12. David Foot. Operational Urban Models. Routledge, October 2017. URL: http://dx.doi.org/10.4324/9781315105307.
  13. Naveen Garg, Goran Konjevod, and R. Ravi. A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. Journal of Algorithms, 37(1):66-84, October 2000. URL: http://dx.doi.org/10.1006/jagm.2000.1096.
  14. Marco César Goldbarg, Elizabeth Ferreira Gouvêa Goldbarg, Henrique P. L. Luna, Matheus da S. Menezes, and Lucas Corrales. Integer programming models and linearizations for the traveling car renter problem. Optimization Letters, 12(4):743-761, April 2017. URL: http://dx.doi.org/10.1007/s11590-017-1138-5.
  15. Marco César Goldbarg, Elizabeth Ferreira Gouvêa Goldbarg, Matheus da S. Menezes, and Henrique P. L. Luna. Quota traveling car renter problem: Model and evolutionary algorithm. Information Sciences, 367-368:232-245, November 2016. URL: http://dx.doi.org/10.1016/j.ins.2016.05.027.
  16. Marco César Goldbarg, Elizabeth Ferreira Gouvêa Goldbarg, Paulo Henrique Asconavieta da Silva, Matheus da S. Menezes, and Henrique P. L. Luna. A transgenetic algorithm applied to the Traveling Car Renter Problem. Expert Systems with Applications, 40(16):6298-6310, November 2013. URL: http://dx.doi.org/10.1016/j.eswa.2013.05.072.
  17. Marco César Goldbarg, Paulo Henrique Asconavieta da Silva, and Elizabeth Ferreira Gouvêa Goldbarg. Memetic algorithm for the Traveling Car Renter Problem: An experimental investigation. Memetic Computing, 4(2):89-108, September 2011. URL: http://dx.doi.org/10.1007/s12293-011-0070-y.
  18. M. Grazia Speranza. Trends in transportation and logistics. European Journal of Operational Research, 264(3):830-836, February 2018. URL: http://dx.doi.org/10.1016/j.ejor.2016.08.032.
  19. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. URL: http://dx.doi.org/10.1007/978-3-642-97881-4.
  20. Sudipto Guha and Samir Khuller. Greedy Strikes Back: Improved Facility Location Algorithms. Journal of Algorithms, 31(1):228-248, April 1999. URL: http://dx.doi.org/10.1006/jagm.1998.0993.
  21. Eran Halperin and Robert Krauthgamer. Polylogarithmic Inapproximability. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 585-594, New York, NY, USA, 2003. ACM. URL: http://dx.doi.org/10.1145/780542.780628.
  22. David S. Johnson, Maria Minkoff, and Steven Phillips. The Prize Collecting Steiner Tree Problem: Theory and Practice. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '00, pages 760-769, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=338219.338637.
  23. Xin Luan, Lin Cheng, Yang Zhou, and Fang Tang. Strategies of Car-Sharing Promotion in Real Market. In 2018 3superscriptrd IEEE International Conference on Intelligent Transportation Engineering (ICITE), pages 159-163. IEEE, September 2018. URL: http://dx.doi.org/10.1109/icite.2018.8492652.
  24. Matheus da S. Menezes. O problema do Caixeiro alugador com coleta de prêmios: Um estudo algorítmico. PhD thesis, Universidade Federal do Rio Grande do Norte, 2014. Google Scholar
  25. Brenner Humberto Ojeda Rios. Hibridização de meta-heurí stí cas com métodos baseados em programação linear para o problema do caixeiro alugador. Master’s thesis, Universidade Federal do Rio Grande do Norte, 2017. Google Scholar
  26. Brenner Humberto Ojeda Rios, Elizabeth Ferreira Gouvêa Goldbarg, and Greis Yvet Oropeza Quesquen. 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. IEEE, June 2017. URL: http://dx.doi.org/10.1109/cec.2017.7969584.
  27. Philipp Rode, Graham Floater, Nikolas Thomopoulos, James Docherty, Peter Schwinger, Anjali Mahendra, and Wanli Fang. Accessibility in Cities: Transport and Urban Form. In Disrupting Mobility, pages 239-273. Springer International Publishing, 2017. URL: http://dx.doi.org/10.1007/978-3-319-51602-8_15.
  28. Shmuel Safra and Oded Schwartz. On the complexity of approximating tsp with neighborhoods and related problems. Computational Complexity, 14(4):281-307, March 2006. URL: http://dx.doi.org/10.1007/s00037-005-0200-3.
  29. Paulo Henrique Asconavieta da Silva. O problema do caixeiro viajante alugador: Um estudo algorítmico. PhD thesis, Universidade Federal do Rio Grande do Norte, 2011. Google Scholar
  30. Paulo Henrique Asconavieta da Silva, Marco César Goldbarg, and Elizabeth Ferreira Gouvêa Goldbarg. The car renter salesman problem: An algorithmic study. In Anais do XLII SBPO Simpósio Brasileiro de Pesquisa Operacional, 2010. Google Scholar
  31. Paulo Henrique Asconavieta da Silva, Marco César Goldbarg, and Elizabeth Ferreira Gouvêa Goldbarg. Evolutionary algorithm for the Car Renter Salesman. In 2011 IEEE Congress of Evolutionary Computation (CEC), pages 593-600. IEEE, June 2011. URL: http://dx.doi.org/10.1109/cec.2011.5949673.
  32. Vijay V. Vazirani. Approximation Algorithms. Springer, Berlin, 2001. URL: http://dx.doi.org/10.1007/978-3-662-04565-7.
  33. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, Cambridge, 2011. URL: http://dx.doi.org/10.1017/CBO9780511921735.
  34. Henk Zijm and Matthias Klumpp. Logistics and Supply Chain Management: Developments and Trends. In Logistics and Supply Chain Innovation, pages 1-20. Springer International Publishing, August 2015. URL: http://dx.doi.org/10.1007/978-3-319-22288-2_1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact