一类基于拉格朗日的分裂算法求解交通均衡问题

前言（1）选题的目的和意义近年来我国的交通设施越发发达，交通需求量大大增加，便利的交通出行工具为我们提供了很大的方便.但是这也引发了一系列的社会影响，比如交通堵塞问题的频繁出现，这已经成为了许多城市的发展瓶颈，大大限制了社会的发展.所以交通均衡问题就成为了我们不得不面对的话题.交通流量分配是交通规划的一个重要的组成成分，在交通规划中占据了核心的地位交通均衡问题是一类约束优化问题，交通资源是有限的，出行者的数量也是有限的.当所有出行者都选择某一条道路出行时，他们就需要争夺交通资源.当此条道路的交通资源被耗尽时，会造成交通拥堵情况.所以此时就需要一个控制机制来进行交通资源的分配，这个控制机制需要尽量保证交通流中的每一出行者都能够充分利用有限的资源，并且不会对道路中的其他出行者造成不必要的干扰，同时得到每个出行者较高的满意度.这个控制流程就成为交通均衡原则，系统将调查得到的OD对之间的交通流量进行记录，从而形成一个OD矩阵，然后再将现有的交通出行流量均匀合理的分配到交通网络的各条道路上.研究交通均衡问题，就是要调节均衡各个道路上的交通量，做好交通流量的分配任务，以寻求交通网络利益最大化和花费最小化，使得更加科学的利用基础设施，实现交通流量需求和流量容纳量的均衡发展.为了对交通网络的需求模式进行掌握，我们通常以起点-终点相关矩阵或需求函数来描述，交通模型的研究基于当提供给不同的供给和需求时，何时达到花费最小化并且交通网络中没有拥堵现象[1].根据这一定义，Wardrop等人提出了用户均衡模型，模型假设道路使用者的出行需求都是固定的，并且他们都能够准确的得知道路交通网上的所有出行信息[2].但是交通出行反而是一种随机现象，并且道路出行者对道路的理解能力也是一个随机变量，因此这种前提是很难被满足的，所以有许多学者从事于研究更加适用于现实需要的网络交通模型.在1977年由Daganzon和Sheffi等人提出了随机用户均衡系统[2]，此随机用户均衡模型将交通出行者对于道路的理解程度以及选择出行道路定义为了一个随机变量，这就很好的解决了此前Wardrop提出的交通均衡模型难以满足的问题，随机用户均衡体系统一了随机分布和交通均衡的概念，更适用于现实实际.然而，在中国的城市交通中，交通工具鱼龙混杂，研究混合型交通均衡问题更适用于中国的交通体系.混合型交通均衡问题就是各种交通出行方式共存于一个交通网络中，因此使用单一的出行模型去描述实际的交通状况是不适宜的[2].本文通过运用研究变分不等式相关理论，提出了两类改进算法，并适用于研究均衡配流问题中.道路出行者可根据模型求解得到的数据进行分析从而得出最优出行决策，更好地利用交通资源，使得资源供应量与需求量维持平衡，道路网络维持稳定[1]．(2)国内外文献综述：交通分配在交通规划中占据着重要的地位，交通分配就是指将交通流量矩阵在一个指定的道路交通网络中，更为合理以及符合实际的分配到道路交通网络的每条道路上，从而可以得到道路交通网络中的各条路段的实际出行交通流量.近几十年众多学者都在进行对于交通流量的分配研究.其实在早些年人们就已经认识到交通出行时间、道路拥挤程度等都会影响出行者选择相应的道路，但是由于缺乏系统的理论知识和计算的算法，人们不得不依靠经验进行判断[3].20世纪50年代以后，美国人BPR，HR通过研究交通转移率从而提出了一种转移概率曲线的方法，这可以称之为交通分配理论的初始尝试[4].1957年，Moore和Dantzin发布了搜索网络中两点之间的最短路径的方法，该方法对交通流量的分配原则发展具有着深远的影响[5].在Carroll和Schneider等人的努力之后，在20世纪50年代后期，基于最短路径方法的“全有全无”方法被应用于交通分配问题中[2].“全有全无”方法从出行者的角度考虑，遵从出行者的选择来进行交通流量的分配，该方法的运行机制是将所有起讫点之间的交通流量需求进行分配.但是显然结果与实际交通状态不尽相同.为了避免这种不合实际的情况，在随后的研究中又有许多专家提出不同的分配算法，其中较为符合实际并且计算结果较好的是Mclanghlin方法[6]，即交通容量限制和概率分配方法.1952年，Wardrop第一个提出交通流均衡的原则，它是交通均衡问题的开端，交通均衡原则指出，道路的出行者会在起止讫点之间选择出行成本最小的道路通行，而出行成本较高的道路则将不会被选择.Wardrop的交通均衡原则虽然被较早提出了，但是由于数学算法的难以实现，其研究一直没有实质性的进展.在1956年，Bankmann基于Wardrop均衡模型进行研究，最终得到了解决Wardrop难以求解问题的方法，完善模型和求解问题提供了很大的帮助，他们的研究已经形成了比较完整的均衡理论体系，在交通分配理论体系中占有着很大的权重.(3)研究的内容及预期目标：更加合理地调节交通流量配置，从而实现交通需求与道路通行容量的平衡，防止堵塞现象的发生.第1章：绪论23弹性需求下的用户均衡配流模型5章：总结及展望总结论文的思路结构，提出一些合理化的建议，并提出对未来工作的展望绪论凸优化问题凸优化问题的研究已经进行了很长时间，早期研究的线性最小二乘问题和线性规划问题属于凸优化的特殊形式.随着各个学科领域的交叉融合，凸优化问题可以解决许多领域的实际问题，具有着重要的作用[7].一个凸优化问题可以描述为：（1-1）其中是一个凸函数，并且可行范围为凸集.当问题的目标函数为可分离的情形时，则有如下式子：（1-2）其中目标函数为闭凸函数，，是给定的向量，并且可行集为凸集.由于凸规划问题可视为求凸函数在其定义域上的极小点，可得以下性质：凸规划的任一驻点是极小点凸规划的任一极小点是全局最优点变分不等式变分不等式在应用数学领域中发挥着重要的作用，它也是偏微分方程的一个重要分支.其求解的数值方法出现在1972年，后来出现了梯度外推法等一系列算法.目前变分不等式已广泛应用于均衡、运筹学问题等[8].利用变分不等式的知识，我们更方便的研究与凸优化有关的一系列问题.变分不等式(记为)的一般形式如下：找一点，使得，（1-3）其中是的非空闭凸子集，是到上的一个映射.定理1.2.1若在闭凸集上是连续的可微凸函数，假设是优化问题（1-1）的最优解，则也是变分不等式（1-3）的一个解.证明如下：分析如下凸优化问题，其中是一个的可微凸函数，，若是问题（1-1）的最优解，等同于假设且，进而等同于假设于是问题，(1-4)的解.定理1.2.1可以说明在目标函数连续可微的条件下，凸优化问题与变分不等式可以进行相互转换，即求解（1-1）问题就等于求解（1-5）的变分不等式问题，用符号语言表示为：找一点，使得，(1-5)故由此我们可以了解到数学中的许多凸规划问题，都可以借助转化得到的变分不等式问题进行求解.当凸优化的目标函数为可分离的形式时，我们拿出拆分为三个函数的形式进行考虑：(1-6)其中目标函数为闭凸函数，，是给定的向量，并且可行集为凸集.问题(1-6)的目标函数是由三个可分离的凸函数构成的，这类优化问题在运筹学交通均衡等方面都有着广泛的应用[7].令为(1-6)中线性约束对应的拉格朗日乘子.则(1-6)的一阶优化条件为：找一点，使得不等式(1-7)成立.对，令，，(1-8)则(1-7)可以写成我们寻找一点使得变分不等式(1-5)成立.由此可见，变分不等式问题与凸优化问题是紧密相连的.这样的变分不等式不仅仅是最小化一个目标函数的简单优化问题，它也可以将凸优化问题理解为一类特殊的变分不等式问题.所以求解变分不等式常在凸优化理论框架内进行研究.1.3预备知识定义1.3.1.给定凸集和，如果满足下式，则称关于是单调的.(1-9)定义1.3.2.令映射，若满足下式，则称在上单调.(1-10)命题1.3.1假设关于是单调的，则序列是有界的，并且收敛到任一.算法及改进增广拉格朗日算法在凸优化问题（1-1）中，可行域通常有如下形式：.为了使有约束问题转换为无约束问题，我们对线性约束引入拉格朗日乘子(可以衡量灵敏度)，得到其Lagrange函数：(2-1)如果点满足不等式(2-2)则此点称为拉格朗日函数的鞍点，(2-2)可表示为(2-3)若是可微的，记，则(2-3)可表示为(2-4)若令，则(2-4)可表示为，.为了增强对偶上升法的鲁棒性和放松目标函数的强凸约束，我们再引入一个罚参数，可得到其增广拉格朗日函数：(2-5)ALM算法的迭代步骤为：ALM算法也称为增广拉格朗日乘子法.ALM算法是一种经典的解析方法，引入参数的目的是可以将有约束的优化模型问题转化为无约束优化模型问题.对于问题1-6，其ALM的迭代步骤为：给定点通过以下步骤产生新的迭代点，其中并行分裂的增广拉格朗日乘子法是可以很有效的求解优化问题.对于约束条件较多、条件较复杂的情况，该方法可以很好地得到计算结果[9].但在计算过程中，需要同时计算多个原始变量，这是计算量很大的问题，且没有考虑(1-6)问题可分性问题的特殊性[10].ADMM交替方向乘子法ADMM算法是广泛使用的一种优化算法.它在统计、图像处理等大规模优化领域的问题中得到了广泛的应用.它是ALM算法的扩展.ALM算法削弱了对偶上升法的收敛条件，但由于在计算优化步骤中引入了一个二次项从而导致不可能分别求解每个原始变量[11].为了改进这一问题，Gabay、Mercier等人希望将乘数法的收敛性与对偶升序法的可分解可解性相结合，提出ADMM算法来解决可分凸优化问题[12].ADMM是一个经典的算法应用在许多领域，如矩阵优化、图像处理等.ADMM算法的求解步骤：(2-6)其中ADMM迭代算法是在原方法的迭代步骤基础上中又增加了一个高斯赛德尔分解[7]，因此函数可以被分步计算，大问题被转化为小问题，从而可以简化目标函数的迭代，达到使子问题的求解变得更加容易的目的.但是原始变量交替计算需要大量的时间，而且目标函数为三个及以上的这类凸优化问题的收敛性还不能确定，这意味我们不能够直接运用算法(2-6)去解决(1-6)这类问题.为了解决这一问题He等人提出了PSALM算法来求解这类凸优化问题[13].PSALM并行分裂算法PSALM算法的求解步骤：相比于ADMM算法，PSALM算法可以实现优化问题分离的特点[8]

，因此这两类算法对于求解结构性变分不等式问题十分有效，同时PSALM算法可以同时计算多个原始变量，大大的节省了计算时间，所以PSALM算法更适用于求解大规模凸优化问题. 为了更加容易的求解此类问题，在此之后又有许多学者对此类算法进行了创新和改进.例如，有一些学者采用限制修改算法中对应参数的取值范围，从而达到调整算法的迭代速率的办法，还有一些学者在研究过程中向子问题中添加一类扰动项，使得子问题的每个对应函数都完全单调，从而实现近似解决子问题的目的.例如，He等人利用交替方向法求解具有单调性的变分不等式问题时，将惩罚参数控制在一定范围内进行迭代运算，运行得到的结果效果较好.ADMM-split算法考虑(1-6)情况，首先算法由给定的初值先产生预测的迭代点，再产生修正步，其算法框架如下：.给定，和.令.产生预测点：.修正迭代点：.停机准则：如果则停止，否则令，转.对于ADMM-split算法，其预测步骤中三个原始变量迭代求解.校正步骤中算法只对第三个原始变量进行修正，且这种算法是收敛的.考虑到这个因素，本文提出一种新的算法.改进的基于增广拉格朗日分裂算法2.5.1改进算法1.给定，和.令.产生预测点：(2-7).修正迭代点：.产生预测点：.停机准则：如果则停止，否则令，转.其中注2.5.1.1：改进算法1与ADMM-split算法都采用了预测校正技巧，通过先产生一个预测点，然后通过结合初始迭代值产生新的迭代点，因此改进算法1的工作量与ADMM-split的算法接近.2.5.2改进算法2.给定和.令.产生预测点：(2-7).修正迭代点：其中.停机准则：如果则停止，否则令，转.其中注2.5.2.1：在改进算法2中，含有两个参数.在算法中可视为步长，所以在数值实验中我们要选取合适的数值来加速改进算法的收敛性.相比于改进算法1，我们设法将每步迭代中的最优步长计算出来并参与下一次的迭代，这样更有益于节省计算时间，使得程序尽快收敛.且在预测步骤中，第三个自由变量的计算利用了第一，二个自由变量的更新迭代值.改进算法的收敛性分析由于改进算法1，2的证明思路类似，本论文只作出改进算法1的收敛性分析，改进算法2同理引理2.6.1.若并且，则由改进算法的预测步骤中产生的是变分不等式(1-6)的解.证明：因为并且则有，又由则可推知由(2.5.1)预测产生，则由一阶最优性条件可知，其与下式等价：其中也就是，找一点使得不等式(2-8)将带入到(2-8)中，有(2-9)记(2-10)(2-11)则由(2-4)中对于的定义，不等式(2.5.2)可化为：(2-12)当，时，我们有，故上式(2-12)化为：故由此可知，则由改进算法的预测步骤中产生的是变分不等式VIP(1-6)的解.注：引理2.6.1表明在不等式中，当时是问题(1-6)的解，所以我们把称为停止准则.引理2.6.2.令是(1-6)的任意一个解，则由改进算法产生的序列和满足(2-13)其中记，(2-14)证明：由于是(1-6)的任意一个解，取则根据(1-7)有：(2-15)即(2-16)又由于则根据(2-12)有：(2-17)将(2-16)与(2-8)上下两式相加并经整理可得到又因为单调，所以有由(2-14)的定义，上述不等式又等价于将(1-7)，(2-1)，(2-10)带入整理得到：即上式左右两边同时加上引理2-9即证明.注：引理2.6.2表明是的下降方向，从而可以沿着这个下降方向来产生新的迭代点.引理2.6.3.令是(1-6)的任意一个解，则由改进算法产生的序列是关于集合单调的证明：由改进算法的修正迭代步骤得其中为对角阵，因此将(2-6)代入下式有(2-18)又有(2-19)其中再假设条件为列满秩下，矩阵Q为对称正定矩阵当且仅当(2-20)矩阵为对称正定的.当，时，很容易求证(2-20)中的矩阵为对称正定矩阵.将(2-19)代入到(2-18)中可得(2-21)引理2.6.3得证，则由改进算法产生的序列是关于集合单调的.定理2.6.1.令，，则由改进算法产生的序列收敛到VIP(1-6)的解证明：由(2-21)可知则上式两边对求和可得这意味着(2-22)由引理2.6.3可知，由改进算法产生的序列是关于集合单调的，则由命题(1.3.1)和(2-22)可知：序列和是有界的；存在常数使得，在算法的迭代步骤中我们得知序列和是有界的，则有界数列必有收敛子列，令为的聚点，则存在子列满足(2-23)又由(2-22)可知(2-24)结合(2-23)，(2-24)带入到(2-12)有由此可知序列收敛到VIP(1-6)的一个解，全局收敛性证明完毕.增广拉格朗日并行分裂算法求解交通均衡问题本文第二章研究了解可分离型带线性约束的凸优化问题的一些算法，并给出了一种新的基于增广拉格朗日并行分裂算法.由于这类特殊的凸优化问题可以被适用于研究各种各样的应用背景，例如交通分配、网络分配、经济等方面，故本章建立了可用来解决交通均衡配流问题的变分不等式模型.交通均衡体系概述交通均衡问题是日益发达的社会环境下需要着重考虑的事情，配流问题是指将交通流量通过合理的配置使他们分配到交通网络的各个路线上去，使交通流量可以在道路网络上均匀分布并且避免出现交通拥堵情况，使得交通资源合理利用，时空分布合理.在实际的道路网络中，起止讫点之间与众多路线.倘若OD对之间有许多条通行道路但是却没有那么大量的交通流量，此时交通流量一定会沿着费用函数最小的道路行驶.但随着OD对之间交通流量的增多，费用函数最小的道路上的交通流量也会相应的增多，在交通流量达到了最短路径对应的可接纳容量时，该路径就会发生交通阻碍情况[14].此时该路径的行驶时间就会因为堵塞情况而增加，这时就会有一部分的出行者选择次短的道路出行.随着起讫点之间的交通流量持续增加，当容量增加到一定程度时，OD对之间的所有道路都可能被使用.如何去调控这个复杂的运行机制就是交通均衡的意义所在.交通均衡问题可以使用变分不等式方法进行求解，经济专家knight首先提出了均衡的概念，而后Wardrop在1952年提出了两个均衡准则用户均衡(UE)和系统优化(SO)原则[15].给定一个网络，如果出行者(用户)从他自己的角度寻求个人利益的最大化，那么每个人在这个过程中都会成为个人利益最大化的一个限制，最终得到重复博弈后的用户均衡状态，这称之为用户均衡原则;另一方面，为了使整个系统的成本降到最低，假设所有交通出行者都自觉接受系统的调控，从而使得整个交通网络的出行成本最小这就称之为系统优化原则.如图所示，给出了交通分配模型的分类结构.根据交通流量的变化特点，可以将大体的模型分为两类动态交通和静态交通.静态交通表明道路网络流量处于一个稳定状态.交动态交通分配模型描述了随时间变化的交通状态.图3-1交通分配模型的分类Figure3-1Classificationoftrafficassignmentmodels符号定义交通均衡问题是一类带线性约束的凸优化问题，目前已经有一些方法来求解，但如何有效的求解交通流分配问题仍然是许多研究者关心的课题.本文运用拉格朗日分裂算法来解决一类交通均衡问题，并且通过一个简单的数值算例说明该分裂方法的有效性.由于交通网络的复杂性，为了便于描述，现做如下符号说明符号说明强连通的有向图结点集路段集合路段上的交通流量()起始节点集合()路段上的实际出行能力()终讫结点集合连接对的路径集合，OD对之间的路径上的潜在需求表示出行者费用的敏感度参数其中阻抗函数，也称交通行驶时间或者交通出行成本.在交通规划的交通分配阶段，要考虑到某一路段的时间出行成本.可以根据行驶时间和路段交通流量之间的关系来确定.其一般形式为，最为常见的路阻函数是美国联邦公路局函数（BPR）：其中为路段自由行驶时间，为待定系数，建议取值分别为0.15，4.用户均衡分配模型定理3.3.1Wardrop第一原理（UE定义）若道路使用者都完全掌握道路网络的通行情况，并希望选择最短路径出行时，网络将会达到到均衡状态.当交通网络达到平衡状态时，我们可以对应得到交通网络中的最小出行成本所有被使用道路的行驶时间相等且等于最小的行驶时间其他未被利用的道路的行驶时间大于或者等于最小的行驶时间用符号语言表达即（3-1）Wardrop第一均衡状态从道路的使用者角度考虑，道路使用者希望通行的道路畅通且具有最小的出行成本，这种选择方式导致所有被交通使用者选择后的道路之间具有着相同且最小的行驶时间（即出行成本），因此可以对应得到用户均衡状态下的交通阻抗[16].Wardrop在提出均衡准则后，由于数值计算的难度性导致这个问题的研究没有实质性进展.后来由Beckmann等人提出了一种满足UE规则的数学模型.提出的模型如下：（3-2）其中该模型称为用户最优模型（UE）.由定理1.2.1可知，上述凸优化问题可以在一定条件下转化为一类变分不等式问题.于是（3-2）对应的增广拉格朗日函数为（3-3）如果点满足不等式则有下式若令，则(3-2)可表示为，.图形表示为：图3-2用户均衡的概念Figure3-2Conceptofuserequalization系统均衡分配模型在系统均衡的条件下，整个系统的出行路线是由所有的道路出行者共同决定的.SO均衡的原则是使得整个道路交通网络的出行成本最小，当其中一方道路出行者发生了道路决策的变化，都会影响最终的总出行成本.这是SO均衡原则与UE均衡原则的不同的地方.定理3.4.1Wardrop第二原理（SO定义）在考虑交通流量超出道路负荷能力后，新增的交通流量对路段的出行成本有影响的网络中，网络中的交通量应该遵循使网络中交通量的总出行成本最小的分配原则进行分配.用户交通均衡原理它反映了交通网络中的出行者选择出行路线的方法，即选择的道路最短并且出行成本最小，这种原理所运用得到的结果是交通出行者会主动选择的结果.Wardrop第二原理即系统均衡原理它努力实现使得道路网络中的总出行成本达到最小，为了符合这个条件，原理假设所有的道路出行者都服从指挥的去选择出行方式.但是在现实的交通道路中这种原则是很难被满足的，这种原则只是被用来为规划城市道路提供一些决策[17].我们可以根据定义要求归纳为下述模型：该模型称为系统最优模型SO.数值试验考虑如下所示的交通网络，设交通起讫点之间的交通运行量为1000辆，定义各路径的交通费用函数图3-3交通网络Figure3-3TrafficNetwork若想求得此问题的最优交通配流，则这类交通均衡实例可以转化为如下的凸优化问题进行求解：（3-4）问题所对应的增广拉格朗日函数为实验结果：我们利用全有全无分配法得到起始迭代初值为(0，500，500)，选取适当的参数值后可得运算迭代结果如下，所有的代码都是运用MATLABR2008b编写.表3-1：迭代次数的结果比较Table3-1:Comparisonofresultsofiterations初始迭代值迭代次数改进算法1改进算法2ADMM-split(0，500，500)222(300，300，400)19844(0，1000，0)26454(400，500，100)>100034表3-2：目标函数值的结果比较Table3-2:Comparisonofresultsofobjectivefunctionvalues初始迭代值目标函数值改进算法1改进算法2ADMM-split(0，500，500)(50，290，108)（50，108，178）(50，350，48)(300，300，400)(50，350，219)(50，298，148)(50，350，190)(0，1000，0)(50，349，220)(50，308，180)(50，350，163)(400，500，100)(30，350，219)(50，321，181)(50，350，209)图3-4绘制误差图Figure3-4Drawinganerrorgraph图3-4中，我们可以看出本文提出的改进算法1中误差下降的最快，但是由表3-1的迭代次数可知，虽然改进算法1具有着最快下降速率但是却需要迭代多次才能得到最优解.且选取不同的迭代初值，会使改进算法1的迭代次数有着较大的波动，甚至可能在超出数组迭代运行后仍然得不到符合条件的最优解.而本文提出的改进算法2中，其误差的下降速率与ADMM-split算法相近，但迭代次数却在每一次实验中都是最少的，这意味着改进算法2相对于改进算法1具有着很大的改进.通过表3-2中的数值试验结果可以发现，改进算法2不仅在迭代次数和迭代时间上有很大的优势，受初值选取的影响不大，都近似维持在10次以内，能够在很短的时间内通过迭代得到符合条件的解集..3.6小结本章主要是将并行分裂的增广拉格朗日方法（ADMM-split）以及新提出的两种改进算法应用到求解交通网络资源分配问题中，本章中的数值实验只是一个很简单易求解的问题，而现实中的交通网络是非常复杂的，我们通过这一简单的小实验去验证了算法的有效性.弹性需求下的用户均衡配流模型Wardrop所提出的的用户均衡（UE）模型，是在假设道路出行者可以完全掌握出行信息，这是一个理想化的假设.但现实生活中，人们并不能够完全的掌握出行信息，并且只能对出行成本进行一个粗略的估计.并且由于不同出行者存在着个体差异，使得他们对道路出行成本会有不同的估计．于是通过学者们的深入研究，他们对原始的用户均衡模型进行了一系列的改进，从而得到了基于弹性需求的用户均衡模型.弹性需求是指，对于道路出行者来说，出行需求是一个顺势而改变的数值，出行费用过高时有些出行者可能会选择不出行或者使用公共出行方式，这样就会使交通需求量变成一个受到道路通行时间影响的一个变量，即当道路最小通行时间增大时，有一些使用者会放弃出行.所以弹性需求是一个随着道路通行时间增大而单调递减的函数[18].即当交通网络中的初始截止结点之间的道路交通流量增加时，这条道路上对应的出行流量就会相应的发生变化，这条道路的出行量就会降低.我们研究OD对之间交通量可变的情况下的用户均衡分配问题，可以称之为弹性用户均衡问题，原始的用户均衡分配问题被称之为固定需求问题.弹性用户均衡分配问题更适用于动态性的交通分配问题.该问题可以表达为下述模型：其中如果路段流量和交通需求视为决策变量，由于凸优化问题的目标函数是凸函数，这意味着区间流量值和需求也是在弹性需求的用户均衡状态下固定的.同样，如果将路径流量视为决策变量，则优化问题的一般目标函数不是严格凸的，这意味着考虑弹性需求的用户平衡状态下的路径流量解决方案并不是唯一的[19].解决优化问题的算法与考虑固定需求的算法基本相同.任何解决固定需求问题的算法都适用于考虑弹性需求问题.因此，我们使用经过验证的具有良好收敛性和有效性的改进算法2来进行具体的数值求解.4.1数值算例图4-1算例中的网络Figure4-1Networkinthestudy如图4-1所示，该交通网络图中包含着4个起讫点，并且对应了12个路段.其中的路段出行成本使用传统的BPR函数其中为路段自由行驶时间，为待定系数，取值分别为0.15，4.表4-1路段出行费用函数的参数Table4-1Parametersofthelinktravelcostfunction路段a12345610.07.012.07.012.012.0120100120120200220路段a78910111210.012.08.010.010.010.0220240150150150120假设所有OD对采用如下形式的需求函数：(4.1.1)给出计算各个路径需求的参数如下：表4-2OD对之间的需求函数Tab