关闭

关闭

关闭

封号提示

内容

首页 可交易瓶颈许可证的交通网络对偶均衡模型

可交易瓶颈许可证的交通网络对偶均衡模型.pdf

可交易瓶颈许可证的交通网络对偶均衡模型

commander47.ak47 2012-07-05 评分 0 浏览量 0 0 0 0 暂无简介 简介 举报

简介:本文档为《可交易瓶颈许可证的交通网络对偶均衡模型pdf》,可适用于工程科技领域,主题内容包含  收稿日期:20111214修回日期:20120117  基金项目:国家自然科学基金资助项目(70672110)上海市教委科技创新项目(10YS1符等。

  收稿日期:20111214修回日期:20120117  基金项目:国家自然科学基金资助项目(70672110)上海市教委科技创新项目(10YS105)  作者简介:何胜学(1976)男陕西三原人副教授博士主要研究方向为超网络、交通网络建模、信息网络优化(lovellhe@126.com).可交易瓶颈许可证的交通网络对偶均衡模型何胜学(上海理工大学管理学院200093)摘 要:为了能实际求解可交易瓶颈许可证(TBP)均衡系统利用网络对偶均衡理论建立了TBP的交通网络对偶均衡模型。以路段和节点的均衡条件代替路径均衡条件并放松了节点流量的平衡条件和分时OD流量与总需求的平衡条件从而得到了TBP的互补问题方程。利用互补问题与变分不等式基本等价定理得到动态交通网络变分不等式模型。建构等价的非线性优化问题说明新模型的有效性并给出了基于时空网络的模型解的存在性判别方法。算例的求解验证了模型的可行性。关键词:交通工程可交易瓶颈许可证交通流分配变分不等式均衡中图分类号:TP301.6   文献标志码:A   文章编号:10013695(2012)07243804doi:10.3969/j.issn.10013695.2012.07.010TrafficnetworkdualequilibriummodelwithtradablebottleneckpermitsHEShengxue(SchoolofBusinessUniversityofShanghaiforScience&TechnologyShanghai200093China)Abstract:ThedualequilibriumtrafficnetworkmodelofTBPproposedbyusingnetworkdualequilibriumtheoremcansolvetheequilibriumsystemsoftradablebottleneckpermits(TBP).ThroughusingequilibriumconditionsonlinksandnodesinsteadofonpathsandrelaxingtheflowconservationconditionsonnodesandequilibriumconditionbetweentotaldemandandtimespecifiedODflowthispaperconstructedthecomplementarityproblems(CP)ofTBPsystems.ThecorrespondingVImodelmadeuseofthebasicequivalencetheorybetweenCPandVariationalInequalities(VI).Thengaveoutanequivalentnolinearprogrammingmodeltoshowtheeffectivenessofthenewmodelandalsogaveoutthemethodofjudgingtheexistenceofsolutionbasedontemporalspacialnetwork.AnumericalexamplewasgiventoshowthevalidityoftheVImodel.Keywords:trafficengineeringtradablebottleneckpermits(TBP)trafficassignmentvariationalinequalities(VI)equilibrium  如何缓解交通拥挤是交通领域的核心问题之一。随着信息通信技术的发展许多新的交通拥堵解决方法应运而生。2006年Akamatsu等人[1]提出了定量式的可交易瓶颈许可证管理模式。与以前的众多方法相比可交易瓶颈许可证系统实施方便操作性强具有兼顾社会公平和系统效益的特征。但是要将该理论付诸实施仍有许多理论与实践问题亟待解决如已知的基于一般交通网络的可交易瓶颈许可证均衡模型还没有有效的求解方法。目前国际上交通领域的相关研究很少国内还没有相关的研究发表。本文将从网络对偶均衡理论角度出发扩展已有模型的假设并给出问题的有效解法。Akamatsu等人[1]提出了可交易瓶颈许可证(TBP)理念并对TBP在单路段的简单网络上实施的有效性进行了分析。文中证明了实施TBP的系统在均衡态时等价于一个系统最优的动态容量限制流量分配模型。随后2007年Akamatsu[2]对TBP理论在一般路网上加以扩展给出了单OD对(originanddestinationpair)条件下TBP系统应用于一般路网的均衡模型并给出了对应的系统最优动态交通流分配非线性规划模型和模型有解的最小费用流算法。通过对比Akamatsu得出TBP在完全信息条件下等价于拥挤收费(congestionpricingCP)而在不完全信息条件下TBP系统有显著优势。Kikuchi等人[3]和Wada等人[4]利用多智能体理论对TBP系统的运行加以分析说明该系统能较好地收敛于系统最优状态但大量的假设参数妨碍了该方法的实用性。2009年Nagae等人[5]提出了可退还的交易瓶颈许可证(refundabletradablebottleneckpermitsRTBP)概念并基于单路段的简单路网对RTBP的实施进行了理论分析得出RTBP系统能更好地描述具有随机出行需求的交通网络系统提高系统的整体经济效益。尽管Akamatsu[2]对多OD对的一般网络模型也作了简单说明但对一般情况模型是否有解以及如何求解系统的均衡状态均未给出说明。本文将利用网络对偶均衡理论(networkdualequilibriumtheoremNDET)[6~8]对一般的TBP系统均衡模型约束加以放松从而得到适应性更强、易于求解的TBP系统变分不等式模型(variationalinequalitiesmodelVIM)。同时利用超级网络添加虚拟路段和虚拟节点方法[9~11]给出模型有解的时空网络验证方法。" 交通网络中的可交易瓶颈许可证系统"" 一般交通网络考虑一般交通网络G(NL)的动态交通流分配问题。N第29卷第7期2012年7月 计算机应用研究ApplicationResearchofComputersVol.29No.7Jul.2012是网络节点集合其中的一个节点用i表示L是路段集合其中的一条路段用(ij)表示i和j分别是路段的起点和终点。为了表述简单又不失一般性设网络中只有一对OD对(od)o和d分别是OD对的起点和终点。出行者将在给定的时间段I=[0T]之间完成出行。OD对(od)间总的出行需求给定为Q。假设任一路段(ij)均由两部分组成一部分是具有固定行程时间tij的自由通行段另一部分是具有最大通行能力μij的瓶颈点排队段。对任一路段而言tij和μij已知且不随时间变化。这里对路段的假设具有通用性如实际路段有多个瓶颈时可将其分为多个路段而当路段无瓶颈限制时可假设对应的最大通行能力为无限大。" BC交易市场和管理信息平台所谓的TBP指的是允许该许可证持有者在特定时间通过特定路段通行瓶颈的一种权利[1~5]。实施TBP系统的目的就是缓解并消除城市交通拥堵实现社会效益最大化[2]。已有的TBP研究均假设网络中存在一个系统管理者和众多的路网使用者。管理者基于社会效益最大化对路网瓶颈的通行权加以管理具体体现为向路网使用者投放适量的TBP并保证TBP系统在路网上的顺利实施。而路网使用者则需要事先决策抵达目的地时间和出行路线购得相应路段的瓶颈通行许可证。出行者购得相应TBP后具体出行途中可通过交通专用短程通信(dedicatedshortrangecommunicationDSRC)系统获准在特定时间通过特定瓶颈。管理者可通过路网瓶颈利用情况调整TBP的投放量。出行者通过基于网络信息平台的TBP拍卖市场购买TBP。已有研究均假设相应的TBP拍卖市场处于完全竞争状态能有效地分派TBP资源平衡市场供需。但是现实中要求出行者事先选择合理出行路线和到达目的地时间并不可行同时如果所选路线涉及大量的路段TBP购买时期望出行者能通过相关TBP市场购得合理价格的瓶颈通行许可证也不现实。因此除了提供开放灵活的TBP交易平台管理者还应当为出行者提供基本的出行路线相关信息、针对具体TBP设定一个市场参考价以及其他的相关服务。同时由于交通网络流的动态特征管理者也应对网络的意外情况加以合理处置从而减少出行者的不确定性损失。基于上述认识在原有TBP系统中增加一个管理信息平台就很有必要。一个有效的管理信息平台必须具有关于路网的基本状态和出行者特征的必要知识同时能处理相关变化信息为出行者提供路线选择、路线通行时间以及TBP价格等信息。只有在TBP交易市场和管理信息平台的共同作用下TBP系统才更好地付诸实施相关的社会效益才能得以有效实现。建立TBP系统的管理信息平台表明有效求解已有TBP系统的均衡模型的紧迫性和重要性这也正是本文研究的意义所在。 可交易许可证系统的对偶均衡模型" 节点流量均衡条件在网络中任意节点i处在时刻tI进入该点的流量应当大于从该点流出的流量。同时对应OD对节点i存在一个从OD对起点到达该点的广义费用πi(t)。t表示用户达到i点的时刻。根据NDET的建模规则[6~8]在节点处有如下流量均衡条件成立:(kNI(i)zki(t)-kNO(i)yik(t)-q(t)δid)πi(t)=0kNI(i)zki(t)kNO(i)yik(t)+q(t)δidπi(t){0 iNtI(1)其中:Zki和Yik分别表示在时刻t流入和流出节点i的流率NI(i)表示以i为终点的路段的起点集合NO(i)表示以i为起点的路段的终点集合。当i也是OD对终点时Gid取1否则Oid取0值。q(t)表示t时刻达到OD终点的流率。 路径选择均衡条件对于t时刻进入路段(ij)的用户设定其利用路段(ij)的广义行程费用cij(t)为对应行程时间tij的时间价值αtij和购买该路段TBP的费用Pij(t)之和。α表示时间与费用的转换系数。根据NDET的建模规则[6~8]在路段处有如下路径均衡条件成立:(πi(t)+cij(t)-πj(t+tij))yij(t)=0cij(t)+πi(t)πj(t+tij)yij(t){0(ij)LtI(2)式(2)等价于在到达目的地时刻确定条件下用户选择具有最小费用的路径出行的路径选择条件[2]。假设对任意路段(ij)而言网络流量满足先进先出原则(firstinfirstoutFIFO)即Aij(t)=Dij(t+tij(t))(3)这里Aij(t)和Dij(t)分别表示t时刻累积进入和离开路段(ij)的流量。相应的流率形式为yij(t)=zij(t+tij(t))(1+dtij(t)/dt)(4)其中:tij(t)表示t时刻进入路段(ij)的用户在路段(ij)上的行程时间。在TBP系统下tij(t)为定值因此式(3)简化为yij(t)=zij(t+tij(t))(5)' 分时>流率与>总需求的均衡条件根据NDET的建模规则[6~8]分时OD流率与OD总需求存在如下关系:(T0q(u)du-Q)ρ=0T0q(u)duQρ{0(6)其中:ρ表示OD对间最小的广义行程费用。( 目的地到达时刻的选择条件对于选择t时刻到达OD终点的用户而言实际达到的时间t与期望到达的时间可能存在差异。由这种差异导致的费用称为计划费用(schedulecost)[2]用w(t)来表示。用户在对目的地到达时间的选择时需考虑相应的广义网络行程费用和计划费用。在相互博弈下目的地到达时间的选择需满足(πd(t)+w(t)-ρ)q(t)=0πd(t)+w(t)ρq(t){0 tI(7)) BC价格的决定条件路段(ij)上t时刻的TBP价格由TBP的供需情况决定。而对路段(ij)而言t时刻TBP的供给量是一个定值等于对应瓶颈的最大通行能力μij。当对TBP的需求大于供给时对应路段对应时刻的TBP价格为0而当需求大于供给时通过网上拍卖市场会产生一个相应的TBP价格。具体的TBP价格均衡条件如下:9342第7期何胜学:可交易瓶颈许可证的交通网络对偶均衡模型   (μij-yij(t))pij(t)=0μijyij(t)pij(t){0 (ij)LtI(8)* BC的DE,将流量项y、q与费用项π、ρ、p看做系统状态变量X在互补均衡条件式(1)(2)及式(6)~(8)中与之互补的式子构成状态函数。根据互补问题与变分不等式的基本定理可以得到对应上述互补均衡条件式的VIM为F(X)(X-X)0X0。这是一个以约束集为变量的非负空间的基本VIM。对于这类问题存在许多有效的求解算法其中文献[8]给出了分阶段阶梯式梯度投影算法可以有效地求解上述VIM。' 等价动态系统最优分配模型'" 动态系统最优分配模型考虑下面的优化模型(P-1):min(qy)0Fp(qy)T0q(t)w(t)dt+α(ij)LT0yij(t)tiddt(9)约束:T0q(u)duQ(10)yij(t)μij (ij)LtI(11)kNI(i)yki(t-tki)kNO(i)yik(t)+q(t)δid iNtI(12)在文献[2]中上面的约束式(10)和(12)是等式。考虑到目标函数是使得网络中用户总费用最小因此在均衡态条件下不等式(10)和(12)必取等号。因此这里的模型P-1与文献[2]中相应模型等价。文献[2]证明了其给出的动态系统优化模型与TBP系统均衡模型等价。因此只需证明模型P-1与本文第2章的互补均衡条件等价即说明对应VIM模型合理表征了TBP系统均衡状态。设ρ、{p(t)}和{π(t)}是分别对应约束式(10)~(12)的拉格朗日乘子。得到问题P-1的拉格朗日函数L为:L(qyρπp)Fp(qy)+ρ{Q-T0q(t)dt}+(ij)LT0pij(t){yij(t)-μij}dt+iNT0πi(t){kNO(i)yik(t)+q(t)δid-kNI(i)yki(t-tki)}dt(13)利用L的KuhnTucker条件问题P-1的最优解的充分必要条件为L/q(t)=0 ifq(t)>0L/q(t)0 ifq(t){=0 tI(14)L/yij(t)=0 ifyij(t)>0L/yij(t)0 ifyij(t){=0 (ij)LtI(15)L/ρ=0 ifρ>0L/ρ0 ifρ{=0(16)L/pij(t)=0 ifpij(t)>0L/pij(t)0 ifpij(t){=0 (ij)LtI(17)L/πi(t)=0 ifπi(t)>0L/πi(t)0 ifπi(t){=0 iNtI(18)对式(14)~(18)加以计算易知其等价于第2章的互补均衡条件。至此证明了问题P-1与TBP的VIM的等价性。当然求解TBP的VIM不仅可以得到网络的流量项也可得到相关的费用项。文献[7]证明了利用对偶问题的部分解可以加速基本VIM的求解速度因此若能迅速求解问题P-1可加速TBP的VIM的求解算法收敛。' 具有多对一形式>对的模型解的存在性文献[2]给出了单OD条件下相应优化模型的求解方法。下面将该方法推广到多起点单终点的情况。首先将时间段I分为M等份每一等份时长为Δt。其中的时间分界点表示为t=mΔt(m=012…M)。并假设任意路段(ij)的行程时间tij均为Δt的倍数即存在整数nij使tij=nijΔt成立。设共有R个OD起点。下面建立原网络的时空网络步骤如下:a)生成原网络G(NL)中所有节点的M+1个拷贝。对任意节点i用i(m)表示它的第m个拷贝代表时空网络中节点i在时刻mΔt的位置。b)对任一OD起点Or生成对应的一个虚拟起点Or并生成一个总的虚拟OD起点O和一个虚拟的OD终点d。c)对所有的m如果存在路段(ij)生成一个连接i(m)和j(m+nij)的时空路段。新的时空路段具有与原路段相同的tij和uij。d)对所有r连接Or与所有对应的or(m)生成行程时间为0、无最大通行能力限制的新时空路段。连接O与所有的Or生成行程时间为0、最大通行能力限制等于OD需求Qord的新时空路段。连接所有的dm与d生成行程时间为w(mΔt)、无最大通行能力限制的新时空路段。在上述生成的时空网络G(NL)中以O为起点、d为终点求解相应的最小费用最大流问题对应多起点单终点的优化问题P-1。观察连接O与所有的Or的时空路段是否达到了其最大通行能力可以判断对应优化问题是否有解。与上述方法相似可以方便地处理单起点多终点的优化问题。但是对于多对多的情况为了利用上述方法判断模型解的存在性首先需要引入网络出行者的一个行为原则优先出牌原则[12]。这一原则指具有不同起讫点的出行者当其实际出行距离或时间越大时会越早做出路线选择决策且做出决定后越不易改变原定方案。基于上述原则可通过三个步骤判断模型解的存在性:a)不考虑瓶颈收费对所有OD对按照最小行程时间的大小从大到小排序b)按照上面建构时空网络的方法建构多OD的时空网络c)按照一定的比例如2:2:2:2:1:1依OD的排序将相应的OD流量逐步依据当前最优路径加载上网加载不断剔除已经达到路段通行能力的时空网络路段。如果按上述方法所有流量可以顺利加载上网说明模型的解存在否则解不存在。( 数值算例图1是一个有11条路段的简单网络其中包含两个OD对:OD对(15)的需求量为30OD对(26)的交通需求量为20。考虑时段I=[014]离散化后Δt=1。设对应OD对(15)和(26)的计划费用函数分别为w(t)=2|t-8|+3和w(t)=2|t-9|+4。各路段的固定行程时间tij和Δt时段内的最大通行量μij如表1所示。设行程时间与费用的转换系数α=1。表1 路段的行程时间tij和最大通行量μij路段标号1234567891011tij34253223544μij10857944117640442计算机应用研究 第29卷  利用文献[8]提供的算法经编程计算可得ρ(15)=11ρ(26)=15非零的TBP价格项有p1(2)=1.953p3(2)=2.051p3(3)=3.857p3(4)=5.872p11(5)=1.93。这里ρ的下标是OD对p的下标是路段的标号。相关的非零路段流量如表2所示。表2 标明进入时刻的路段流量路段标号(进入时刻)流量路段标号(进入时刻)流量路段标号(进入时刻)流量2(0)5.0123(4)3.6215(5)4.9951(1)7.2498(2)3.9088(6)7.8131(2)9.8548(3)0.1775(6)4.2831(3)7.7465(3)0.4127(5)0.3691(4)9.2666(3)0.0845(7)0.4723(0)4.3778(4)8.08311(5)3.9953(1)0.6575(4)5.82211(6)0.3573(2)5.3956(4)0.01610(4)4.1953(3)5.0088(5)10.016  对于OD对(26)而言可以找出已经被选用的路径比较其广义的通行费用是否相等从而判断计算结果的合理性。具体比较数据如表3所示。表3 OD对(26)间部分已选用路径广义费用比较路径路段序列出发时刻路径广义费用3511535213+p3(2)=15.0513549+p3(4)=14.87235311+p3(3)=14.8573811013+p11(5)=14.9313675115  从表3可以看出OD对(26)间已选用的路径的广义通行费用基本相等这证明了结论的合理性。同理对于OD对(15)间已选路径广义费用的分析可以得到同样的结论。) 结束语在原有的TBP系统中引入管理信息平台可以有效提升TBP的实施效果加强TBP市场管理。但是引入管理信息平台必然要求管理者对路网整体状态、用户特征以及相关信息技术有相当程度的把握。本文建立可以方便求解TBP系统对偶均衡模型就是为TBP的实施工程中管理信息平台的创建提供理论技术支持。将TBP系统应用于实际还有许多工作需要完成如建立随机需求下一般网络中的TBP均衡模型和TBP系统与CP的融合问题。参考文献:[1]AKAMATSUTSATOSNGUYENXL.Tradabletimeofdaybottleneckpermitsformorningcommuters[J].JSCEJournalofInfrastructurePlanningandManagement200662(4):605620.[2]AKAMATSUT.Asystemoftradablebottleneckpermitsforgeneralnetworks[J].JSCEJournalofInfrastructurePlanningandManagement200763(3):287301.[3]KIKUCHISAKAMATSUT.DynamicsofdecentralizedMultiagentsystemsforimplementingtradablenetworkpermits[J].InfrastructurePlanningReview200825(3):589596.[4]WADAKAKAMATSUTKIKUCHIS.Convergenceofdaytodaytrafficflowdynamicsundertradablebottleneckpermits[J].UrbanTransport200814(3):579588.[5]NAGAETGAIN.Tradablebottleneckpermitsunderdemanduncertainty[C]//Procofthe14thHKSTSInternationalConferenceonTransportationandGeography.2009:771778.[6]HEShengxueFANBingquan.Generalizedwardropprincipleanditsapplicationinregionaltransportation[J].TransonResearchRecord20082085(1):4956.[7]何胜学董琼徐福缘.基于网络对偶均衡的交通流分配模型[J].公路交通科技201027(9):105110.[8]何胜学董琼徐福缘等.基于投影动态系统理论的网络交通演化模型[J].系统工程201028(4):3540.[9]何胜学.基于超级网络的区域综合运输网络理论模型与算法[D].上海:上海理工大学2007.[10]何胜学范炳全.城市交通网络非稳定随机均衡分析[J].中国公路学报200821(3):101105.[11]何胜学董琼徐福缘等.含目的地选择的城市交通网络非稳定均衡分析[J].系统工程201028(1):813.[12]何胜学何建佳徐福缘.基于网络对偶均衡的有边约束的交通流分配模型[J].交通运输系统工程与信息201111(2):100105.(上接第2437页)[7]BERPARKMJBERNARDIFOLIVUCCIMetal.Molecularmechanicsvalencebondmethodsforlargeactivespacesapplicationtoconjugatedpolycyclichydrocarbons[J].ChemicalPhysicsLetters1994217(56):513519.[8]谭福平刘洪刚.Winograd矩阵乘法算法用于任意阶矩阵时的一种新处理方法[J].应用数学与计算数学学报200418(1):9498.[9]周德俊邢永丽.SW型二阶矩阵快速乘法的最少乘法运算次数[J].工程数学学报199916(1):909423.[10]周德俊林彦芬田增保.二阶矩阵快速乘法的一个新的算法集合[J].高等学校计算数学学报199618(04):380383.[11]古志民孙贤和.并行计算机系统结构与可扩展计算[M].北京:清华大学出版社2009.[12]章隆兵吴少刚蔡飞等.PC机群上共享存储与消息传递的比较[J].软件学报200415(6):842849.[13]陈华范宜仁邓少贵等.基于多核微机的微粒群并行算法[J].计算机工程与应用201046(13):3739.[14]章隆兵吴少刚蔡飞等.适合机群OpenMP系统的制导扩展[J].计算机学报200427(8):11291136.[15]CHENYongjianSHUJiwuLIJianjiangetal.StaticanalysisofOpenMPdirectivenestingtypesanditsapplication[J].JournalofSoftware200516(2):194204.[16]顾丽红吴少刚章隆兵等.针对非规则应用的OpenMP制导扩展[J].小型微型计算机系统200526(1):124128.1442第7期何胜学:可交易瓶颈许可证的交通网络对偶均衡模型   

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +1积分

资料评分:

/4
0下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料