Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Online and offline algorithms for the time-dependent TSP with time zones

Brodén, Björn LU ; Hammar, M and Nilsson, BJ (2004) In Algorithmica 39(4). p.299-319
Abstract
The time-dependent traveling salesman problem (TDTSP) is a variant of TSP with time-dependent edge costs. We study some restrictions of TDTSP where the number of edge cost changes are limited. We find competitive ratios for online versions of TDTSP. From these we derive polynomial time approximation algorithms for graphs with edge costs one and two. In addition, we present an approximation algorithm for the orienteering problem with edge costs one and two.
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
time dependencies, online algorithms, the traveling salesman problem, the orienteering problem
in
Algorithmica
volume
39
issue
4
pages
299 - 319
publisher
Springer
external identifiers
  • wos:000221367200003
  • scopus:21044439691
ISSN
0178-4617
DOI
10.1007/s00453-004-1088-z
language
English
LU publication?
yes
id
30682cd4-e6b9-4ee4-a1bf-ab3f882b2376 (old id 279239)
date added to LUP
2016-04-01 11:42:08
date last changed
2022-01-26 08:56:07
@article{30682cd4-e6b9-4ee4-a1bf-ab3f882b2376,
  abstract     = {{The time-dependent traveling salesman problem (TDTSP) is a variant of TSP with time-dependent edge costs. We study some restrictions of TDTSP where the number of edge cost changes are limited. We find competitive ratios for online versions of TDTSP. From these we derive polynomial time approximation algorithms for graphs with edge costs one and two. In addition, we present an approximation algorithm for the orienteering problem with edge costs one and two.}},
  author       = {{Brodén, Björn and Hammar, M and Nilsson, BJ}},
  issn         = {{0178-4617}},
  keywords     = {{time dependencies; online algorithms; the traveling salesman problem; the orienteering problem}},
  language     = {{eng}},
  number       = {{4}},
  pages        = {{299--319}},
  publisher    = {{Springer}},
  series       = {{Algorithmica}},
  title        = {{Online and offline algorithms for the time-dependent TSP with time zones}},
  url          = {{http://dx.doi.org/10.1007/s00453-004-1088-z}},
  doi          = {{10.1007/s00453-004-1088-z}},
  volume       = {{39}},
  year         = {{2004}},
}