论文部分内容阅读
C.H.Papadimiteiou和M.Yannakadis提出了加拿大旅行者问题(Canadian Traveler Problem,简称CTP)。为了制定行走策略,Manasse S M和David S B将在线问题和竞争算法运用到此问题上,使该策略得到的解离最优方案给出的解总在一定的比例之内,但以上的研究都与实际问题有一定的差距,于是可恢复加拿大旅行者问题提出,许多学者对此问题进行了进一步的研究,但在这些研究中,在线的方法都是假设旅行者在到达堵塞发生地时可获得关于堵塞恢复时间的确定信息,这个假设与现实差异较大,如何使得堵塞恢复时间更接近于现实是有待研究的问题。 本文将不确定性思想和方法引入其中,主要针对堵塞恢复时间不确定的旅行者问题进行了分析和研究,主要工作概括如下: 第一章首先介绍了加拿大旅行者问题的背景,模型,策略和竞争性能比的基本概念,然后阐述了堵塞可恢复和堵塞不可恢复的加拿大旅行者问题的相关研究成果,最后对区间数的概念和相关性质进行了总结。 第二章在堵塞可恢复且堵塞恢复时间随机的基础上,提出了堵塞恢复时间分别服从正态分布和指数分布的旅行者问题,给出了堵塞恢复时间服从不同分布时采取等待策略和贪婪策略下的竞争性能比的具体表达式,通过分析比较从而确定出最优行走方案。 第三章在堵塞可恢复且堵塞恢复时间不确定的基础上,引入了模糊的思想,提出了堵塞恢复时间为区间数的旅行者问题,给出了旅行者在等待策略,迂回策略,混合策略下的竞争性能比,并对相应的问题进行了案例分析验证了采取混合策略优于单独采用等待策略或迂回策略的结论,从而确定出最优行走方案。 第四章总结了全文的工作,并对堵塞恢复时间不确定的旅行者问题的研究前景作了展望。