规划模型与Wardrop平衡一致的证明.doc

规划模型与wardrop平衡一致的证明对于任意一个非线性规划问题，其任意局部极小点的解或驻点解均满足一阶必要条件。如果模型（p1）的一阶必要条件等同于wardrop平衡条件，则说明在任意极小点（或驻点）上，wardrop平衡条件成立，也就证明了等价关系。模型（p1）是一个带线性等式约束和非负约束的极小值问题，其拉格朗日函数为： （p-1）式中为等式约束（7b）的拉格朗日乘子（即对偶变量），为非负约束的拉格朗日乘子，分别为其对应的向量表示。问题（p1）的一阶条件等价于使极小的一阶必要条件，即：的变量是路径流量和拉格朗日乘子，其一阶条件如下： ， （6-11） ， （6-12）， （6-13）其中上式中第一项为：其中；因此有：上式中的第二项为注意到，是已知量，并不是的函数。上式中的第三项为：注意到，在这里是非负变量的拉格朗日乘子，因此有，。由以上分析可知一阶条件（6-11）又可以写为：，进一步再写为：，显然可以得到下式：通过采用（6-13）：， （6-14）又因为有， ， （6-15）对于一阶条件（6-12）、（6-13）很容易推导出： ， （6-16） ， （6-17）显然，（6-16）和（6-17）就是流量守恒约束和路径流量非负约束，它们在平衡状态下自然应该满足。我们来分析（6-14）和（6-15），当时，；当时，。这就是说，对应于o-d对的拉格朗日乘子总是小于或等于连接o-d对的任意路径的费用，因此是起始节点到终讫节点之间的最小费用。很明显，以上所推导出的一阶必要条件表达了用户平衡原则，即：连接o-d对的路径可分为两类，一类路径上有流量，其费用总是等于最小o-d费用；另一类路径上没有流量，其费用总是大于或等于最小o-d费用。当流量分布达到平衡状态时，再没有一个司机能够通过单方面改变行驶路径而可以减少其行驶费用了。到此，就证明了模型（p1）的解与用户平衡条件之间的等价性。优化模型的特性说明模型（p1）是一个由线性等式约束和非负约束构成的非线性规划，约束集自然是凸的，如果目标函数也是凸的，那么（p1）就是一个凸规划问题，最优目标函数值唯一。如果目标函数是严格凸的，则（p1）是一个严格凸规划问题，其最优解唯一。目标函数的hessian矩阵为： （6-18）根据（6-9）式可知是正定的，因此（p1）的目标函数是严格凸函数，所以它的最优解是唯一的。换句话说，费用函数是非负性和单调递增是（p1）具有唯一最优解的条件。然而不幸的是这种凸性并不适合于路径流量（更详细的说明请查阅sheffi，1985）。这种路径流量最优解的非唯一性最终成为解决交通运输问题的下降算法应用中的一个严重障碍。f-w方法的说明frank 和wolfe于1956年提出求解线性约束问题的一种凸组合算法，通常简称f-w算法，是属于可行方向法的一种。由于本章中出现的最优化问题主要是非线性目标函数与线性约束的，故先介绍这一著名算法。考虑非线性规划问题：s.t. 其中是矩阵，秩为，是维列向量，是连续可微函数。可行域记为：。f-w算法的基本思想是，在每次迭代中，将目标函数线性化，通过解线性规划来求得下降可行方向，进而沿此方向在可行域内作一维搜索以得到新的迭代点。现在给出具体的求解方法。设已知某可行点，将在处展开，用一阶泰劳多项式：逼近。解线性规划问题：s.t. 去掉上面目标函数中的常数项，将此问题改写为如下形式：s.t. 假设此问题存在有限最优解，由线性规划的基本性质可知，这个最优解可在某极点达到。求解线性规划的结果必为下列两种情况之一：1 如果，则停止迭代，可证明，此时就是原问题的k-t点。2 如果，则必有： 因此（）为处的下降方向，且是可行的。从出发，沿下降方向作一维搜索：s.t. 求得，令，由于，且为下降方向，因此有得到后，再重复以上过程。关于f-w算法的收敛性，在此不作证明，大家可进一步查阅有关文献。对f-w方法的评价：f-w算法的每一次迭代中，搜索方向总是指向某个极点，并且当迭代点接近最优解时，搜索方向与目标函数的梯度趋于正交，这样的搜索方向并非是最好的，因此算法收敛较慢。但是，这种方法能把求解非线性规划问题转化为求解一系列的线性规划问题。一般而言，f-w算法主要由两个部分组成，一是在每次迭代中确定搜索方向，二是确定搜索步长。而确定搜索方向相当于求解一个满足相应约束条件的线性规划问题，这在理论上当然很容易求解，但是对于大规模的网络来说，求解这个线性规划问题的计算量就很大，并且在每次迭代中都要求解这样的一个问题。但是将f-w算法应用到交通网络中，由于问题的特殊结构，线性规划问题将被寻找最短路径所代替，从而大大缩短了算法的计算时间，避免了列举所有路径的困难。下面我们分析模型（p1）的求解算法。根据f-w算法求解非线性凸规划模型（p1）的一般步骤，迭代次数为时，令目标函数值下降的搜索方向应由解下面的线性规划问题得到：（p2） （6-19） s.t. ， （6-20） ， （6-21） ， （6-22）式中是可行路径流量，是可行路段流量。由，因此（6-19）可变换为：以上各式中是已知数，即由决定的路段出行费用，是要求解的未知数。因此，该模型实际上是在各路段出行费用一定的条件下使网络总费用最小的经典运输问题。显然，在这种情况下，将o-d需求量全部沿o-d间的最短路径上分配即可使目标函数值最小。而这正是众所周知的“全有全无”配流方法，这种方法主要的工作量即是寻找最短路径。因此很多交通问题的研究学者称线性规划问题（p2）为“全有全无”规划。求解出的决定了第次迭代的方向，即下一步迭代的方向为与的连线。迭代步长由下面的一维极值问题决定： （p3） （6-23） s.t. （6-24）对于一维极值问题（p3），许多方法都可以求解，其中比较有效的也许是二分法，因为目标函数（3-23）对的导数很容易计算，即：此方法在一般的高等数学或运筹学书中都可以查到。这样，用“全有全无”配流法可以得到下一步的迭代方向，求解一维极值问题可以得到迭代步长，因此，下一步的迭代点便可以由下式得出： （6-25）对于算法的收敛准则，可以根据两次相邻迭代中交通流量的变化来判定，如果变化很小，就可以认为达到平衡而停止迭代。比如，可以由下式决定： （3-26）其中为预先给定的误差值。现将求解固定需求平衡配流模型（p3.1）的算法归纳如下：第1步：初始化。令，用“全有全无”法将o-d需求量加载到道路网络上，得到弧流量，置迭代次数；第2步：计算；第3步：搜索可行方向。根据，用“全有全无”法将o-d需求量加载上网，得到弧流量；第4步：寻找迭代步长。求解一维极小值问题：s.t.假定求得步长为；第5步：更新流量。置，；第6步：收敛性检查。如果满足收敛性准则，则算法终止，否则令，转到第二步。求解算法的评价：在这个算法中，没有存贮路径变量，只用到了弧变量，大大的节约了计算机内存的需求量。此算法的缺陷是在迭代过程的后期收敛速度较低，原因是当趋近于问题的最优解时，搜索方向将垂直于目标函数在的梯度。当然影响算法的收敛速度的主要因素还有：初始解、网络结构和拥挤程度。初始解离平衡点越近，则需要的迭代次数就越少。网络结构越复杂，即从起点到终点的可选路径越多，则需要的迭代次数就越多。拥挤程度大的网络需要更多的迭代次数到达平衡点。系统最优模型在问题（p1）中，网络使用者只从自身利益出发去寻找最小费用路径，使用者之间互不协调，经过系统不断地内部调整后，达到一个平衡状态，这就是ue问题，符合wardrop用户最优原则。而系统最优原则则描述了另外一种网络用户的路径选择问题，即假定网络的使用者能接受统一的调度，大家共同的目标是使系统总的费用最小，这就是系统最优问题。此时，可用如下的数学规划模型来进行描述（p2）： （7.10a） ， （7.10b） ， （7.10c） ， （7.10d）（p2）被称为系统最优模型，简称so（system optimization）。通常情况下，so的解不是一个ue解。但可以证明，如果在网络中忽略拥挤效应时，so与ue是等价的。需要说明的是，由于so模型与ue模型的结构十分相似，事实上两者的差别只体现在路段费用函数的构造上。如果在ue模型（p1）中，令目标函数为 （7.11）其中： （7.12）则容易证明其解与问题（p2）的解完全相同。通常被称为路段对网络总费用的边际贡献，也称路段的边际出行费用（marginal cost）。同用户平衡问题类似，可以用f-w方法来求解系统最优问题，区别在于算法的第四步中，一维极值问题的目标函数用（7.11）来代替。显然，在so原则下的解会使得每一o-d对之间的路径上的边际费用相等且最小。也很容易证明模型（p2）的解与系统最优是等价的以及其解是唯一的（sheffi,1985）。具有路段通过能力限制的ue配流问题在一般的ue配流模型中，我们都是假定路段的通过能力是无限制的，即每一个路段能容纳所有分配在该路径上的流量。但是在实际问题中，每一条路段的通过能力总是有限的。一般情况下，当路段流量达到或超过路段能力时，我们可以将该路段的费用函数设为随着流量增加而不断增加以满足路段能力限制的约束（如著名的bpr公式或davidson公式）。在模型中如能明确表示路段的能力约束，则有利于分析交通网络中的排队问题。随机用户均衡配流问题对于前面所介绍的确定性用户均衡配流，有两个假定条件，一是假定出行者能够随时掌握交通网络的状态，也就是说，能够准确的得到每条路径上的费用从而能够完全正确的选择路径；二是假定出行者的计算能力和水平都是相同的。显然，这两个假设条件是不符合现实问题的。一般来说，出行者对道路上的费用只能作出估计，对于同一条路段，不同的出行者所做出的估计值也是不同的。因此，在配流问题中，应该将路段费用看作一个随机变量，这就是随机配流问题。如果有一组出行者从起点到终点之间有多条路径，由于出行者对路网状况、交通现状并不完全了解，且存在着一些难以量化的因素，如天气变化及考虑道路沿线风景等，有理由将出行者对路径费用的估计视为分布于出行者群上的随机变量。如果仍沿用wardrop用户最优原则所定义的出行者路径选择原则，即选择最短路径出行，但与确定性均衡配流模型不同的是，这里的最短路径是估计最短路径，即在o-d对之间存在着多条路径，同一出行者对这些路径存在着不同的费用估计。对于某一个特定的出行者来说，他（她）总是选择具有最小估计费用的路径出行。由于每条路径的估计费用是随机变量，有相应的概率密度函数，对于某一特定出行者，每条路径均有一个被选择的概率。随机均衡配流模型（stochastic user equilibrium，简称sue）就是在研究路径估计费用分布函数的基础上，计算有多少出行者选择每一条路径。随机均衡配流模型分为两大类：第一类模型中，不考虑拥挤效应，即假定路段上的费用与其上的流量无关的随机用户均衡配流模型；例如dial模型虽然能够进行随机均衡配流，但其路段实际费用是与交通量无关的，也就是说没有考虑拥挤因素。这显然与实际交通状况不相符。第二类模型则是在数学规划的基础上，考虑路段上的费用与其上的流量相关的随机用户均衡配流模型。在这里，主要介绍考虑拥挤因素的随机用户均衡配流问题。所谓随机用户均衡就是指这样一种交通流分布形态，任何一个出行者都不可能通过单方面改变出行路径来减少自己的估计形式费用。也可以这样描述：在起终点之间所有可供选择的路线中，使用者所利用的各条线路的出行费用的期望值全都相等，而且不大于未被利用线路的出行费用的期望值。随机用户均衡分配中出行者的路径选择行为仍然遵循wardrop用户最优原则，只不过用户选择的是自己估计费用最小的路径而已（sheffi，1985）。假定估计路段费用的期望值是路段流量的函数，一般可表示为如下形式：，其中表示路段的估计费用，为相应路段的随机误差项，且，从而有。连接o-d对之间的路径被选择的概率，就是其估计费用在该o-d对间所有可能路径的费用中为最小的概率，即 （7.32）其中表示o-d对之间的路径上的估计费用值，。应该注意到，上述选择概率是一个条件概率，即它是在均衡状态的路段费用期望值的条件上确定的概率。如果路段费用是常数，问题就可以用dial算法解决了。由随机均衡配流的定义可知，在这种均衡状态下，某个o-d对之间所有已被选用的路径上，并不一定有相同的实际费用值，而只满足下述条件， （7.33）在此式中，路径流量与有关，而与估计路径费用大小有关，估计路径费用大小与估计路段费用有关且是随机变量，实际路段费用又是流量的函数，如此循环，达到sue的条件。sue问题更具有普遍性，ue仅是sue的一种特例，如果估计费用的方差为0，sue就变成ue。fisk于1980年提出了一个最优化问题，该问题中o-d矩阵（）已知，路段流量（）被直接视为变量。可以证明最优化问题的解对应于logit形式的路径选择公式，故它也是一个sue解（sheffi，1985）（p6）： ， ， 式中是一个非负的校正参数，它掌握了整个模型的随机特性。当时，目标函数的第二项就会控制整个函数，模型就变为一个标准的ue问题。当时，o-d矩阵（）将均匀的分布到网络上，相当于令所有路径的阻抗都相等。事实上，它说明增大时，路段方差减小，整个模型向确定性的ue接近。但是，模型从外表上看，不是一个随机配流模型，却含有logit形式随机配流问题的全部特征。显然，模型（p6）的一阶条件为 ， 其中和分别为对应于（p6）相关约束的拉格朗日乘子。定义从到的有效路径集合（由dial算法可以得到，详见（sheffi，1985）为，在之内的所有路径，如，应有。显然，若，则，注意到，从而有将此式推出的代入到（p7.6）路径流量与o-d流量之间的守恒方程中，可求出，然后代入到上式中，可得到著名的logit公式如下， fisk模型的可塑性很强，它用值代表用户们对网络费用的认识程度，显然，用户的认识越深，估计的路段费用方差就越小，值就应该高一些。由于fisk随机用户均衡模型中用到路径变量，而在城市交通网络中，路径数目远远大于路段数目，所以，求解fisk模型的难点在于如何列出o-d队之间的路径。在dial算法中，有一种路径列出原则，可以用于求解fisk模型的过程中。在这里，介绍一种算法，这种算法是由powell和sheffi（1982）基于msa算法提出的。具体步骤如下第一步：确定有效路径的集合。第二步：初始化。令,，置迭代次数。第三步：根据，然后根据logit随机配流算法计算路段流量，。第四步：迭代。计算 ，。第五步：收敛性检查。若满足收敛条件，则停止迭代；否则，令，转第四步。由于上述算法是基于msa算法提出的，故在定理5.3的条件下，算法是收敛的。变分不等式表示的交通网络均衡问题dafermos（1980）将城市交通网络均衡流问题改写为变分不等式问题，最一般的形式就是：寻找均衡路段流量，使得对所有的有 （7.34a）其中 （7.34b）其中为路段阻抗向量函数，为路径流量，为o-d需求量，代表路段/路径关联矩阵，代表o-d对/路径关联矩阵。如果严格单调，则均衡路段流向量是唯一的，而均衡路径流量向量不一定是唯一的，包含于如下的一个凸的多面体集合中（polytope） 其中是由（7.34a）和（7.34b）中求出的均衡路段流量。双 层 规 划 模 型 简 介由于实际的规划、决策问题都是庞大而异常复杂的系统，涉及到各种各样的影响因素，关系着各个部门、单位和个人的具体利益，因此所采用的决策方法应该是多层次的系统决策方法，而不能是单一层次的决策方法。一般而言，决策机构都是一个分级或分层次的管理机构，在总体目标一致的前提条件下，各级都有其各自独立或相互矛盾的目标。因此，在作出科学而系统的最终决策之前，需要综合考虑彼此之间存在相互作用的、有其各自目标的各个层次上的部门、机构和个人的意见，力求最终的决策能使整个系统达到最优的目的。 多层规划问题的一个重要特点就是可以应用在多层决策问题中，多层规划使用一个分层次的结构，在各个层次上的决策者都有其各自的目标函数，在某种程度上，本层的决策空间是由其它层次决定的。此外，某一层次上的决策者通过特定的方法和手段以影响其它各层的决策制定，从而达到优化其自身目标函数的目的。例如，这些方法和手段可以是控制较低层次的资源分配和使用、调整分配给各层的利益等。在多层规划中，所有的决策者优化其自身的目标函数，而不考虑他们的决策对其它各个层次的影响。 多层规划问题的另一个重要特点是：决策变量的控制权分别属于各层的决策者，而在传统的单层规划中，决策者同时控制所有的决策变量。但在政府部门的实际决策过程中，对决策变量的控制和处理并不是同时进行的，而是采用自上而下的多层次决策方法。例如，在大多数国家中，中央政府首先在各个省之间分配资源 （指的是广义的资源），然后各个省在中央政府所分配的资源基础上，决定其各自的行为、政策。 在交通系统中，政府部门对交通基础设施投入大量资金和财政补贴，采用建设新的道路、改善已有路段、更新公交汽车等等措施以维护整个交通系统的正常运行，满足日益增长的交通需求，而公众则调节自己的出行行为以适应这些给定的交通设施。也就是说在政府部门为出行者提供交通基础设施之后，出行者根据具体的交通状况来决定自己的出行方案。可见在多层规划中，以优化自己的目标函数为目的的决策者在高层决策者事先确定决策变量值之后，对自己能控制的决策变量进行优化，以达到最优目的。多层规划比单层规划具有优势，包括能够明确建模表示顺序决策过程的能力，能够明确表示不同层次优化过程或不同决策系统之间的相互作用的能力。双层规划问题是多层规划问题的一种特例，其中只有两个层次，两种决策者。由于交通投资决策过程涉及到政府部门和公众的出行选择相互作用或者他们之间的联合决策行为，是一个典型的双层决策问题，因此双层规划模型成为描述交通投资决策过程的理想工具。1 双层规划模型的定义和特性1.1 定义 一般来说，双层规划模型具有如下形式：（p1） （u1） （1）s.t. （2）其中由下述规划求得：（l1） （3）s.t. （4）其中，。双层规划模型（p1）是由上层模型（u1）和下层模型（l1）组成，式（1）（2）构成上层问题，式（3）（4）构成下层问题。上层决策者通过设置的值影响下层决策者，因此限制了下层决策者的可行约束集，上层决策者通过下层决策者的目标函数与下层决策者相互作用。必须注意到：下层决策变量是上层决策变量的函数，即，这个函数一般被称为反应函数。1.2 计算复杂性一般来说，双层规划问题的求解都是非常复杂的，原因之一就是由于双层规划问题是一个np-hard问题。ben-ayed和blair （1988） 在jeroslow （1985） 的研究基础上继续深入探讨了这一问题，指出：即使是很简单的双层线性规划问题也是np-hard问题，不存在多项式求解算法。双层规划的非凸性是造成双层规划问题求解异常复杂的另一重要原因。即使上层问题和下层问题均为凸问题，整个双层问题仍然为非凸问题的可能性非常大。而双层问题的非凸性表明：即使能找出双层问题的解，通常也只可能是局部最优解而非全局最优解。这样，即使是对于某类双层规划存在精确算法，也是难以实际应用的，因此为使计算简便易行，目前双层规划模型所采用的求解算法都是启发式的，实际计算表明这些启发式算法对双层规划问题是有效的。由于双层规划问题和博弈论具有一些基本的相同特性，因此可以利用博弈论中的一些方法来限定双层规划问题的解的范围。在博弈论中，同两个选手分别控制各自的决策变量相比，如果一个选手能控制所有的决策变量，那么，这个选手就能更好的优化其自身的目标。基于上述观点，根据所控制的决策变量的不同，可以将双层规划问题重新表示为以下两个不同的规划问题。 （1）如果上层决策者控制所有的决策变量，则双层问题变为：（p2） （16）s.t. （17） （18）（2）如果上层决策者和下层决策者分别独立地控制各自的决策变量，则双层问题变为：（p3） （u3） （19）s.t. （20）其中（l3） （21）s.t. （22）必须注意到：在问题（p3）中，下层决策变量不再是上层决策变量的函数。 假设：、和分别代表问题（p1）、（p2）和（p3）的解，则有： （23）一般而言，单层规划问题（p2）和（p3）比双层规划问题（p1）更容易求解，因此，不必直接求解双层规划问题（p1），而直接求解单层规划问题（p2）和（p3），然后尽量减小与,与之间的差异，可以得到近似解。shaw （1980） 和ben-ayed（1988）就设计了基于上述思想的求解双层规划的启发式算法。1.3 求解双层规划模型的算法概述到目前为止，对于双层规划的求解大约有十几种求解算法。归纳起来，可以分为四大类，即极点搜索法（ex