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