详情

原文传递动态不确定路径优化模型与算法

论文题名：	动态不确定路径优化模型与算法
关键词：	交通路网;路径优化;不确定性;动态性
摘要：	路径优化是交通运输领域中的基本问题。出行者在预先设定的优化路径上通行，不仅能节省出行费用，而且对提高整个路网的通行效率也起到积极作用。然而在实际的交通环境中，由于各种因素的影响，路网状态通常会呈现出高度的动态性和不确定性。因此，如何充分考虑并合理处理复杂路网的动态性和不确定性，以得到更加接近实际的路网信息，为出行者提供有效的路径向导是一个值得深入探讨的课题。本论文以路径优化为主线，采用基于场景并与时间相关的路段通行时间及通行能力表示交通路网的不确定性和动态性，研究了动态不确定最短路的生成策略和协同路径优化方法。进一步将提出的模型和方法应用于突发事件发生下车辆或者人员的疏散路径优化。具体来讲，本文的研究工作主要包括以下五个方面: 　　(1)动态模糊交通路网中最优路径的评价准则。在缺少路段通行时间历史数据甚至没有数据的情况下，通过专家估计的方法将拥挤时段的不确定路段通行时间处理为动态模糊变量。基于可信性理论，分别针对单一时间区间和多个时间区间（即一个时间区段）提出三种路径评价准则:确定性支配准则、一阶模糊支配准则和模糊期望支配准则。最后，通过算例具体说明三种支配准则下比较路径的方法。　　(2)动态模糊交通路网中期望时间最短路径的求解方法。基于模糊期望支配准则，以寻找包含多个出发时刻的期望时间最短路径为目标，建立了多目标0-1数学规划模型。不同于动态随机路网中路径生成遵循的相加相乘运算法则，在动态模糊路网中，由于路段通行时间的模糊性，路径的生成遵循取大取小运算法则。鉴于此，提出了该路网环境下期望时间最短路径的具体生成方法，并设计了禁忌搜索算法对所建模型进行求解。与回溯法相比，禁忌搜索算法能够高效地求得较高精度的近似最优解。　　(3)随机约束最短路问题及拉格朗日松弛算法。为表示交通路网的随机性，将路段通行时间处理为基于场景的离散随机变量，建立了以期望时间最短为目标的随机约束最短路模型。由于该模型是NP难问题，采用拉格朗日松弛方法将模型的复杂约束松弛至目标函数中，从而使得松弛模型易于求解。设计了集次梯度优化算法、标号修正算法及K最短路算法于一体的启发式算法来最小化目标值上界和下界间的相对差值以得到模型的近似最优解。考虑到路段通行时间的联合概率质量函数随时间而动态变化的特点，将该模型扩展为动态随机约束最短路模型，并采用改进的启发式算法求解。最后，通过不同规模交通网络上的算例对算法的性质、上下界间的相对差值及计算效率进行了分析。试验结果表明，所提出的算法能够高效地求解大规模算例的近似最优解。　　(4)随机环境下基于灾难应急响应的疏散路径规划模型。当地震、洪水及飓风等突发事件发生时，通常需要尽快将危险区域的人员疏散至安全区域。为体现不同灾难级别对路网造成的影响，本文将路段通行时间和通行能力处理为离散随机变量。同时，考虑到决策者对风险的偏好程度，引入极小-极大可靠性方法、百分位可靠性方法以及期望负效用方法分别来刻画目标函数，建立了不同评价标准下的随机疏散路径规划模型。最后，设计了拉格朗日松弛方法和K最短路技术相结合的启发式算法对期望负效用模型进行求解。数值算例验证了算法求解大规模问题的有效性。　　(5)动态随机环境下两阶段应急疏散路径规划模型。根据突发事件发生时能否获取路段实时通行信息，将路网划分为先验优化阶段和自适应选择阶段。在先验优化阶段，假设突发事件即将发生或刚刚发生时不可获取路段通行信息，受灾人员按照预先给定的方案进行疏散。在自适应选择阶段，假设突发事件发生一段时间后可及时获取路网实时信息，采用自适应路径选择方式在不同场景下选择不同疏散方案。基于最小费用流模型，建立了以极小化期望总疏散时间为目标的两阶段随机路径优化模型。最后，将该模型转化为等价单阶段优化模型，并结合最小费用路算法及次梯度优化算法，设计了基于拉格朗日松弛方法的启发式算法对该模型进行求解。
作者：	王莉
专业：	交通运输规划与管理
导师：	高自友;杨立兴
授予学位：	博士
授予学位单位：	北京交通大学
学位年度：	2017
正文语种：	中文