基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡模型

李雪飛，郎茂祥

（北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京100044）

基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡模型

李雪飛，郎茂祥＊

（北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京100044）

介紹了廣義巢式Logit的基本理論，在此基礎(chǔ)上，考慮具有不同時(shí)間價(jià)值的多種用戶類別出行者，構(gòu)造了基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡的等價(jià)數(shù)學(xué)規(guī)劃模型，并對(duì)該模型的等價(jià)性和唯一性進(jìn)行了證明.設(shè)計(jì)了求解所提出的隨機(jī)用戶平衡模型的基于路徑的相繼平均法，通過(guò)一個(gè)算例驗(yàn)證了所設(shè)計(jì)算法的有效性.分析了分散系數(shù)變化對(duì)交通分配結(jié)果的影響，最后與多項(xiàng)式Logit的分配結(jié)果進(jìn)行對(duì)比.算例結(jié)果表明，本文所提出的模型能夠克服多項(xiàng)式Logit模型的IIA特性，設(shè)計(jì)的算法具有較高的求解效率.

城市交通；隨機(jī)用戶平衡；相繼平均法；廣義巢式Logit；多用戶；多準(zhǔn)則

1 引言

交通分配模型研究是交通規(guī)劃領(lǐng)域研究的熱點(diǎn)問(wèn)題.自從Daganzo和Sheffi[1]在1977年提出隨機(jī)用戶平衡（Stochastic User Equilibrium,SUE）配流原則以來(lái)，眾多學(xué)者構(gòu)建和發(fā)展了多種隨機(jī)用戶平衡模型.Fisk[2]構(gòu)建了隨機(jī)用戶平衡的數(shù)學(xué)規(guī)劃模型，該模型的解對(duì)應(yīng)于Logit路徑選擇公式. Sheffi和Powell[3]構(gòu)建了隨機(jī)用戶平衡的無(wú)約束數(shù)學(xué)規(guī)劃模型.周晶和徐晏[4]考慮出行需求隨節(jié)點(diǎn)間擁擠程度的變化，構(gòu)建了基于彈性需求的隨機(jī)用戶平衡分配模型.劉海旭和蒲云[5]定義了行程質(zhì)量的概念，構(gòu)建了基于行程質(zhì)量的隨機(jī)用戶平衡分配模型.張波等[6]給出了交通流連續(xù)分布下路徑前景的連續(xù)函數(shù)表達(dá)式，構(gòu)建了基于累積前景理論的隨機(jī)用戶平衡分配模型.余孝軍等[7]構(gòu)建了基于Logit模型的、具有固定需求的多用戶類隨機(jī)均衡的變分不等式模型，并研究了在時(shí)間和費(fèi)用度量?jī)煞N出行準(zhǔn)則下的效率損失上界.徐兵和朱道立[8]研究了非對(duì)稱費(fèi)用函數(shù)、多用戶類、多準(zhǔn)則、固定需求下的隨機(jī)用戶平衡模型和算法.

路徑選擇模型是隨機(jī)用戶平衡分配模型的核心.通過(guò)總結(jié)可以發(fā)現(xiàn)，目前大部分研究中所采用的路徑選擇模型是多項(xiàng)式Logit（MNL）模型.然而，由于多項(xiàng)式Logit模型具有不相關(guān)備選方案的獨(dú)立性（IIA）[9]等不良特性，無(wú)法反映路徑重疊對(duì)用戶路徑選擇行為的影響.同時(shí)，以往很多研究中假定路網(wǎng)中所有的使用者性質(zhì)相同，然而當(dāng)使用者面臨出行時(shí)間和貨幣成本等多個(gè)準(zhǔn)則時(shí)，由于收入水平和個(gè)人偏好等因素的影響，會(huì)造成用戶的路徑選擇不同.因而有必要根據(jù)用戶的性質(zhì)進(jìn)行分類，建立具有多用戶多準(zhǔn)則的隨機(jī)用戶平衡分配模型，使交通分配結(jié)果與實(shí)際情況更加接近.

基于以上分析，本文采用Chieh-Hua Wen和Frank S Koppelman[10]所提出的可以克服MNL模型IIA特性的廣義巢式Logit模型，并對(duì)路網(wǎng)使用者進(jìn)行分類，建立基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡模型（MMSUE-GNL）.對(duì)所構(gòu)建模型的等價(jià)性和唯一性進(jìn)行證明，并設(shè)計(jì)求解該模型的基于路徑的相繼平均法（MSA）.最后通過(guò)一個(gè)算例驗(yàn)證了所提出算法的有效性，分析參數(shù)變化對(duì)交通分配結(jié)果的影響，并與多項(xiàng)式Logit模型的分配結(jié)果進(jìn)行對(duì)比分析.

2 基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡模型構(gòu)建

2.1 廣義巢式Logit模型的基本理論

McFadden[11]提出了廣義極值（Generalized Extreme Value,GEV）理論，該理論為路徑選擇模型的發(fā)展提供了更加廣闊的空間，先后有多種新的路徑選擇模型被提出和應(yīng)用.廣義巢式Logit[10]（Generalized Nested Logit，GNL）模型作為GEV模型的一種，具有捕獲方案之間相似性的特點(diǎn)，能夠克服MNL模型的IIA特性.

本文采用一個(gè)雙層巢式結(jié)構(gòu)來(lái)進(jìn)行研究，上層為交通網(wǎng)絡(luò)中的所有路段（巢），下層為OD間所有有效路徑.每一條路徑可以屬于不同的巢，并以分配系數(shù)表示一條路徑屬于某一個(gè)巢的比率.廣義巢式Logit模型中OD對(duì)rs間第i類用戶選擇路徑k的概率為[10]

廣義巢式Logit模型的概率表達(dá)式可以分解為包含邊際概率和條件概率的公式：

上式中，OD對(duì)rs間第i類用戶選擇巢m的邊際概率為

在選擇巢m的條件下選擇第k條路徑的條件概率為

2.2 模型的構(gòu)建

考慮用一個(gè)賦權(quán)有向圖G(N,A)來(lái)表示交通網(wǎng)絡(luò)，其中N為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，A為所有邊（路段）的集合.R為所有OD對(duì)的集合，rs表示以r為起點(diǎn)，s為終點(diǎn)的一個(gè)OD對(duì)，rs∈R.K為所有OD對(duì)間路徑的集合，Krs為OD對(duì)rs之間的有效路徑集合，Krs∈K，k為OD對(duì)rs之間的第k條路徑，k∈Krs.M為巢的集合，m∈M.xia表示路段a的第i類用戶的流量，xa表示路段a的總流量.qirs為OD對(duì)rs間第i類用戶的出行需求量，本文設(shè)定為固定值.fmi,krs為OD對(duì)rs間第i類用戶屬于第m個(gè)巢的路徑k的流量.

本文根據(jù)用戶所具有時(shí)間價(jià)值的不同將用戶分為I類，i為第i類用戶，i∈I.本文中廣義成本是以時(shí)間度量的，第i類用戶的廣義路段出行時(shí)間為

因而rs間第i類用戶的廣義路徑出行時(shí)間為

式中ta(xa)表示路段a的出行時(shí)間函數(shù)；pa為路段a的出行貨幣費(fèi)用；Viot為第i類用戶的出行時(shí)間價(jià)值表示OD對(duì)rs間若路段a在路徑k上，則，否則

本文構(gòu)建基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡的數(shù)學(xué)規(guī)劃模型如下：

式（7）為最小化目標(biāo)函數(shù)，該式無(wú)任何直觀的經(jīng)濟(jì)意義；式（8）為路徑流量與OD量之間的關(guān)系；式（9）為分用戶類路段流量與路徑流量之間的關(guān)系；式（10）為路段總流量與分用戶類路段流量之間的關(guān)系；式（11）是路徑流量的非負(fù)約束.

定理1本文提出的數(shù)學(xué)規(guī)劃模型與基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡配流等價(jià).

證明：

首先，構(gòu)造式（7）的拉格朗日函數(shù)：

式中λirs為拉格朗日乘子.

對(duì)式（12）求導(dǎo)，得到其相應(yīng)的Kuhn-Tucker條件如下：

將式（18）對(duì)路徑k求和，可以得到

對(duì)式（19）取μrsm次方可得

將式（20）對(duì)巢m求和可得

（21）

將式（20）除以式（21），我們可以得到OD對(duì)rs間第i類用戶選擇巢m的邊際概率為

將式（18）除以式（19）可以得到OD對(duì)rs間第i類用戶選擇巢m的條件下，選擇路徑k的條件概率為

上述式（22）對(duì)應(yīng)于廣義巢式Logit的邊際概率式（3），式（23）對(duì)應(yīng)于廣義巢式Logit的條件概率式（4）.

通過(guò)以上證明，可以說(shuō)明本文所提出的數(shù)學(xué)規(guī)劃模型與基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡配流等價(jià).

定理2本文提出的數(shù)學(xué)規(guī)劃模型的解是唯一的.

證明：

目標(biāo)函數(shù)式（7）的前兩項(xiàng)與Yang H和Huang H J[13]所提出的數(shù)學(xué)規(guī)劃模型一樣，對(duì)于路徑流量為凸函數(shù)，但不是嚴(yán)格凸函數(shù).只需要證明目標(biāo)函數(shù)式（7）的后兩項(xiàng)為嚴(yán)格凸的，則可以證明本文所提出的數(shù)學(xué)規(guī)劃模型解的唯一性.令目標(biāo)函數(shù)式（7）的第三項(xiàng)和第四項(xiàng)分別為

Z1和Z2對(duì)OD對(duì)rs間第i類用戶屬于巢m的第k條路徑流量fi.rsmk的一階導(dǎo)數(shù)分別為

從而Z1和Z2對(duì)OD對(duì)rs間第i類用戶屬于巢m的第l條路徑流量fi.rsml的二階導(dǎo)數(shù)分別為

可以看出Z1的二階導(dǎo)數(shù)所對(duì)應(yīng)的Hessian矩陣正定，因而Z1為嚴(yán)格凸函數(shù).

可以看出Z2的二階導(dǎo)數(shù)所對(duì)應(yīng)的Hessian矩陣的每一個(gè)元素都相等，因而該Hessian矩陣半正定，因此Z2為凸函數(shù)，但不是嚴(yán)格凸函數(shù).

綜上所述，目標(biāo)函數(shù)Z是兩個(gè)凸函數(shù)和一個(gè)嚴(yán)格凸函數(shù)之和，因而Z對(duì)于分用戶類路徑流量為嚴(yán)格凸的.同時(shí)，約束條件式（8）-式（11）為非負(fù)的線性約束.因此本文所構(gòu)建的基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡數(shù)學(xué)規(guī)劃模型的解是唯一的.

2.3 求解算法設(shè)計(jì)

本文采用基于路徑的相繼平均法（Method of Successive Average，MSA）[14]來(lái)求解基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡模型.該算法的主要步驟如下：

第1步確定有效路徑集合Krs，?rs∈R.

第2步初始化.根據(jù)各路段初始流量為0，各路段的出行貨幣費(fèi)用pa及第i類用戶的出行時(shí)間價(jià)值Voit，計(jì)算分用戶類各路段廣義自由出行時(shí)間從而計(jì)算有效路徑的分用戶類廣義出行時(shí)間(?k∈Krs,i∈I,rs∈R).根據(jù)式（1）和計(jì)算初始路徑流量fki,rs(n)，從而獲得初始路段流令迭代次數(shù)n=1.

第3步更新令tia(n)=ta(x(an))+pa/Voit(?a∈A,i∈I).

第4步確定下降方向.在當(dāng)前分用戶類路段出行時(shí)間tia(n)的基礎(chǔ)上，計(jì)算新的有效路徑的分用戶類廣義出行時(shí)間根據(jù)式（1）和可以得到分用戶類附加路徑流量

第6步收斂性檢驗(yàn).本文采用均方根誤差（Root Mean Squared Error，RMSE）來(lái)進(jìn)行收斂判斷：

式中K為所有OD對(duì)間路徑的集合；I為用戶類別數(shù)；本文取RMSE(n)≤0.0001.當(dāng)滿足精度條件時(shí)，算法停止；否則，令n=n+1，返回到第3步繼續(xù)計(jì)算.

圖1 算例網(wǎng)絡(luò)Fig.1 Example traffic network

3 算例分析

本算例采用如圖1所示的交通網(wǎng)絡(luò).該交通網(wǎng)絡(luò)包括3條可選路徑，路徑1包含路段1和路段4，路徑2包含路段1、路段3和路段5，路徑3包含路段2和路段5.假設(shè)圖中的各條路段長(zhǎng)度都相等，均為l.算例在具有1.66GHz的Intel T2300處理器的筆記本電腦運(yùn)行.

假設(shè)只有1個(gè)OD對(duì)ad，總需求量為1000 veh/h.假設(shè)路網(wǎng)中有2類用戶，即I=2，其中第一類用戶的需求為300 veh/h，第二類用戶的需求為700 veh/h.路段a的出行時(shí)間函數(shù)ta(xa)采用廣泛使用的BPR函數(shù)，即

式中t0a為路段a的自由出行時(shí)間；xa為路段a的流量；ca為路段a的最大通行能力.

因此，第i類用戶的廣義路段出行時(shí)間為

表1 路段自由出行時(shí)間及最大通行能力Table 1 The freedom travel time and maximum capacities of different links

算例網(wǎng)絡(luò)的雙層巢式結(jié)構(gòu)、分配系數(shù)，以及嵌套系數(shù)如圖2所示.由圖2可知，巢數(shù)m=5，路徑數(shù)k=3.根據(jù)式可以得到分配系數(shù)根據(jù)式可以得到嵌套系數(shù)表2給出了當(dāng)分散系數(shù)θ取不同的值時(shí)，各路段的平衡流量.

圖2 算例網(wǎng)絡(luò)的雙層巢式結(jié)構(gòu)Fig.2 The two-level nesting structure of example traffic network

表2 當(dāng)θ取不同值時(shí)，各路段的平衡流量Table 2 Whenθtakes different values,the equilibrium flow on each link

由表2可以看出，隨著θ取不同的值，各路段流量發(fā)生了顯著的變化.隨著θ值的增大，路段1、3和4的流量不斷減少，而路段2和5的流量不斷增加.當(dāng)分散系數(shù)θ較小時(shí)，各條路段都有一定的流量，而當(dāng)θ增大時(shí)，大部分用戶選擇了路徑3.這是由于分散系數(shù)θ反映了用戶對(duì)路況的熟悉程度，θ越大表明用戶掌握更多的路網(wǎng)信息，對(duì)路況的理解誤差較小，因而用戶對(duì)路徑的選擇更接近于確定性選擇.

圖3 當(dāng)θ取不同值時(shí)，算法收斂所需迭代次數(shù)Fig.3 Whenθtakes different values,the convergence number of iterations

圖3反映了隨著θ取不同的值，本文所設(shè)計(jì)的算法收斂所需要的迭代次數(shù)變化情況.

由圖3可以看出，本文所設(shè)計(jì)算法收斂所需要的迭代次數(shù)隨分散系數(shù)θ的增大呈現(xiàn)先增加后減少的趨勢(shì).通過(guò)求解結(jié)果還可以發(fā)現(xiàn)，在不同分散系數(shù)θ取值下，基于路徑的相繼平均法能夠在7.0秒內(nèi)達(dá)到精度RMSE(n)≤0.0001的要求，具有較高的求解效率.

圖4 當(dāng)θ=0.1時(shí)，廣義巢式Logit和MNL模型分配的路段流量Fig.4 Whenθ=0.1,the link flows assigned by GNL and MNL models

圖4對(duì)比分析了當(dāng)分散系數(shù)θ=0.1時(shí)，分別采用GNL和MNL模型時(shí)的路段流量分配結(jié)果.可以看出，GNL模型在路段1、3、5分配的流量比MNL模型小，而在路段2和4分配的流量比MNL模型大.MNL模型的IIA特性是由于不考慮路徑之間的相關(guān)關(guān)系而帶來(lái)的，因而會(huì)高估重疊路段的流量，而GNL模型考慮了路徑之間的重疊關(guān)系，多條路徑重合的路段分配的流量要比MNL模型小，能夠在一定程度上克服MNL模型的IIA特性，本文的路段分配結(jié)果正體現(xiàn)了這一點(diǎn).

4 研究結(jié)論

本文提出了應(yīng)用廣義巢式Logit模型，以及對(duì)路網(wǎng)中的用戶按照時(shí)間價(jià)值不同進(jìn)行分類而構(gòu)建模型的研究思路.介紹了廣義巢式Logit模型的基本理論.構(gòu)建了基于廣義巢式Logit的多用戶多準(zhǔn)則隨機(jī)用戶平衡數(shù)學(xué)規(guī)劃模型，證明了該模型的等價(jià)性與唯一性.該模型能夠解決路徑重疊問(wèn)題、反映出用戶的多類別特點(diǎn)，能夠更客觀反映實(shí)際情況.設(shè)計(jì)了所構(gòu)建模型的基于路徑的相繼平均算法，通過(guò)一個(gè)算例驗(yàn)證了算法的有效性.分析了參數(shù)變化對(duì)交通分配結(jié)果的影響，并與多項(xiàng)式Logit模型的交通分配結(jié)果進(jìn)行對(duì)比.通過(guò)算例結(jié)果可以看出：分散系數(shù)θ對(duì)交通分配結(jié)果有重要影響，隨著θ的增大，交通分配結(jié)果不斷接近確定性分配；在不同分散系數(shù)取值下，本文所提出的算法都能夠在較短時(shí)間內(nèi)達(dá)到精度的要求；廣義巢式Logit模型能夠克服多項(xiàng)式Logit的IIA特性，使流量分配結(jié)果接近實(shí)際.進(jìn)一步的研究可以考慮將本文提出的模型應(yīng)用于大型交通網(wǎng)絡(luò)進(jìn)行測(cè)試，并通過(guò)實(shí)際數(shù)據(jù)對(duì)模型參數(shù)進(jìn)行標(biāo)定，研究更加有效的求解算法.

[1]Daganzo C F,Sheffi Y.On stochastic models of traffic as?signment[J].Transportation Science,1977,11(3):253-274.

[2]Fisk C.Some developments in equilibrium traffic assign?ment[J].Transportation Research Part B,1980,14(3): 243-255.

[3]Sheffi Y,Powell W B.An algorithm for the equilibrium assignment problem with random link times[J].Net?works,1982,12(2):191-207.

[4]周晶,徐晏.彈性需求隨機(jī)用戶平衡分配模型及其應(yīng)用[J].系統(tǒng)工程學(xué)報(bào),2001,16(2):88-94.[ZHOU J,XU Y.Stochastic user equilibrium assignment with elastic demand and its application[J].Journal of Systems Engi?neering,2001,16(2):88-94.]

[5]劉海旭，蒲云.基于行程質(zhì)量的隨機(jī)用戶平衡分配模型[J].中國(guó)公路學(xué)報(bào),2004,17(4):93-95,118.[LIU H X,PU Y.Stochastic user equilibrium assignment model based on travel trait[J].China Journal of Highway and Transport,2004,17(4):93-95,118.]

[6]張波,雋志才,林徐勛.基于累積前景理論的隨機(jī)用戶均衡交通分配模型[J].西南交通大學(xué)學(xué)報(bào),2011,46 (5):868-874.[ZHANG B,JUAN Z C,LIN X X.Stochas?tic user equilibrium model based on cumulative pros?pect theory[J].Journal of Southwest Jiaotong University, 2011,46(5):868-874.]

[7]余孝軍,黃海軍,劉天亮.固定需求網(wǎng)絡(luò)中多用戶類隨機(jī)均衡的效率損失[J].交通運(yùn)輸系統(tǒng)工程與信息, 2009,9(4):83-89.[YU X J,HUANG H J,LIU T L.Effi?ciency loss of the multi-class stochastic traffic equilibri?um assignment with fixed demand[J].Journal of Trans?portation Systems Engineering and Information Technol?ogy,2009,9(4):83-89.]

[8]徐兵,朱道立.多用戶多準(zhǔn)則固定需求隨機(jī)交通均衡變分模型[J].公路交通科技,2007,24(4):129-133. [XU B,ZHU D L.A multiclass and multicriteria stochas?tic traffic network equilibrium variational inequality model with fixed demand[J].Journal of Highway and Transportation Research and Development,2007,24(4): 129-133.]

[9]Kenneth E Train.Discrete choice methods with simula?tion(the Second Edition)[M].United States of America: Cambridge University Press,2003.

[10]Chieh-Hua Wen,Frank S Koppelman.The generalized Nested logit model[J].Transportation Research Part B, 2001,35(7):627-641.

[11]McFadden D.Modelling the choice of residential location [M].Institute of Transportation Studies,University of California,1978.

[12]Bekhor S,J N Prashker.Stochastic user equilibrium for?mulation for generalized Nested logit model[J].Transpor?tation Research Record:Journal of the Transportation Research Board,2001,1752:84-90.

[13]Yang H,Huang H J.The Multi-Class,Multi-criteria traffic network equilibrium and systems optimum prob?lem[J].Transportation Research Part B,2004,38(1):1-15.

[14]Bekhor S,Reznikova L,Toledo T.Application of crossnested logit route choice model in stochastic user equi?librium traffic assignment[J].Transportation Research Record:Journal of the Transportation Research Board, 2007,2003(1):41-49.

Multi-Class and Multi-Criteria Stochastic User Equilibrium Model Based on Generalized Nested Logit Model

LI Xue-fei,LANG Mao-xiang
（MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University,Beijing 100044,China）

ract:This paper focuses on the multi-class,multi-criteria stochastic user equilibrium model based on the generalized nested logit model.The basic theory of generalized nested Logit model is introduced and the multi-class users with different value of times are considered.Then the equivalent mathematical programming model for the multi-class,multi-criteria stochastic user equilibrium model based on the generalized nested Logit model is set up and the equivalence and uniqueness conditions are proved.The path-based method of successive averages(MSA)algorithm is designed to solve the proposed mathematical programming model and the effectiveness of the proposed algorithm is verified in a numerical example.The influences of dispersion parameter with different values on the traffic assignment results are analyzed and the assignment result is compared with that of MNL model.The results of the numerical example show that the proposed model can overcome the IIAproperty of the MNL model and the proposed algorithm has high efficiency.

rds:urban traffic;SUE;MSA;generalized nested Logit;multi-class;multi-criteria

1009-6744（2014）04-0139-07

U491.1

A

2013-11-12

2014-02-18錄用日期：2014-03-10

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助（2012YJS054）.

李雪飛（1986-），男，內(nèi)蒙古呼和浩特市人，博士生. *

mxlang@bjtu.edu.cn