Research on Strategy for Stochastic Blockage Recovery time in Canadian Travel Problem Based on Exponential Distribution
Ligang Zhou · Shuxue de shijian yu renshi · 2011
The online Canadian Traveler Problem(CTP) is considered for the case when the blockages occur one by one without any predictable information.From the online point of view,the waiting strategy and the greedy strategy are proposed.The competitive ratios of the two strategies are given based on the assumption that each blockage recovery time satisfies exponential distribution.The performance of these two strategies are analyzed and compared in the paper.