The canadian traveller problem and its competitive analysis

Yinfeng Xu (), Maolin Hu (), Bing Su (), Binhai Zhu () and Zhijun Zhu ()
Additional contact information
Yinfeng Xu: Xi’an Jiaotong University
Maolin Hu: Guyuan Teachers College
Bing Su: Xi’an Jiaotong University
Binhai Zhu: Montana State University
Zhijun Zhu: Xi’an Jiaotong University

Journal of Combinatorial Optimization, 2009, vol. 18, issue 2, No 6, 195-205

Abstract: Abstract From the online point of view, we study the Canadian Traveller Problem (CTP), in which the traveller knows in advance the structure of the graph and the costs of all edges. However, some edges may fail and the traveller only observes that upon reaching an adjacent vertex of the blocked edge. The goal is to find the least-cost route from the source O to the destination D, more precisely, to find an adaptive strategy minimizing the competitive ratio, which compares the performance of this strategy with that of a hypothetical offline algorithm that knows the entire topology in advance. In this paper, we present two adaptive strategies—a greedy or myopic strategy and a comparison strategy combining the greedy strategy and the reposition strategy in which the traveller backtracks to the source every time when he/she sees a failed edge. We prove tight competitive ratios of 2 k+1−1 and 2k+1 respectively for the two strategies, where k is the number of failed edges in the graph. Finally, we propose an explanation of why the greedy strategy and the comparison strategy are usually preferred by drivers in an urban traffic environment, based on an argument related to the length of the second-shortest path in a grid graph.

Keywords: Online algorithms; Competitive analysis; Greedy strategy; Comparison strategy (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-008-9156-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:18:y:2009:i:2:d:10.1007_s10878-008-9156-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-008-9156-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().