基于時變隨機路網(wǎng)的綠色可靠路徑選擇問題模型及算法
發(fā)布時間：2018-11-17 13:59
【摘要】：交通領(lǐng)域CO2排放問題日益嚴重,將CO2排放約束納入個人交通出行中,已成為研究減少交通出行中CO2排放的新思路。在復雜交通路網(wǎng)中,研究綠色可靠路徑選擇問題,為出行者提供滿足CO2排放約束和通行時間可靠的最優(yōu)路徑,對促進綠色交通發(fā)展具有重要現(xiàn)實意義�？紤]現(xiàn)實交通路網(wǎng)的復雜時變與隨機特性,論文采用時間區(qū)段離散化和基于場景的方法,表示路網(wǎng)中時變隨機的路段通行時間和CO2排放數(shù)據(jù)。研究時變隨機路網(wǎng)中綠色可靠路徑選擇問題,分別以路徑通行時間可靠性和期望CO2排放為評價準則,構(gòu)建綠色可靠路徑選擇模型和低排放路徑選擇模型。基于此,設(shè)計拉格朗日松弛算法求解文中所構(gòu)建模型,得到原問題近似最優(yōu)解。最后分別以三種規(guī)模的交通路網(wǎng)為研究背景,通過算例結(jié)果分析驗證模型和算法的有效性。論文主要研究內(nèi)容包括:(1)考慮時變隨機的路段通行時間和路段CO2排放,刻畫路網(wǎng)的時變與隨機特性。分析路段CO2排放量與路段平均速度間二次關(guān)系方程及路段通行時間與路段平均速度間的反比例關(guān)系。采用基于場景的方法刻畫隨機性,每種場景下均考慮整個網(wǎng)絡(luò)中時變的路段通行時間和路段CO2排放。(2)構(gòu)建時變隨機路網(wǎng)下綠色可靠路徑選擇模型。首先,在時變隨機路網(wǎng)中設(shè)定時間閾值,驗證時空路徑是否為準時時空路徑,最后根據(jù)與物理路徑相映射的不同時空路徑的準時到達概率定義物理路徑的可靠性。模型目標函數(shù)為最小遲到概率,且采用CO2排放標準約束路徑期望CO2排放。(3)構(gòu)建時變隨機路網(wǎng)下低排放路徑選擇模型,其目標函數(shù)為路徑期望CO2排放最少。根據(jù)出行者期望設(shè)定時間閾值,并約束路徑期望通行時間。最后,詳細分析模型復雜性,并指出需設(shè)計啟發(fā)式算法有效求解大規(guī)模網(wǎng)絡(luò)問題模型。(4)采用拉格朗日松弛算法和次梯度算法求解得模型近似最優(yōu)解。通過對偶松弛原問題模型中難約束得到松弛后模型,該對偶模型可進一步分解為兩個子問題(即標準最短路問題和簡單線性單變量問題)和一個常數(shù),采用改進的標號修正算法和單變量線性規(guī)劃分別求解子問題。最后,采用次梯度算法更新迭代,得到上下界間的緊差值,進而得到模型近似最優(yōu)解。(5)設(shè)計小規(guī)模網(wǎng)絡(luò)、中等規(guī)模網(wǎng)絡(luò)和大規(guī)模網(wǎng)絡(luò)算例證明模型和算法的有效性。在小規(guī)模三點網(wǎng)絡(luò)算例中,分別采用枚舉法和拉格朗日松弛算法求解模型。以Sioux Falls網(wǎng)絡(luò)和Salt Lake City網(wǎng)絡(luò)為算例背景,設(shè)計數(shù)值實驗分析解的質(zhì)量以及模型中時間閾值和排放閾值的靈敏度。
[Abstract]:The problem of CO2 emission is becoming more and more serious in the field of transportation. It has become a new idea to study the reduction of CO2 emissions in traffic travel by incorporating CO2 emission constraints into individual traffic travel. In the complex traffic network, it is of great practical significance to study the problem of green reliable path selection and to provide the optimal path to meet the CO2 emission constraints and reliable passage time for travelers to promote the development of green transportation. Considering the complex time-varying and stochastic characteristics of the real traffic network, the time interval discretization and scenario-based approach are used to represent the time-varying random road passage time and CO2 emission data. The problem of green reliable path selection in time-varying stochastic road network is studied. The green reliable path selection model and the low emission path selection model are constructed based on the path time reliability and expected CO2 emission respectively. Based on this, Lagrangian relaxation algorithm is designed to solve the proposed model, and the approximate optimal solution of the original problem is obtained. Finally, taking three traffic networks of different scales as the background, the validity of the model and the algorithm is verified by example analysis. The main contents of this paper are as follows: (1) considering the time varying random road passage time and CO2 emission, the paper describes the time-varying and stochastic characteristics of road network. The quadratic relation equation between CO2 emission and average speed of road section and the inverse relation between road passage time and average speed of road section are analyzed. A scenario based approach is used to characterize randomness. In each scenario, the time-varying road passage time and CO2 emissions are considered in each scenario. (2) the green reliable path selection model is constructed under time-varying stochastic road network. First, the time threshold is set in the time-varying random road network to verify whether the space-time path is a punctual space-time path. Finally, the reliability of the physical path is defined according to the punctual arrival probability of different space-time paths mapped to the physical path. The objective function of the model is the minimum tardiness probability and the expected CO2 emission by the CO2 emission standard constrained path. (3) the low emission path selection model under the time-varying stochastic road network is constructed, and the objective function is that the path expected CO2 emission is the least. The time threshold is set according to the traveler's expectation, and the expected passage time is constrained. Finally, the complexity of the model is analyzed in detail, and it is pointed out that a heuristic algorithm should be designed to solve the large-scale network problem effectively. (4) the Lagrangian relaxation algorithm and the sub-gradient algorithm are used to solve the approximate optimal solution of the model. The relaxed model can be further decomposed into two subproblems (i.e. the standard shortest path problem and the simple linear single variable problem) and a constant. The improved label correction algorithm and univariate linear programming are used to solve the subproblems respectively. Finally, the subgradient algorithm is used to update the iteration, and the compact difference between upper and lower bounds is obtained, and the approximate optimal solution of the model is obtained. (5) the effectiveness of the model and the algorithm is proved by the design of small scale network, medium scale network and large scale network. The enumeration method and Lagrangian relaxation algorithm are used to solve the model of small scale three-point network. Taking Sioux Falls network and Salt Lake City network as examples, the quality of solution and the sensitivity of time threshold and emission threshold in the model are analyzed by numerical experiments.
【學位授予單位】：北京交通大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：U491
本文編號：2338045
[Abstract]:The problem of CO2 emission is becoming more and more serious in the field of transportation. It has become a new idea to study the reduction of CO2 emissions in traffic travel by incorporating CO2 emission constraints into individual traffic travel. In the complex traffic network, it is of great practical significance to study the problem of green reliable path selection and to provide the optimal path to meet the CO2 emission constraints and reliable passage time for travelers to promote the development of green transportation. Considering the complex time-varying and stochastic characteristics of the real traffic network, the time interval discretization and scenario-based approach are used to represent the time-varying random road passage time and CO2 emission data. The problem of green reliable path selection in time-varying stochastic road network is studied. The green reliable path selection model and the low emission path selection model are constructed based on the path time reliability and expected CO2 emission respectively. Based on this, Lagrangian relaxation algorithm is designed to solve the proposed model, and the approximate optimal solution of the original problem is obtained. Finally, taking three traffic networks of different scales as the background, the validity of the model and the algorithm is verified by example analysis. The main contents of this paper are as follows: (1) considering the time varying random road passage time and CO2 emission, the paper describes the time-varying and stochastic characteristics of road network. The quadratic relation equation between CO2 emission and average speed of road section and the inverse relation between road passage time and average speed of road section are analyzed. A scenario based approach is used to characterize randomness. In each scenario, the time-varying road passage time and CO2 emissions are considered in each scenario. (2) the green reliable path selection model is constructed under time-varying stochastic road network. First, the time threshold is set in the time-varying random road network to verify whether the space-time path is a punctual space-time path. Finally, the reliability of the physical path is defined according to the punctual arrival probability of different space-time paths mapped to the physical path. The objective function of the model is the minimum tardiness probability and the expected CO2 emission by the CO2 emission standard constrained path. (3) the low emission path selection model under the time-varying stochastic road network is constructed, and the objective function is that the path expected CO2 emission is the least. The time threshold is set according to the traveler's expectation, and the expected passage time is constrained. Finally, the complexity of the model is analyzed in detail, and it is pointed out that a heuristic algorithm should be designed to solve the large-scale network problem effectively. (4) the Lagrangian relaxation algorithm and the sub-gradient algorithm are used to solve the approximate optimal solution of the model. The relaxed model can be further decomposed into two subproblems (i.e. the standard shortest path problem and the simple linear single variable problem) and a constant. The improved label correction algorithm and univariate linear programming are used to solve the subproblems respectively. Finally, the subgradient algorithm is used to update the iteration, and the compact difference between upper and lower bounds is obtained, and the approximate optimal solution of the model is obtained. (5) the effectiveness of the model and the algorithm is proved by the design of small scale network, medium scale network and large scale network. The enumeration method and Lagrangian relaxation algorithm are used to solve the model of small scale three-point network. Taking Sioux Falls network and Salt Lake City network as examples, the quality of solution and the sensitivity of time threshold and emission threshold in the model are analyzed by numerical experiments.
【學位授予單位】：北京交通大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：U491
【參考文獻】
相關(guān)期刊論文 前10條
1 張水艦;劉學軍;楊洋;;動態(tài)隨機最短路徑算法研究[J];物理學報;2012年16期
2 周慶新;;基于相似度測量法的模糊最短路徑問題[J];西南師范大學學報(自然科學版);2011年03期
3 劉建美;馬壽峰;馬帥奇;;基于改進的Dijkstra算法的動態(tài)最短路計算方法[J];系統(tǒng)工程理論與實踐;2011年06期
4 孫小軍;;最短路問題的改進算法[J];計算機工程與設(shè)計;2009年16期
5 張德全;吳果林;劉登峰;;最短路問題的Floyd加速算法與優(yōu)化[J];計算機工程與應用;2009年17期
6 何方國;齊歡;范瓊;;有約束的隨機最短路問題模型及算法[J];武漢理工大學學報(交通科學與工程版);2008年06期
7 范巍巍;程琳;;隨機路網(wǎng)的最短路徑問題研究[J];公路交通科技;2007年09期
8 魏航;李軍;劉凝子;;一種求解時變網(wǎng)絡(luò)下多式聯(lián)運最短路的算法[J];中國管理科學;2006年04期
9 牟海波;劉林忠;;模糊隨機最短路徑問題模型與算法[J];蘭州交通大學學報;2006年03期
10 張蕾;矩陣方法求賦權(quán)圖中最短路的算法[J];西北大學學報(自然科學版);2004年05期
相關(guān)博士學位論文 前1條
1 俞峰;復雜動態(tài)隨機網(wǎng)絡(luò)最短路徑問題研究[D];浙江大學;2009年
相關(guān)碩士學位論文 前1條
1 楊曉飛;基于隨機場景的兩階段期望最短路模型及算法研究[D];北京交通大學;2013年
，本文編號：2338045
本文鏈接：http://sikaile.net/kejilunwen/daoluqiaoliang/2338045.html
