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

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

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.

Detaljer

Författare
  • Björn Brodén
  • M Hammar
  • BJ Nilsson
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Sidor (från-till)299-319
TidskriftAlgorithmica
Volym39
Utgivningsnummer4
StatusPublished - 2004
PublikationskategoriForskning
Peer review utfördJa