何勝學(xué)

(上海理工大學(xué)管理學(xué)院 上海 200093)

0 引 言

選擇出行目的地和具體出行路線是交通出行的兩個(gè)基本決策，也是進(jìn)行交通網(wǎng)絡(luò)系統(tǒng)運(yùn)行效率評價(jià)和交通系統(tǒng)規(guī)劃的重要組成部分.傳統(tǒng)的交通規(guī)劃四步驟法將上述兩個(gè)決策按序分別考慮，忽視了兩個(gè)決策間存在的相互影響.因此有研究者針對上述問題試圖將兩個(gè)決策問題整合為一個(gè)單層優(yōu)化模型，但是在嘗試構(gòu)建這些單層組合模型過程中出現(xiàn)的特殊參數(shù)標(biāo)定與不合理概念使得這些模型很難應(yīng)用于實(shí)際.針對上述問題，本文嘗試建立相應(yīng)的雙層規(guī)劃模型來合理反映兩個(gè)決策的特征與差異，并設(shè)計(jì)有效算法求解上述雙層規(guī)劃模型.

Wardrop提出了出行路徑選擇兩原則，即Wardrop第一原則(用戶均衡)和Wardrop第二原則(系統(tǒng)最優(yōu)).Beckman給出了用戶均衡交通流分配優(yōu)化模型，即有名的Beckman變換.Leblanc首次給出了求解用戶均衡模型的實(shí)用有效Frank-Wolfe算法.近年來研究者開始應(yīng)用投影動(dòng)態(tài)理論對動(dòng)態(tài)和擬動(dòng)態(tài)的交通流分配問題進(jìn)行建模分析[1-4].針對路段流量一般受限于路段通行能力的情況，研究者也提出了有邊約束的交通流分配變分不等式模型[5-6].為了反映路段行程時(shí)間函數(shù)具有的兩階段特征，最近研究者開始利用非凸規(guī)劃理論研究交通流的分配和網(wǎng)絡(luò)演化問題[7-8].

交通流分配中的組合網(wǎng)絡(luò)模型也是研究者關(guān)注的重點(diǎn).大致可分為：運(yùn)量分布與交通分配組合模型、方式分擔(dān)與交通分配組合模型、運(yùn)量分布/方式分擔(dān)/交通分配組合模型[9].本文關(guān)注的運(yùn)量分布與交通分配組合模型又可分為：單運(yùn)量分布約束組合模型和雙運(yùn)量分布約束組合模型.現(xiàn)有運(yùn)量分布約束組合模型多為單層模型.運(yùn)量分布約束組合模型中均需設(shè)定目的地吸引力測度指標(biāo)Ms，?s∈D[10].令O和D分別為起點(diǎn)和終點(diǎn)集合.令μrs為起點(diǎn)r∈O與終點(diǎn)s∈D間最短的可行路徑行程時(shí)間.運(yùn)量分布約束組合模型通常依據(jù)μrs-Ms大小決策起訖點(diǎn)對間交通量.Ms的量綱需要與μrs一致，在實(shí)踐中通常很難給出符合要求的合理值.為了方便后續(xù)求解，考慮終點(diǎn)需求函數(shù)的單運(yùn)量分布約束組合模型和常見的雙運(yùn)量分布約束組合模型一般會(huì)基于熵最大化理論在目標(biāo)函數(shù)中加入對應(yīng)項(xiàng).而該加入項(xiàng)的系數(shù)需要利用歷史的起訖點(diǎn)對間完整交通需求量加以標(biāo)定，而該信息在現(xiàn)實(shí)應(yīng)用時(shí)一般很難取得的.考慮到上述問題，本文通過建立雙層規(guī)劃模型，免去對熵最大化理論加入項(xiàng)系數(shù)進(jìn)行標(biāo)定的工作，同時(shí)放松了對目的地吸引力測度指標(biāo)Ms量綱的限制.在建立的新模型中，終點(diǎn)s作為出行目的地對出行者的吸引力系數(shù)標(biāo)定將更加方便和符合實(shí)際.

本文主要的貢獻(xiàn)包括：①建立了考慮目的地選擇的交通流分配雙層規(guī)劃模型.上層模型拓展了目的地選擇概念，可以適用于各種已有的目的地選擇理論，如重力模型和熵最大化模型.②設(shè)計(jì)了求解上述雙層規(guī)劃的有效算法.通過將下層路徑選擇模型抽象為一個(gè)映射，并利用經(jīng)典Frank-Wolfe法對其進(jìn)行求解，從而可以更有效地對上層目的地選擇模型設(shè)計(jì)求解方法.將針對下層模型的Frank-Wolfe法嵌入為上層模型設(shè)計(jì)的可行下降方向法中，最終實(shí)現(xiàn)雙層規(guī)劃模型的求解.

1 模型構(gòu)建

1.1 參變量介紹

1.2 目的地選擇假設(shè)

經(jīng)典的網(wǎng)絡(luò)交通流分配模型一般假設(shè)起訖點(diǎn)對間的交通需求qrs給定.而實(shí)際中，交通規(guī)劃者往往通過交通出行調(diào)查只知道任意起點(diǎn)總的交通需求量qr.因此需要對出行者的目的地進(jìn)行選擇，使其滿足如下的起點(diǎn)基本流量守恒條件.

(1)

一般而言出行者對出行目的地的選取不僅需要考慮出行的行程時(shí)間長短，也許考慮備選目的地的吸引力大小.這里的吸引力主要指備選目的地滿足出行者出行目的的可能性.例如，對于出行者購物需求，如果目的地是一個(gè)商業(yè)購物中心，則具有較強(qiáng)的吸引力.用吸引力系數(shù)As的值表示目的地的吸引力大小.在后續(xù)分析中，假設(shè)As的值給定.

下面給出兩種情況確定目的地選擇比例wrs的方法.第一種情況下，假設(shè)wrs滿足

(2)

式中：m為一給定正整數(shù)，一般取值1或2.當(dāng)m等于2時(shí)，式(2)與出行分布中的重力模型相一致，即由確定起點(diǎn)出發(fā)的出行者中選擇某終點(diǎn)為目的地的數(shù)量與該起訖點(diǎn)對間的行程時(shí)間平方成反比.

第二種情形源于熵最大化理論，假設(shè)wrs滿足

wrs=Asexp(-μrs)/∑d∈D[Adexp(-μrd)] (3)

至于實(shí)際中應(yīng)用哪種假設(shè)則需要根據(jù)具體情況進(jìn)行估計(jì)選擇.兩種情況下，∑s∈Dwrs=1均成立.

如果有了目的地選擇比例，起訖點(diǎn)對間的期望交通需求量為

(4)

如果μ為由所有μrs構(gòu)成的列向量，可將wrs視為μ的函數(shù)，即wrs=wrs(μ).

1.3 下層路徑選擇行為模型

針對出行者的擇路行為，對應(yīng)的用戶均衡模型(user equilibrium model，UEM)為

(5)

(6)

(7)

(8)

與經(jīng)典用戶均衡模型的唯一差別在于上述模型中起訖點(diǎn)對間的交通需求量是待定的.式(6)為連接指定起訖點(diǎn)對的可行路段上的路徑交通流量之和等于該起訖點(diǎn)對間的交通需求量.式(7)為路徑流量的非負(fù)約束.式(8)為一個(gè)隱含約束條件，表明指定路段流量等于所有途經(jīng)該路段的路徑流量之和.式(5)可理解為所有路段的流量逐步累計(jì)過程中單位流量行程時(shí)間的加和.

(9)

式中：上標(biāo)“*”為相關(guān)量對應(yīng)模型的最優(yōu)解.

1.4 上層目的地選擇模型

給定起訖點(diǎn)對間的交通需求模式q，由下層優(yōu)化模型可以確定一個(gè)唯一的μ.上述關(guān)系可以抽象為映射μ=Ψ(q)或μrs=Ψrs(q)，?rs.因此，wrs=wrs(μ)=wrs(Ψ(q))成立.

(10)

式中：q的可行集合定義為Q≡{q|qrs≥0,?rs∈W;∑s∈Dqrs=qr,?r}.

2 求解算法

下層模型(即抽象映射μ=Ψ(q)) 可利用Frank-Wolfe法進(jìn)行求解，具體步驟為

下面我們?yōu)槭?10)設(shè)計(jì)一個(gè)可行下降方向法.由模型(10)的目標(biāo)函數(shù)，可得

(11)

利用式(11)給出的dk可對q進(jìn)行如下更新.

qk+1=qk+αkdk

(12)

具體步長αk的確定可以利用一維搜索算法實(shí)現(xiàn).鑒于實(shí)現(xiàn)的復(fù)雜性，應(yīng)當(dāng)盡量減少調(diào)用下層求解算法的次數(shù)，因此可采用一些啟發(fā)式一維搜索算法，如Armijo法.Armijo法中的步長αk=βmks，mk是從小到大滿足下式的第一個(gè)非負(fù)整數(shù)：

以式(2)作為目的地選擇比例的計(jì)算式，求解雙層規(guī)劃的具體步驟為

步驟2計(jì)算新的最短路行程時(shí)間.調(diào)用求解下層規(guī)劃UEM的算法，計(jì)算得到μk=Ψ(qk).

步驟3方向搜索 按照式(11)，計(jì)算可行下降方向dk.

步驟4步長計(jì)算 利用Armijo法，依據(jù)式(13)計(jì)算得到αk.

步驟5交通需求模式更新.令qk+1=qk+αkdk.

步驟6中的ε和ε′均為事先給定的較小正數(shù)，作為收斂指標(biāo).注意算法中目的地選擇比例wrs的計(jì)算方法應(yīng)保持一致，可以選擇式(2)～(3)，也可以選擇其他可能的形式.

3 算例分析

本節(jié)利用Nguyen和Dupius路網(wǎng)[11]來對本文提出的模型和算法加以驗(yàn)證.該路網(wǎng)包含13個(gè)節(jié)點(diǎn)，其中節(jié)點(diǎn)1和2為起點(diǎn)，3和4為終點(diǎn).相關(guān)節(jié)點(diǎn)和路段的標(biāo)號見圖1.算法的終止指標(biāo)設(shè)定為ε″=0.001、ε=0.05和ε′=0.05.上層模型算法中Armijo步長搜索的參數(shù)設(shè)定為σ=0.6、β=0.5和s=0.5.以式(2)中參數(shù)m為2時(shí)的重力模型來確定目的地選擇比例.

圖1 13個(gè)節(jié)點(diǎn)的Nguyen和Dupius路網(wǎng)

考慮兩個(gè)不同的情景進(jìn)行計(jì)算分析.情景1設(shè)定起點(diǎn)①和②的交通需求量分別為1 800和1 300，而終點(diǎn)③和④的吸引力系數(shù)分別為100和210.情景2設(shè)定起點(diǎn)①和②的交通需求量分別為1 800和2 300，而終點(diǎn)3和4的吸引力系數(shù)分別為200和120.

利用Java程序語言實(shí)現(xiàn)上節(jié)的算法，并在NetBeans IDE 8.0.2環(huán)境下執(zhí)行.路段均衡流量的計(jì)算結(jié)果總結(jié)見表1；最終的交通需求分布結(jié)果見表2；計(jì)算過程中上層目標(biāo)函數(shù)的變化記錄見表3.兩種情境下上層算法均執(zhí)行七次后收斂，雙層模型整體求解的運(yùn)行時(shí)間均小于1 ms(即計(jì)算機(jī)顯示執(zhí)行時(shí)間為0，小于其可給出的最小時(shí)間單位1 ms).利用節(jié)點(diǎn)流量守恒條件可判定計(jì)算結(jié)果的合理性.

表1 路段行程時(shí)間函數(shù)的參數(shù)和均衡流量

表2 交通需求分布結(jié)果

表3 上層目標(biāo)函數(shù)變化情況

4 結(jié) 束 語

綜合考慮出行目的地選取和路線選取兩種決策，可以有效提高交通系統(tǒng)規(guī)劃和系統(tǒng)運(yùn)行評價(jià)的準(zhǔn)確性和可靠性.本文通過設(shè)計(jì)整合兩種決策的雙層規(guī)劃模型，不僅拓展了現(xiàn)有理論處理目的地選擇模型的靈活性，也降低了現(xiàn)有模型應(yīng)用時(shí)面臨的參數(shù)標(biāo)定工作.本文設(shè)計(jì)的內(nèi)嵌經(jīng)典用戶均衡模型的Frank-Wolfe法的可行下降算法可以實(shí)現(xiàn)對本文雙層規(guī)劃模型的高效求解，因此其實(shí)際應(yīng)用前景良好.