TY - GEN
T1 - A risk-reward competitive analysis for the recoverable Canadian traveller problem
AU - Su, Bing
AU - Xu, Yinfeng
AU - Xiao, Peng
AU - Tian, Lei
PY - 2008
Y1 - 2008
N2 - From the online point of view, we study the Recoverable Canadian Traveller Problem (Recoverable-CTP) in a special network, in which the traveller knows in advance the structure of the network and the travel time of each edge. However, some edges may be blocked and the traveller only observes that upon reaching the vertex of the blocked edge, and the blocked edge may be reopened but the traveller doesn't know its recovery time. The goal is to find a least-cost route from the origin node to the destination node, more precisely, to find an adaptive strategy minimizing the ratio of traversed time to the travel time of the optimal offline shortest path (where all blocked edges and their recovery time are known in advance). We present an optimal online strategy - a comparison strategy and prove its competitive ratio. Moreover, with the different forecasts of the recovery time, some online strategies are given under the risk-reward framework, and the rewards and the risks of the different strategies are analysed.
AB - From the online point of view, we study the Recoverable Canadian Traveller Problem (Recoverable-CTP) in a special network, in which the traveller knows in advance the structure of the network and the travel time of each edge. However, some edges may be blocked and the traveller only observes that upon reaching the vertex of the blocked edge, and the blocked edge may be reopened but the traveller doesn't know its recovery time. The goal is to find a least-cost route from the origin node to the destination node, more precisely, to find an adaptive strategy minimizing the ratio of traversed time to the travel time of the optimal offline shortest path (where all blocked edges and their recovery time are known in advance). We present an optimal online strategy - a comparison strategy and prove its competitive ratio. Moreover, with the different forecasts of the recovery time, some online strategies are given under the risk-reward framework, and the rewards and the risks of the different strategies are analysed.
KW - Comparison strategy
KW - Competitive analysis
KW - Recoverable-CTP
KW - Risk-reward model
UR - https://www.scopus.com/pages/publications/51849094959
U2 - 10.1007/978-3-540-85097-7_39
DO - 10.1007/978-3-540-85097-7_39
M3 - 会议稿件
AN - SCOPUS:51849094959
SN - 3540850961
SN - 9783540850960
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 417
EP - 426
BT - Combinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings
T2 - 2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008
Y2 - 21 August 2008 through 24 August 2008
ER -