动态不确定路径优化模型与算法及其在交通应急管理中的应用

Routing optimization is a basic problem in the field of traffic and transportation. In practice,since dynamics and uncertainty often occur in the real-world transportation network, especially during the process of traffic emergency management, how to generate optimal routes in the given network with the complicated state is thus a worthwhile research for the real applications. This research focuses on the methods of dynamic and uncertain routing optimizaion and its applications in traffic emergency management, where scenario-based time-dependent link travel time is used to describe the dynamics and uncertainty of the transportation network. Specifically, itegrating with the a priori optimization and adaptive routing strategy, we shall investigate the time-dependent uncertain shortest path generation strategy and coordinated routing optimization methods based on the scenario optimzation methods.Then, multi-stage uncertain integer programming model will be formulated to describe the selection process of optimal routes. The mathematical properties of models, including equivalent model, total unimodular, linear programming relaxation and Lagrangian relaxation, will be further explored. In algorithm, Lagrangian relaxation approach will be used to relax the hard constraints. After decomposing the Lagrangian relaxation problem,a sub-gradient algorithm will be designed to seek a tight lower bound and approximate optimal solution based on the label correcting algorithm. Finally, we try to apply the proposed methodologies to evacuation routing selection in traffic emergency management, and obtain the useful models and algorithms in management science.

路径优化是交通运输领域中的基本问题。通常实际路网状态会呈现出高度动态性和不确定性，特别是在交通应急管理中，因此如何在复杂路网状态下选择最优路径是一个值得深入探讨的课题。本项目将开展对动态不确定路径优化问题及其在交通应急管理中应用的研究。首先，采用基于场景并与时间相关的路段通行时间描述路网的动态性和不确定性。而后综合应用先验优化和自适应路径策略，基于场景优化方法，研究时间相关不确定最短路生成策略和协作路径优化方法，并建立路径优化问题的多阶段不确定整数优化模型。研究模型的数学性质及松弛方法，如等价模型、约束条件的TU性质、线性松弛、拉格朗日松弛等。算法上，将应用拉格朗日松弛方法对模型中不易处理的约束进行松弛，研究拉格朗日松弛问题的分解，设计基于标号修正算法的次梯度算法求解模型最优下界和近似最优解。最后，尝试将研究方法应用于交通应急管理中人员和车辆疏散路径的选择，提出管理上实用的模型与算法。

路径优化是交通运输领域的基本问题，出行者在优化的路径上通行，不仅能节省出行费用，而且对提高整个路网的通行效率也起到积极作用。本项目基于实际交通路网的动态性和不确定性特点，探讨了动态不确定最优路径的生成方法及其在交通管理和列车运行图中的应用。主要做了如下三方面的工作。. （1）研究了动态不确定路网中最优路径的选择问题。具体地，采用基于场景的时间相关数据描述路网属性的动态性和随机性，为最短路问题构建了最小期望通行时间模型，并设计了基于拉格朗日松弛算法的启发式搜索算法。此外，根据路段通行信息的可获取性，采用两阶段随机规划思想，为可靠最短路问题和地铁换乘站点选择问题构建了两阶段0-1整数规划模型，设计了有效的启发式搜索算法求解模型。. （2）应用不确定优化技术研究交通应急管理中路径规划及列车运行调整问题，为突发事件发生情况下制定可行的路径规划方案提供了重要指导。具体地，将灾难级别处理为离散随机场景，为疏散路径规划问题构建了不同评价标准下的优化模型，探讨了模型的数学性质及等价类。进一步，为解决轨道交通事故场景下列车运行调整问题，将路段事故时间和客流需求处理为不确定变量，基于协同路径优化思想，为该问题建立了不确定优化模型。设计了GAMS优化代码和近似动态规划算法快速求解模型的近似最优解。. （3）采用动态时空路径规划方法，构建了列车运行图优化模型并设计高效求解算法。具体为，详细分析了列车使用既定轨道和对向轨道的延迟状况，对已有列车路径分配策略进行了显著改进；针对动态客流，建立了极小化乘客总通行时间和列车运行总能耗的多目标规划模型以优化列车运行图；基于协同优化思想，为列车停站方案与运行图同步优化问题构建了混合整数规划模型。此外，采用实际运营数据对上述成果的实用性和有效性进行了验证。. 相关研究对提高不同路网的使用效率具有重要的指导意义。