基于随机场景的两阶段期望最短路模型及算法研究

摘要

本文以最短路问题为研究对象，探讨了路网上基于场景数据的随机静态和随机时变最短路问题。具体来说，考虑到现实的交通网络中各种不确定因素的影响，将路网上各路段通行时间处理为与时间相关的不确定变量，采用基于随机场景的数据表示方式，以极小化期望通行时间为目标，为随机静态和动态最短路问题建立基于不确定场景数据的两阶段期望值优化模型。进一步，基于对模型的特性分析，设计了GAMS优化代码和拉格朗日松弛算法求解原问题的近似最优解。最后，以Sioux Falls路网为研究背景，验证模型和算法的有效性。本文的主要内容包括:
　　(1)基于静态随机场景数据的两阶段最短路优化模型
　　将不同场景下的路段通行时间处理为静态离散随机变量。依据通行信息的可获取性，将时间轴划分为两个阶段。同时假设第一时间阶段内路网通行信息非实时获取，而第二时间阶段为路网通行信息可实时获取阶段。基于如上时间阶段的划分，采取两种不同的路径搜索策略选择出行路径。在数学模型中，以期望通行时间最小为目标，构建了静态两阶段随机期望值最短路模型，并分析了模型的若干数学性质。
　　(2)基于动态随机网络的期望值最短路模型
　　将不同场景下的路段通行时间处理为时间相关的离散随机变量。引入动态时空网络分析方法，在第一时间阶段内搜索最优基准物理路径，而在第二时间阶段内搜索自适应时间相关最短路径。根据给定的时间阶段划分特征，构建了基于场景数据的两阶段时间相关最短路期望值优化模型。
　　(3)拉格朗日松弛和次梯度算法
　　鉴于所研究问题的复杂性，采用场景优化方法，研究了所建立模型的等价类，并采用不同的方法对唯一路径约束进行了处理。进一步，利用拉格朗日松弛算法将复杂约束对偶化并构建了松弛模型，研究松弛模型的分解方法。设计了基于标号修正算法和次梯度算法的启发式搜索算法搜寻原问题最优目标函数的紧下界和近似最优解。在算法中，利用次梯度算法迭代并更新拉格朗日乘子，从而不断提高所生成的目标函数下界，最终得到松弛问题的最优解即为原模型的一个紧下界。
　　(4)算例研究
　　为了验证本文所提算法求解原问题近似最优解的有效性和计算效率，本文以Sioux Falls路网为例进行验证并进行结果分析。

目录

致谢

摘要

1 绪论

1．1 研究背景及意义

1．2 最短路问题分类及国内外研究现状

1．2．1 最短路问题的分类

1．2．2 静态最短路问题研究现状

1．2．3 动态最短路问题研究现状

1．3 论文主要内容和结构

2 基于静态场景数据的随机最短路问题

2．1 最短路问题的一般模型

2．2 物理路径与时空路径

2．3 基于静态随机场景的两阶段问题分析

2．4 基于静态场景的两阶段随机期望值模型

2．4．1 模型第一阶段

2．4．2 模型第二阶段

2．4．3 目标函数

2．4．4 静态网络两阶段随机期望值模型

2．5 基于静态场景的两阶段随机期望值模型分析

2．5．1 两阶段随机期望值模型性质分析

2．5．2 两阶段随机期望值模型与WAS模型对比

2．6 小结

3 基于动态随机场景的两阶段最短路问题

3．1 动态网络与静态网络的对比分析

3．2 基于动态场景的两阶段最短路优化模型

3．3 小结

4 拉格朗日松弛算法

4．1 松弛方法

4．2 随机模型中复杂约束的松弛

4．2．1 复杂唯一路径约束处理的一般方法

4．2．2 处理复杂路径约束的简化方法

4．3 模型分解

4．4 次梯度算法

4．4．1 次梯度方向

4．4．2 拉格朗日乘子迭代

4．5 算法过程

4．6 小结

5 算例研究

5．1 静态随机最短路问题算例设计

5．2 基于拉格朗日松弛算法的算例设计

5．2．1 小规模网络算例

5．2．2 中等规模网络算例

5．3 小结

6 总结与展望

6．1 论文的主要工作与结论

6．2 进一步研究方向

参考文献

作者简历

声明

学位论文数据集