【摘要】：交通領(lǐng)域CO2排放問(wèn)題日益嚴(yán)重,將CO2排放約束納入個(gè)人交通出行中,已成為研究減少交通出行中CO2排放的新思路。在復(fù)雜交通路網(wǎng)中,研究綠色可靠路徑選擇問(wèn)題,為出行者提供滿足CO2排放約束和通行時(shí)間可靠的最優(yōu)路徑,對(duì)促進(jìn)綠色交通發(fā)展具有重要現(xiàn)實(shí)意義。考慮現(xiàn)實(shí)交通路網(wǎng)的復(fù)雜時(shí)變與隨機(jī)特性,論文采用時(shí)間區(qū)段離散化和基于場(chǎng)景的方法,表示路網(wǎng)中時(shí)變隨機(jī)的路段通行時(shí)間和CO2排放數(shù)據(jù)。研究時(shí)變隨機(jī)路網(wǎng)中綠色可靠路徑選擇問(wèn)題,分別以路徑通行時(shí)間可靠性和期望CO2排放為評(píng)價(jià)準(zhǔn)則,構(gòu)建綠色可靠路徑選擇模型和低排放路徑選擇模型。基于此,設(shè)計(jì)拉格朗日松弛算法求解文中所構(gòu)建模型,得到原問(wèn)題近似最優(yōu)解。最后分別以三種規(guī)模的交通路網(wǎng)為研究背景,通過(guò)算例結(jié)果分析驗(yàn)證模型和算法的有效性。論文主要研究?jī)?nèi)容包括:(1)考慮時(shí)變隨機(jī)的路段通行時(shí)間和路段CO2排放,刻畫路網(wǎng)的時(shí)變與隨機(jī)特性。分析路段CO2排放量與路段平均速度間二次關(guān)系方程及路段通行時(shí)間與路段平均速度間的反比例關(guān)系。采用基于場(chǎng)景的方法刻畫隨機(jī)性,每種場(chǎng)景下均考慮整個(gè)網(wǎng)絡(luò)中時(shí)變的路段通行時(shí)間和路段CO2排放。(2)構(gòu)建時(shí)變隨機(jī)路網(wǎng)下綠色可靠路徑選擇模型。首先,在時(shí)變隨機(jī)路網(wǎng)中設(shè)定時(shí)間閾值,驗(yàn)證時(shí)空路徑是否為準(zhǔn)時(shí)時(shí)空路徑,最后根據(jù)與物理路徑相映射的不同時(shí)空路徑的準(zhǔn)時(shí)到達(dá)概率定義物理路徑的可靠性。模型目標(biāo)函數(shù)為最小遲到概率,且采用CO2排放標(biāo)準(zhǔn)約束路徑期望CO2排放。(3)構(gòu)建時(shí)變隨機(jī)路網(wǎng)下低排放路徑選擇模型,其目標(biāo)函數(shù)為路徑期望CO2排放最少。根據(jù)出行者期望設(shè)定時(shí)間閾值,并約束路徑期望通行時(shí)間。最后,詳細(xì)分析模型復(fù)雜性,并指出需設(shè)計(jì)啟發(fā)式算法有效求解大規(guī)模網(wǎng)絡(luò)問(wèn)題模型。(4)采用拉格朗日松弛算法和次梯度算法求解得模型近似最優(yōu)解。通過(guò)對(duì)偶松弛原問(wèn)題模型中難約束得到松弛后模型,該對(duì)偶模型可進(jìn)一步分解為兩個(gè)子問(wèn)題(即標(biāo)準(zhǔn)最短路問(wèn)題和簡(jiǎn)單線性單變量問(wèn)題)和一個(gè)常數(shù),采用改進(jìn)的標(biāo)號(hào)修正算法和單變量線性規(guī)劃分別求解子問(wèn)題。最后,采用次梯度算法更新迭代,得到上下界間的緊差值,進(jìn)而得到模型近似最優(yōu)解。(5)設(shè)計(jì)小規(guī)模網(wǎng)絡(luò)、中等規(guī)模網(wǎng)絡(luò)和大規(guī)模網(wǎng)絡(luò)算例證明模型和算法的有效性。在小規(guī)模三點(diǎn)網(wǎng)絡(luò)算例中,分別采用枚舉法和拉格朗日松弛算法求解模型。以Sioux Falls網(wǎng)絡(luò)和Salt Lake City網(wǎng)絡(luò)為算例背景,設(shè)計(jì)數(shù)值實(shí)驗(yàn)分析解的質(zhì)量以及模型中時(shí)間閾值和排放閾值的靈敏度。
[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.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：U491

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張水艦;劉學(xué)軍;楊洋;;動(dòng)態(tài)隨機(jī)最短路徑算法研究[J];物理學(xué)報(bào);2012年16期

2 周慶新;;基于相似度測(cè)量法的模糊最短路徑問(wèn)題[J];西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年03期

3 劉建美;馬壽峰;馬帥奇;;基于改進(jìn)的Dijkstra算法的動(dòng)態(tài)最短路計(jì)算方法[J];系統(tǒng)工程理論與實(shí)踐;2011年06期

4 孫小軍;;最短路問(wèn)題的改進(jìn)算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2009年16期

5 張德全;吳果林;劉登峰;;最短路問(wèn)題的Floyd加速算法與優(yōu)化[J];計(jì)算機(jī)工程與應(yīng)用;2009年17期

6 何方國(guó);齊歡;范瓊;;有約束的隨機(jī)最短路問(wèn)題模型及算法[J];武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版);2008年06期

7 范巍巍;程琳;;隨機(jī)路網(wǎng)的最短路徑問(wèn)題研究[J];公路交通科技;2007年09期

8 魏航;李軍;劉凝子;;一種求解時(shí)變網(wǎng)絡(luò)下多式聯(lián)運(yùn)最短路的算法[J];中國(guó)管理科學(xué);2006年04期

9 牟海波;劉林忠;;模糊隨機(jī)最短路徑問(wèn)題模型與算法[J];蘭州交通大學(xué)學(xué)報(bào);2006年03期

10 張蕾;矩陣方法求賦權(quán)圖中最短路的算法[J];西北大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年05期

相關(guān)博士學(xué)位論文 前1條

1 俞峰;復(fù)雜動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)最短路徑問(wèn)題研究[D];浙江大學(xué);2009年

相關(guān)碩士學(xué)位論文 前1條

1 楊曉飛;基于隨機(jī)場(chǎng)景的兩階段期望最短路模型及算法研究[D];北京交通大學(xué);2013年

，

本文編號(hào)：2338045