基于有效路徑集逐步生成的網(wǎng)絡(luò)交通流分配方法

何勝學(xué)

(上海理工大學(xué)管理學(xué)院 上海 200093)

0 引 言

有效的交通流分配有助于設(shè)計有效的交通信號控制方案、完善交通基礎(chǔ)設(shè)施建設(shè)、提升交通誘導(dǎo)信息質(zhì)量.實現(xiàn)網(wǎng)絡(luò)交通流分配的方法大致可分為基于路段的配流方法和基于路徑的配流方法.由于現(xiàn)實中一般很難預(yù)知所有的有效路徑，因此基于路徑的交通流分配方法一般用于小規(guī)模的路網(wǎng)和理論分析.而等價的基于路段的交通流分配方法則在各類實踐中被廣泛應(yīng)用.與基于路段的配流方法相比，基于路徑的配流方法具有更強的解釋性，其配流結(jié)果更加直觀，因此更方便被用于其他領(lǐng)域.本文將嘗試解決基于路徑配流方法面臨的有效路徑集合一般無法提前預(yù)知的難題，并針對投影集合特征，改進投影梯度類算法的投影操作效率.

在解決無法預(yù)知有效路徑集方面，最常見的處理方法是將有效路徑行程時間或出行費用限定在一定范圍，例如，限定在當前最短路徑對應(yīng)值的一個倍數(shù)范圍之內(nèi)[1-2].文獻[3-4]提出了一些方法來確定上述的有效路徑.何勝學(xué)等[5]提出利用起訖點對的相對位置，模擬重力場，利用水流的流動確定給定起訖點對間的有效路徑集.另一個常用方法是直接利用圖論中的K最短路方法搜索有效路徑集合.在基于路段的交通流分配結(jié)束后，文獻[6-7]提出了利用線路流量持續(xù)分解得到任意起訖點對間實際被選路徑的一種有效方法.另一種常用方法是記錄在執(zhí)行“全有全無”步驟時產(chǎn)生的最短路，將其作為最終的有效路徑集合元素[8].與上述研究不同，本文將結(jié)合基于路徑的交通流分配方法，在算法的執(zhí)行過程中逐步生成有效路徑集合，并在算法收斂時得到實際被選用的路徑集合、對應(yīng)的路徑流量和路徑出行費用.

基于路徑的交通流分配方法中，最常用是投影梯度類算法.而該類算法的核心步驟是進行投影操作.為了提升投影操作的效率，本文將摒棄求解投影的二次規(guī)劃類經(jīng)典方法，針對投影集合的特征設(shè)計一個無需迭代可一次性確定投影精確解的有效算法，并通過數(shù)值試驗驗證新方法的有效性.

1 基于路徑的交通流分配模型

1.1 基本參變量

W為交通網(wǎng)絡(luò)中的起訖點對集合；w為交通網(wǎng)絡(luò)一個典型起訖點對(OD對)，w∈W；dw為OD對w間的交通出行需求量；Rw為OD對w間所有有效路徑集合；Pw為OD對w間已知的有效路徑集合；p為交通路網(wǎng)中的一條路徑；xw,p為連接OD對w的路徑p上的路徑流量；cw,p為連接OD對w的路徑p的出行費用，一般指路徑的行程時間；x為由所有有效路徑流量組成的網(wǎng)絡(luò)路徑流向量，稱為網(wǎng)絡(luò)路徑流量模式；ΠQ(·)為向集合Q進行投影操作；*為上標，指示對應(yīng)的量為網(wǎng)絡(luò)流量處于平衡狀態(tài)時的對應(yīng)量值.

1.2 網(wǎng)絡(luò)交通流平衡分配模型

根據(jù)經(jīng)典交通流分配理論，網(wǎng)絡(luò)交通流處于平衡狀態(tài)時應(yīng)滿足Wardrop第一原則，即用戶均衡原則[9].Wardrop第一原則表明當網(wǎng)絡(luò)流處于平衡狀態(tài)時，任一OD對間實際被選用的出行路徑具有相同且最小的出行阻抗，而未被選取的路徑阻抗均大于或等于上述阻抗.路徑行程時間是一種常用的路徑出行阻抗.

(1)

將對應(yīng)OD對w間的所有有效路徑上的上述不等式加和，可得：

(2)

可對(2)作如下的代數(shù)計算：

(3)

考慮到任意可行流量模式x與平衡條件下的流量模式x*均須滿足∑p∈Rwxw,p=dw，因此

(4)

將對應(yīng)所有OD對的不等式(4)加和，得到最終的網(wǎng)絡(luò)流平衡模型為

(5)

(6)

xw,p≥0，?w∈W,p∈Rw

(7)

式(5)為平衡路徑流需要滿足的變分不等式；式(6)為路徑流量在OD對上的流量守恒約束；式(7)為路徑流量的非負約束.

2 求解算法

2.1 基于有效路徑集逐步生成的修正投影梯度算法

在有效路徑集合逐步生成條件下，對經(jīng)典的修正投影算法加以改進，得到求解問題(5)的算法步驟如下.

(8)

xw,p≥0，?w∈W,p∈Pw

(9)

在約束集合Qw上，進行如下的投影.

(10)

(11)

步驟3如果|xk+1-xk|≤θ，算法終止；否則，令k:=k+1，轉(zhuǎn)步驟2.

如果將投影操作(7)和(8)用下面的單一投影操作代替，

(12)

上面的修正投影梯度算法就變成了經(jīng)典投影梯度算法.一般而言，修正投影梯度算法比投影梯度算法要求的算法收斂條件低，但是計算量相對較大.

2.2 算法的有效性證明

定理1當2.1給出的修正投影梯度算法(或投影梯度算法)收斂時，得到的路徑流量在整個交通路網(wǎng)上滿足Wardrop第一原則.

證明設(shè)OD對w間的所有有效路徑集合為Rw，當前已知的OD對w間的所有有效路徑集合為Pw.Rw與Pw之間的關(guān)聯(lián)機制如下：在xk流量模式下，得到OD對w間的一條最短路徑pw；如果pw?Pw，則令Pw:=Pw∪{pw}，xw,pw=0；否則，Pw保持不變.

如果在執(zhí)行第k+1次迭代時，Pw保持不變，那么根據(jù)投影理論[10]，在集合Pw上，Wardrop第一原則成立；而此時，集合Rw-Pw中所有路徑流量為0，而且其中的最短路徑出行費用與Pw中最短路徑的出行費用相等，因此可以看出在Rw上Wardrop第一原則依然成立.

2.3 內(nèi)嵌的投影精確解確定方法

在2.1的相關(guān)投影梯度算法中，需要反復(fù)進行投影操作.如果采用常見的二次規(guī)劃算法求解該投影子問題，一般需要較多的迭代計算才能得到滿意的投影結(jié)果.為了提高投影操作效率，針對投影的具體集合特征，下面給出一個無需迭代的投影精確解確定方法.

觀察可知2.1的相關(guān)投影梯度算法可分別針對不同的OD對進行，而對于任一給定OD對w，需要在其上進行投影的集合具有如下形式.

(13)

xw,p≥0，?p∈Pw

(14)

(15)

式中：集合X={x=(x1,x2,…,xn)|∑ixi=D且xi≥0,?i=1,2,…,n}.

首先分析如何求解問題(11).由下面的簡單代數(shù)計算.

(16)

(17)

(18)

定理2問題(11)與問題(14)等價.

證明問題(13)的目標函數(shù)：

問題(14)的目標函數(shù).

由上面的計算可知，具有相同約束集合的問題(13)與問題(14)的目標函數(shù)僅相差一個常數(shù)項，因此兩者等價.而已知問題(11)與問題(13)等價，因此問題(11)與問題(14)等價.

圖1為對應(yīng)問題(14)的交通流分配網(wǎng)絡(luò).其中起點r到終點s的總流量為D；連接起點r和終點s有n條路徑，其中路徑i的流量和行程時間函數(shù)分別表示為xi和xi+bi.根據(jù)經(jīng)典交通流分配理論，問題(14)是對應(yīng)圖(1)中路網(wǎng)的用戶均衡配流模型.而用戶均衡配流模型的最優(yōu)路徑流量需滿足Wardrop第一原則.依據(jù)Wardrop第一原則，可以設(shè)計求解問題(14)的無迭代精確解算法.

圖1 問題(14)對應(yīng)的交通流分配網(wǎng)絡(luò)

算法的基本思路簡述如下.假設(shè)b1≤b2≤…≤bn成立；否則，對b中元素加以重新排序與編號，使其滿足上述條件.接下來確定路徑流量，具體思路如下：出行者首先選擇路徑1(對應(yīng)路徑阻抗x1+b1)；而當在該路徑上的當前流量x10滿足：x10+b1=b2時，出行者將同時選擇路徑1和路徑2(對應(yīng)路徑阻抗x2+b2)出行，并保持兩條路徑的出行阻抗相等；而當兩條路徑上的當前流量滿足x10+x20+b1=x20+b2=b3時，出行者將選擇路徑1，2，3同時出行，并保持三條路線的出行阻抗相等.上述操作可以持續(xù)進行，直到所有流量被加載上網(wǎng).

具體的路徑流量確定步驟總結(jié)如下．

步驟1依次考慮路徑1，2，…,n；設(shè)當前的路徑為i.

步驟2如果i+1≤n，令：xi0=bi+1-bi.

xj:=xj+xi0，?j=1,2,…,i；

很多學(xué)生在參與中長跑活動后會出現(xiàn)一些副作用，包括胸悶、氣短、臉色發(fā)白等，這些副作用讓學(xué)生對中長跑活動存有一定的抵觸心理。所以教師要云用合適的方法引導(dǎo)學(xué)生去“善后”，幫助學(xué)生去可致不良反應(yīng)，這樣能夠讓學(xué)生環(huán)節(jié)對中長跑活動的為難心理。如教師可以帶領(lǐng)學(xué)生做一些保健按摩、放松操，適當?shù)淖鲆恍┖唵蔚妮p松的小游戲等，讓學(xué)生對中長跑活動不再抵觸。

xj:=0，?j∈{k|k>i}.

步驟3如果i=n，進行如下路徑流量更新.

3 算例分析

圖2 具有13個節(jié)點的交通網(wǎng)絡(luò)

表1的流量列情景1列出了基于路段的Frank-Wolfe算法的路段流量解，情景2列出了基于有效路徑逐步生成的梯度投影算法的路段流量解.通過對比可知，兩種算法得到的路段流量基本一致，證實了新方法的有效性.

表1 路段行程時間函數(shù)的參數(shù)和均衡流量

表2 已知有效路徑均衡流量和行程時間

從結(jié)果可以看出除了OD對(1,4)之間有兩條有效路徑被實際選用，其他OD對間均只有一條有效路徑被選用.表中的路徑流量和行程時間符合Wardrop第一原則.

新算法的迭代終止閥值θ設(shè)為0.000 5，算法執(zhí)行254次終止.同樣閥值下，F(xiàn)rank-Wolfe算法執(zhí)行136次終止.在不同閥值和OD需求量條件下，兩種算法的執(zhí)行次數(shù)表現(xiàn)差異較大，兩者間不存在必然的優(yōu)劣關(guān)系.在基于路段的Frank-Wolfe法流量分配結(jié)束后，計算各OD對間最短路的行程時間，結(jié)果為：對應(yīng)OD對(1,3)、(1,4)、(2,3)和(2,4)的最短行程時間分別為30.288、54.050、48.024和40.873.上述結(jié)果與表2中各OD對間最短行程時間比較，可知兩者基本一致.

4 結(jié) 束 語

通過在投影梯度類算法執(zhí)行過程中，不斷搜索各OD對間的最短路徑，逐步擴展各OD對之間可選的有效路徑集合，從而實現(xiàn)在算法收斂條件下有效路徑集合的構(gòu)建和網(wǎng)絡(luò)交通流量分配.通過問題形式的轉(zhuǎn)化，可以將算法中的投影操作轉(zhuǎn)化為一個簡單路網(wǎng)上的流量分配問題，進而設(shè)計了求解投影的無迭代精確算法.通過解決上述兩個問題，可以使傳統(tǒng)的基于路徑的網(wǎng)絡(luò)交通流分配方法更有效地應(yīng)用于實際.