学位论文 > 优秀研究生学位论文题录展示

时变网络乡村邮路问题割平面及蚁群算法研究

作　者: 曲宏磊
导　师: 谭国真
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 乡村邮路问题 割平面算法 线性整数规划 蚁群算法 时变网络
分类号: O221.4
类　型: 硕士论文
年　份: 2011年
下　载: 47次
引　用: 0次
阅　读: 论文下载
 

内容摘要


中国邮路问题是弧路由问题,是图论中的经典问题,作为中国邮路问题的变体,乡村邮路问题也得到了广泛的研究。该问题在街道清扫,垃圾回收,信件分发路线,机器人检测路线路线,校车接送线路以及软件测试序列优化等领域有着重要的应用,许多年来一直吸引着众多学者的研究。近年来,随着智能交通,混合系统测试和物联网技术等复杂系统的发展,人们对系统的实时性越来越重视。但传统的中国邮路问题都是在静态网络中研究,假设网络上的权值是静态不变的,这往往和实际情况不符合。例如交通情况随上下班人流高峰期的产生而变化,那么旅行时间也就应该随之变化。所以时间依赖的中国邮路问题的研究越来越显得紧迫和意义重大。与时间有关的弧路由问题包括时间窗约束的弧路问题、服务代价时间依赖的弧路由问题和旅行时间时间依赖的弧路由问题。其中前两种之前有过研究,但旅行时间时间依赖的中国邮路问题,由问题的复杂度,建模的困难,所以少有人研究。本实验室之前研究过时间依赖的中国邮路问题,但对其变体乡村邮路问题还没有研究；本文将致力于中国邮路问题的变种时间依赖乡村邮路问题的研究。本文首先对传统的中国邮路问题和乡村邮路问题的研究进行了总结,并介绍了有关带有时间因素的中国邮路问题的研究现状。然后建立了一个整数规划模型：弧-路径模性。由于整数规划问题规模大,难于求解,本文设计了一个启发式割平面算法。论文提供了一些割平面不等式,实验结果证明算法能得到满意的解。论文考虑到割平面时间消耗很大,提供了一个元启发式算法-蚁群算法求解时间依赖的乡村邮路问题,实验证明蚁群算法能够很好的收敛于最优解.相对于随机初始化信息素,利用线性规划的线性松弛解的情况初始化信息素更倾向收敛于最优解。

全文目录


摘要  4-5
Abstract  5-9
1 绪论  9-15
  1.1 研究背景及意义  9-10
  1.2 研究现状  10-13
    1.2.1 传统乡村中国邮路问题和中国邮路问题  10-12
    1.2.2 时间相关的弧路由问题  12-13
  1.3 本文的研究方法及主要工作  13-14
  1.4 本文的组织结构  14-15
2 乡村邮路问题和中国邮路问题  15-26
  2.1 中国邮路问题介绍  15-18
    2.1.1 无向中国邮路问题  15-17
    2.1.2 有向中国邮路问题  17-18
  2.2 乡村中国邮路问题  18-22
    2.2.1 无向乡村邮路问题  18-21
    2.2.2 有向乡村邮路问题  21-22
    2.2.3 堆垛机问题(SCP)  22
  2.3 带有时间因素的弧邮路问题  22-26
    2.3.1 带时间窗的弧邮路问题  23
    2.3.2 服务代价时间依赖弧邮路问题  23-24
    2.3.3 旅行时间时间依赖弧邮路问题  24-26
3 割平面方法求解时间依赖乡村邮路问题  26-41
  3.1 时间依赖乡村邮路问题定义  26
  3.2 TDRPP整数规划模型  26-35
    3.2.1 建模思想  26-28
    3.2.2 变量说明  28
    3.2.3 TDRPP的整数规划模型  28-31
    3.2.4 TDRPP模型线性化  31-32
    3.2.5 更有效的时间相关不等式  32-34
    3.2.6 极大面不等式  34-35
  3.3 基于TDRPP模型的割平面方法  35-41
    3.3.1 算法设计  35-37
    3.3.2 实验结果  37-41
4 蚁群算法求解TDRPP、TDCPP问题  41-52
  4.1 蚁群算法介绍  41-42
    4.1.1 基本蚁群算法  41-42
    4.1.2 最大最小蚁群算法(MMAS)  42
  4.2 蚁群算法求解TDCPP问题  42-47
    4.2.1 问题介绍及圈向量模型回顾  42-43
    4.2.2 蚁群算法求解时间依赖中国邮路问题  43-46
    4.2.3 实验结果分析  46-47
  4.3 蚁群算法求解时间依赖乡村邮路问题  47-51
    4.3.1 算法过程描述  47-48
    4.3.2 实验结果及分析  48-51
  4.4 小结  51-52
结论  52-53
参考文献  53-57
攻读硕士学位期间发表学术论文情况  57-58
致谢  58-59

相似论文

  1. 多导弹协同作战突防效能评估及组合优化算法研究,TJ760.1
  2. 基于蚁群算法的电梯群优化控制研究,TU857
  3. 动态环境下移动对象导航系统相关技术的研究,TP301.6
  4. 基于改进蚁群算法的机器人路径规划研究,TP242
  5. 改进的蚁群算法及其在TSP上的应用研究,TP301.6
  6. 基于免疫机制蚁群算法的电力系统无功优化研究,TP18
  7. 基于视觉反馈与行为记忆的GPU并行蚁群算法,TP301.6
  8. 基于物理拓扑感知的Chord算法研究,TP393.02
  9. 电渣炉过程控制系统的设计及优化控制,TP273
  10. Ad Hoc网络中分簇路由算法的研究,TN929.5
  11. 图像信息处理机的图像处理方法研究,TP391.41
  12. 智能光网络中路由选择算法的研究,TN929.1
  13. 面向无线传感器网络的多路径路由协议研究,TN915.04
  14. 改进蚁群算法在盲均衡中的应用,TN911.5
  15. 智能光网络动态路由和波长分配算法的研究,TN929.1
  16. 基于蚁群算法的移动商务个性化推荐体系研究,TP391.3
  17. 基于蚁群算法的车辆调度问题研究,TP301.6
  18. 融合MMTD与仿生算法的路由选择研究,TP393.05
  19. 基于改进蚁群算法的多目标退化调度问题的研究,O221.6
  20. 面向可穿戴生理检测的无线传感器网络QoS路由研究,TP212.9
  21. 基于蚁群算法的聚类算法研究,TP311.13

中图分类: > 数理科学和化学 > 数学 > 运筹学 > 规划论（数学规划） > 整数规划
© 2012 www.xueweilunwen.com