Paper Info
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.
Year
DOI
Venue
2004
https://doi.org/10.1007/s00453-004-1088-z
Algorithmica
Keywords
Field
DocType
Online algorithms,The traveling salesman problem,Time dependencies,The orienteering problem
Discrete mathematics,Online algorithm,Theoretical computer science,Travelling salesman problem,Online and offline,Mathematics
Journal
Volume
Issue
ISSN
39
4
0178-4617
Citations 
PageRank 
References 
2
0.43
9
Authors
3
Name
Order
Citations
PageRank
Björn Brodén161.89
Mikael Hammar216316.22
Brengt J. Nilsson320.43