基于有效路徑集逐步生成的網絡交通流分配方法

何勝學

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

0 引 言

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

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

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

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

1.1 基本參變量

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

1.2 網絡交通流平衡分配模型

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

(6)

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

(7)

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

2 求解算法

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

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

(8)

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

(9)

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

(10)

(11)

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

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

(12)

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

2.2 算法的有效性證明

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

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

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

2.3 內嵌的投影精確解確定方法

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

觀察可知2.1的相關投影梯度算法可分別針對不同的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).由下面的簡單代數計算.

(16)

(17)

(18)

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

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

問題(14)的目標函數.

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

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

圖1 問題(14)對應的交通流分配網絡

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

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

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

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

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

很多學生在參與中長跑活動后會出現一些副作用，包括胸悶、氣短、臉色發白等，這些副作用讓學生對中長跑活動存有一定的抵觸心理。所以教師要云用合適的方法引導學生去“善后”，幫助學生去可致不良反應，這樣能夠讓學生環節對中長跑活動的為難心理。如教師可以帶領學生做一些保健按摩、放松操，適當的做一些簡單的輕松的小游戲等，讓學生對中長跑活動不再抵觸。

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

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

3 算例分析

圖2 具有13個節點的交通網絡

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

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

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

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

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

4 結 束 語

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