Template-Type: ReDIF-Paper 1.0
Author-Name: Srour, F.J.
Author-Name-Last: Srour
Author-Name-First: Jordan
Author-Name: Zuidwijk, R.A.
Author-Name-Last: Zuidwijk
Author-Name-First: Rob
Title: How Much is Location Information Worth? A Competitive Analysis of the Online Traveling Salesman Problem with Two Disclosure Dates
Abstract: In this paper we derive the worst-case ratio of an online algorithm for the Traveling Salesman Problem (TSP) with two disclosure dates. This problem, a variant of the online TSP with release dates, is characterized by the disclosure of a job’s location at one point in time followed by the disclosure of that job’s release date at a later point in time. We present an online algorithm for this problem restricted to the positive real number line. We then derive the worst-case ratio of our algorithm and show that it is best-possible in two contexts – the first, one in which the amount of time between the disclosure events and release time are fixed and equal for all jobs; and a second in which the time between disclosure events varies for each job. We conclude that the value of advanced information can be attributed to the location information alone – yielding an optimal solution in favorable instances.
Creation-Date: 2008-11-13
File-URL: https://repub.eur.nl/pub/13837/ERS-2008-075-LIS.pdf
File-Format: application/pdf
Series: RePEc:ems:eureri
Number: ERS-2008-075-LIS
Classification-JEL: C69, M, M11, R4
Keywords: advanced information, competitive ratio, online routing, traveling salesman, worst-case ratio
Handle: RePEc:ems:eureri:13837