License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09261.19
URN: urn:nbn:de:0030-drops-21720
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2172/
Go to the corresponding Portal

Jaillet, Patrick ; Lu, Xin

Online Traveling Salesman Problems with Flexibility

pdf-format:
09261.JailletPatrick.ExtAbstract.2172.pdf (0.1 MB)

Abstract

The Traveling Salesman Problem (TSP) is a well-known combinatorial
optimization problem. We are concerned here with online versions of a
generalization of the TSP on metric spaces where the server doesn't have
to accept all requests. Associated with each request (to visit a point in the
metric space) is a penalty (incurred if the request is rejected). Requests
are revealed over time to a server, initially at a given origin, who must
decide which requests to serve in order to minimize the time to serve all
accepted requests plus the sum of the penalties associated with the
rejected requests.

In a first online version of this problem (basic version), we assume that the
server's decision to accept or reject a request can be made any time after
its release date. In a second online version of this problem (real-time
version), we assume that the server's decision to accept or reject a
request must be made exactly at its release date.

After reviewing prior results on the online TSP, we first provide an optimal
2-competitive online algorithm for the basic version of the problem in a
general metric space, improving prior results from the literature. We then
consider the real-time version of the problem and show that there can't be
any finite $c$-competitive online algorithm in a general metric space.

BibTeX - Entry

@InProceedings{jaillet_et_al:DagSemProc.09261.19,
  author =	{Jaillet, Patrick and Lu, Xin},
  title =	{{Online Traveling Salesman Problems with Flexibility}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2009/2172},
  URN =		{urn:nbn:de:0030-drops-21720},
  doi =		{10.4230/DagSemProc.09261.19},
  annote =	{Keywords: Online TSP, service flexibility, rejection options}
}

Keywords: Online TSP, service flexibility, rejection options
Collection: 09261 - Models and Algorithms for Optimization in Logistics
Issue Date: 2009
Date of publication: 02.10.2009

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