基于指数分布的可恢复加拿大旅行者问题的策略研究

Research on Strategy for Stochastic Blockage Recovery time in Canadian Travel Problem Based on Exponential Distribution

针对旅行者在行走过程中遇到的某一或一系列无法预知堵塞事件的加拿大旅行者问题,考虑每个堵塞恢复时间是一个相互独立随机变量且服从指数分布的情形,从在线问题与竞争策略的角度,给出了等待策略和贪婪策略以及相应策略下的竞争比,并对两种策略的执行效果进行了分析和比较.

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.