一個基于無約束優(yōu)化方法的交通組合模型

胡文君，周溪召

(1.上海中僑職業(yè)技術(shù)學(xué)院 經(jīng)濟(jì)與管理學(xué)院，上海 201309； 2. 上海理工大學(xué) 管理學(xué)院，上海 200093)

0 引 言

由交通生成、交通分布、模式劃分和交通分配4個階段構(gòu)成的“四階段預(yù)測”模型是交通規(guī)劃和預(yù)測中常用的模型方法，但這種方法割裂了各階段之間的相互聯(lián)系。為克服這一不足，許多研究人員將4個階段中的兩個或多個階段結(jié)合，建立一個組合模型，如交通生成與分布組合模型[1]、交通分布與交通分配組合模型[2-3]、方式劃分與分配組合模型[4]或交通生成、分布、方式劃分、分配組合模型[5-6]。

在由兩個或更多階段構(gòu)成的組合模型中，數(shù)學(xué)規(guī)劃法[7-8]、非線性互補(bǔ)[9]、變分不等式[10]、基于出行鏈的方法[11]及構(gòu)建超級網(wǎng)絡(luò)方法[12]是學(xué)界中常用的方法，很少有研究者采用無約束優(yōu)化方法。

無約束優(yōu)化方法在通訊、計算機(jī)、控制、工程和管理等領(lǐng)域有著廣泛應(yīng)用[13-14]，它是非線性規(guī)劃中的一種，是許多帶約束優(yōu)化問題研究的基礎(chǔ)。該方法沒有等式或不等式約束，其思想是尋求多元函數(shù)y=f(x1,x2,Λ,xn)在整個實n維空間Rn中的局部最小值。在實際應(yīng)用中，許多情景被抽象為函數(shù)形式后均為凸函數(shù)。對于凸函數(shù)，局部最小值點(diǎn)即為全局最小值點(diǎn)，因此只要能求得這類函數(shù)的一個局部最小值點(diǎn)，該點(diǎn)一定為全局最小值點(diǎn)。

采用無約束優(yōu)化方法，筆者建立了一個組合出行-終點(diǎn)-模式-路徑選擇模型，提出了組合模型的無約束最小化一般公式，分析了解的性質(zhì)，推導(dǎo)了該無約束最小化一般模型與組合模型解的等價性，解的存在性和唯一性。將之推廣到基于多項式Logit(multinomial logit, MNL)和C-Logit的無約束優(yōu)化組合模型。最后用一個簡單算例證明了模型可行性和有效性。

1 符號和假設(shè)

1.1 符號定義

r為一個起點(diǎn)；s為一個終點(diǎn)；j為一種模式；k為一條路徑；R為起點(diǎn)集合；S為終點(diǎn)集合；J為模式集合；K為路徑集合；Nr為從起點(diǎn)r出發(fā)的潛在出行需求量；Tr為起點(diǎn)r用戶中選擇出行的出行者流量；Trs為從起點(diǎn)r出發(fā)選擇終點(diǎn)s的出行者流量；Trsj為從起點(diǎn)r出發(fā)到終點(diǎn)s，使用模式j(luò)的出行者流量；Trsjk為從起點(diǎn)r出發(fā)到終點(diǎn)s，使用模式j(luò)取道路徑k的出行者流量；β為組合模型參數(shù)，βr,βs,βj,βk分別是與出行、終點(diǎn)、模式、路徑相關(guān)的正參數(shù)；Pr為給定潛在出行需求條件下，出行者選擇出行的概率；Ps∣r為給定起點(diǎn)r條件下，出行者選擇終點(diǎn)s的概率；Pj∣rs為在起點(diǎn)r到終點(diǎn)s已經(jīng)確定條件下，出行者選擇模式j(luò)的概率；Pk∣rsj為在起點(diǎn)r到終點(diǎn)s模式j(luò)已經(jīng)確定條件下，出行者選擇路徑k的概率；Wr為出行者在起點(diǎn)r所期望獲得效用；Ws∣r為出行者從起點(diǎn)r到終點(diǎn)s所期望獲得效用；Wj∣rs為出行者從起點(diǎn)r到終點(diǎn)s使用模式j(luò)所期望獲得效用；Wk∣rsj為出行者從起點(diǎn)r到終點(diǎn)s使用模式j(luò)且取道路徑k所期望獲得效用；ga(xa)為出行者在路段a上的出行阻抗函數(shù)；gr(Tr)為出行者從起點(diǎn)r出發(fā)的出行阻抗函數(shù)；grs(Trs)為出行者從起點(diǎn)r出發(fā)駛向終點(diǎn)s的出行阻抗函數(shù)；grsj(Trsj)為出行者從起點(diǎn)r出發(fā)駛向終點(diǎn)s采用模式j(luò)的出行阻抗函數(shù)；grsjk(Trsjk)為出行者從起點(diǎn)r出發(fā)駛向終點(diǎn)s采用模式j(luò)取道路徑k的出行阻抗函數(shù)。

1.2 模型假設(shè)

假定某個出行者對出行、終點(diǎn)、模式和路徑的選擇符合一個自上而下的層級結(jié)構(gòu)，在每一層次做出選擇取決于上一層次的選擇。首先在第1層，一個潛在出行者Nr決定是否出行，形成兩種可能：出行和不出行，Tr為出行流，Pr是一個潛在出行者決定出行概率；第2層決定出行終點(diǎn)，若第1層選擇出行，那么他/她在第2層選擇一個終點(diǎn)s，形成條件概率Ps∣r；第3層決定出行模式，在第2層終點(diǎn)選擇下，需要選擇一種模式j(luò)，形成條件概率Pj∣rs；第4層決定出行路徑，需要選擇從r到s模式j(luò)下的一條路徑k，形成條件概率Pk∣rsj。

組合模型中假定層級結(jié)構(gòu)如圖1，與文獻(xiàn)[15]給出的結(jié)構(gòu)類似。

圖1 組合出行、終點(diǎn)、模式、路徑選擇層次結(jié)構(gòu)Fig. 1 Hierarchical structure of combined travel, destination, mode and route choice

假定Nr為起點(diǎn)r的潛在出行需求，Tr為起點(diǎn)r出行者中選擇出行的出行者流量，Pr為給定潛在出行需求的條件下，出行者選擇出行概率，如式(1)：

Tr=Nr·Pr

(1)

類似地，當(dāng)從起點(diǎn)r出發(fā)，駛往終點(diǎn)s的出行者流量滿足式(2)：

Trs=Tr·Ps|r

(2)

同理，從起點(diǎn)r出發(fā)到終點(diǎn)s的出行者，選擇模式j(luò)的流量如式(3)：

Trsj=Trs·Pj|rs

(3)

從起點(diǎn)r出發(fā)到終點(diǎn)s的出行者，使用模式j(luò)的出行者選擇路徑k的流量可通過從路徑選擇階段到出行選擇階段層次結(jié)構(gòu)中每一階段條件概率相乘得到，如式(4)：

Trsjk=Trsj·Pk|rsj=Nr·Pr·Ps|r·Pj|rs·Pk|rsj

(4)

根據(jù)期望效用理論，選擇方案i的效用為：Ui=ui+εi。其中：ui為效用的確定性部分，反映了方案的屬性和出行者的特征，εi為隨機(jī)誤差項，反映了效用中的不確定因素。

從起點(diǎn)r到終點(diǎn)s，使用模式j(luò)取道路徑k的一次出行總效用可假設(shè)如式(5)：

Ursjk=ur+urs+ursj+ursjk+εr+εrs+εrsj+εrsjk

(5)

式中：ur,urs,ursj,ursjk分別是與出行、終點(diǎn)、模式和路徑選擇相關(guān)的系統(tǒng)效用；εr,εrs,εrsj,εrsjk分別是與4個階段選擇相關(guān)的誤差項。

假定有式(6)：

(6)

式中：grs(·)是從起點(diǎn)r到終點(diǎn)s的廣義出行阻抗(負(fù)效用函數(shù))；gr(·)是出行的負(fù)效用函數(shù)；grsj(·)是從起點(diǎn)r到終點(diǎn)s使用模式j(luò)的負(fù)效用函數(shù)；grsjk(·)是從起點(diǎn)r到終點(diǎn)s使用模式j(luò)取道路徑k的負(fù)效用函數(shù)。

給定已選擇的起點(diǎn)r、終點(diǎn)s和模式j(luò)，一個出行者在一次出行中選擇路徑k的條件概率的效用等于：Wk∣rsj=ursjr+εrsjk；給定已選擇的起點(diǎn)r和終點(diǎn)s，出行者在一次出行中選擇模式j(luò)的條件概率效用如式(7)、(8)：

Uj|rs=uj|rs+εrsj=ursj+Wj|rs+εrsj

(7)

Wj|rs=E(maxUk|rsj)

(8)

式中：Wg∣rs表示從起點(diǎn)r到終點(diǎn)s使用模式j(luò)的期望獲得效用(滿意函數(shù))。

從起點(diǎn)r到終點(diǎn)s的期望獲得效用和在起點(diǎn)r的期望獲得效用分別如式(9)、(10)：

Ws|r=E(maxUj|rs)

(9)

Wr=E(maxUr|s)

(10)

根據(jù)滿意函數(shù)W特征，滿意函數(shù)對一個方案的系統(tǒng)效用偏導(dǎo)數(shù)等于該方案選擇概率，即為?W(U)/?Ui=Pi(U)，可知出行者在每一層選擇路徑、模式、終點(diǎn)的概率分別如式(11)～(13)：

(11)

(12)

(13)

2 組合無約束優(yōu)化模型

2.1 組合無約束優(yōu)化基本模型

在組合模型中，當(dāng)用戶未能通過單方面改變其出行、終點(diǎn)、模式和路徑選擇來改善其獲得的效用時，可達(dá)到模型均衡狀態(tài)。當(dāng)達(dá)到均衡狀態(tài)時，存在一個可行流模式T=[Tr,Trs,Trsj,Trsjk]，滿足式(1)～(4)。

若路徑出行阻抗可加，則可將路段流表示為經(jīng)過該路段所有路徑的路徑流之和，如式(14)：

(14)

同時，對終點(diǎn)、模式和路徑需滿足以下網(wǎng)絡(luò)流守恒約束，如式(15)～(17)：

(15)

(16)

(17)

在一個N為節(jié)點(diǎn)集，A為路段集的交通網(wǎng)絡(luò)G(N,A)中，假如網(wǎng)絡(luò)中出行者的阻抗函數(shù)ga(xa),gr(Tr),grs(Trs),grsj(Trsj),grsjk(Trsjk)是連續(xù)、可微、嚴(yán)格增且可分的，只取決于該路段、出行、終點(diǎn)、模式或路徑自身的流，且廣義阻抗函數(shù)grsjk(·)可加，則可將組合模型表現(xiàn)為一個無約束最小化問題Z1，如式(18)：

(18)

式中：ga(xa)表示路段a上的廣義阻抗函數(shù)；gr(Tr),grs(Trs),grsj(Trsj),grsjk(Trsjk)分別表示與出行、終點(diǎn)、模式和路徑相關(guān)的廣義阻抗函數(shù)，當(dāng)gr(Tr),grs(Trs),grsj(Trsj),grsjk(Trsjk)為常數(shù)時，相關(guān)變量可去除，這表明目標(biāo)函數(shù)不會受這幾個參數(shù)影響。

2.2 模型解的特征分析

2.2.1 解的等價性

解的等價性是證明無約束優(yōu)化模型〔式(18)〕恰為組合模型的路段流、出行流、終點(diǎn)流、模式流和路徑流解。

首先求解目標(biāo)函數(shù)Z1對路段a上流量xa的偏導(dǎo)數(shù)。當(dāng)路段阻抗函數(shù)ga(xa)連續(xù)、可微且可分時，路徑阻抗函數(shù)grsjk可表示為經(jīng)過該路徑所有路段之和的函數(shù)相加，如式(19)：

(19)

目標(biāo)函數(shù)中第1項對路段流的偏導(dǎo)數(shù)如式(20)：

(20)

目標(biāo)函數(shù)中第2、3項對路段流xa偏導(dǎo)數(shù)如式(21)：

(21)

目標(biāo)函數(shù)中第4、 5項和第5、 6項對路段流xa的偏導(dǎo)數(shù)如式(22)：

(22)

目標(biāo)函數(shù)中第8、 9項和第10、 11項對路段流xa的偏導(dǎo)數(shù)如式(23)：

(23)

綜合式(20)～(23)，可得式(24)：

(24)

由于路段阻抗函數(shù)嚴(yán)格增，?ga(xa)/?xa≠0，則有式(25)：

(25)

式 (25)為式(14)給出的均衡路段流。

目標(biāo)函數(shù)式(18)對出行流Tr求偏導(dǎo)。目標(biāo)函數(shù)式(21)的第1項對Tr偏導(dǎo)如式(26)：

(26)

同理，目標(biāo)函數(shù)的第4、5項對Tr的偏導(dǎo)如式(27)：

(27)

其余幾項對Tr的偏導(dǎo)均為0。由于gr(Tr)嚴(yán)格增，即?gr(Tr)/?Tr≠0，可式(28)：

Tr=Nr·Pr

(28)

式(28)恰為式(1)給出的均衡出行流。

目標(biāo)函數(shù)式(18)對終點(diǎn)流Trs求偏導(dǎo)，如式(29)：

(29)

由于grs(Trs)嚴(yán)格增，即?grs(Trs)/?Trs≠0，得式(30)：

Trs=Tr·Ps|r

(30)

式(30)恰為式(2)給出的均衡終點(diǎn)流。

同理，目標(biāo)函數(shù)式(18)對Trsj和Trsjk的偏導(dǎo)如式(31)、(32)：

Trsj=Tr·Ps|r·Pj|rs=Trs·Pj|rs

(31)

Trsjk=Tr·Ps|r·Pj|rs·Pk|rsj=Trsj·Pk|rsj

(32)

式 (31)恰為式(3)給出的均衡模式流；式(32)恰為式(4)給出的均衡路徑流。

綜上，無約束最小化問題最優(yōu)解給出了均衡的出行流、終點(diǎn)流、模式流和路徑流。因此，提出無約束最小化模型等價于組合出行-終點(diǎn)-模式-路徑選擇模型。

2.2.2 解的存在性和唯一性

目標(biāo)函數(shù)式(18)對路徑流Trsjk的偏導(dǎo)數(shù)如式(33)：

(33)

式(33)中各項均為嚴(yán)格凸函數(shù)，則目標(biāo)`函數(shù)Z1為嚴(yán)格凸函數(shù)，且當(dāng)?Z1/?Trsjk=0時，得到Trsjk=Tr·Ps∣r·Pj∣rs·Pk∣rsj為模型的解，因此所構(gòu)造模型有解且有唯一解。

2.3 模型拓展

2.3.1 基于MNL的組合無約束最小化模型

多項式Logit(MNL)結(jié)構(gòu)可視為提出的無約束最小化模型的特例。在MNL中，每階段出行者的選擇概率服從一個層級MNL結(jié)構(gòu)，如式(34)～(37)：

(34)

(35)

(36)

(37)

式中：Wr、Ws∣r、Wms∣r、Wj∣rs、Wk∣rsj分別為出行、終點(diǎn)、模式、路徑選擇階段的期望獲得效用。

在MNL路徑選擇下分別如式(38)～(41)：

(38)

(39)

(40)

(41)

MNL結(jié)構(gòu)下的組合無約束最小化問題如式(42)：

(42)

Ws|r滿足式(39)，進(jìn)而滿足式(40)、(41)。式(42)可作為式(18)的一個特例，且與式(18)類似，如式(43)～(46)：

(43)

(44)

(45)

(46)

式(42)～(46)給出無約束最小化問題的最優(yōu)解滿足均衡條件且能求解得到MNL下組合模型的唯一均衡出行流、終點(diǎn)流、模式流與路徑流解。

2.3.2 基于C-Logit的組合無約束最小化模型

在路徑選擇行為中，為反映更常見的路徑重疊問題，筆者采用C-Logit模型[16]來處理路徑重疊問題。C-Logit模型由其解析閉型概率表達(dá)式、較少的校正、符合隨機(jī)效用理論的較理性行為而受到廣泛應(yīng)用。其采用一個系統(tǒng)效用項中的共同因子(CF)來解釋重疊路徑。

在C-Logit模型中，選擇一條路徑k的概率如式(47)：

(47)

式中：θ為與路徑選擇相關(guān)的參數(shù)；CF為路徑重疊參數(shù)。

一個典型的CF形式如式(48)：

r∈R,s∈S

(48)

式中：Lkl為路徑k和l共同路徑的長度；Lk和Ll分別為路徑k和l的長度；η1、η2分別為參數(shù)，若η1=0，則CF因子為0，C-Logit模型退化為傳統(tǒng)的MNL模型。

在組合模型路徑選擇層，采用C-Logit模型表示，如式(49)：

(49)

其中：CF因子滿足式(48)的形式。其他層次選擇概率與MNL相同，服從式(34)～(36)。則C-Logit模型下的無約束最小化問題與式(42)的形式相同。其中：Ws∣r滿足式(39)，進(jìn)而滿足式(40)、(50)。式(50)表述為：

(50)

與MNL下的無約束優(yōu)化公式類似，可得式(51)～(54)：

(51)

(52)

(53)

(54)

式(50)～(54)給出無約束最小化問題的最優(yōu)解滿足均衡條件且能求解得到C-Logit下組合模型的唯一均衡出行流、終點(diǎn)流、模式流與路徑流解。

3 算法和算例

在求解無約束優(yōu)化問題時，最速下降法是一常用的求解算法。它選取一個目標(biāo)函數(shù)值下降最快的方法，以利于盡快地達(dá)到極小點(diǎn)。這種算法關(guān)鍵是最速下降法的選取，一般取負(fù)梯度作為最速下降方向，然后進(jìn)行一維搜索，當(dāng)滿足精度要求時則停止計算。其一般步驟為：

4)步驟四：移動。yn+1=yn-yn·ynZ(yn)；

最速下降法中，最主要的步驟是下降方向確定和線性搜索。條件概率Pr、Ps|r、Pj|rs、Pk|rsj分別由式(34)～(37)(MNL無約束模型中)或式(47)～(49)(C-Logit無約束模型中)給出。

用一個簡單算例來研究提出的模型特征。使用一個如圖2的網(wǎng)絡(luò)，包含3個OD對1-3、1-4、1-5，5個節(jié)點(diǎn)和8個路段。OD對和路段、路徑間的對應(yīng)關(guān)系見表1。

圖2 一個簡單網(wǎng)絡(luò)Fig. 2 A simple network

表1 OD對和路段、路徑間的對應(yīng)關(guān)系Table 1 Correspondence among OD pair, road section and paths

假定網(wǎng)絡(luò)中僅有兩種模式：汽車和公交，為方便分析用1和2表示，即j=1表示汽車，j=2表示公交。兩種模式網(wǎng)絡(luò)有相同的拓?fù)浣Y(jié)構(gòu)且相互獨(dú)立。

假設(shè)汽車網(wǎng)絡(luò)的路段、終點(diǎn)、OD對和路徑的負(fù)效用函數(shù)分別用式(55)表示：

(55)

則汽車網(wǎng)絡(luò)的路段、終點(diǎn)、OD對和路徑負(fù)效用函數(shù)分別如式(56)：

(56)

設(shè)與出行選擇、終點(diǎn)、模式相關(guān)參數(shù)βr,βs,βj=1，與路徑選擇相關(guān)的參數(shù)βk=0.5。從起點(diǎn)1出發(fā)的潛在出行者數(shù)N1=1 000，吸引力h1=5。OD對1-4和1-5吸引力分別為h14=3.5，h15=3.8；OD對1-4間汽車和公交兩種模式吸引力分別為h141=3.5，h142=3.6；OD對1-5間汽車和公交兩種模式的吸引力為h151=3.8，h152=3.4。OD對間每一路段自由流出行時間均為500，如表2。

表2 終點(diǎn)和路徑選擇階段均衡流量結(jié)果Table 2 Equilibrium flow results in terminal and route selection stages

為反映路徑重疊效應(yīng)對均衡解的影響，采用基于C-Logit的無約束優(yōu)化模型進(jìn)行再求解。仍采用上述參數(shù)和負(fù)效用函數(shù)形式。另外，令式(48)中CF參數(shù)η1=0.9，η2=0.8。各路段長度為：路段2、6、7、8長度為5；路段1、4長度為12；路段3、5長度為8?？芍窂?、3重疊部分，以及路徑6、7的重疊部分即為路段2的長度。計算得到終點(diǎn)選擇階段和路徑選擇階段均衡解如表2第3列。

由表2知在C-Logit組合模型中，路段流會隨路徑重疊而變化，其對路徑流量進(jìn)行分配時，相對MNL下的組合模型，重疊路徑上被分配到的流量會減少，而非重疊路徑上被分配到的流量會相應(yīng)增加，以保持流量守恒，這說明傳統(tǒng)MNL會高估重疊路徑流，而低估非重疊路徑流。同理，OD流也會隨路徑重疊而變化，通過改變每一OD對的吸引力來改變OD流變化，有重疊路徑OD對會使自身吸引力下降，因而使OD需求減少，反之沒有重疊路徑的OD對會使自身吸引力上升，OD需求增加。即OD對(1, 3)和(1, 5)間需求減少，OD對(1, 4)間需求增加，這說明MNL會高估重疊路徑OD需求水平，而低估非重疊路徑OD需求水平。

4 結(jié) 論

為克服傳統(tǒng)的4步驟序列模型不同階段中行為不一致問題，筆者采用了一個組合出行-終點(diǎn)-模式-路徑選擇模型，將出行與否的選擇、出行終點(diǎn)選擇、模式選擇和交通分配納入一個統(tǒng)一的框架進(jìn)行分析；分析了組合模型在期望效用理論下的出行阻抗、用戶分別選擇出行、終點(diǎn)、模式和路徑的概率或條件概率，及滿意函數(shù)和特征；建立了組合模型的一般無約束優(yōu)化公式；分析了解的性質(zhì)，證明了一般無約束優(yōu)化公式與帶約束組合模型解的等價性、存在性和唯一性；并將模型推廣到服從多項式Logit和C-Logit組合模型無約束優(yōu)化公式；用算法和算例證明了模型的可行性和有效性。

結(jié)果表明：無約束優(yōu)化公式與帶約束的組合模型公式在求解均衡解方面是等價的。且路徑重疊效應(yīng)會對均衡路徑流分配產(chǎn)生影響，同時通過影響OD對的吸引力來對有重疊路徑的OD對的需求水平產(chǎn)生影響。