基于鲁棒优化的城市交通网络设计模型与算法研究

发布时间：2018-01-02 11:31

本文关键词：基于鲁棒优化的城市交通网络设计模型与算法研究　出处：《北京交通大学》2014年博士论文　论文类型：学位论文

【摘要】：城市交通网络设计问题是城市综合规划的核心问题,也是关系到城市经济长期、快速、和谐和稳定发展的基本问题。当前,随着城市的高速发展,城市交通拥堵现象日益严重,交通供需矛盾日益突出,缓解和预防交通拥堵已经成为城市发展当务之急。另一方面,城市交通网络中存在着大量的不确定因素,如果在交通网络设计中忽视这些不确定性因素,可能会导致交通网络更加严重的拥堵。因此,不确定的交通网络设计问题的研究是必不可少的。当前,不确定城市交通网络设计的研究方法主要有随机规划和鲁棒优化两种,其中随机规划的方法需要事先假定不确定参数满足某种概率分布。然而,在现实中,由于缺少大量数据去校准这种概率分布,这种假定的概率分布可能不能用。而鲁棒优化的方法则不需要事先假定不确定参数满足某种概率分布。因此,应用鲁棒优化的方法研究不确定交通网络设计问题具有更加实际的意义。本论文基于鲁棒优化的方法,研究不确定的城市交通网络设计问题,探讨不确定交通网络设计问题的建模和求解算法。具体来讲,本论文研究工作主要有以下几个方面： (1)运用鲁棒非线性优化方法研究了基于用户均衡下不确定需求的连续交通网络设计问题,其中不确定需求属于一个椭球集合。通过运用鲁棒优化的思想和灵敏度分析的方法,我们将连续交通网络设计问题的鲁棒对应(Robust Counterpart,RC)模型转化为一系列带互补约束的数学规划问题(Mathematical Programms with Complementarity Problem, MPCC),并运用一种松弛算法求解这一系列的MPCC。另外,我们将它和Yin和Lawphongpanich[1]提出的鲁棒对应模型进行了比较。数值实验的结果表明,我们提出的鲁棒对应模型比Yin和Lawphongpanich[1]的鲁棒对应模型更加灵活,没那么保守。 (2)探讨了不确定需求下的鲁棒可靠性用户均衡模型,其中模型并不要求知道不确定需求的准确的概率分布,而仅需知道它的前m阶矩。基于最坏风险值(Worst-case Value-at-Risk, WVaR)和最坏条件风险值(Worst-Case Conditional Value-at-Risk, WCVaR)[2],我们定义了鲁棒分位走行时问和鲁棒均值-超量走行时问,并证明了两种走行时间在需求一般分布情况下是等价的。基于这种等价的走行时问提出了鲁棒分位用户均衡(鲁棒均值-超量交通均衡)模型,模型被表示为一个非线性互补问题(Nonlinear Complementarity Problem, NCP),并证明了模型的等价性和解的存在性。然后一种基于间隙函数的方法被用来求解这个非线性互补问题。基于提出的均衡模型,我们进一步研究了带分布式鲁棒联合机会约束的连续交通网络设计模型,通过利用Bonferroni不等式,模型中的分布式鲁棒联合机会约束被近似为非线性约束,我们应用积极集的算法求解近似后的模型,数值实验的结果验证了提出的模型和算法的有效性。 (3)运用可调整的鲁棒优化方法研究了基于元胞传输模型(Cell Transimission Model, CTM)[3-4]的单层动态交通网络设计模型,其中不确定需求被假定属于一个多面体集合。通过运用仿射决策准则和线性规划的对偶,我们构建了相应的仿射可调整的鲁棒对应模型,同时将它与传统的鲁棒对应模型进行了比较,数值算例的结果显示,可调整的鲁棒对应模型比传统的鲁棒对应模型更加灵活。 (4)基于元胞传输模型,研究了单层动态交通网络设计问题的分布式鲁棒联合机会约束模型,模型假定OD需求的概率分布是未知的,仅知道它的期望和方差。首先,我们将模型中的分布式鲁棒联合机会约束近似为最坏条件风险值约束,然后,利用锥对偶原理,将最坏条件风险值约束等价的转化为半定规划约束。另外,这种基于半定规划的近似被用来和基于Bonferroni不等式的近似以及基于二阶锥优化(Second-Order Cone Programming,SOCP)的近似进行比较。数值算例的结果证实了基于半定规划(Semidefinite Programming, SDP)的近似方法更加灵活,没那么保守,比基于Bonferroni不等式和基于SOCP的近似有更优的目标函数值 (5)基于元胞传输模型,通过利用最坏条件风险值,我们建立了不确定需求下的双层动态交通网络设计模型,其中不确定需求的概率分布被假定属于由几种已知概率分布所组成的多面体集合。基于下层的用户最优的最优性条件,我们将双层动态交通网络设计模型等价转化为带互补约束的数学规划模型。一种松弛的算法被用来求解转化后的模型,通过数值实验的结果证实了模型和算法的有效性。
[Abstract]:City traffic network design problem is the core problem of city comprehensive planning of the city, but also related to the long-term economic, rapid, harmonious and stable development of the basic problem. At present, with the rapid development of city, city traffic congestion has become more serious, the contradiction between supply and demand have become increasingly prominent, mitigation and prevention of traffic congestion has become a pressing matter of the moment. Another city development and there are many uncertain factors in city traffic network, if we ignore these uncertain factors in traffic network design, network traffic may lead to more serious congestion. Therefore, transportation network design problem of uncertainty is essential. At present, the research of uncertain methods of city traffic network design major there are two kinds of stochastic programming and robust optimization method, the stochastic programming need to assume the uncertain parameters satisfy a certain probability distribution. However, in reality, due to the lack of large amounts of data to calibrate the probability distribution, the probability distribution of possible this assumption can not be used. The robust optimization method is not required to assume the uncertain parameters satisfy a certain probability distribution. So it has more practical significance to design problem of robust optimization application of uncertain network traffic.
Based on the robust optimization method, this paper studies the design problem of uncertain urban transportation network, and discusses the modeling and solving algorithm of uncertain transportation network design.
(1) based on the robust of continuous transportation network design problem of user equilibrium under uncertain demand based on nonlinear optimization method, which belongs to an uncertain demand. By analyzing the ellipsoid set robust optimization thought and sensitivity of use, we will continuous transportation network design problem of robust counterpart (Robust Counterpart, RC) model into a series of mathematical programming problems with complementarity constraints (Mathematical Programms with Complementarity Problem, MPCC), and the use of a relaxation algorithm to solve this series of MPCC. also, we will model and corresponding robust Yin and Lawphongpanich[1] is proposed. By comparing the results of numerical experiments show that the proposed model than the corresponding robust robust Yin and Lawphongpanich[1] corresponding to the model is more flexible and less conservative.
(2) discuss the robust reliability of user equilibrium model under demand, the model does not require the exact probability distribution of demand uncertainty, and only need to know the first m moments. It's the worst value based risk (Worst-case Value-at-Risk, WVaR) and the worst condition risk value (Worst-Case Conditional Value-at-Risk. WCVaR [2]), we define a robust walking time and robust mean excess travel time, and proves that two kinds of walking time distribution in general demand are equivalent. Based on the equivalent time walking into a robust user equilibrium (robust mean excess traffic equilibrium) model, the model is formulated as a nonlinear complementarity problem (Nonlinear Complementarity, Problem, NCP), and proved the existence of equivalent model of reconciliation. Then a method based on gap functions are used to solve the non line Complementarity problems. Equilibrium model based on the proposed continuous transportation network design model we further studied with the distributed robust joint chance constraint, by using the Bonferroni inequality, a robust distributed joint chance constraints in the model is similar to the algorithm for solving the nonlinear constraints, we apply the active set approximation of the model, the results of numerical experiments validate the effectiveness of the proposed model and algorithm.
(3) the use of adjustable robust optimization method based on the cell transmission model (Cell Transimission Model, CTM) - dynamic traffic network design model of [3-4], the demand uncertainty is assumed to belong to a polytope. By using the dual affine set of decision criteria and linear programming, we construct the corresponding robust model the affine adjustable, and it corresponds with the traditional robust model were compared. The numerical results show that the robust model can adjust the corresponding than the traditional robust corresponding model is more flexible.
(4) the cell transmission model based on distributed robust design problem of single joint chance constraint model of dynamic traffic network, the probability distribution model assumes that the demand of OD is unknown, only know the expectation and variance of it. First, we will model the distributed robust joint chance constraint approximation for the worst conditional value at risk then, by using the cone constraint, duality principle, the conditional value at risk transformation constraints as semidefinite programming constraints. In addition, this approximation based on semidefinite programming is used to approximate and based on the Bonferroni inequality and is based on two order cone optimization (Second-Order Cone Programming, SOCP) were compared with the numerical approximation. The results proved that based on semidefinite programming (Semidefinite Programming SDP) approximation method is more flexible and less conservative than the Bonferroni inequality and the SOCP approximation based on better. Standard function
(5) based on cell transmission model, through the use of the worst condition value at risk, we established a double uncertain dynamic traffic network design model under demand uncertainty, the probability distribution of demand is assumed to be set by several known probability distribution composed of polyhedra. The optimality conditions based on the underlying user optimum. We will double the dynamic traffic network design model is transformed into a mathematical programming model with complementary constraints. A relaxation algorithm is used to solve the transformed model, the validity of the model and algorithm is verified by numerical experiments.

【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：F224;F572

【参考文献】