城市區域交通網絡的線性互補模型和快速算法

鄭華，劉玲

城市區域交通網絡的線性互補模型和快速算法

鄭華，劉玲

（韶關學院數學與統計學院，廣東韶關512005）

結合區域交通網絡的特殊性對問題進行合理簡化得到線性互補模型，用以描述平衡狀態下的交通流量，利用模型的線性性質設計快速求解方法，可以解決一類特殊的實際問題.

交通流均衡模型；線性互補模型；無模線性方法

城市交通擁堵已成為阻礙社會經濟發展的主要瓶頸之一，如何緩解交通擁堵是相關學者面對的難題.城市交通系統是由許多要素按照特定的關系組成的一個有機整體，任意一個要素的微小變化都會對整個系統產生影響，引起交通網絡運行的變化.為了刻畫交通網絡中交通流變化的整體性質，經典的Wardrop準則［1］假設出行車輛滿足以下兩個條件：

（1）所有車輛獨立地做出令自己運行時間最小的決策，即在相同的起訖點(稱為OD對)之間，被使用路徑的運行時間不超過未被使用路徑的運行時間；

（2）所有車輛以“網絡總旅行時間最小”為目標來選擇路徑.

用W表示為交通網絡中全部OD對的集合，A表示為交通網絡中全部路段的集合，n表示該交通網絡中的路徑總數.?w∈W，表示為路徑的OD對w之間第k條路徑的路徑流量，表示為路徑的OD對w之間第k條路徑的通行時間表示路徑的OD對w之間最短路徑的通行時間，qw表示OD對w之間在平衡狀態下的交通流量的關系是：

其中Ta是路段a的路段通行時間函數是路段的連接關系變量，反映路徑k與路段a之間的關系，即如果路徑k包含路段a，則=1，否則=0；記γwk是“路徑—OD對”關聯變量，Γwk定義為如果路徑k在所考慮的OD對w中，則Γwk=1，否則Γwk=0.

記OD對w的流量需求為qw，e為全1向量，設：

從Wardrop準則出發，最終所有路徑的交通流將趨于穩定，可得到交通流均衡模型［1-2］如下：

其中

由于F（z）是非線性函數，在沒有任何假設的前提下，通常較難得到適用于一般交通網絡的算法.本文考慮結合城市區域交通網絡的特殊性，對模型（1）做合理的假設簡化得到線性互補模型，并設計與之匹配的快速算法，能高效求解得到平衡狀態下各路徑的交通流.

1線性互補模型及其快速算法

為了降低模型（1）的求解難度，同時匹配城市區域交通的特殊性，考慮對F（z）中的兩個函數關系Ta（fw）以及做線性化近似.

首先，設定在第k條路徑路徑流量fkw與路徑通行時間Ta的關系式為：上式的含義是路段a的路段通行時間由兩部分組成，一方面由路段流量造成的運行時間，式中Sk是第k條路徑的距離長，vk是車輛在第k條路徑的平均行駛速度；另一方面考慮到車輛在第k個路段的行駛過程中，由于紅綠燈、行人、交叉口等因素的影響，會對理論的行駛時間產生隨機影響，基于此引入白噪聲bk刻畫各路段的運行時間［3］，即bk服從標準正態分布N（0,1）.此時便有：

這里非負常數σ通過平衡狀態下的交通流信息獲取,進一步利用Taylor公式做線性化近似［4-5］有：

記：

可得F（z）=Az+q這樣就得到了交通流均衡簡化模型：

這是一個線性互補模型［6-8］.

基于模型（3），充分利用其特殊性質，可設計與之匹配的快速算法.

定理1如果△是列滿秩矩陣,那么由（2）定義的矩陣A是正定矩陣.

12非奇異的，因此△T△D是正定矩陣,結合σ>0,就有xTAx＞0,這表明A是正定矩陣.證畢.

注：定理1表明在所構造的模型（3）中，A為特殊的正定矩陣，因此可充分利用正定線性互補問題的無模線性方法［9］進行快速求解，得到交通網絡在平衡狀態下各路徑的交通流，這也說明對交通流均衡模型所做的簡化假設對于模型求解是有效的.

因為△是列滿秩矩陣，且顯然

2實際應用

2016年國務院發布《關于進一步加強城市規劃建設管理工作的若干意見》后，關于城市小區是否應該開放成為了熱點討論問題，本節從小區開放對周邊道路通行的影響角度，應用模型（3）設計相應的算法給出該問題的解決方案.

小區及其周邊道路交通網絡是較小的區域交通網絡,各路徑的交通流差別不會太大，在此情形下上節對T（afw）以及qw（twmin）所做的線性化近似是合理的，因此可以利用模型（3）刻畫該問題，進而構建求解模型（3）的快速算法，可求出小區及其周邊交通網絡在平衡狀態下各路徑的交通流.

顯然，模型（3）中的相關參數在小區開放前后意味著數據量的增減，而小區開放后所增加的路徑在小區開放前可視作流量為0，并且在△，Γ兩個矩陣中體現為相關元素由0變為1.因此，為了節省計算機內存通信時間，先在小區開放后求解模型（3），再計算小區開放前的情形.

結合上節討論，建立該問題的求解方法如下：

Step 1:小區開放后的數據輸入.

①根據交通網絡圖的頂點和邊的信息可得到△，Γ，Sk；

②σ通過平衡狀態下的觀測交通流通過負指數擬合得到［10］；

③平均行駛速度vk由給定交通網絡各路段的限速信息得到；

④白噪聲bk由數學軟件MATLAB的randn命令生成［11］.

Step 2:用無模線性方法求解（3）得到各路徑的流量向量fw(1)以及最小行駛時間

Step 3:改變△，Γ，Sk，vk中相關路段的參數，使之符合小區開放前的要求.

Step 4:用無模線性方法［3］求解（3）得到各路徑的流量向量fw(2)以及最小行駛時間

一旦由上述算法計算得到了該小區周邊交通網絡在小區開放前后的流量和最小行駛時間對比，就可以用來計算相關指標，從而評價小區開放對周邊道路通行的影響，進而給交管部門提出建議.

3結語

本文考慮城市區域交通網絡的特殊性，對交通流均衡模型做合理的簡化假設得到線性互補模型,該簡化假設適用于實際應用中的一類特殊交通網絡問題(比如小區開放對周邊道路通行的影響)，并針對特殊的模型設計了快速算法.本文的建模和算法設計思想可以推廣到其他特殊的交通網絡問題中.

參考文獻：

［1］程琳.城市交通網絡流理論[M].南京:東南大學出版社，2010.

［2］于雷，宋國華.城市交通流理論[M].北京：北京交通大學出版社，2016.

［3］何書元.應用時間序列分析[M].北京：北京大學出版社，2003.

［4］張筑生.數學分析新講,第一冊[M].北京：北京大學出版社，1990.

［5］蔣爾雄，趙風光，蘇仰鋒.數值逼近[M].上海：復旦大學出版社，2008.

［6］韓繼業，修乃華，戚厚鐸.非線性互補理論與算法[M].上海:上海科學技術出版社，2006．

［7］Cottle R W,Pang J S,Stone R E.The linear complementarity problem[M].SanDiego:Academic,1992．

［8］Murty K G.Linear complementarity,linear and nonlinear programming[M].Berlin:Heldermann Verlag,1988．

［9］Zheng H,Li W，Qu W.A non-modulus linear method for solving the linear complementarity problem[J].Linear Algebra and its Applications,2016(495):38-50.

［10］李慶揚，王能超，易大義.數值分析[M].北京：高等教育出版社，2008.

［11］劉衛國.MATLAB程序設計與應用[M].北京：高等教育出版社，2008.

On the Linear Complementarity Model for Urban Regional Transportation Network and Its Fast Algorithm

ZHENG Hua，LIU Ling
（School of Mathematics and Statistics，Shaoguan University，Shaoguan 512005，Guangdong，China）

By reasonable simple assumptions from the specific characteristics of the regional transportation network，linear complementarity model is obtained to describe the traffic flow in equilibrium.Fast algorithm is established by the linear property of the model，to solve some special practical problems.

traffic flow equilibrium model;linear complementarity model;non-modulus linear method

O224%

A%%%

1007-5348（2017）03-0005-04

（責任編輯：邵曉軍）

2016-11-28

韶關市科技計劃項目（韶科[2016]44/15）.

鄭華（1982-），男，廣東韶關人，韶關學院數學與統計學院講師，博士；研究方向：計算數學.