时间依赖网络中国邮路问题的列生成算法

发布时间：2020-04-13 07:18

【摘要】： 中国邮路问题是图论中的经典问题,得到了广泛的研究。该问题有着众多的应用领域,如邮件投递路线,扫雪车路线,警车出巡安排,机器人检测路线路线以及软、硬件系统的测试序列优化等等,因此吸引了众多学者的研究兴趣。 近年来,由于计算机网络与通信、智能交通系统以及混合系统实时测试等复杂应用领域的需求,时变网络中国邮路问题的研究具有更为重要的现实应用意义。带时间窗的中国邮路问题、时间依赖服务代价中国邮路问题以及时间依赖旅行时间中国邮路问题均属于时变网络中国邮路问题。其中,前两个问题已经得到了较好的研究,但由于时间依赖旅行时间中国邮路问题建模十分困难,因此,一直鲜有研究。然而,本文将致力于时间依赖旅行时间中国邮路问题的研究。 本文首先对传统的中国邮路问题和时变网络中国邮路问题的研究方法进行了归纳总结,并介绍了列生成算法的原理及其在时变网络中的应用。然后,通过将中国邮路可行解看成是图中圈的排列组合,设计了以基本圈为决策变量的整数线性规划模型,并从理论上证明了该模型中基本圈数的上界为m-n+1。由于该整数规划模型的规模比较大,因此,本文设计了列生成算法求解该问题。首先,将圈变量整数规划模型抽象为带偏序关系的集合覆盖主问题模型,降低了解空间的维数；然后,通过对偶理论设计了时间依赖最短路子问题,并应用遗传算法求解,从而进一步确定了最优解的搜索方向。但是,这个模型只能解决所有圈均过原点的特例,针对存在圈不过原点的网络拓扑,文章针对可行解的特点给出了另外一个“层路径”数学规划模型,同时对该模型的上界进行了理论分析,算例验证了该模型的正确性。
【图文】：

;若该路径是投递路线的最后一层路径，则规定其下一层路径为路径不为空。将给出一个例子，来说明上面的思想。例如在图6.2的有向图一1一2一O一3一2一O。我们用图6.3的形式来描述这条邮路。很容易看出径连接而成的。O一1一2是第一层路径，O一3一2是第二层路径，第;2一O是第一层路径和第二层路径之间的连接弧，2一0是第二层连接弧。把每一层的图补全后，可以得到更直观的图6.4。图6.2TDCPP实例Fig.6，2TheInstaneeofTDCPP

;若该路径是投递路线的最后一层路径，则规定其下一层路径为路径不为空。将给出一个例子，来说明上面的思想。例如在图6.2的有向图一1一2一O一3一2一O。我们用图6.3的形式来描述这条邮路。很容易看出径连接而成的。O一1一2是第一层路径，O一3一2是第二层路径，，第;2一O是第一层路径和第二层路径之间的连接弧，2一0是第二层连接弧。把每一层的图补全后，可以得到更直观的图6.4。图6.2TDCPP实例Fig.6，2TheInstaneeofTDCPP
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2010
【分类号】：F616;TP399-C6

【引证文献】

相关硕士学位论文 前2条

1 曲宏磊;时变网络乡村邮路问题割平面及蚁群算法研究[D];大连理工大学;2011年

2 孟宪超;两阶段法求带时间窗的时间依赖乡村邮路问题[D];大连理工大学;2011年

本文编号：2625750