| 摘要 | 第3-5页 |
| ABSTRACT | 第5-6页 |
| 1 绪论 | 第11-24页 |
| 1.1 研究背景及意义 | 第11-13页 |
| 1.2 国内外相关研究综述 | 第13-19页 |
| 1.2.1 等待时间的感知 | 第13-14页 |
| 1.2.2 旅行商问题及其扩展研究 | 第14-16页 |
| 1.2.3 在线旅行商问题及其扩展研究 | 第16-19页 |
| 1.3 相关理论综述 | 第19-21页 |
| 1.3.1 在线优化与竞争分析 | 第19-20页 |
| 1.3.2 竞争分析中的博弈 | 第20-21页 |
| 1.4 研究内容及论文框架 | 第21-24页 |
| 2 基于预知信息的占线Nomadic TSP问题 | 第24-37页 |
| 2.1 问题描述与基本定义 | 第24-25页 |
| 2.2 基于预知信息的占线Nomadic TSP问题的下界 | 第25-27页 |
| 2.3 直线上基于预知信息的占线Nomadic TSP问题 | 第27-32页 |
| 2.3.1 ENO-dd算法性质分析 | 第27-30页 |
| 2.3.2 ENO-dd算法的竞争比 | 第30-32页 |
| 2.4 一般网络图上基于预知信息的占线Nomadic TSP问题 | 第32-34页 |
| 2.5 预知信息对竞争比的影响 | 第34-35页 |
| 2.6 本章小结 | 第35-37页 |
| 3 基于服务时间约束和服务选择的在线旅行商问题 | 第37-59页 |
| 3.1 问题描述 | 第37-38页 |
| 3.2 问题的下界 | 第38-42页 |
| 3.2.1 确定性在线算法的下界 | 第38-41页 |
| 3.2.2 随机性在线算法的下界 | 第41-42页 |
| 3.3 线段上具有服务选择和时间约束的在线旅行商问题 | 第42-57页 |
| 3.3.1 在线段网络上的下界 | 第42-48页 |
| 3.3.2 Conjecture算法及其竞争比 | 第48-57页 |
| 3.4 结果比较分析 | 第57-58页 |
| 3.5 本章小结 | 第58-59页 |
| 4 基于预知信息和服务时间约束的在线旅行商问题 | 第59-74页 |
| 4.1 问题描述 | 第59页 |
| 4.2 问题的下界 | 第59-63页 |
| 4.3 线段上的具有预知信息和服务时间约束的在线旅行商问题 | 第63-66页 |
| 4.3.1 问题在线段网络上的下界 | 第63-65页 |
| 4.3.2 RePlan算法及其竞争比 | 第65-66页 |
| 4.4 均匀度量空间上基于预知信息和时间约束的在线旅行商问题 | 第66-71页 |
| 4.4.1 问题在均匀度量空间上的下界 | 第67-69页 |
| 4.4.2 贪婪算法及其竞争比 | 第69-71页 |
| 4.5 结果分析比较 | 第71-73页 |
| 4.6 本章小结 | 第73-74页 |
| 5 基于服务时间约束的在线Prize-Collecting旅行商问题 | 第74-98页 |
| 5.1 问题描述 | 第74-75页 |
| 5.2 问题的下界 | 第75-77页 |
| 5.3 线段网络上基于服务时间约束的在线Prize-Collecting旅行商问题 | 第77-90页 |
| 5.3.1 问题在线段网络上的下界 | 第78-83页 |
| 5.3.2 CMC（Conjecture, Move and Collect）算法及其竞争比 | 第83-90页 |
| 5.4 均匀度量空间上基于服务时间约束的在线Prize-Collecting旅行商问题 | 第90-96页 |
| 5.4.1 问题的下界 | 第91-95页 |
| 5.4.2 CGA（Constrained Greedy Algorithm）算法及其竞争比 | 第95-96页 |
| 5.5 结果比较与分析 | 第96-97页 |
| 5.6 本章小结 | 第97-98页 |
| 6 结论与展望 | 第98-101页 |
| 6.1 研究结论 | 第98-99页 |
| 6.2 研究展望 | 第99-101页 |
| 致谢 | 第101-102页 |
| 参考文献 | 第102-107页 |
| 攻读学位期间取得的研究成果 | 第107页 |
| 攻读学位期间参加科研项目 | 第107页 |
| 攻读学位期间获得奖励 | 第107-109页 |
