动态不确定路径优化模型与算法

发布时间：2018-08-13 10:36

【摘要】：路径优化是交通运输领域中的基本问题。出行者在预先设定的优化路径上通行,不仅能节省出行费用,而且对提高整个路网的通行效率也起到积极作用。然而在实际的交通环境中,由于各种因素的影响,路网状态通常会呈现出高度的动态性和不确定性。因此,如何充分考虑并合理处理复杂路网的动态性和不确定性,以得到更加接近实际的路网信息,为出行者提供有效的路径向导是一个值得深入探讨的课题。本论文以路径优化为主线,采用基于场景并与时间相关的路段通行时间及通行能力表示交通路网的不确定性和动态性,研究了动态不确定最短路的生成策略和协同路径优化方法。进一步将提出的模型和方法应用于突发事件发生下车辆或者人员的疏散路径优化。具体来讲,本文的研究工作主要包括以下五个方面:(1)动态模糊交通路网中最优路径的评价准则。在缺少路段通行时间历史数据甚至没有数据的情况下,通过专家估计的方法将拥挤时段的不确定路段通行时间处理为动态模糊变量。基于可信性理论,分别针对单一时间区间和多个时间区间(即一个时间区段)提出三种路径评价准则:确定性支配准则、一阶模糊支配准则和模糊期望支配准则。最后,通过算例具体说明三种支配准则下比较路径的方法。(2)动态模糊交通路网中期望时间最短路径的求解方法。基于模糊期望支配准则,以寻找包含多个出发时刻的期望时间最短路径为目标,建立了多目标0-1数学规划模型。不同于动态随机路网中路径生成遵循的相加相乘运算法则,在动态模糊路网中,由于路段通行时间的模糊性,路径的生成遵循取大取小运算法则。鉴于此,提出了该路网环境下期望时间最短路径的具体生成方法,并设计了禁忌搜索算法对所建模型进行求解。与回溯法相比,禁忌搜索算法能够高效地求得较高精度的近似最优解。(3)随机约束最短路问题及拉格朗日松弛算法。为表示交通路网的随机性,将路段通行时间处理为基于场景的离散随机变量,建立了以期望时间最短为目标的随机约束最短路模型。由于该模型是NP难问题,采用拉格朗日松弛方法将模型的复杂约束松弛至目标函数中,从而使得松弛模型易于求解。设计了集次梯度优化算法、标号修正算法及K最短路算法于一体的启发式算法来最小化目标值上界和下界间的相对差值以得到模型的近似最优解。考虑到路段通行时间的联合概率质量函数随时间而动态变化的特点,将该模型扩展为动态随机约束最短路模型,并采用改进的启发式算法求解。最后,通过不同规模交通网络上的算例对算法的性质、上下界间的相对差值及计算效率进行了分析。试验结果表明,所提出的算法能够高效地求解大规模算例的近似最优解。(4)随机环境下基于灾难应急响应的疏散路径规划模型。当地震、洪水及飓风等突发事件发生时,通常需要尽快将危险区域的人员疏散至安全区域。为体现不同灾难级别对路网造成的影响,本文将路段通行时间和通行能力处理为离散随机变量。同时,考虑到决策者对风险的偏好程度,引入极小-极大可靠性方法、百分位可靠性方法以及期望负效用方法分别来刻画目标函数,建立了不同评价标准下的随机疏散路径规划模型。最后,设计了拉格朗日松弛方法和K最短路技术相结合的启发式算法对期望负效用模型进行求解。数值算例验证了算法求解大规模问题的有效性。(5)动态随机环境下两阶段应急疏散路径规划模型。根据突发事件发生时能否获取路段实时通行信息,将路网划分为先验优化阶段和自适应选择阶段。在先验优化阶段,假设突发事件即将发生或刚刚发生时不可获取路段通行信息,受灾人员按照预先给定的方案进行疏散。在自适应选择阶段,假设突发事件发生一段时间后可及时获取路网实时信息,采用自适应路径选择方式在不同场景下选择不同疏散方案。基于最小费用流模型,建立了以极小化期望总疏散时间为目标的两阶段随机路径优化模型。最后,将该模型转化为等价单阶段优化模型,并结合最小费用路算法及次梯度优化算法,设计了基于拉格朗日松弛方法的启发式算法对该模型进行求解。
[Abstract]:Path optimization is a basic problem in the field of transportation. Travelers can not only save travel costs but also play a positive role in improving the efficiency of the whole road network by using the pre-determined optimal path. However, in the actual traffic environment, the state of the road network usually presents a high degree of mobility due to various factors. Therefore, how to fully consider and reasonably deal with the dynamic and uncertainties of complex road network to get closer to the actual road network information and provide effective route guide for travelers is a topic worthy of further discussion. Section travel time and capacity represent the uncertainties and dynamics of traffic network. The generation strategy of dynamic uncertain shortest path and the method of cooperative path optimization are studied. Furthermore, the proposed model and method are applied to the evacuation path optimization of vehicles or people in emergencies. It includes the following five aspects: (1) the evaluation criterion of the optimal path in the dynamic fuzzy traffic network. In the absence of historical data or even no data, the uncertain passage time in the congestion period is treated as dynamic fuzzy variables by expert estimation method. In this paper, three evaluation criteria are proposed for intervals and multiple time intervals (i.e. one time interval). They are deterministic domination criterion, first-order fuzzy domination criterion and fuzzy expectation domination criterion. Finally, an example is given to illustrate the method of comparing the paths under the three domination criteria. (2) The method of solving the expected shortest path in the dynamic fuzzy traffic network. Based on the fuzzy expectation domination criterion, a multi-objective 0-1 mathematical programming model is established to find the shortest path with multiple departure times. Unlike the additive multiplication algorithm followed by path generation in dynamic random road network, the path generation obeys due to the fuzzy passage time in dynamic fuzzy road network. In view of this, a method to generate the shortest path with expected time in the network environment is proposed, and a tabu search algorithm is designed to solve the model. Compared with the backtracking algorithm, the tabu search algorithm can efficiently obtain the approximate optimal solution with high accuracy. (3) The shortest path problem with random constraints and Lagrange In order to represent the randomness of the traffic network, the passage time is treated as discrete random variables based on the scene, and a stochastic constrained shortest path model with the objective of minimizing the expected time is established. A heuristic algorithm combining subgradient optimization algorithm, label correction algorithm and K-shortest path algorithm is designed to minimize the relative difference between the upper and lower bounds of the target value in order to obtain the approximate optimal solution. The model is extended to a dynamic stochastic constrained shortest path model and solved by an improved heuristic algorithm. Finally, the properties of the algorithm, the relative difference between the upper and lower bounds and the computational efficiency are analyzed by an example on a traffic network of different sizes. The approximate optimal solution of the example. (4) Evacuation path planning model based on disaster emergency response in random environment. When earthquake, flood and hurricane occur, people in dangerous area should be evacuated to safety area as soon as possible. At the same time, considering the preference degree of the decision maker for risk, the minimax reliability method, the percentile reliability method and the expected negative utility method are introduced to characterize the objective function respectively, and the random evacuation path planning models under different evaluation criteria are established. A heuristic algorithm combined with K-shortest path technique is used to solve the expected negative utility model. Numerical examples show the effectiveness of the algorithm in solving large-scale problems. (5) Two-stage emergency evacuation path planning model in dynamic random environment. According to the real-time traffic information of the road section, the road network is divided into a priori. In the priori optimization stage, the disaster victims evacuate according to the pre-determined plan assuming that the road traffic information can not be obtained when the emergency is about to happen or just happened. Based on the minimum cost flow model, a two-stage stochastic path optimization model with the objective of minimizing the expected total evacuation time is established. Finally, the model is transformed into an equivalent one-stage optimization model, which is combined with the minimum cost path algorithm and the sub-gradient optimization algorithm. A heuristic algorithm based on Lagrange relaxation method is proposed to solve the model.
【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：U491

【相似文献】