Online and offline algorithms for the time-dependent TSP with time zones
(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:
https://lup.lub.lu.se/record/279239
- author
- Brodén, Björn LU ; Hammar, M and Nilsson, BJ
- organization
- publishing date
- 2004
- 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}}, }