已知起點需求和部分路段流量的交通OD 反推模型及算法

何勝學

（上海理工大學管理學院，上海200093）

隨著各種交通檢測技術的發展和交通量檢測器的網絡布設，獲取路網中部分路段交通流量也變得比較容易[1]。出于經濟角度的考慮，目前全網范圍的檢測器布設還不現實[2]。本文希望針對起點交通生成量已知和部分路段流量可測條件下的交通OD 反推展開研究，提升現有研究的針對性和可行性。

交通流分配中OD 量作為輸入，直接影響分配結果的有效性[3-4]。但是由于通過交通調查得到OD 量的復雜性和耗時性，利用已有信息對OD 量進行反推逐漸被理論研究者和實踐工作者重視。 OD 反推大致分為靜態和動態兩大類[5]。靜態反推研究形成了最大熵模型、最小二乘模型、最大似然模型和貝葉斯模型等。由于這些模型多假設現狀OD 矩陣已知， 并通過建立OD 量與路段流量的直接關聯關系， 期望推算出未來的OD量，因此現有模型需要的數據調查量仍然很大。 動態OD 反推是目前交通理論研究的一個重點，但是考慮到目前與之對應的動態交通流分配技術的停滯，相關研究的實用性還有待進一步證實。 由于OD 反推與交通流分配結果的密切相關，而實現網絡交通流分配的計算復雜性，研究者開始著眼于如何有效利用各種現有交通規劃和仿真軟件實現OD 反推[5-8]。同時研究者也開始將OD 反推融合于其他相關研究，如路網脆弱性分析和高速公路效益評估[9-10]。 與現有研究相比，本文將考慮已知起點交通生成量，而非現狀OD 矩陣，因此前期交通調查的工作量大大降低。 與傳統理論利用單層模型簡化出行者路線選擇行為相比，本文將利用雙層規劃理論直接將交通流分配作為下層模型，從而提升反推結果的可靠性。

本文的主要研究貢獻包括： ① 在起點交通生成量已知和部分路段流量可測條件下建立了OD 反推的優化模型；②基于上層約束的線性單純性特征，設計了求解上層模型的近似Frank-Wolfe 算法；③利用微分近似處理不可導抽象函數的偏導數和采用Armijo 搜索減少調用求解下層模型的子程序，從而提升了新算法的效率和有效性。

1 參變量介紹與問題

1.1 參變量簡介

1.2 問題介紹

2 雙層規劃模型

根據交通網絡均衡狀態下得到的路段流量xa（q），?a∈A 應當與觀測得到的路段流量xa，?a∈A 相等或接近，建立如下的上層規劃模型

約束

上述模型的約束（2）表示來自同一起點的交通需求量之和應當等于該起點的交通生成量；約束（3）是交通需求量的非負約束。 目標函數（1）表示在可觀測路段集合上，均衡狀態下的路段流量與觀測路段流量之間的誤差應當越小越好。 均衡狀態下的xa（q）將在給定q 條件下通過下層的用戶均衡模型求得。 與現有的OD 反推模型相比，我們增加了起點交通生成量qr，?r∈O 已知的約束條件（2）。 該條件的增加將拓展現有OD 反推理論的應用場景，但也使得模型的求解變得更加復雜，下一節將給出一種針對上述模型的有效求解算法。

3 求解算法設計

在上層目標函數（1）中，xa（q）表示可由給定的q 確定對應的路段流量x。xa（q）的實現需要求解下層的用戶均衡流量分配模型。 下面給出求解下層模型的經典Frank-Wolfe 算法步驟：

4 算例分析

本節利用Nguyen 和Dupius 路網[12]來對本文提出的模型和算法加以驗證。 該路網包含13 個節點，其中節點1 和2 為起點，3 和4 為終點。 相關節點和路段的標號已在圖1 中標示。算法的終止參數設定為ε=0.001 和ε′=0.001。 上層模型算法中Armijo 步長搜索的參數設定為σ=0.6，β=0.5 和s=0.5。 設定起點1 和2 的交通生成量分別為1 800 和1 600。 我們將采用常用的BPR 函數ta（xa）=ta0［1＋0.15（xa/Ca）4］作 為 路 段 行 程 時 間 函數。 表1 給出了各路段的自由流行程時間ta0和通行能力Ca。 路網中路段5，7 和13 構成可觀測到流量的路段集合。 為了比較驗證算法的有效性，我們分三種情景為上述3 條路段假設不同的觀測交通流量，具體分情景的觀測路段流量見表2。

圖1 13 個節點的Nguyen 和Dupius 路網Fig.1 Nguyen and Dupius Network with 13 nodes

利用Java 程序語言實現上節的算法，并在NetBeans IDE 8.0.2 環境下執行。 不同情境下路段均衡流量的計算結果總結在表1；可觀測路段的計算交通流量在表2 中列出；最終得到的OD 交通需求量在表3 中給出。利用節點流量守恒條件可判定表1 中路段流量計算結果的合理性。三種情境下算法整體依次執行9，16和11 次后收斂，三種情境下雙層模型整體求解的運行時間均小于0.001 s（即計算機顯示執行時間為0，小于其可給出的最小時間單位0.001 s）。

表1 路段行程時間函數的參數和均衡流量Tab.1 Coefficients of link travel time functions and the equilibrium flows on links

表2 不同情境下路段流量的觀測值和計算值對比Tab.2 Observed and calculated flows on observable links with respect to different scenarios

5 結論

在已知起點交通生成量和部分路段流量可觀測條件下，推算起訖點對間的分布交通需求需要考慮出行者路線選擇行為的影響。本文利用雙層規劃模型分別將出行者的路徑選擇行為和如何利用可觀測路段流量構建為數學規劃模型，從而實現擇路行為滿足用戶均衡原則條件下路段的分配流量與觀測流量間差異的最小化。 考慮到上層模型約束的單純形特點，為其設計了一個近似Frank-Wolfe 算法。 該近似算法中目標函數對變量的偏導數利用微分定義進行了近似處理。 本研究不僅針對一類特殊的OD 量反推問題給出了對應模型與算法，而且為處理類似問題提供了新的思路方法。