基于时变随机路网的绿色可靠路径选择问题模型及算法

发布时间：2018-11-17 13:59

【摘要】：交通领域CO2排放问题日益严重,将CO2排放约束纳入个人交通出行中,已成为研究减少交通出行中CO2排放的新思路。在复杂交通路网中,研究绿色可靠路径选择问题,为出行者提供满足CO2排放约束和通行时间可靠的最优路径,对促进绿色交通发展具有重要现实意义。考虑现实交通路网的复杂时变与随机特性,论文采用时间区段离散化和基于场景的方法,表示路网中时变随机的路段通行时间和CO2排放数据。研究时变随机路网中绿色可靠路径选择问题,分别以路径通行时间可靠性和期望CO2排放为评价准则,构建绿色可靠路径选择模型和低排放路径选择模型。基于此,设计拉格朗日松弛算法求解文中所构建模型,得到原问题近似最优解。最后分别以三种规模的交通路网为研究背景,通过算例结果分析验证模型和算法的有效性。论文主要研究内容包括:(1)考虑时变随机的路段通行时间和路段CO2排放,刻画路网的时变与随机特性。分析路段CO2排放量与路段平均速度间二次关系方程及路段通行时间与路段平均速度间的反比例关系。采用基于场景的方法刻画随机性,每种场景下均考虑整个网络中时变的路段通行时间和路段CO2排放。(2)构建时变随机路网下绿色可靠路径选择模型。首先,在时变随机路网中设定时间阈值,验证时空路径是否为准时时空路径,最后根据与物理路径相映射的不同时空路径的准时到达概率定义物理路径的可靠性。模型目标函数为最小迟到概率,且采用CO2排放标准约束路径期望CO2排放。(3)构建时变随机路网下低排放路径选择模型,其目标函数为路径期望CO2排放最少。根据出行者期望设定时间阈值,并约束路径期望通行时间。最后,详细分析模型复杂性,并指出需设计启发式算法有效求解大规模网络问题模型。(4)采用拉格朗日松弛算法和次梯度算法求解得模型近似最优解。通过对偶松弛原问题模型中难约束得到松弛后模型,该对偶模型可进一步分解为两个子问题(即标准最短路问题和简单线性单变量问题)和一个常数,采用改进的标号修正算法和单变量线性规划分别求解子问题。最后,采用次梯度算法更新迭代,得到上下界间的紧差值,进而得到模型近似最优解。(5)设计小规模网络、中等规模网络和大规模网络算例证明模型和算法的有效性。在小规模三点网络算例中,分别采用枚举法和拉格朗日松弛算法求解模型。以Sioux Falls网络和Salt Lake City网络为算例背景,设计数值实验分析解的质量以及模型中时间阈值和排放阈值的灵敏度。
[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

【参考文献】