不确定环境下在线旅行者问题策略研究

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 加拿大旅行者问题

1.2堵塞不可恢复的加拿大旅行者问题[31]

1.3 占线可恢复的加拿大旅行者问题

1.4区间数的定义和性质

1.5本文研究工作概述

第二章 随机环境下堵塞可恢复的旅行者问题策略研究

2.1引 言

2.2基本定义和问题描述

2.3堵塞恢复时间服从正态分布的策略分析

2.4堵塞恢复时间服从指数分布的策略分析

2.5案例分析

第三章 堵塞恢复时间为区间数的旅行者问题策略研究

3.1 堵塞恢复时间不确定

3.2 堵塞恢复时间为区间数的策略分析

3.3不同策略下的竞争性能讨论

3.4案例分析

第四章小结与展望

参考文献

致谢

攻读硕士学位期间的相关工作情况