楊 泳,嚴(yán)余松,戶佐安,馬 毅

(西南交通大學(xué)交通運(yùn)輸與物流學(xué)院,成都610031)

Logit隨機(jī)網(wǎng)絡(luò)配流模型的改進(jìn)Dial算法

楊 泳,嚴(yán)余松*,戶佐安,馬 毅

(西南交通大學(xué)交通運(yùn)輸與物流學(xué)院,成都610031)

研究Logit隨機(jī)網(wǎng)絡(luò)配流模型及實(shí)現(xiàn)模型求解的Dial算法,針對原模型及算法的缺陷,通過引入路段長度相關(guān)的容錯(cuò)系數(shù)指標(biāo)重新定義有效路徑的判定條件,在此基礎(chǔ)上提出一種改進(jìn)的Dial算法,并應(yīng)用于Logit隨機(jī)網(wǎng)絡(luò)配流模型中.改進(jìn)算法在不降低原算法精度下不僅保留了原算法的無需路徑枚舉、計(jì)算效率高等優(yōu)越性,而且滿足實(shí)際出行者偏好在較短路段上“迂回”選擇潛在有效路段的特點(diǎn).最后通過一個(gè)路網(wǎng)實(shí)例對2種算法的配流結(jié)果進(jìn)行了對比.結(jié)果表明,改進(jìn)的算法避免了原算法缺陷導(dǎo)致的結(jié)果異常,配流效果更加符合實(shí)際,其計(jì)算效果明顯優(yōu)于原算法.

城市交通;配流;有效路段;Logit模型;Dial算法;交通網(wǎng)絡(luò);容錯(cuò)系數(shù)

1 引 言

給定交通需求與路網(wǎng)供給特征,求解網(wǎng)絡(luò)流量分布的交通問題被稱為配流問題.每個(gè)出行者總是力圖選擇起訖點(diǎn)之間阻抗最小的路徑,當(dāng)不存在出行者能單方面改變出行路徑從而降低阻抗時(shí),達(dá)到一種穩(wěn)定狀態(tài),被稱為用戶平衡狀態(tài)(UE)[1].在用戶平衡配流中,假定用戶知道每條可選路徑的準(zhǔn)確交通時(shí)間,而且能夠持續(xù)做出完全正確的路徑選擇決策.在此假設(shè)前提下,形成的交通流平衡狀態(tài)稱為確定性用戶平衡[2].然而該假設(shè)是不合理的,由于客觀信息的缺乏和主觀路徑的偏好,對于同一路徑,不同用戶估計(jì)的交通時(shí)間不同.將用戶對路段阻抗的理解值與實(shí)際值之間的差別視為隨機(jī)變量,出行者會(huì)選擇自己認(rèn)為阻抗最小的路徑而達(dá)到一種平衡狀態(tài),被稱為隨機(jī)用戶均衡狀態(tài),把這種條件下的流量分配也稱為隨機(jī)性配流[1,2].

在隨機(jī)性配流問題中,路徑集的選取相當(dāng)重要,因?yàn)槁窂郊亩x不同,選擇路徑的行為準(zhǔn)則和概率則不同,將直接影響配流的效果.Dial于1971年提出的STOCH算法[3]是求解非擁擠交通網(wǎng)絡(luò)隨機(jī)配流問題的經(jīng)典算法之一,該算法以路段為媒介,無需路徑列舉,配流結(jié)果滿足多項(xiàng)式Logit模式,適用于大規(guī)模交通網(wǎng)絡(luò),也稱Dial算法.該算法有識(shí)別有效路徑的初始化階段,許多明顯不被出行者考慮的路徑被隔離在有效路徑集之外,OD流量僅限在有效路徑集上進(jìn)行分配.但由于Dial算法對有效路徑集的選取過于嚴(yán)格,導(dǎo)致出現(xiàn)阻抗較低的路徑未被使用而阻抗較高的路徑反被使用的異常現(xiàn)象,配流結(jié)果明顯不滿足Wardrop第一與第二原則[1],從而限制了 Dial算法在實(shí)際中的應(yīng)用.

針對Dial算法實(shí)際應(yīng)用中存在的局限,各國研究者設(shè)計(jì)了一些改進(jìn)的模型和算法.Bell[4]、BAR-GERAH[5-7]提出了相關(guān)的Logit改進(jìn)模型及改進(jìn)Dial算法,通過網(wǎng)絡(luò)權(quán)重矩陣的求和序列及矩陣變換來計(jì)算Logit模型,但對于求解大規(guī)模交通網(wǎng)絡(luò)缺乏有效的算法;李景等[8,9]針對有效路段和有效路徑兩個(gè)概念對多路徑分配問題進(jìn)行了深入的研究及模型的改進(jìn);李志純等[10,11]分別從廣度優(yōu)先和深度優(yōu)先2個(gè)方向給出了求解網(wǎng)絡(luò)中2個(gè)節(jié)點(diǎn)間所有連通路徑的算法,這2種搜索方法的時(shí)間復(fù)雜度相同,只是對節(jié)點(diǎn)的訪問順序不同;李軍等[12]基于拓?fù)渑判虻乃枷胩岢鰧ふ衣窂降乃惴?但只有在網(wǎng)絡(luò)存在環(huán)路的情況下才可以排除不合理路段,這個(gè)假定條件對于實(shí)際的交通網(wǎng)絡(luò)而言并不合理.這些方法多基于圖論的有效路徑算法或連通路徑算法,在求解實(shí)際問題時(shí)存在一定的困難.

本文在研究隨機(jī)交通流分配中有效路徑選擇的基礎(chǔ)上,提出一種改進(jìn)Dial算法.在新算法中放寬對有效路徑的定義,選取有效路段時(shí)考慮該路段實(shí)際阻抗,避免原算法所產(chǎn)生的錯(cuò)誤的同時(shí),合理解釋實(shí)際交通過程中出行者的路徑選擇行為,使交通流分配結(jié)果更符合實(shí)際情況.

2 Logit模型及Dial算法

在隨機(jī)性配流問題中,定義起訖點(diǎn)r,s間各備選路徑具有令人滿意的程度為效用,出行者總是選擇主觀判斷效用最大的路徑,第k條路徑的效用值可表示為

式中 Uk為起迄點(diǎn)選擇路徑k的效用;crks為路徑k的實(shí)測阻抗;θ為將一個(gè)實(shí)測阻抗轉(zhuǎn)換成效用的正的轉(zhuǎn)換參數(shù);εrks表示路徑不能觀測到的因素構(gòu)成的隨機(jī)誤差項(xiàng).Logit模型就是建立在隨機(jī)誤差項(xiàng)相互獨(dú)立且服從Gumbel分布的基礎(chǔ)上[13],基于Logit模型的求解選擇路徑k的概率為

這樣通過各路段的選擇概率Prks,就可以得到各路徑上的流量

式中 qrs為r,s之間的交通需求量.當(dāng)含有n個(gè)節(jié)點(diǎn)完全圖中,任意兩個(gè)節(jié)點(diǎn)之間的路徑數(shù)為其中Pi=n!/i! .在實(shí)際交通網(wǎng)絡(luò)中,

n雖然節(jié)點(diǎn)的鄰接邊比較少,但要找出r,s間所有的路徑進(jìn)行計(jì)算也是不切實(shí)際的.

Dial算法定義OD對r,s之間的路徑上任意滿足下列條件的路段i,j為有效路徑

式中 r(·)為相應(yīng)節(jié)點(diǎn)到起點(diǎn)r最小路徑阻抗; s(·)為相應(yīng)節(jié)點(diǎn)到終點(diǎn)s的最小路徑阻抗.

Dial算法的具體執(zhí)行步驟如下[1].

步驟1 初始化.對路網(wǎng)中每一個(gè)節(jié)點(diǎn),采用最短路徑算法求解 r(i),s(i).最短路徑算法有Dijkstra算法、Floyd-Warshall算法和Moore-pape算法等,本文計(jì)算采用Floyd-Warshall算法.

步驟2 計(jì)算路段似然值.對每條路段i,j,計(jì)算各有效路段的似然值

式中 cij為路段i,j的實(shí)際阻抗值.

步驟3 向前計(jì)算路段權(quán)重.從起點(diǎn)r開始,按r(i)的上升順序依次考慮節(jié)點(diǎn),對于每個(gè)節(jié)點(diǎn),計(jì)算離開它的所有路段的權(quán)重值W值.W(i,j)的計(jì)算公式為

式中 Ii為終點(diǎn)為i的路段起點(diǎn)集合,當(dāng)達(dá)到終點(diǎn)s時(shí)終止計(jì)算.

步驟4 向后計(jì)算路段流量.從終點(diǎn)s開始,按s(j)的上升順序依次考慮節(jié)點(diǎn),對每個(gè)節(jié)點(diǎn),計(jì)算進(jìn)入它的所有路段的流量X,計(jì)算公式為

式中 qrs為OD對r,s之間的交通需求量;Oi為起點(diǎn)為i的路段終點(diǎn)集合,當(dāng)達(dá)到起點(diǎn)r時(shí)終止計(jì)算.

3 有效路段的重新定義

1971年Dial提出的算法能較好地實(shí)現(xiàn)Logit模型的求解過程,其出發(fā)點(diǎn)是通過判斷一條路徑是否為“有效路徑”來排除大量的“無效路徑”.由于Dial算法對有效路徑的定義過于嚴(yán)格,將導(dǎo)致分配結(jié)果中阻抗較低的路徑不被使用,而阻抗較高的路徑反被使用的現(xiàn)象.

如圖1的算例網(wǎng)絡(luò)中,共有9個(gè)節(jié)點(diǎn),13條路段,弧段上方或右側(cè)數(shù)字代表該路段的時(shí)間阻抗.起點(diǎn)1到訖點(diǎn)9的OD分布量q1,9=1 000個(gè)單位出行量,根據(jù)Logit模型及相應(yīng)的Dial算法對該道路網(wǎng)絡(luò)進(jìn)行流量分配,結(jié)果如圖2所示.

圖1 道路網(wǎng)絡(luò)圖Fig.1 Example for road network

圖2 Dial算法的配流結(jié)果Fig.2 Assignment result with Dial's algorithm

從配流結(jié)果圖2可以看出,路段7-8并沒有得到流量分配.表1列出Dial算法初始化后響應(yīng)節(jié)點(diǎn)到起點(diǎn)1的最小阻抗值,根據(jù)Dial算法對有效路段的定義,可以發(fā)現(xiàn)路段(7,8)并不屬于有效路段,所以1-4-7-8-9就被排除在配流的有效路徑之外.然而1-4-7-8-9的阻抗為8,而被認(rèn)為有效路徑的1-2-3-6-9阻抗也為8,顯然,這結(jié)果是不合理的.

表1 Dial算法的初始化Table 1 Initialization of Dial's algorithm

在實(shí)際的交通網(wǎng)絡(luò)中,出行者在進(jìn)行路徑選擇過程中,通常不會(huì)嚴(yán)格遵守Dial定義的“離起點(diǎn)越來越遠(yuǎn),離終點(diǎn)越來越近”有效路段條件,而在可預(yù)見范圍內(nèi)能容忍一定程度的偏差.這種偏差易引起出行者在選擇有效路段時(shí)與Dial嚴(yán)格定義的有效路段形成一定的誤差,實(shí)際上選擇一些在嚴(yán)格意義上的非有效路段而“迂回”前進(jìn),從而達(dá)到不斷靠近終點(diǎn)的出行目的.這些額外被考慮的“有效路段”,其費(fèi)用通?？梢灶A(yù)見且在出行者可承受范圍之內(nèi).受這一現(xiàn)象的啟發(fā),本文通過引進(jìn)基于路段量化指標(biāo)Δ(i,j)——容錯(cuò)系數(shù).對此,可重新定義有效路段為,如果OD對r,s之間路段i,j滿足下列條件,則該路段為有效路段

從式(8)可以看出,有效路段的判斷準(zhǔn)則根據(jù)出行者的實(shí)際出行行為進(jìn)行優(yōu)化,從而達(dá)到對有效路段進(jìn)行有效控制和擴(kuò)展的目的.在實(shí)際的路網(wǎng)中,按照這種方法確定有效路段集會(huì)隨出行者對路網(wǎng)的熟悉程度及風(fēng)險(xiǎn)偏好程度的變化而發(fā)生變化,因而引入容錯(cuò)系數(shù)上線來定量描述路網(wǎng)中出行者實(shí)際出行條件下對不滿足“離起點(diǎn)越來越遠(yuǎn),離終點(diǎn)越來越近”的量化容忍程度,且分別用定義出發(fā)點(diǎn)、終止點(diǎn)的容錯(cuò)系數(shù),兩者相互獨(dú)立.容錯(cuò)系數(shù)上限越高,說明出行者越偏好在路網(wǎng)中“迂回”選擇有效路段,而且對于相同容錯(cuò)系數(shù)上限而言,路段越長,出行者越容易考慮其相連通且路段長度較短的支路.在的情況下,式(4)和式(8)等價(jià),即原始有效路段判定條件是假定出行者完全掌握路網(wǎng)信息且不能容忍任何非有效路段介入的特殊情況.

在原始的Dial算法中,計(jì)算節(jié)點(diǎn)序列與有效路段的判定是密切相關(guān)的.根據(jù)有效路段的重新定義后,依然可以采用原始算法的執(zhí)行步驟,保留算法無需窮舉所有連通路徑的優(yōu)點(diǎn),因此改進(jìn)后的Dial算法在步驟2計(jì)算路段似然值時(shí)更新如下

步驟2(更新) 計(jì)算路段似然值.對每條路段i,j,計(jì)算各有效路段的似然值

4 算例分析

以圖1算例網(wǎng)絡(luò)為例進(jìn)一步說明改進(jìn)后的模型流量分配結(jié)果,取詳細(xì)計(jì)算結(jié)果如表2所示.

表2 算法改進(jìn)前后配流結(jié)果對比Table 2 The assignment result comparison between before improvement and after improvement

圖3為網(wǎng)絡(luò)中基于改進(jìn)的有效路段判定條件下的配流結(jié)果,對比圖2可以明顯看出,路徑4-7-8從零流量的不合理情況得到一定的流量分配,解決了一些本應(yīng)被選擇的有效路徑?jīng)]有分配到交通量的不合理配流現(xiàn)象.

圖4顯示算法改進(jìn)前后流出節(jié)點(diǎn)流量的結(jié)果對比,橫坐標(biāo)表示道路網(wǎng)絡(luò)圖1中對應(yīng)的節(jié)點(diǎn)序號(hào),縱坐標(biāo)表示節(jié)點(diǎn)流出的流量,可以明顯看出,隨著新的有效節(jié)點(diǎn)7的流量分流,網(wǎng)絡(luò)中大部分節(jié)點(diǎn)的流量保持不變或者有所降低,整個(gè)網(wǎng)絡(luò)流量分配趨于均勻合理化,而在流量減少的節(jié)點(diǎn)中,以交通最為擁擠的中心節(jié)點(diǎn)5下降最為明顯,降幅高達(dá)18.3%,說明正確的交通流分配模型及算法對于合理分配路網(wǎng)流量特別是交通量非常高的中心路段的分流作用是非常明顯的.而對于節(jié)點(diǎn)4,流出流量有一定程度的上升,原因是節(jié)點(diǎn)4連通中心節(jié)點(diǎn)5及新的有效節(jié)點(diǎn)7,但其流量總量(417.3)相比于中心節(jié)點(diǎn)5不大,有利于提升節(jié)點(diǎn)4的路網(wǎng)使用效率.根據(jù)改進(jìn)Dial算法,可以確保一部分非嚴(yán)格意義上的有效路段也得到一定的流量分配,得到比原始Dial算法更符合世紀(jì)的配流結(jié)果.

圖3 改進(jìn)Dial算法的配流結(jié)果Fig.3 Assignment result with improved Dial's algorithm

圖4 算法改進(jìn)前后節(jié)點(diǎn)流量對比Fig.4 The node flow assignment comparison between before improvement and after improvement

5 研究結(jié)論

本文針對Logit模型的Dial算法固有缺陷,提出一種基于路段阻抗的容錯(cuò)系數(shù)對有效路段重新定義,并在路網(wǎng)中驗(yàn)證改進(jìn)模型和算法.研究結(jié)果表明:

(1)改進(jìn)Dial算法保留了原Dial算法的優(yōu)點(diǎn),即在配流過程中,不需要列舉所有連通路徑,而是通過路段信息進(jìn)行有效路段的篩選;

(2)對有效路段進(jìn)行了重新定義,與原Dial算法相比,改進(jìn)Dial算法可得出更加合理的有效路段集合,從而避免了原Dial算法遺漏有效路段的內(nèi)在缺陷,使配流結(jié)果更加合理;

(3)在改進(jìn)Dial算法中,影響有效路徑集合的因素主要是出行者在路段預(yù)見范圍內(nèi)對偏差容忍程度,即路段容錯(cuò)系數(shù)Δ(i,j),系數(shù)越大,說明出行者越偏好在路網(wǎng)中“迂回”選擇有效路段,在零容錯(cuò)條件下模型與原模型等價(jià);

(4)改進(jìn)的Dial算法在考慮路段的容錯(cuò)能力時(shí),僅考慮了本路段的阻抗,并沒有考慮其相鄰路段的阻抗;然而,在出行者實(shí)際交通選擇過程中,不僅僅考慮本路段的狀況,還將考慮相鄰路段的情況,因此如何在“有限”范圍內(nèi)考慮相鄰路段的實(shí)際情況來進(jìn)一步研究有效路段的選擇,有待做進(jìn)一步的研究.

[1]Sheffiy.Urban transportation networks equilibrium analysis with mathematicalprogramming methods [M]. Englewood Cliffs New Jersey:Prentice Hall,1985.

[2]Sheffiy.城市交通網(wǎng)絡(luò)[M].云輝,戴香菊,譯.成都:西南交通大學(xué)出版社,1992.[Sheffiy.Urban transportation networks[M].YUN H,DAI X J, Translate.Chengdu:Southwest Jiao Tong University Press,1992.

[3]Dial R B,A probabilistic multipath traffic assignment model which obviates path enumeration[J]. Transportation Research,1971,5(2):83-111.

[4]Bell M G H.Alternatives to Dial's Logit assignment algorithm[J].Transportation Research Part B,1995, 29(4):287-295.

[5]Bar-Gera H.Primal method for determining the most likely route flowsin large road networks[J]. Transportation Science,2006,40(3):269-286.

[6]Larsson T,Lundgren J T,Patriksson M,et al.Most likely traffic equilibrium route flows:analysis and computation[M].Netherlands:Kluwer Academic Publishers,2001:129-159.

[7]Bar-Gerah Luzonal.Differences among route flow solutions for the user equilibrium origin-based algorithm for the traffic assignment problem[J]. Journal of Transportation Engineering,2007,133(4): 232-239.

[8]李景,彭國雄,臧亦文.改進(jìn)型多路徑分配模型及算法設(shè)計(jì)[J].系統(tǒng)工程理論與實(shí)踐,2001(9): 130-134.[LI J,PENG G X,ZANG Y W.An improved multi-path assignment model and algorithms design[J].Systems Engineering-Theory&Practice, 2001(9):130-134.]

[9]郭仁擁,黃海軍.考慮OD需求變異的網(wǎng)絡(luò)交通流演化模型[J].系統(tǒng)工程理論與實(shí)踐,2009(1): 118-123.[GUO R Y,HUANG H J.Network traffic flow evolution model considering OD demand mutation [J].Systems Engineering-Theory&Practice,2009 (1):118-123.]

[10]李志純,黃海軍.隨機(jī)交通分配中有效路徑的確定方法[J].交通運(yùn)輸系統(tǒng)工程與信息,2003,3(1): 28-32.[LI Z C,HUANG H J.Determining the efficient paths in stochastic traffic assignment[J]. Journal of Transportation Systems Engineering and Information Technology,2003,3(1):28-32.]

[11]朱順應(yīng),王煒,鄧衛(wèi).交通網(wǎng)絡(luò)可靠度及其通路算法研究[J].中國公路學(xué)報(bào),2000,13(1):91-94. [ZHU S Y,WANG W,DENG W.Research on traffic network reliability and access road algorithm[J]. China Journal of Highway and Transport,2000,13 (1):91-94.]

[12]李軍,辛松歆,蔡銘.基于拓?fù)涮幚淼腖ogit型網(wǎng)絡(luò)加載算法[J].中國公路學(xué)報(bào),2005,18(4):87-90.[LI J,XIN S X,CAI M.Algorithm for Logit network loading problem based on topological sorting [J].China Journal of Highway and Transport,2005, 18(4):87-90.]

[13]黃海軍.城市交通網(wǎng)絡(luò)平衡分析-理論與實(shí)踐[M].北京:人民交通出版社,1994.[HUANG H J. Urban transportation network equilibrium analysis: theory and practice [M]. Beijing: China Communications Press,1994.]

Improved Dial's Algorithm for Logit-Based Stochastic Traffic Assignment Model

YANG Yong,YAN Yu-song,HU Zuo-an,MA Yi
(School of Transportation and Logistics,Southwest Jiaotong University,Chengdu 610031,China)

This paper analyzes the multi-path Logit assignment model and the classical Dial's algorithm. To overcome the drawback in existing model and algorithm,an improved algorithm is presented.The efficient path condition is modified based on a quantitative correction coefficient on individual path.The improved algorithm retains the main advantages of original algorithm,in which the path enumeration is not required and a similar computing efficiency with the original algorithm is guaranteed.Meanwhile,the preference to potential valid road links with short distance among urban traffic travellers is satisfied.A numerical example based on a traffic road network is used to illustrate the application of proposed algorithm and two algorithms are then compared.Results show that the improved algorithm is able to eliminate the abnormal behavior of the original algorithm with more feasible and reasonable traffic flow assignment results.It is evident that the proposed algorithm is more effective than the original one.

urban traffic;traffic flow assignment;effective path;Logit model;Dial's algorithm;traffic network;correction coefficient

TP18,U491

A

TP18,U491

A

1009-6744(2013)02-0158-06

2012-10-30

2013-01-25錄用日期:2013-02-05

國家自然科學(xué)基金(61104175).

楊泳(1982-),男,湖北大治人,博士生.

*通訊作者:yanyusong@263.net