摘要
针对旅行者在行走过程中遇到的某一或一系列无法预知堵塞事件的加拿大旅行者问题,考虑每个堵塞恢复时间是一个相互独立随机变量的情形,从在线问题与竞争策略的角度,给出了每个堵塞恢复时间都为正态分布下的等待策略和贪婪策略以及相应策略下的竞争比,并对两种策略的执行效果进行了分析和比较。
The online Canadian Traveler Problem（CTP）is considered for the case when the traveler meets some unexpected accident or a series of unexpected accidents during the travel process.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 is a normal distribution.The performance of these two strategies are analyzed and compared in the paper.
出处
《运筹与管理》
CSCD
北大核心
2010年第3期30-34,共5页
Operations Research and Management Science
基金
国家自然科学基金资助项目资助(70571001)
安徽省优秀青年科技基金资助项目资助(08040106835)
安徽省自然科学基金资助项目资助(070416245)
安徽高等学校省级教学研究项目资助(2007jyxm177)
安徽大学人才队伍建设项目
安徽省高校青年教师资助项目资助(2007jq1017
2008jq1128)
关键词
决策分析
随机
竞争比
可恢复堵塞
在线加拿大旅行者问题
decision making
stochastic
competitive ratio
recoverable blockage
online Canadian traveler problem
