基于鲁棒优化的随机时变网络最优路径研究

发布时间：2020-12-10 11:13

　　交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近... 

【文章来源】：运筹与管理. 2020年05期 第37-42页 北大核心CSSCI

【文章页数】：6 页

【部分图文】：

路径λ的图形表示

针对解决动态网络下最短路径问题,许多学者已经给出了能够在多项式时间复杂度(polynomial-time complexity)下求解的算法,这也是解决大规模网络问题的前提。本次研究将Sun等人[10]提出的改进Dijkstra算法应用到解决基于鲁棒优化的随机时变网络中最优路径问题,并基于图2中的小型交通网络进行标号法的算例测试。其中,vo代表出发的起始节点,t1代表从vo出发的时间;vd代表需要到达的终止节点,t*代表vd的期望到达时间,即时间窗约束。根据第3节中的证明结果,可以将原问题转换为解决一个确定性时变网络中的最短路问题,而转换后新的时变网络中的路段行程时间可以用原网络中相对应路段的行程时间上限来表示,即对应于分段函数中每个时间段t,路段行程时间有Rtij+dtij。因此,图2中随机时变网络的最优路径问题等价于在图3中所示的确定性时变网络中,求解vo至vd行程时间用时最少的最短路径问题。

转换后的确定性时变网络算例

【参考文献】：
期刊论文
[1]随机时变车辆路径问题的多目标鲁棒优化方法[J]. 段征宇,雷曾翔,孙硕,杨东援.  西南交通大学学报. 2019(03)



本文编号：2908597