具有路段容量限制的广义系统最优交通分配

俞礼军

(华南理工大学 土木与交通学院，广东 广州 510640)

基于给定起点-目的地交通需求并按照一定的择路原则确定运输网络中路段平衡流量的问题通常称为交通分配问题(TAP)，其是运输系统分析中的经典问题。文献[1]中Wardrop提出的用户均衡(UE)和系统最优(SO)是交通分配中常见的基本原则。Beckmann等[2]最早提出满足UE原理的凸数学规划Beckmann模型。LeBlanc等[3]首次将经典的Frank-Wolfe算法用在小型网络上。Beckmann模型与经典SO模型属于无路段容量约束的凸规划模型。这两类经典模型一直是重要的研究对象。其中UE模型(Beckmann模型)相对于SO模型体现一定的自由竞争内涵且其对应的算法做些微改造即可用于SO模型，因而成为绝大多数研究者关注的对象。Beckmann模型与SO模型使用的绝大多数路段阻抗函数，包括著名的BPR函数，都属于多项式函数。求解基于此类多项式路段阻抗函数的Beckmann模型或系统最优(SO)模型，其平衡解可能包含相当多的过饱和路段，极端情况下得到的个别路段流量是容量的2～3倍。超过通行能力的高流量路段是不切实际的，这样的计算结果对于在第一线上的从业者当然是不能令人满意的。从理论和实践上考虑，路段上的流量不应高于其通行能力。Daganzo[4- 5]使用渐进函数的方法来处理这个问题，即设计一种路段阻抗函数，当流量趋于通行能力时，时间就趋于无穷大。Boyce等[6]认为路段旅行时间数值异常大的结果有违现实。为克服此问题，一个很自然的想法就是在Beckmann模型中添加路段流量小于等于其通行能力的约束，如此则得到与经典意义上的Wardrop均衡状态不同的结果。研究者针对此新模型定义了一种新的用户均衡状态。不同于带流量约束的Beckmann模型，含通行能力约束下的SO模型的交通分配结果与经典SO原则可能是不同的，而目前尚未有关于此问题的深入研究成果。故此，在路段容量限制条件下建立新的SO模型是有意义的工作。

另一方面，目前理论与实践中得到大量应用的BPR路段阻抗函数属于阻抗是流量增函数的多项式函数。基于此类阻抗函数的Beckmann模型与SO模型是凸规划模型。对于具有路段容量约束且阻抗是流量增函数的路段,阻抗函数的UE均衡模型可以采用四种类型的收敛算法来求解Beckmann模型：内部和外部惩罚函数方法[7]、拉格朗日乘数方法[8]、拉格朗日对偶方法[9]和对偶上升方法[10]。阻抗若不是流量增函数的多项式函数，则对应的具有路段容量约束的SO模型可能不是凸规划模型。例如，在节假日或者交通流事故等原因而受到交通管制条件下的交通流，尽管可以用多项式函数来描述，但其流量阻抗之间并不具有阻抗是流量增函数的特性，构建的广义SO模型通常是非凸模型。用于处理具有路段容量约束的凸UE均衡模型算法很难推广到具有一般多项式阻抗函数和路段容量限制的非凸广义SO模型。为此，有必要探求能够求解具有一般多项式阻抗函数的广义SO模型的方法。

应当指出，基于路段流量为变量的经典SO模型是严格凸规划问题，而基于路径流量为变量的经典SO问题是不严格凸的，即路径流量解不是唯一的[1]。实际应用中每个OD对的可行路径通常在4到7条之间[11]，业者常常根据已有信息指定每个OD对的路径并基于对应的路径变量求解经典的SO问题，期望同时得到多个路径流量解以便根据实际情况采取必要措施实现特定交通流的引导。对于这样的问题，经典方法较难稳定地得到多组解。特别的，对基于路径流量为变量的非凸广义SO模型，采用经典凸优化算法求解是异常困难的，若此类非凸SO模型有多组最优解，针对凸规划的经典算法不能处理此类问题。

综上所述，具有一般的多项式阻抗函数和路段容量约束的广义SO问题尚未解决。据作者所知，对于解决具有一般的多项式阻抗函数的广义SO问题的障碍来自以下事实：在经典定义与模型框架下，仅将一般的多项式阻抗函数与路段容量约束添加到任何标准SO模型中，无法获得相应等效SO条件，同时也缺乏求解非凸问题的算法。为此，本文针对经典系统最优(SO)模型的局限性，建立具有可分离的一般多项式阻抗函数和路段容量限制的广义系统最优交通分配模型并新定义广义SO原则，该定义要求经典SO模型与广义SO模型的解都应满足广义SO原则。关于广义SO模型解的存在性是广义SO问题中的一个大的挑战。一般情况下建立的广义SO模型不必然是凸模型。本文首先指出在非空、紧凸集上定义的扩展SO模型具有至少一个全局最优解，即所提出的模型满足广义SO原则。随后提出一个问题：在解存在的情况下如何求新模型的解。根据广义SO模型的特征，采用基于矩半定规划的算法获得广义SO模型的全局最优解。对于指定路径并基于对应路径流量的广义SO模型，若其存在多组路径最优解，则采用本文方法可以获得多组路径流量全局最优解。

1 问题描述与模型

1.1 符号与假设

对整个交通网络做以下假设：

(1)网络是强连通的，即任一OD对之间至少有一条路径连接;

(2) 任意一个路段a的流量za都不超过路段的最大流量限制Ca，即za≤Ca，a∈A;

(3)每一条路段a∈A有一个与之相对应的实系数非负多项式路段阻抗函数且该路段阻抗函数是关于该路段流量的函数，即ta(za);

(4)O-D需求为正常数，OD需求可以通过网络，即模型有可行解。

1.2 模型

在上述假设下，对应的带路段容量限制的系统最优交通分配问题可以由如下非线性规划模型描述：

(1)

上述模型也可以写成如下等价的路段-节点模型[12]：

(2)

经典SO模型属于凸规划模型，而上述模型(1)、(2)不必然是凸规划模型。模型(1)、(2)的约束集为非空、紧致凸集[12]，模型目标函数均为非负多项式，由Weierstrass定理知道，紧集上的多项式函数必然存在全局最优解[13- 14]，即存在使系统的总交通时间全局最小的交通流分布。

广义系统最优交通分配：路段流量有容量约束或无容量约束条件下交通量按照某种方式分配以使系统的总交通时间全局最小。

按照广义系统最优交通分配定义可知，经典SO模型与新模型的解都应满足扩展广义交通系统最优条件，即广义系统最优交通分配定义是经典系统最优交通分配定义的扩展。

对于非凸规划模型，采用经典方法获得全局最优解通常是非常困难的。近年来，半定规划(SDP)[15]的凸松弛方法已经成为优化领域的研究热点。对于非凸优化问题，如果凸松弛可以提供与原始问题的解等效的结果，则可以通过解决该松弛问题来获得原问题的全局最优解。本文基于矩理论将上述模型转化为等价的矩半定规划(MSDP)模型，从而获得原问题的全局最优解。

为方便介绍与广义SO模型等价的矩半定规划模型与相应计算方案，又因为有部分理论来自代数几何且并不显而易见。故这里扼要给出半定规划、多项式函数与矩相关的理论。

常见SDP问题指的是具有线性矩阵不等式(LMI)约束的线性目标函数最小化问题。LMI问题是凸的，可以用内点法有效地解决。

这里采用符号xα表示一个单项式，α为复合序号，α=[α1,…,αn]T∈Nn(包含0在内的自然数)，任意一个单项式可以表示为

(3)

采用记号|α|表示xα的阶次

(4)

多项式函数中的每个单项式均可用一个新的变量表示，因而可将一个多项式函数表达为关于若干单项式(新变量)的线性组合。为便于线性化处理，阶次不大于d的多项式，可以定义多项式基向量为

(5)

它包含最高阶次为d的单项式，所有基都可以形式的表示为xα。

对于任意的d阶多项式函数f(x)，其线性化表达式为

(6)

式中，fα为xα的系数，[fα]为系数向量。具体问题中，可以将d阶函数写成更高阶的表达形式，这时高于阶次d的单项式系数设为 0。

矩是概率论中的定量测度[16]，有多种用途[17]。矩可以表示为概率测度μ下的积分。 函数f(x)的矩函数L(f)可以写成：

(7)

将式(6)代入函数的矩表达式(7)，可得

(8)

式中,yα是对应于单项式xα的矩，即

(9)

令y0,…,0=1。

式(8)将函数f(x)的矩函数表示为关于矩变量yα的线性组合，它是矩半定规划方法的重要组成部分。

将模型(1)或(2)的约束写成不等式形式，借用上述关于多项式的符号表示，将相应的SO模型表示为具有以下形式的多项式优化问题：

(10)

式中，多项式gi(x)为约束函数，giα为单项式xα的系数。

矩半定规划(MSDP) 松弛处理方法的思路是，将式(10)中的多项式目标函数与约束函数转化为关于矩变量的线性关系式的目标函数以及关于矩变量的半正定矩阵约束，从而对多项式优化问题(10)建立等价的凸半定规划松弛模型。

为了建立模型(10)的SDP松弛模型，以下依次给出矩变量的LMI约束与不等式约束的LMI表示。

基于向量[x]s，可以定义对应的s阶矩矩阵Ms(y)：

(11)

Ms(α1,α2)=L(xα1xα2)=yα1+α2

(12)

式中：α1，α2∈Nn是其行序号和列序号，|α1|,|α2|≤s;矩阵Ms(y)是对称的。

矩矩阵Ms(y)由所有矩变量yα组成，在矩变量空间，矩阵Ms(y)为正半定矩阵[13]，即

Ms(y)0

(13)

有了Ms(y)不难给出一组对称矩阵，写出其LMI表示形式。

给定多项式函数g(x)不等式约束，可以由阶次不大于2s的部分矩变量yα定义(构建)一个与g(x)相关的矩变量局部矩阵来刻画原优化问题的约束关系。一般采用部分矩变量yα(|α|≤2s)定义与多项式函数g(x)相关的局部化矩矩阵Ms′(gy)为

Ms′(gy)=L(g)Ms′(y),s′

(14)

(15)

(16)

式中，L(g)是g(x)的矩函数，其表示为矩变量的线性组合；Ms′(y)为s′阶矩矩阵；为保证L(g)Ms′(y)所得矩变量的最高阶次不大于2s，要求s′>s。

约束g(x)≥0与矩阵Ms′(gy)正半定是等价关系[13]，即

g(x)≥0⟺Ms′(gy)0

(17)

式(13)是一个LMI约束,其揭示了矩变量之间的关系。式(17)表明不等式约束可以转化为LMI形式。根据矩表达式(7)和半正定矩阵关系式(13)、(17)，可以得到广义系统最优模型(10)的等价SDP松弛模型(18)

(18)

原则上，模型(18)为标准的 SDP 问题，对于一般规模的问题，调用诸如SeDuMi[18]、SDPT3[19]等任意一款SDP计算软件包均可求得模型(18)中的各个矩变量的解。

阶数s可以设置为1,2,3，…。为了求出原问题的全局最优解，需要一个全局最优的充分条件。已有研究回答了这个问题。即

定理[20]：设y*为模型(18)的最优矩解，当矩矩阵的秩满足如下条件：

rank(Ms(y*))=rank(Ms-1(y*))=k

(19)

则模型(18)的目标值与原问题的全局最优值f*相等。其中秩k表示原问题具有k个全局最优解。

根据上述定理可以求得全局最优的矩量解。至此还剩一个问题有待解决，即如何由该概率测度下所对应的矩量解求得原问题的全局最优解。若矩量矩阵的秩为1，对应原问题的全局最优解x*是唯一的，根据矩矩阵的结构特点，x*可从M1(y*)的第1行(第1列)直接得到。若矩矩阵的秩为k且k大于1，则原问题有k个全局最优解。此时采用三阶段方法求解[21]：矩矩阵的奇异值分解；构造提取等式；采用特征值法求解精确最优解。

2 求解方案

待求解的均衡模型约束均为线性约束，又模型涉及的阻抗函数均为非负多项式，因而其约束、目标函数均为多项式。为求解此类均衡问题，需将原均衡问题模型重新构建为不等式约束的最优化问题，并基于矩的理论进一步将不等式约束的多项式优化问题构建为关于矩变量的半定规划问题。基于矩的理论得到的半定规划的松弛阶次s=1,2,…,因而转化后的SDP模型具有层次结构。阶s可以取很大的值，变量的数量随着s的增加呈指数增长，这对于工程研究是不利的。幸运的是，已有研究[13]证明了当阶s增加时，模型(18)的最优值逼近原问题的全局最小值，一般的，相对较小的s值就可以达到全局最小值。

实际计算中，首先令基于矩的SDP模型中的s=1，并采用内点法求得对应SDP问题的矩解；再判断矩解是否满足全局最优的充分条件，若不满足则增大基于矩的SDP模型中的松弛阶次，即s=s+1，重新求解直到找到一个恰当的s满足全局最优条件；若满足全局最优的充分条件则进一步采用三阶段方法计算得到原问题的最优解[21]。具体实现方法参看图1的算法流程图。

3 算例

3.1 算例1

这里使用如图2所示的一个简单网络。此网络由两个结点以及连接两结点的两条并行的路段(路线)组成。图中点1和点2分别为起点和终点。路段1是受到交通管制的交通流；路段 2 是正常使用的道路，其交通流呈现正常的旅行时间与流量呈现单调增加的关系。

路段1与路段2的时间阻抗函数(如图3所示)由如下两式给定：

(20)

t2(x2)=0.075 85x2+0.85

(21)

图1 基于矩的SDP算法流程

图2 简单网络

图3 路段阻抗函数

假定从起点1到终点2的出行需求量是：D12=4辆/min。通行能力为2、4辆/min；假定出行者满足系统最优条件，确定出行者满足系统最优条件的路段流量问题可以用下面的模型来表达:

(22)

经整理之后，模型(22)转化为

(23)

采用本文方法求解得到全局最优解：x1=0,x2=4。本算例仅仅属于示例，由图4容易看出结果。事实上，采用经典方法随初值不同可能得到x1=0或x1=2。若模型中其他不改变，而将x1的约束条件改为0≤x1≤2.035 4，求解模型可以同时得到两组解。x1=0,x2=4或x1=2.035 4，x2=1.964 6。

图4 目标函数

3.2 算例2

图5 Nguyen and Dupuis网络

表1 Nguyen-Dupuis网络路段参数

表2 Nguyen-Dupuis网络OD出行需求

系统最优模型的目标函数为

(24)

基于路段流量为变量的经典SO模型是严格凸规划问题，均衡状态的路段交通量是唯一的。本算例模型属于凸规划模型。经典的交通平衡配流模型路径流量解通常不唯一。采用经典方法与本文方法计算可得相同的路段交通量如表4所示。本算例为每个OD对指定5到8条可行路径，基于指定路径采用本文方法计算路径流量如表5所示。而采用经典方法较难稳定地得到多组解。

如前所述，业者常常根据在实际应用中获得的经验与信息为每个OD对指定可行路径，构建、求解基于指定路径对应的路径变量为决策变量的广义SO问题。由此得到的多组路径流量在实际应用中有特殊价值。据我们的调查，目前多数司机在使用特定信息系统提供的路径指引。如何在以时间作为准则的系统最优的前提下得到多组路径流量，结合其他因素为线路指引提供参考对于特定目的的调度指挥具有现实意义。文中提供了一种新方法，丰富了获取系统最优状态时的多组路径流量的手段。尤其对于基于路径的非凸广义SO模型，经典算法不能处理此类问题，本文方法从理论上给出了获得全局最优解的通用解决方案。

表3 路段路径关联关系

表4 系统最优时的路段流量

表5 系统最优时的路径流量

4 结语

本文中研究具有一般非负多项式阻抗函数和路段容量限制的广义系统最优交通分配问题的模型开发和算法设计。基于测试算例，得到如下结论：

1)建立了广义系统最优交通分配模型并给出了获取其全局最优解的方法。本文定义的广义系统最优交通分配原则推广了经典的系统最优交通分配原则。文中模型将经典SO模型推广为更为一般的情况，克服了经典系统最优交通分配模型所必须满足凸规划性质的限制。提出的方法可以用来处理具有一般非负多项式阻抗的广义系统最优交通分配问题。

2)两个测试算例的计算结果表明，MSDP松弛方法能够有效求解具有一般非负多项式阻抗函数和路段容量限制的广义系统最优交通分配模型。对于存在多个全局最优解的广义系统最优交通分配模型，本文算法能够获得多个全局最优解。针对指定路径并基于对应的路径变量的SO问题，若其存在多个全局最优解，采用本文方法能够得到多组路径流量。本文算法从理论上克服了针对凸规划的经典算法的局限性，更具有普适性。

3)本文的模型与算法用于小规模算例效果良好、符合预期。当应用于大规模问题时,MSDP的内存消耗过高，会出现内存溢出情况。笔者在工作中验证了稀疏性的可行性，后续工作是研究面向问题的具体稀疏方法以进一步提高性能，这项工作将具有很大的挑战性。