交通網絡結構優化的改進Dial算法＊

曾明華 李夏苗

(華東交通大學軌道交通學院1) 南昌 330013) (中南大學交通運輸工程學院2) 長沙 410075)

國內外對交通運輸網絡結構研究很多,在研究方法和手段上,基本上利用分形分析方法[1]、耗散結構理論[2]、復雜網絡[3]或傳統理論如數學規劃[4]等理論來研究交通運輸網絡結構形態.從研究的內容來看,對各種交通運輸方式之間的結構問題進行研究的成果相對較多[5].城市交通平衡網絡設計問題也是研究交通運輸網絡結構的一個重要方面[6].這些研究在交通網絡規劃中占有非常重要的地位,但是,可以認為這些對交通網絡結構的研究絕大多數只是在采用的具體理論與方法工具上有所差異.由于層次性是交通運輸網絡的幾大系統特性之一,層次性觀點是現代系統論三大支柱觀點之一,且以往關于層次性的研究成果較少,因此,本文將從交通網絡本身的基本特征——層次性出發,換一個角度來研究交通網絡的結構優化問題.

1 符號系統

2 交通網絡結構優化算法

Logit加載是隨機交通分配的2種經典分配技術之一.基于Logit加載的SUE交通分配模型雖有缺陷,卻十分簡潔、流行.本文基于層次性設計的改進Dial算法仍然是一種Logit交通分配算法;更為重要的是,改進Dial算法區別對待網絡中不同層次的路段,能得到比Dial算法性能更優的交通網絡結構.

2.1 算法基礎及原理分析

2.1.1 實踐基礎 不同級別的路段,其通行能力和服務水平存在差別,它們有著較為明顯的功能定位差異.陸建和胡剛[7]根據常規公交線路客流特征和公交出行服務水平調查,參照道路劃分標準,將常規公交線路劃分為三個層次：公交主干線、公交次干線和公交支線.

美國在1950年提出了“市區道路網規劃中根據高速道路、干線道路、局部道路的不同功能賦予明確的特性分工,按一定層次構成網絡”的思路.我國在交通運輸網絡規劃如城市公交網絡規劃中也常采用這種方法[8].

但關于交通網絡分層規劃的實踐,基本上建立在經驗和感性認識之上,缺乏一定的基礎理論支持.國內外在交通網絡分層規劃的理論研究方面較為缺乏,大大滯后于規劃實踐.就我國而言,相對于大量的工程實踐也是遠遠不夠的[9].

2.1.2 理論依據 Dial算法的核心技術要點之一是采用最短路徑搜索技術確定被選擇的路徑,常用的最短路搜索算法是Dijkstra算法及其變體.根據人類思維特點及消費者行為心理學,出行者往往使自己的最優路徑選擇盡可能地在高階層次完成.然而,這在交通網絡平衡配流算法通常所采用的最短路徑搜索算法尋找到的最短路徑(不管是以阻抗還是距離作路段長度的衡量準則)中并不能得以體現.原因在于,那樣所得到的最短路徑中往往包含一些狹窄的小巷或者由其他一些等級較低的路段構成,因而不能滿足交通用戶的舒適性和便捷性的心理需求;同時在這些低等級線路上行駛有更大幾率碰到交通突發事件,安全性也大打折扣;且如果這些路段分配的流量過大,還會妨礙社區鄰里的生活;更何況,這樣的低等級路段越多,所需切換的次數越多,所需的切換時間和心理成本會越大,還可能造成路段交叉口和層次切換處交通擁堵.因此,要選擇盡量多包含快速通道和交通干道等層次較高的路徑,且盡量減少在不同的層次交通線路上切換次數.

2.1.3 基本原理 假設對區域交通網絡中所有路段按照功能和技術等級分為不同層次h∈H,并對每個層次賦予一個度量lh∈(0,1)?R+用以指示其對出行者相對吸引強度,且滿足將稱為層次因子.層次因子相對于Logit模型中參數而言具有一個顯著優點,即它是不難從理論上計算確定的.路段的層次和其對應的層次因子滿足關系

令

從而

考慮到Dial算法的一個典型特征——帶參數指數函數所表示的路段似然,即在前向過程中,按照離出發點時間上升的順序從一個節點到另一個節點通過網絡,并給所有的路段分配一個權重,該權重為帶參數指數函數表示的路段似然.因此,結合第2.1.1和2.1.2的討論,?a=(i,j)∈A,按式(7)定義路段似然

式中：oi和oj為從起始點o到i和j的最小阻抗.根據式(7)定義的路段似然,路段所處層次越高,它的路段似然值越大,該路段在交通均衡分配過程中被選擇的概率越大.

2.2 改進Dial算法

步驟1 預處理 (1)?i∈A,計算從起始點o到i的最短路徑長度按式(7)計算“路段似然”值.

步驟2 向前計算路段權重.從起始點o開始,按oi的升序依次考慮每個節點i,即,對于節點i,按式(8)計算權重

式中：qoj為從起始點o到節點j∈V的交通量;若j不是某個OD對的終訖點,則取qoj=0;當O(j) =?時

2.3 證明改進的Dial算法為Logit加載

由于一條路徑被選中的概率與該路徑上所有路段的似然值成正比例關系,且選擇各個路段的決策是相互獨立的事件,因此,路徑被選中的概率與該路徑上所有路段的似然值之積成正比例關系,即

于是,由式(7)和式(10),得到

又由于

從而,依據式(5)以及式(12)可得

這就證明了上述改進Dial算法可為OD對間的所有有效路徑分配滿足Logit函數的流量.

3 算法分析

算例交通網絡取自Dial(1971),如圖1所示.網絡共9個節點,12條路段,路段的測定阻抗值標在相應路段旁.設節點1和9分別是惟一OD對的起始點和終訖點,OD交通量為qod=1 000單位.

圖1 實例網絡

假設圖1給出的道路網絡中路段(4,5)和(5,6)處于第一層次h1(較高層次),其他所有路段均為第二層次(較低層次),則相應的層次因子為.令h∈H.式中.鑒于wh與層次因子lh之間的簡單關系,下文中只出現wh.按照第2.2設計的改進Dial算法進行編程計算(取θ=1).

改進Dial算法的執行過程如下.

由路段分配流量及路段阻抗,得到整個交通網絡的總阻抗(記為T I)

TI是關于wh1和wh2的函數,記為T I(wh1,wh2),且其定義域為≤wh2≤1,wh1+wh2=1},則可繪制函數圖像如圖2所示.需要說明的是,圖2和圖3中用和w2代表和

根據Dial算法可知,TIDial=6 772.圖2中,空間曲面C1：T I=TI(wh1,wh2),平面和的交線在坐標面上的投影為直線L2：wh1+wh2=1(圖3)與的交點為(wh1＊, wh1＊)=(0.388 2,0.611 8),當時,所設計的改進Dial算法即可實現與Dial算法進行流量加載得到的總阻抗相等.對應的層次因子的值為若道路的層次性是用技術參數速度來衡量,則該計算結果對應于較高層次與較低層次路段的速度之比為1.576.而通常情況下,速度比約為1.67,不超過2,這意味著較高層次與較低層次路段的層次因子與或者wh1與wh2之間的差距還能加大,只要wh2不大于2/3,即可在圖3中點線段所示的區域調整.由圖2和圖3知,當(wh1,wh2)在Ω＊=∶{(wh1,wh2)|wh1＊＜wh2＜0.67,wh1+wh2=1}內取值時,交通系統總阻抗小于利用Dial算法配流得到的系統總阻抗,即

圖2 網絡總阻抗

圖3 網絡總阻抗降低的區域

對于實際的交通網絡,利用這里確定的能使網絡結構得以優化的wh,h∈H的取值范圍,進而確定層次因子的取值范圍,根據實際情況進行調整以給出一組層次因子的值,將調整值代回由改進Dial算法得到的路段流量表達式,便可確定各路段的流量,即得到交通網絡的優化結構.對于較大規模的交通網絡,由于通常只有幾個層次,因此,應用同樣的分析處理方法可以確定相對Dial算法更優的交通網絡結構.

4 結束語

本文利用交通網絡層次性改進Logit加載方法,以Dial算法為基礎從算法設計到實例計算給出了充分論證.與經典Dial算法相比,具有顯著的區別：(1)基于層次特征定義了層次因子,該層次因子具有可算可控性,并進一步設計了改進Dial算法;(2)改進的Dial算法能比Dial算法在合理范圍內通過調整層次因子來調節流量加載,從而有效地優化配置交通網絡資源,且使系統總阻抗小于Dial算法結果.

由于所設計的算法具有上述特點,因此,它相對于Dial算法而言,具有找到更優網絡結構的能力和靈活性.盡管實例網絡規模小,但所設計的改進Dial算法對大規模網絡同樣適用,且由于一般交通網絡最多幾個層次等級,所以實際計算復雜度仍然只取決于網絡本身的規模大小.故可以認為,交通網絡的層次性,是交通網絡結構優化設計的重要途徑,是提高交通系統效率的有效手段;本文研究結果對進一步探討可持續交通網絡設計和交通規劃理論具有基礎性意義.

[1]陳彥光,劉繼生.區域交通網絡分形的 DBM特征——交通網絡Laplacian分形性質的實證研究[J].地理科學,1999,19(2)：114-118.

[2]陳 濤,陳森發.城市道路交通系統耗散結構特性的研究[J].土木工程學報,2004,37(1),74-77.

[3] Angeloudis P,Fisk D.Large subway systems as complex networks[J].Physic A,2006,367：553-558.

[4]四兵鋒,趙小梅,孫壯志.城市混合交通網絡系統優化模型及其算法[J].中國公路學報,2008,21(1)：77-82.

[5]王媛媛,陸化普.基于可持續發展的土地利用與交通結構組合模型[J].清華大學學報：自然科學版, 2004(9)：1 240-1 243.

[6]趙 彤,高自友.交通離散網絡設計與土地使用問題的組合模型與求解算法[J].土木工程學報,2003, 36(7)：33-38.

[7]陸 建,胡 剛.常規公交線網布局層次規劃法及其應用[J].城市交通,2004,2(4)：34-37.

[8]肖 濱,范炳全,柯 欣.城市公交線網的分層規劃方法[J].城市交通,2005,3(3)：19-22.

[9]van Nes R,Bovy P.Multimodal traveling and its impact on urban transit network design[J].Journal of Advanced Transportation,2004,38(3),225-241.