带路票约束条件的用户均衡网络模型

带路票约束条件的用户均衡网络模型

1973年，达拉提出了管理污水排放的概念，这一概念主要是为了实现控制污水的排放。近年来,有些学者将这一思想引荐到交通领域以缓解城市交通拥堵,由此产生了路票交易体系。Yang等1在票款限制下，用户的基本数学模型1.1旅行时间费用首先定义一个交通网络G=(N,A),用W表示起讫点对(OD对)w,R本文中所涉及的出行成本一般指广义费用,它是对流量速度关系、距离、旅行时间等的总称。由于旅行时间直接影响出行者的路径选择行为,因此这些属性中最重要的是旅行时间。通常情况下用户出行成本包含车辆本身的运行成本(一般包括燃料的消耗、轮胎的磨损等)以及旅行时间费用(即旅行时间所体现的价值)。一般情况下,采用旅行时间来代替广义费用值不会产生较大的误差。当有路票容量约束时,本文所提及的出行费用将包括两部分:传统的旅行时间费用和出行时选择路径的路票成本。路票成本则是收取的路票数量与价格之积(即pκ式中:t需要解释的是,式(1)中的旅行时间和路票的量纲不一致,在后面计算时需要通过旅行时间价值换算系数θ来进行转换,θ在物理意义上表示驾驶员社会经济属性及收入水平,在本文中的物理意义则表示使用者能够为单位旅行时间所承受的价格。假设出行者均是同质的,则通过变换得到的实际出行费用为:在确定了广义出行费用之后,需要对出行路径的选择作一定的说明。根据Wardrop第一原理,在假设所有出行者均能独立做出使自己出行成本最小的决策前提下,相同OD对之间的所有使用路径的成本相等并且最小,所有未被使用路径的成本大于或等于使用路径的成本。该用户均衡模型可以下式来表示:1.2有路票总量约束的动态分析根据上文对出行费用及出行路径选择定义的描述,对比前文对路段及节点容量约束下的用户均衡网络流模型的建立,路票约束的固定需求模型也可以用下面的非线性规划问题来描述:满足:上述模型中,式(6)和(8)分别表示路径流量与OD交通量守恒以及路径流量和与路段流量守恒条件。除此以外,在路票约束下,其本身也存在固有的均衡条件,即在路网中所有路段使用者所缴纳的路票总数应小于或等于路票发行总量K,即式(9)。同时在路票交易市场中存在一定的清算条件,当所有路票均使用时,路票价格大于零,当路票未被完全使用,路票的均衡价格为零。用公式表示如下:需要特别说明的是,K表示的是路票总量,一般由政府发放,其取值在很大意义上能够决定模型是否有最优解。当K的取值过小时,使用路票无论选择哪条路径,路票总量均不够,模型无解;当K的取值过大时,使用者所累积的路票足够多,这样就不需要在路票交易市场中存在买卖,通过发行路票来缓解交通拥堵的作用也就弱化,从一定意义上讲路票就成了可有可无的废票。对于K的取值,政府可预先估计初始值,通过每一期(一般是一个月)路票的运行效果逐步调整,最后得出路票的最优发行量。带有路票总量约束条件的用户均衡模型的目标函数是带有线性约束的严格的凸函数,该非线性凸规划问题有且只有唯一的路段流量最优解,路径交通量不唯一。其最优化的充要条件可用(karush-kuhn-tucker,KKT)条件表述。用p表示路票约束的拉格朗日乘子,μ表示路径流量守恒条件约束的拉格朗日乘子,则该约束模型的KKT条件表述如下:很明显可以看出上述公式与UE模型是等价的,其中拉格朗日乘子p在路票交易市场中的物理意义是表示路票的均衡价格,而拉格朗日乘子μ的物理意义则是最小费用。根据1.1节中对于出行成本的定义,本文采用以上就是路票约束下的用户均衡网络流最优化问题,对于一个给定的路票方案,当存在至少一对OD对之间的多条路径的路票收取量不同时,该模型一定存在唯一解。2模型算法的设计2.1算法的初始和主要参数路票约束问题在本质上是带有线性约束的非线性规划问题,根据目标函数的描述,该模型是关于路段流量的最优化凸规划问题,具有唯一的最优路段解。这类问题的求解,一般都是将问题转化成无约束的最优化问题。基于路票约束条件与路段容量约束类似,基于路票约束的模型求解采用增强拉格朗日乘子法在路票交易体系中,均衡网络问题可用下面的模型来表述:式中:s是松弛变量,其主要目的是将不等式约束条件转化成等式约束条件。这样路票约束下的交通网络均衡问题与上述问题等价的模型为对比式(18)和(19),并求极值,得可以得到下式:由此可以得到路票约束下的增强拉格朗日函数,即更新拉格朗日乘子,可得拉格朗日乘子和惩罚参数的初值采用以下公式来确定:本文采用的收敛准则为关于模型求解的子算法,本文选用牛顿算法,路票约束下的牛顿算法与传统均衡问题的算法略有不同,主要体现在旅行时间上。新的路段旅行时间为算法的步骤如下。初始化:产生路径解。步骤0:设置内循环迭代次数等于零,n=0;所有路段流量等于零,x步骤1:迭代次数递增,n=n+1。步骤2:更新路段旅行费用;最短路径搜索,找到最新的最短路k步骤3:在路径集中添加最新的最短路。如果k均衡化:在路径集进行交通量分配。步骤4:计算路径流量的移动方向其中,步骤5:如果步骤6:根据路径流量的可行性计算极限步长,步骤7:通过路径流量的移动方向,计算路段流量的移动方向,步骤8:计算路段流量的最优步长,步骤9:综合路径、路段流量的要求得出最优步长,λ步骤10:更新路径、路段的流量:收敛判断:如果满足下面条件,就停止内循环迭代。步骤11:如果2.2拉格朗日乘子法根据上文对路票约束下的增强拉格朗日乘子法的描述,结合子算法牛顿算法,基于路票约束条件的用户均衡网络流分配算法的流程可表示如下。步骤1:求解传统交通网络均衡模型,得到传统无约束条件下的路段交通量和路径交通量的最优解。步骤2:给出拉格朗日乘子初值μ步骤3:调用牛顿算法主循环,运用增强拉格朗日乘子法求解带路票约束的交通分配问题,获得与乘子及惩罚参数相对应的路段交通量。步骤3.1:获得均衡网络交通流的初始解。步骤3.2:进行收敛性检验,若满足收敛条件,转入步骤4,否则,转入步骤3.1。步骤4:按照式(25)更新乘子的值μ步骤5:按照式(29)进行收敛检验,若满足,结束循环;否则转入步骤3。3实行路票政策后的效应如图2所示,对于起终点为A、B的OD对之间,有路径1和路径2,分别收取6个单位和2个单位的路票数,即k若不实施路票交易体系,根据传统的用户均衡原理,有下列公式:很容易可以解得x当实行路票交易后,根据用户均衡模型原理及路票均衡条件,运用增强拉格朗日乘子法,拉格朗日乘子初值取μ根据所有使用路径的路径费用都相等,路票交易价格可用下式求得:通过对比两组解,可以明显看出,在实行路票政策以后,路径1上会有部分流量转移到路径2上,使高流量路段的交通量减少了25%。相对于传统的路径流量分配不均匀的现象,当路径1和2的道路条件相同,这种流量的转移是非常可喜的,不仅使路径1的拥挤得到缓解,同时还能够充分利用路径2的道路资源。这也充分说明了路票政策缓解交通拥堵的可能性及原理,即通过引入路票来改变用户出行费用,从而间接影响用户的出行选择。4用户均衡问题传统求解算法构建了路票交易模型并设计了求解算法。构建所得的模型是带线性约束的非线性规划问题。