经过指定中间服务节点的抗堵塞路径选择研究

摘要

如何在出发前为运输车辆选择一条抗堵塞路径使路段堵塞带来的时间延误损失最少具有重要意义。现有研究或者不考虑路段突发性堵塞只研究经过指定节点的路径选择，或者不考虑经过指定节点只研究从起点到终点的抗堵塞路径选择，不能满足实际需求。本文针对任意路段都有可能发生堵塞的情形，提出路段堵塞对路径选择影响的度量指标，建立运输车辆经过单个和多个指定中间服务节点的抗堵塞路径选择模型并进行求解，为相关企业和部门制定路径选择方案提供决策依据。论文的主要工作和成果如下。
　　建立经过单个指定中间服务节点的抗堵塞路径选择模型并设计算法求解。提出路段堵塞对路径选择影响的度量指标——路段堵塞损失值。分析堵塞路段在路径上位于单个中间服务节点之前和之后2种位置关系，给出路段堵塞损失值的具体计算方法。计算任一路径上每一条路段堵塞损失值的最大值，比较每一条路径的路段损失值最大值并找出其中的最小值，把它对应的路段所在的路径称为单节点抗堵塞服务路径，并结合抗堵塞服务路径本身的长度选择出单节点最优抗堵塞服务路径。分析网络中特殊路段的性质分别在一般网络中设计时间复杂性为O(n3)的算法，在方格网络中设计时间复杂性为O(1)的算法进行求解，并用MATLAB进行编程实现。结合实例验证模型和算法的有效性。
　　建立经过多个指定中间服务节点的抗堵塞路径选择模型并设计算法求解。分析堵塞路段在路径上位于所有中间服务节点之前、经过部分指定中间服务节点和位于所有中间服务节点之后3种位置关系，给出路段堵塞损失值的具体计算方法。计算任一路径上每一条路段堵塞损失值并找出最大值，每一条路径均可找出该最大值，从这些最大值中找出最小值，把它对应的路段所在的路径称为多节点抗堵塞服务路径，并结合抗堵塞服务路径本身的长度选择出多节点最优抗堵塞服务路径。分别计算起点到某个中间服务节点的局部路径，连接所有中间服务节点的局部路径和某一中间服务节点到终点的局部路径，将这三段局部路径连接在一起得到从起点出发经过多个指定中间服务节点到达终点的路径。分析网络中特殊路段的性质在一般网络中设计时间复杂性为O(kn3)的算法进行求解，并用MATLAB编程实现。结合实例验证模型和算法的有效性。

目录

摘要

1 绪论

1．1 研究背景与意义

1．2 论文内容与框架

1．2．1 论文内容

1．2．2 论文框架

2 国内外相关研究综述

2．1 经过指定中间服务节点的路径选择

2．1．1 起讫点相同的路径选择

2．1．2 起讫点不同的路径选择

2．2 未考虑指定中间服务节点的抗堵塞路径选择

2．2．1 最短路径上路段堵塞的抗堵塞路径选择

2．2．2 任意短路径上路段堵塞的抗堵塞路径选择

3 经过单个指定中间服务节点的抗堵塞路径选择

3．1 问题描述与相关定义

3．1．1 问题描述

3．1．2 相关定义

3．2 模型分析与求解

3．2．1 一般网络上的模型求解

3．2．2 方格网络上的模型求解

3．3 实例分析

3．3．1 一般网络上的实例分析

3．3．2 方格网络上的实例分析

3．4 本章小结

4 经过多个指定中间服务节点的抗堵塞路径选择

4．1 问题描述与相关定义

4．1．1 问题描述

4．1．2 相关定义

4．2 模型分析与求解

4．3 实例分析

4．4 本章小结

5 结论

5．1 论文主要结论

5．2 需要进一步研究的问题

参考文献

攻读硕士学位期间发表的论文

攻读硕士学位期间参与的项目

致谢

声明

附录