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

Björn Brodén; M Hammar; BJ Nilsson

doi:10.1007/s00453-004-1088-z

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

Björn Brodén, M Hammar, BJ Nilsson

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	299-319
Journal	Algorithmica
Volume	39
Issue number	4
DOIs	https://doi.org/10.1007/s00453-004-1088-z
Publication status	Published - 2004

Subject classification (UKÄ)

Computer Sciences

Free keywords

time dependencies
online algorithms
the traveling salesman problem
the orienteering problem

Access to Document

10.1007/s00453-004-1088-z

Cite this

@article{30682cd4e6b94ee4a1bfab3f882b2376,

title = "Online and offline algorithms for the time-dependent TSP with time zones",

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.",

keywords = "time dependencies, online algorithms, the traveling salesman problem, the orienteering problem",

author = "Bj{\"o}rn Brod{\'e}n and M Hammar and BJ Nilsson",

year = "2004",

doi = "10.1007/s00453-004-1088-z",

language = "English",

volume = "39",

pages = "299--319",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

number = "4",

}

TY - JOUR

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

AU - Brodén, Björn

AU - Hammar, M

AU - Nilsson, BJ

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - time dependencies

KW - online algorithms

KW - the traveling salesman problem

KW - the orienteering problem

UR - https://www.scopus.com/pages/publications/21044439691

U2 - 10.1007/s00453-004-1088-z

DO - 10.1007/s00453-004-1088-z

M3 - Article

SN - 0178-4617

VL - 39

SP - 299

EP - 319

JO - Algorithmica

JF - Algorithmica

IS - 4

ER -

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

Abstract

Subject classification (UKÄ)

Free keywords

Access to Document

Other files and links

Fingerprint

Cite this