動態(tài)不確定路徑優(yōu)化模型與算法
發(fā)布時間：2018-08-13 10:36
【摘要】：路徑優(yōu)化是交通運輸領域中的基本問題。出行者在預先設定的優(yōu)化路徑上通行,不僅能節(jié)省出行費用,而且對提高整個路網的通行效率也起到積極作用。然而在實際的交通環(huán)境中,由于各種因素的影響,路網狀態(tài)通常會呈現出高度的動態(tài)性和不確定性。因此,如何充分考慮并合理處理復雜路網的動態(tài)性和不確定性,以得到更加接近實際的路網信息,為出行者提供有效的路徑向導是一個值得深入探討的課題。本論文以路徑優(yōu)化為主線,采用基于場景并與時間相關的路段通行時間及通行能力表示交通路網的不確定性和動態(tài)性,研究了動態(tài)不確定最短路的生成策略和協(xié)同路徑優(yōu)化方法。進一步將提出的模型和方法應用于突發(fā)事件發(fā)生下車輛或者人員的疏散路徑優(yōu)化。具體來講,本文的研究工作主要包括以下五個方面:(1)動態(tài)模糊交通路網中最優(yōu)路徑的評價準則。在缺少路段通行時間歷史數據甚至沒有數據的情況下,通過專家估計的方法將擁擠時段的不確定路段通行時間處理為動態(tài)模糊變量�；诳尚判岳碚�,分別針對單一時間區(qū)間和多個時間區(qū)間(即一個時間區(qū)段)提出三種路徑評價準則:確定性支配準則、一階模糊支配準則和模糊期望支配準則。最后,通過算例具體說明三種支配準則下比較路徑的方法。(2)動態(tài)模糊交通路網中期望時間最短路徑的求解方法。基于模糊期望支配準則,以尋找包含多個出發(fā)時刻的期望時間最短路徑為目標,建立了多目標0-1數學規(guī)劃模型。不同于動態(tài)隨機路網中路徑生成遵循的相加相乘運算法則,在動態(tài)模糊路網中,由于路段通行時間的模糊性,路徑的生成遵循取大取小運算法則。鑒于此,提出了該路網環(huán)境下期望時間最短路徑的具體生成方法,并設計了禁忌搜索算法對所建模型進行求解。與回溯法相比,禁忌搜索算法能夠高效地求得較高精度的近似最優(yōu)解。(3)隨機約束最短路問題及拉格朗日松弛算法。為表示交通路網的隨機性,將路段通行時間處理為基于場景的離散隨機變量,建立了以期望時間最短為目標的隨機約束最短路模型。由于該模型是NP難問題,采用拉格朗日松弛方法將模型的復雜約束松弛至目標函數中,從而使得松弛模型易于求解。設計了集次梯度優(yōu)化算法、標號修正算法及K最短路算法于一體的啟發(fā)式算法來最小化目標值上界和下界間的相對差值以得到模型的近似最優(yōu)解�？紤]到路段通行時間的聯合概率質量函數隨時間而動態(tài)變化的特點,將該模型擴展為動態(tài)隨機約束最短路模型,并采用改進的啟發(fā)式算法求解。最后,通過不同規(guī)模交通網絡上的算例對算法的性質、上下界間的相對差值及計算效率進行了分析。試驗結果表明,所提出的算法能夠高效地求解大規(guī)模算例的近似最優(yōu)解。(4)隨機環(huán)境下基于災難應急響應的疏散路徑規(guī)劃模型。當地震、洪水及颶風等突發(fā)事件發(fā)生時,通常需要盡快將危險區(qū)域的人員疏散至安全區(qū)域。為體現不同災難級別對路網造成的影響,本文將路段通行時間和通行能力處理為離散隨機變量。同時,考慮到決策者對風險的偏好程度,引入極小-極大可靠性方法、百分位可靠性方法以及期望負效用方法分別來刻畫目標函數,建立了不同評價標準下的隨機疏散路徑規(guī)劃模型。最后,設計了拉格朗日松弛方法和K最短路技術相結合的啟發(fā)式算法對期望負效用模型進行求解。數值算例驗證了算法求解大規(guī)模問題的有效性。(5)動態(tài)隨機環(huán)境下兩階段應急疏散路徑規(guī)劃模型。根據突發(fā)事件發(fā)生時能否獲取路段實時通行信息,將路網劃分為先驗優(yōu)化階段和自適應選擇階段。在先驗優(yōu)化階段,假設突發(fā)事件即將發(fā)生或剛剛發(fā)生時不可獲取路段通行信息,受災人員按照預先給定的方案進行疏散。在自適應選擇階段,假設突發(fā)事件發(fā)生一段時間后可及時獲取路網實時信息,采用自適應路徑選擇方式在不同場景下選擇不同疏散方案�；谧钚≠M用流模型,建立了以極小化期望總疏散時間為目標的兩階段隨機路徑優(yōu)化模型。最后,將該模型轉化為等價單階段優(yōu)化模型,并結合最小費用路算法及次梯度優(yōu)化算法,設計了基于拉格朗日松弛方法的啟發(fā)式算法對該模型進行求解。
[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
本文編號：2180720
[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
【相似文獻】
相關期刊論文 前10條
1 蘇兵;華春燕;楊倩;崔曉;;出行者信息未知下的修繕路段選擇研究[J];預測;2013年06期
2 姚婷;劉亮;;Braess悖論及其對偶形式的博弈論分析[J];長沙交通學院學報;2007年03期
3 張睿;;關于在十字路口能否為電動車設置更長通行時間的可行性研究[J];科技資訊;2012年16期
4 李巧茹;高玲玲;陳亮;王朋;;交叉口高峰時段右轉車輛通行時間可靠性研究[J];交通科技;2011年05期
5 應江黔;一種利用實時信息與統(tǒng)計信息的可靠路徑生成算法(英文)[J];交通運輸系統(tǒng)工程與信息;2005年04期
6 ;青島 打造“奧運綠色通道”[J];中國交通信息產業(yè);2008年08期
7 劉勇;;怎樣看堵車?(上)[J];駕駛園;2010年11期
8 鐘慧玲;章夢;石永強;蔡文學;;基于剪枝策略的改進TDCALT算法[J];同濟大學學報(自然科學版);2012年08期
9 魏朝輝;崔艷;;SCATS系統(tǒng)在沈陽市的實際應用[J];中國交通信息產業(yè);2004年11期
10 高云峰,楊曉光,胡華;基于飽和度的車道數量確定方法[J];交通與計算機;2005年04期
相關會議論文 前1條
1 尚栩;;案例4 巴黎:“兩不罰”和“罰你沒商量”[A];2011城市國際化論壇——全球化進程中的大都市治理（案例集）[C];2011年
相關重要報紙文章 前10條
1 本報記者 俞瑩邋實習記者 駱明;給行人留出絕對通行時間[N];貴陽日報;2008年
2 柯果;修路越多,車行越慢？[N];民主與法制時報;2011年
3 通訊員 高其峰 記者 李暉;漢十城鐵有望年內開建[N];襄陽日報;2014年
4 記者陳可;11個項目總投資約23億元[N];南通日報;2010年
5 樵夫;“限摩”不如“限路”、“限時”[N];中國信息報;2005年
6 本報記者 程榮;交通擁堵話管制[N];中國國防報;2012年
7 本報記者 袁祥;節(jié)約從點滴做起 便民以分秒計算[N];光明日報;2006年
8 田恬;進入中歐的首張“名片”[N];中國交通報;2014年
9 ;《武漢市長江隧道管理暫行辦法》解讀[N];長江日報;2012年
10 擁軍 長保;交巡警全力維護道路安全暢通[N];鎮(zhèn)江日報;2008年
相關博士學位論文 前1條
1 王莉;動態(tài)不確定路徑優(yōu)化模型與算法[D];北京交通大學;2017年
相關碩士學位論文 前5條
1 林剛;信息有限預知下突發(fā)面擁堵實時路徑選擇研究[D];西安工業(yè)大學;2016年
2 左慶;基于兩類浮動車數據融合的信號交叉口平均通行時間估計[D];重慶大學;2016年
3 楊曉飛;基于隨機場景的兩階段期望最短路模型及算法研究[D];北京交通大學;2013年
4 卜祥濤;新增路段對道路交通網絡性能的影響研究[D];西安工業(yè)大學;2013年
5 陸宇;一種基于貝葉斯網的道路擁堵預測方法[D];云南大學;2010年
，本文編號：2180720
本文鏈接：http://www.wukwdryxk.cn/shoufeilunwen/gckjbs/2180720.html
