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