具有路段容量限制的廣義系統(tǒng)最優(yōu)交通分配

俞禮軍

(華南理工大學(xué) 土木與交通學(xué)院，廣東 廣州 510640)

基于給定起點(diǎn)-目的地交通需求并按照一定的擇路原則確定運(yùn)輸網(wǎng)絡(luò)中路段平衡流量的問題通常稱為交通分配問題(TAP)，其是運(yùn)輸系統(tǒng)分析中的經(jīng)典問題。文獻(xiàn)[1]中Wardrop提出的用戶均衡(UE)和系統(tǒng)最優(yōu)(SO)是交通分配中常見的基本原則。Beckmann等[2]最早提出滿足UE原理的凸數(shù)學(xué)規(guī)劃Beckmann模型。LeBlanc等[3]首次將經(jīng)典的Frank-Wolfe算法用在小型網(wǎng)絡(luò)上。Beckmann模型與經(jīng)典SO模型屬于無路段容量約束的凸規(guī)劃模型。這兩類經(jīng)典模型一直是重要的研究對(duì)象。其中UE模型(Beckmann模型)相對(duì)于SO模型體現(xiàn)一定的自由競爭內(nèi)涵且其對(duì)應(yīng)的算法做些微改造即可用于SO模型，因而成為絕大多數(shù)研究者關(guān)注的對(duì)象。Beckmann模型與SO模型使用的絕大多數(shù)路段阻抗函數(shù)，包括著名的BPR函數(shù)，都屬于多項(xiàng)式函數(shù)。求解基于此類多項(xiàng)式路段阻抗函數(shù)的Beckmann模型或系統(tǒng)最優(yōu)(SO)模型，其平衡解可能包含相當(dāng)多的過飽和路段，極端情況下得到的個(gè)別路段流量是容量的2～3倍。超過通行能力的高流量路段是不切實(shí)際的，這樣的計(jì)算結(jié)果對(duì)于在第一線上的從業(yè)者當(dāng)然是不能令人滿意的。從理論和實(shí)踐上考慮，路段上的流量不應(yīng)高于其通行能力。Daganzo[4- 5]使用漸進(jìn)函數(shù)的方法來處理這個(gè)問題，即設(shè)計(jì)一種路段阻抗函數(shù)，當(dāng)流量趨于通行能力時(shí)，時(shí)間就趨于無窮大。Boyce等[6]認(rèn)為路段旅行時(shí)間數(shù)值異常大的結(jié)果有違現(xiàn)實(shí)。為克服此問題，一個(gè)很自然的想法就是在Beckmann模型中添加路段流量小于等于其通行能力的約束，如此則得到與經(jīng)典意義上的Wardrop均衡狀態(tài)不同的結(jié)果。研究者針對(duì)此新模型定義了一種新的用戶均衡狀態(tài)。不同于帶流量約束的Beckmann模型，含通行能力約束下的SO模型的交通分配結(jié)果與經(jīng)典SO原則可能是不同的，而目前尚未有關(guān)于此問題的深入研究成果。故此，在路段容量限制條件下建立新的SO模型是有意義的工作。

另一方面，目前理論與實(shí)踐中得到大量應(yīng)用的BPR路段阻抗函數(shù)屬于阻抗是流量增函數(shù)的多項(xiàng)式函數(shù)。基于此類阻抗函數(shù)的Beckmann模型與SO模型是凸規(guī)劃模型。對(duì)于具有路段容量約束且阻抗是流量增函數(shù)的路段,阻抗函數(shù)的UE均衡模型可以采用四種類型的收斂算法來求解Beckmann模型：內(nèi)部和外部懲罰函數(shù)方法[7]、拉格朗日乘數(shù)方法[8]、拉格朗日對(duì)偶方法[9]和對(duì)偶上升方法[10]。阻抗若不是流量增函數(shù)的多項(xiàng)式函數(shù)，則對(duì)應(yīng)的具有路段容量約束的SO模型可能不是凸規(guī)劃模型。例如，在節(jié)假日或者交通流事故等原因而受到交通管制條件下的交通流，盡管可以用多項(xiàng)式函數(shù)來描述，但其流量阻抗之間并不具有阻抗是流量增函數(shù)的特性，構(gòu)建的廣義SO模型通常是非凸模型。用于處理具有路段容量約束的凸UE均衡模型算法很難推廣到具有一般多項(xiàng)式阻抗函數(shù)和路段容量限制的非凸廣義SO模型。為此，有必要探求能夠求解具有一般多項(xiàng)式阻抗函數(shù)的廣義SO模型的方法。

應(yīng)當(dāng)指出，基于路段流量為變量的經(jīng)典SO模型是嚴(yán)格凸規(guī)劃問題，而基于路徑流量為變量的經(jīng)典SO問題是不嚴(yán)格凸的，即路徑流量解不是唯一的[1]。實(shí)際應(yīng)用中每個(gè)OD對(duì)的可行路徑通常在4到7條之間[11]，業(yè)者常常根據(jù)已有信息指定每個(gè)OD對(duì)的路徑并基于對(duì)應(yīng)的路徑變量求解經(jīng)典的SO問題，期望同時(shí)得到多個(gè)路徑流量解以便根據(jù)實(shí)際情況采取必要措施實(shí)現(xiàn)特定交通流的引導(dǎo)。對(duì)于這樣的問題，經(jīng)典方法較難穩(wěn)定地得到多組解。特別的，對(duì)基于路徑流量為變量的非凸廣義SO模型，采用經(jīng)典凸優(yōu)化算法求解是異常困難的，若此類非凸SO模型有多組最優(yōu)解，針對(duì)凸規(guī)劃的經(jīng)典算法不能處理此類問題。

綜上所述，具有一般的多項(xiàng)式阻抗函數(shù)和路段容量約束的廣義SO問題尚未解決。據(jù)作者所知，對(duì)于解決具有一般的多項(xiàng)式阻抗函數(shù)的廣義SO問題的障礙來自以下事實(shí)：在經(jīng)典定義與模型框架下，僅將一般的多項(xiàng)式阻抗函數(shù)與路段容量約束添加到任何標(biāo)準(zhǔn)SO模型中，無法獲得相應(yīng)等效SO條件，同時(shí)也缺乏求解非凸問題的算法。為此，本文針對(duì)經(jīng)典系統(tǒng)最優(yōu)(SO)模型的局限性，建立具有可分離的一般多項(xiàng)式阻抗函數(shù)和路段容量限制的廣義系統(tǒng)最優(yōu)交通分配模型并新定義廣義SO原則，該定義要求經(jīng)典SO模型與廣義SO模型的解都應(yīng)滿足廣義SO原則。關(guān)于廣義SO模型解的存在性是廣義SO問題中的一個(gè)大的挑戰(zhàn)。一般情況下建立的廣義SO模型不必然是凸模型。本文首先指出在非空、緊凸集上定義的擴(kuò)展SO模型具有至少一個(gè)全局最優(yōu)解，即所提出的模型滿足廣義SO原則。隨后提出一個(gè)問題：在解存在的情況下如何求新模型的解。根據(jù)廣義SO模型的特征，采用基于矩半定規(guī)劃的算法獲得廣義SO模型的全局最優(yōu)解。對(duì)于指定路徑并基于對(duì)應(yīng)路徑流量的廣義SO模型，若其存在多組路徑最優(yōu)解，則采用本文方法可以獲得多組路徑流量全局最優(yōu)解。

1 問題描述與模型

1.1 符號(hào)與假設(shè)

對(duì)整個(gè)交通網(wǎng)絡(luò)做以下假設(shè)：

(1)網(wǎng)絡(luò)是強(qiáng)連通的，即任一OD對(duì)之間至少有一條路徑連接;

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

(3)每一條路段a∈A有一個(gè)與之相對(duì)應(yīng)的實(shí)系數(shù)非負(fù)多項(xiàng)式路段阻抗函數(shù)且該路段阻抗函數(shù)是關(guān)于該路段流量的函數(shù)，即ta(za);

(4)O-D需求為正常數(shù)，OD需求可以通過網(wǎng)絡(luò)，即模型有可行解。

1.2 模型

在上述假設(shè)下，對(duì)應(yīng)的帶路段容量限制的系統(tǒng)最優(yōu)交通分配問題可以由如下非線性規(guī)劃模型描述：

(1)

上述模型也可以寫成如下等價(jià)的路段-節(jié)點(diǎn)模型[12]：

(2)

經(jīng)典SO模型屬于凸規(guī)劃模型，而上述模型(1)、(2)不必然是凸規(guī)劃模型。模型(1)、(2)的約束集為非空、緊致凸集[12]，模型目標(biāo)函數(shù)均為非負(fù)多項(xiàng)式，由Weierstrass定理知道，緊集上的多項(xiàng)式函數(shù)必然存在全局最優(yōu)解[13- 14]，即存在使系統(tǒng)的總交通時(shí)間全局最小的交通流分布。

廣義系統(tǒng)最優(yōu)交通分配：路段流量有容量約束或無容量約束條件下交通量按照某種方式分配以使系統(tǒng)的總交通時(shí)間全局最小。

按照廣義系統(tǒng)最優(yōu)交通分配定義可知，經(jīng)典SO模型與新模型的解都應(yīng)滿足擴(kuò)展廣義交通系統(tǒng)最優(yōu)條件，即廣義系統(tǒng)最優(yōu)交通分配定義是經(jīng)典系統(tǒng)最優(yōu)交通分配定義的擴(kuò)展。

對(duì)于非凸規(guī)劃模型，采用經(jīng)典方法獲得全局最優(yōu)解通常是非常困難的。近年來，半定規(guī)劃(SDP)[15]的凸松弛方法已經(jīng)成為優(yōu)化領(lǐng)域的研究熱點(diǎn)。對(duì)于非凸優(yōu)化問題，如果凸松弛可以提供與原始問題的解等效的結(jié)果，則可以通過解決該松弛問題來獲得原問題的全局最優(yōu)解。本文基于矩理論將上述模型轉(zhuǎn)化為等價(jià)的矩半定規(guī)劃(MSDP)模型，從而獲得原問題的全局最優(yōu)解。

為方便介紹與廣義SO模型等價(jià)的矩半定規(guī)劃模型與相應(yīng)計(jì)算方案，又因?yàn)橛胁糠掷碚搧碜源鷶?shù)幾何且并不顯而易見。故這里扼要給出半定規(guī)劃、多項(xiàng)式函數(shù)與矩相關(guān)的理論。

常見SDP問題指的是具有線性矩陣不等式(LMI)約束的線性目標(biāo)函數(shù)最小化問題。LMI問題是凸的，可以用內(nèi)點(diǎn)法有效地解決。

這里采用符號(hào)xα表示一個(gè)單項(xiàng)式，α為復(fù)合序號(hào)，α=[α1,…,αn]T∈Nn(包含0在內(nèi)的自然數(shù))，任意一個(gè)單項(xiàng)式可以表示為

(3)

采用記號(hào)|α|表示xα的階次

(4)

多項(xiàng)式函數(shù)中的每個(gè)單項(xiàng)式均可用一個(gè)新的變量表示，因而可將一個(gè)多項(xiàng)式函數(shù)表達(dá)為關(guān)于若干單項(xiàng)式(新變量)的線性組合。為便于線性化處理，階次不大于d的多項(xiàng)式，可以定義多項(xiàng)式基向量為

(5)

它包含最高階次為d的單項(xiàng)式，所有基都可以形式的表示為xα。

對(duì)于任意的d階多項(xiàng)式函數(shù)f(x)，其線性化表達(dá)式為

(6)

式中，fα為xα的系數(shù)，[fα]為系數(shù)向量。具體問題中，可以將d階函數(shù)寫成更高階的表達(dá)形式，這時(shí)高于階次d的單項(xiàng)式系數(shù)設(shè)為 0。

矩是概率論中的定量測度[16]，有多種用途[17]。矩可以表示為概率測度μ下的積分。 函數(shù)f(x)的矩函數(shù)L(f)可以寫成：

(7)

將式(6)代入函數(shù)的矩表達(dá)式(7)，可得

(8)

式中,yα是對(duì)應(yīng)于單項(xiàng)式xα的矩，即

(9)

令y0,…,0=1。

式(8)將函數(shù)f(x)的矩函數(shù)表示為關(guān)于矩變量yα的線性組合，它是矩半定規(guī)劃方法的重要組成部分。

將模型(1)或(2)的約束寫成不等式形式，借用上述關(guān)于多項(xiàng)式的符號(hào)表示，將相應(yīng)的SO模型表示為具有以下形式的多項(xiàng)式優(yōu)化問題：

(10)

式中，多項(xiàng)式gi(x)為約束函數(shù)，giα為單項(xiàng)式xα的系數(shù)。

矩半定規(guī)劃(MSDP) 松弛處理方法的思路是，將式(10)中的多項(xiàng)式目標(biāo)函數(shù)與約束函數(shù)轉(zhuǎn)化為關(guān)于矩變量的線性關(guān)系式的目標(biāo)函數(shù)以及關(guān)于矩變量的半正定矩陣約束，從而對(duì)多項(xiàng)式優(yōu)化問題(10)建立等價(jià)的凸半定規(guī)劃松弛模型。

為了建立模型(10)的SDP松弛模型，以下依次給出矩變量的LMI約束與不等式約束的LMI表示。

基于向量[x]s，可以定義對(duì)應(yīng)的s階矩矩陣Ms(y)：

(11)

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

(12)

式中：α1，α2∈Nn是其行序號(hào)和列序號(hào)，|α1|,|α2|≤s;矩陣Ms(y)是對(duì)稱的。

矩矩陣Ms(y)由所有矩變量yα組成，在矩變量空間，矩陣Ms(y)為正半定矩陣[13]，即

Ms(y)0

(13)

有了Ms(y)不難給出一組對(duì)稱矩陣，寫出其LMI表示形式。

給定多項(xiàng)式函數(shù)g(x)不等式約束，可以由階次不大于2s的部分矩變量yα定義(構(gòu)建)一個(gè)與g(x)相關(guān)的矩變量局部矩陣來刻畫原優(yōu)化問題的約束關(guān)系。一般采用部分矩變量yα(|α|≤2s)定義與多項(xiàng)式函數(shù)g(x)相關(guān)的局部化矩矩陣Ms′(gy)為

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

(14)

(15)

(16)

式中，L(g)是g(x)的矩函數(shù)，其表示為矩變量的線性組合；Ms′(y)為s′階矩矩陣；為保證L(g)Ms′(y)所得矩變量的最高階次不大于2s，要求s′>s。

約束g(x)≥0與矩陣Ms′(gy)正半定是等價(jià)關(guān)系[13]，即

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

(17)

式(13)是一個(gè)LMI約束,其揭示了矩變量之間的關(guān)系。式(17)表明不等式約束可以轉(zhuǎn)化為LMI形式。根據(jù)矩表達(dá)式(7)和半正定矩陣關(guān)系式(13)、(17)，可以得到廣義系統(tǒng)最優(yōu)模型(10)的等價(jià)SDP松弛模型(18)

(18)

原則上，模型(18)為標(biāo)準(zhǔn)的 SDP 問題，對(duì)于一般規(guī)模的問題，調(diào)用諸如SeDuMi[18]、SDPT3[19]等任意一款SDP計(jì)算軟件包均可求得模型(18)中的各個(gè)矩變量的解。

階數(shù)s可以設(shè)置為1,2,3，…。為了求出原問題的全局最優(yōu)解，需要一個(gè)全局最優(yōu)的充分條件。已有研究回答了這個(gè)問題。即

定理[20]：設(shè)y*為模型(18)的最優(yōu)矩解，當(dāng)矩矩陣的秩滿足如下條件：

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

(19)

則模型(18)的目標(biāo)值與原問題的全局最優(yōu)值f*相等。其中秩k表示原問題具有k個(gè)全局最優(yōu)解。

根據(jù)上述定理可以求得全局最優(yōu)的矩量解。至此還剩一個(gè)問題有待解決，即如何由該概率測度下所對(duì)應(yīng)的矩量解求得原問題的全局最優(yōu)解。若矩量矩陣的秩為1，對(duì)應(yīng)原問題的全局最優(yōu)解x*是唯一的，根據(jù)矩矩陣的結(jié)構(gòu)特點(diǎn)，x*可從M1(y*)的第1行(第1列)直接得到。若矩矩陣的秩為k且k大于1，則原問題有k個(gè)全局最優(yōu)解。此時(shí)采用三階段方法求解[21]：矩矩陣的奇異值分解；構(gòu)造提取等式；采用特征值法求解精確最優(yōu)解。

2 求解方案

待求解的均衡模型約束均為線性約束，又模型涉及的阻抗函數(shù)均為非負(fù)多項(xiàng)式，因而其約束、目標(biāo)函數(shù)均為多項(xiàng)式。為求解此類均衡問題，需將原均衡問題模型重新構(gòu)建為不等式約束的最優(yōu)化問題，并基于矩的理論進(jìn)一步將不等式約束的多項(xiàng)式優(yōu)化問題構(gòu)建為關(guān)于矩變量的半定規(guī)劃問題?；诰氐睦碚摰玫降陌攵ㄒ?guī)劃的松弛階次s=1,2,…,因而轉(zhuǎn)化后的SDP模型具有層次結(jié)構(gòu)。階s可以取很大的值，變量的數(shù)量隨著s的增加呈指數(shù)增長，這對(duì)于工程研究是不利的。幸運(yùn)的是，已有研究[13]證明了當(dāng)階s增加時(shí)，模型(18)的最優(yōu)值逼近原問題的全局最小值，一般的，相對(duì)較小的s值就可以達(dá)到全局最小值。

實(shí)際計(jì)算中，首先令基于矩的SDP模型中的s=1，并采用內(nèi)點(diǎn)法求得對(duì)應(yīng)SDP問題的矩解；再判斷矩解是否滿足全局最優(yōu)的充分條件，若不滿足則增大基于矩的SDP模型中的松弛階次，即s=s+1，重新求解直到找到一個(gè)恰當(dāng)?shù)膕滿足全局最優(yōu)條件；若滿足全局最優(yōu)的充分條件則進(jìn)一步采用三階段方法計(jì)算得到原問題的最優(yōu)解[21]。具體實(shí)現(xiàn)方法參看圖1的算法流程圖。

3 算例

3.1 算例1

這里使用如圖2所示的一個(gè)簡單網(wǎng)絡(luò)。此網(wǎng)絡(luò)由兩個(gè)結(jié)點(diǎn)以及連接兩結(jié)點(diǎn)的兩條并行的路段(路線)組成。圖中點(diǎn)1和點(diǎn)2分別為起點(diǎn)和終點(diǎn)。路段1是受到交通管制的交通流；路段 2 是正常使用的道路，其交通流呈現(xiàn)正常的旅行時(shí)間與流量呈現(xiàn)單調(diào)增加的關(guān)系。

路段1與路段2的時(shí)間阻抗函數(shù)(如圖3所示)由如下兩式給定：

(20)

t2(x2)=0.075 85x2+0.85

(21)

圖1 基于矩的SDP算法流程

圖2 簡單網(wǎng)絡(luò)

圖3 路段阻抗函數(shù)

假定從起點(diǎn)1到終點(diǎn)2的出行需求量是：D12=4輛/min。通行能力為2、4輛/min；假定出行者滿足系統(tǒng)最優(yōu)條件，確定出行者滿足系統(tǒng)最優(yōu)條件的路段流量問題可以用下面的模型來表達(dá):

(22)

經(jīng)整理之后，模型(22)轉(zhuǎn)化為

(23)

采用本文方法求解得到全局最優(yōu)解：x1=0,x2=4。本算例僅僅屬于示例，由圖4容易看出結(jié)果。事實(shí)上，采用經(jīng)典方法隨初值不同可能得到x1=0或x1=2。若模型中其他不改變，而將x1的約束條件改為0≤x1≤2.035 4，求解模型可以同時(shí)得到兩組解。x1=0,x2=4或x1=2.035 4，x2=1.964 6。

圖4 目標(biāo)函數(shù)

3.2 算例2

圖5 Nguyen and Dupuis網(wǎng)絡(luò)

表1 Nguyen-Dupuis網(wǎng)絡(luò)路段參數(shù)

表2 Nguyen-Dupuis網(wǎng)絡(luò)OD出行需求

系統(tǒng)最優(yōu)模型的目標(biāo)函數(shù)為

(24)

基于路段流量為變量的經(jīng)典SO模型是嚴(yán)格凸規(guī)劃問題，均衡狀態(tài)的路段交通量是唯一的。本算例模型屬于凸規(guī)劃模型。經(jīng)典的交通平衡配流模型路徑流量解通常不唯一。采用經(jīng)典方法與本文方法計(jì)算可得相同的路段交通量如表4所示。本算例為每個(gè)OD對(duì)指定5到8條可行路徑，基于指定路徑采用本文方法計(jì)算路徑流量如表5所示。而采用經(jīng)典方法較難穩(wěn)定地得到多組解。

如前所述，業(yè)者常常根據(jù)在實(shí)際應(yīng)用中獲得的經(jīng)驗(yàn)與信息為每個(gè)OD對(duì)指定可行路徑，構(gòu)建、求解基于指定路徑對(duì)應(yīng)的路徑變量為決策變量的廣義SO問題。由此得到的多組路徑流量在實(shí)際應(yīng)用中有特殊價(jià)值。據(jù)我們的調(diào)查，目前多數(shù)司機(jī)在使用特定信息系統(tǒng)提供的路徑指引。如何在以時(shí)間作為準(zhǔn)則的系統(tǒng)最優(yōu)的前提下得到多組路徑流量，結(jié)合其他因素為線路指引提供參考對(duì)于特定目的的調(diào)度指揮具有現(xiàn)實(shí)意義。文中提供了一種新方法，豐富了獲取系統(tǒng)最優(yōu)狀態(tài)時(shí)的多組路徑流量的手段。尤其對(duì)于基于路徑的非凸廣義SO模型，經(jīng)典算法不能處理此類問題，本文方法從理論上給出了獲得全局最優(yōu)解的通用解決方案。

表3 路段路徑關(guān)聯(lián)關(guān)系

表4 系統(tǒng)最優(yōu)時(shí)的路段流量

表5 系統(tǒng)最優(yōu)時(shí)的路徑流量

4 結(jié)語

本文中研究具有一般非負(fù)多項(xiàng)式阻抗函數(shù)和路段容量限制的廣義系統(tǒng)最優(yōu)交通分配問題的模型開發(fā)和算法設(shè)計(jì)?；跍y試算例，得到如下結(jié)論：

1)建立了廣義系統(tǒng)最優(yōu)交通分配模型并給出了獲取其全局最優(yōu)解的方法。本文定義的廣義系統(tǒng)最優(yōu)交通分配原則推廣了經(jīng)典的系統(tǒng)最優(yōu)交通分配原則。文中模型將經(jīng)典SO模型推廣為更為一般的情況，克服了經(jīng)典系統(tǒng)最優(yōu)交通分配模型所必須滿足凸規(guī)劃性質(zhì)的限制。提出的方法可以用來處理具有一般非負(fù)多項(xiàng)式阻抗的廣義系統(tǒng)最優(yōu)交通分配問題。

2)兩個(gè)測試算例的計(jì)算結(jié)果表明，MSDP松弛方法能夠有效求解具有一般非負(fù)多項(xiàng)式阻抗函數(shù)和路段容量限制的廣義系統(tǒng)最優(yōu)交通分配模型。對(duì)于存在多個(gè)全局最優(yōu)解的廣義系統(tǒng)最優(yōu)交通分配模型，本文算法能夠獲得多個(gè)全局最優(yōu)解。針對(duì)指定路徑并基于對(duì)應(yīng)的路徑變量的SO問題，若其存在多個(gè)全局最優(yōu)解，采用本文方法能夠得到多組路徑流量。本文算法從理論上克服了針對(duì)凸規(guī)劃的經(jīng)典算法的局限性，更具有普適性。

3)本文的模型與算法用于小規(guī)模算例效果良好、符合預(yù)期。當(dāng)應(yīng)用于大規(guī)模問題時(shí),MSDP的內(nèi)存消耗過高，會(huì)出現(xiàn)內(nèi)存溢出情況。筆者在工作中驗(yàn)證了稀疏性的可行性，后續(xù)工作是研究面向問題的具體稀疏方法以進(jìn)一步提高性能，這項(xiàng)工作將具有很大的挑戰(zhàn)性。