License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2019.14
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11426/
Go to the corresponding OASIcs Volume Portal

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

An Asymptotically Optimal Approximation Algorithm for the Travelling Car Renter Problem

pdf-format:
OASIcs-ATMOS-2019-14.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{pedrosa_et_al:OASIcs:2019:11426,
  author =	{Lehilton L. C. Pedrosa and Greis Y. O. Quesqu{\'e}n and Rafael C. S. Schouery},
  title =	{{An Asymptotically Optimal Approximation Algorithm for the Travelling Car Renter Problem}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{14:1--14:15},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Valentina Cacchiani and Alberto Marchetti-Spaccamela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11426},
  doi =		{10.4230/OASIcs.ATMOS.2019.14},
  annote =	{Keywords: Approximation Algorithm, Travelling Car Renter Problem, LP-rounding, Separation Problem}
}

Keywords: Approximation Algorithm, Travelling Car Renter Problem, LP-rounding, Separation Problem
Collection: 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)
Issue Date: 2019
Date of publication: 15.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI