交通網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化的改進(jìn)Dial算法＊

曾明華 李夏苗

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

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

1 符號系統(tǒng)

2 交通網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法

Logit加載是隨機(jī)交通分配的2種經(jīng)典分配技術(shù)之一.基于Logit加載的SUE交通分配模型雖有缺陷,卻十分簡潔、流行.本文基于層次性設(shè)計(jì)的改進(jìn)Dial算法仍然是一種Logit交通分配算法;更為重要的是,改進(jìn)Dial算法區(qū)別對待網(wǎng)絡(luò)中不同層次的路段,能得到比Dial算法性能更優(yōu)的交通網(wǎng)絡(luò)結(jié)構(gòu).

2.1 算法基礎(chǔ)及原理分析

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

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

但關(guān)于交通網(wǎng)絡(luò)分層規(guī)劃的實(shí)踐,基本上建立在經(jīng)驗(yàn)和感性認(rèn)識之上,缺乏一定的基礎(chǔ)理論支持.國內(nèi)外在交通網(wǎng)絡(luò)分層規(guī)劃的理論研究方面較為缺乏,大大滯后于規(guī)劃實(shí)踐.就我國而言,相對于大量的工程實(shí)踐也是遠(yuǎn)遠(yuǎn)不夠的[9].

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

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

令

從而

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

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

2.2 改進(jìn)Dial算法

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

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

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

2.3 證明改進(jìn)的Dial算法為Logit加載

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

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

又由于

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

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

3 算法分析

算例交通網(wǎng)絡(luò)取自Dial(1971),如圖1所示.網(wǎng)絡(luò)共9個節(jié)點(diǎn),12條路段,路段的測定阻抗值標(biāo)在相應(yīng)路段旁.設(shè)節(jié)點(diǎn)1和9分別是惟一OD對的起始點(diǎn)和終訖點(diǎn),OD交通量為qod=1 000單位.

圖1 實(shí)例網(wǎng)絡(luò)

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

改進(jìn)Dial算法的執(zhí)行過程如下.

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

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

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

圖2 網(wǎng)絡(luò)總阻抗

圖3 網(wǎng)絡(luò)總阻抗降低的區(qū)域

對于實(shí)際的交通網(wǎng)絡(luò),利用這里確定的能使網(wǎng)絡(luò)結(jié)構(gòu)得以優(yōu)化的wh,h∈H的取值范圍,進(jìn)而確定層次因子的取值范圍,根據(jù)實(shí)際情況進(jìn)行調(diào)整以給出一組層次因子的值,將調(diào)整值代回由改進(jìn)Dial算法得到的路段流量表達(dá)式,便可確定各路段的流量,即得到交通網(wǎng)絡(luò)的優(yōu)化結(jié)構(gòu).對于較大規(guī)模的交通網(wǎng)絡(luò),由于通常只有幾個層次,因此,應(yīng)用同樣的分析處理方法可以確定相對Dial算法更優(yōu)的交通網(wǎng)絡(luò)結(jié)構(gòu).

4 結(jié)束語

本文利用交通網(wǎng)絡(luò)層次性改進(jìn)Logit加載方法,以Dial算法為基礎(chǔ)從算法設(shè)計(jì)到實(shí)例計(jì)算給出了充分論證.與經(jīng)典Dial算法相比,具有顯著的區(qū)別：(1)基于層次特征定義了層次因子,該層次因子具有可算可控性,并進(jìn)一步設(shè)計(jì)了改進(jìn)Dial算法;(2)改進(jìn)的Dial算法能比Dial算法在合理范圍內(nèi)通過調(diào)整層次因子來調(diào)節(jié)流量加載,從而有效地優(yōu)化配置交通網(wǎng)絡(luò)資源,且使系統(tǒng)總阻抗小于Dial算法結(jié)果.

由于所設(shè)計(jì)的算法具有上述特點(diǎn),因此,它相對于Dial算法而言,具有找到更優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)的能力和靈活性.盡管實(shí)例網(wǎng)絡(luò)規(guī)模小,但所設(shè)計(jì)的改進(jìn)Dial算法對大規(guī)模網(wǎng)絡(luò)同樣適用,且由于一般交通網(wǎng)絡(luò)最多幾個層次等級,所以實(shí)際計(jì)算復(fù)雜度仍然只取決于網(wǎng)絡(luò)本身的規(guī)模大小.故可以認(rèn)為,交通網(wǎng)絡(luò)的層次性,是交通網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)的重要途徑,是提高交通系統(tǒng)效率的有效手段;本文研究結(jié)果對進(jìn)一步探討可持續(xù)交通網(wǎng)絡(luò)設(shè)計(jì)和交通規(guī)劃理論具有基礎(chǔ)性意義.

[1]陳彥光,劉繼生.區(qū)域交通網(wǎng)絡(luò)分形的 DBM特征——交通網(wǎng)絡(luò)Laplacian分形性質(zhì)的實(shí)證研究[J].地理科學(xué),1999,19(2)：114-118.

[2]陳 濤,陳森發(fā).城市道路交通系統(tǒng)耗散結(jié)構(gòu)特性的研究[J].土木工程學(xué)報,2004,37(1),74-77.

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

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

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

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

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

[8]肖 濱,范炳全,柯 欣.城市公交線網(wǎng)的分層規(guī)劃方法[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.