趙 杰，張 莉，安新磊

（1.蘭州交通大學(xué) 數(shù)理學(xué)院，甘肅 蘭州 730070；2.蘭州工業(yè)學(xué)院 基礎(chǔ)學(xué)科部，甘肅 蘭州 730050）

二階隨機(jī)需求條件下公交網(wǎng)絡(luò)的服務(wù)可靠性研究

趙 杰1，張 莉2，安新磊1

（1.蘭州交通大學(xué) 數(shù)理學(xué)院，甘肅 蘭州 730070；2.蘭州工業(yè)學(xué)院 基礎(chǔ)學(xué)科部，甘肅 蘭州 730050）

引入服務(wù)可靠性這一概念，以乘客出行成本和車行運(yùn)營(yíng)成本最小為目標(biāo)建立隨機(jī)需求下的公交網(wǎng)絡(luò)模型，并提出固定需求的服務(wù)方案模型和改進(jìn)的二階隨機(jī)方案模型。該模型體現(xiàn)了乘客公交出行的選擇策略并反映了公交網(wǎng)絡(luò)中不確定需求和服務(wù)可靠性的相互聯(lián)系。在分析公交出行網(wǎng)絡(luò)中的服務(wù)設(shè)計(jì)，包括常規(guī)服務(wù)和特別服務(wù)的基礎(chǔ)上，運(yùn)用二階下降法通過規(guī)定不確定的隨機(jī)變量（服務(wù)可靠性參數(shù)）來(lái)求解二階隨機(jī)方案：首先在一階段減少混合整數(shù)規(guī)劃的數(shù)量以節(jié)省計(jì)算時(shí)間，隨后在二階段中模擬出一個(gè)線性規(guī)劃，以便有效地求解二階隨機(jī)方案。最后，通過實(shí)例模型驗(yàn)證了該方案的可行性。

公交網(wǎng)絡(luò)；服務(wù)可靠性；二階下降法；隨機(jī)方案；乘客需求

0 引言

隨著科技的發(fā)展，公交系統(tǒng)作為城市中經(jīng)典的復(fù)雜系統(tǒng)越來(lái)越受到人們的關(guān)注。公交網(wǎng)絡(luò)問題也可以抽象成為經(jīng)典的復(fù)雜網(wǎng)絡(luò)，研究公交網(wǎng)絡(luò)模型對(duì)于城市交通規(guī)劃和管理具有重大而積極的意義。

早前對(duì)公交網(wǎng)絡(luò)模型的研究多是以網(wǎng)絡(luò)的結(jié)構(gòu)特征以及拓?fù)湫再|(zhì)為出發(fā)點(diǎn)來(lái)研究網(wǎng)絡(luò)可靠性與抗毀性，高自友等人[1]對(duì)北京市的公交網(wǎng)絡(luò)進(jìn)行了實(shí)證研究分析，發(fā)現(xiàn)北京市公交網(wǎng)絡(luò)具有無(wú)標(biāo)度特性；鄭嘯等人[2]以北京市公交站點(diǎn)和公交線路為例構(gòu)建了公交復(fù)雜網(wǎng)絡(luò)模型，統(tǒng)計(jì)了多項(xiàng)靜態(tài)指標(biāo)并提出優(yōu)化方案；王喆等人[3]對(duì)成都市公交網(wǎng)絡(luò)建立了3種模型，得出公交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和靜態(tài)參數(shù)，并對(duì)網(wǎng)絡(luò)拓?fù)湫再|(zhì)進(jìn)行了分析。

公交網(wǎng)絡(luò)不僅包括靜態(tài)的網(wǎng)絡(luò)特征，還包括一些動(dòng)態(tài)的網(wǎng)絡(luò)行為，例如網(wǎng)絡(luò)中的客流分配方案、乘客的換乘選擇行為以及乘客對(duì)出行的隨機(jī)需求。隨著對(duì)公交網(wǎng)絡(luò)中乘客需求的深入考慮，服務(wù)可靠性的概念也被引入公交網(wǎng)絡(luò)研究領(lǐng)域。Gao Z.Y.等人[4]基于確定的乘客需求建立了經(jīng)典的客流分配服務(wù)模型；Szeto W.Y.等人[5]在隨機(jī)用戶均衡的基礎(chǔ)上建立了客流分配服務(wù)模型；劉志謙等人[6]對(duì)廣州軌道交通復(fù)雜網(wǎng)絡(luò)特征和可靠性進(jìn)行了研究，丁小兵[7]研究了上海城市交通的可靠性；Wang Z.W.等人[8]通過考慮乘客的偏好選擇擴(kuò)展出不同服務(wù)類型的方案；Bagloee S.A.等人[9]研究了交通網(wǎng)絡(luò)設(shè)計(jì)問題優(yōu)化預(yù)算約束下的服務(wù)可靠性。

在對(duì)公交網(wǎng)絡(luò)的研究中，基于確定的乘客需求的文獻(xiàn)已有很多，但研究隨機(jī)條件下的乘客出行，即不確定的乘客需求的文獻(xiàn)較少。陸化普等人[10]建立了OD需求不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型；孫華等人[11]利用魯棒性優(yōu)化方法建立了OD需求不確定環(huán)境下交通網(wǎng)路設(shè)計(jì)極大極小模型并提出了平均法求解算法。

在實(shí)際生活中，乘客的出行與需求本身具有很大的不確定性，因此，研究隨機(jī)需求條件下的乘客出行服務(wù)評(píng)估具有較強(qiáng)的現(xiàn)實(shí)意義，能夠更清晰地體現(xiàn)乘客出行選擇策略，更真實(shí)地反映公交網(wǎng)絡(luò)中不確定需求與服務(wù)可靠性的相互聯(lián)系。本文以乘客成本和運(yùn)營(yíng)耗費(fèi)最小為目標(biāo)，通過服務(wù)可靠性建立隨機(jī)需求下的公交網(wǎng)絡(luò)服務(wù)模型，服務(wù)可靠性可以分離出依賴于混合整數(shù)線性規(guī)劃的二階混合整數(shù)隨機(jī)方案，通過二階下降法規(guī)定不確定的隨機(jī)變量參數(shù)ρ來(lái)求解二階隨機(jī)方案，并借助實(shí)例研究分析了模型的可行性，可為公交調(diào)度提供參考。

1 公交網(wǎng)絡(luò)模型

1.1 相關(guān)假設(shè)

（1）假設(shè)只考慮單一的公交車行類型；

（2）假設(shè)每個(gè)OD對(duì)對(duì)應(yīng)其出行的站點(diǎn)都服從一個(gè)確定的概率分布；

（3）假設(shè)涉及到多線路問題時(shí)，從站點(diǎn)P直接到站點(diǎn)Q的常規(guī)服務(wù)運(yùn)營(yíng)成本比從站點(diǎn)P途經(jīng)站點(diǎn)Z換乘到站點(diǎn)Q的成本小；

（4）假設(shè)在一個(gè)規(guī)劃周期內(nèi)同一個(gè)站點(diǎn)不能選擇返回并重新作為出發(fā)點(diǎn)。

1.2 符號(hào)定義

O：網(wǎng)絡(luò)中初始節(jié)點(diǎn)，對(duì)應(yīng)于公交網(wǎng)絡(luò)中的始發(fā)站點(diǎn)；

D：網(wǎng)絡(luò)中目的節(jié)點(diǎn)，對(duì)應(yīng)于公交網(wǎng)絡(luò)中的終點(diǎn)站點(diǎn)；

G：網(wǎng)絡(luò)中OD節(jié)點(diǎn)對(duì)組成的集合；

d∈G：網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)集合中第d對(duì)OD節(jié)點(diǎn)對(duì)；

Gf=(Nf,Af)：在車行網(wǎng)絡(luò)中點(diǎn)集N和邊集A；Gd=(Nd,Ad)：在乘客網(wǎng)絡(luò)中點(diǎn)集N和邊集A；

,：在相應(yīng)的車行網(wǎng)絡(luò)中一個(gè)規(guī)劃周期內(nèi)的初始點(diǎn)集和終點(diǎn)集；

Sf,Sd：在相應(yīng)的車行網(wǎng)絡(luò)和乘客網(wǎng)絡(luò)中的服務(wù)邊；

Wf,Wd：在相應(yīng)的車行網(wǎng)絡(luò)和乘客網(wǎng)絡(luò)中的等待邊；

Md：在乘客網(wǎng)絡(luò)中的第d個(gè)人工節(jié)點(diǎn)；

(Od,Md)：上述乘客網(wǎng)絡(luò)中人工節(jié)點(diǎn)對(duì)應(yīng)的初始節(jié)點(diǎn)；

(Md,Dd)：上述乘客網(wǎng)絡(luò)中人工節(jié)點(diǎn)對(duì)應(yīng)的目的節(jié)點(diǎn)；

H：重新啟用計(jì)劃持續(xù)時(shí)間的車行相關(guān)的固定成本；

N：最大的公交車數(shù)目；

ξ：公交車行的換乘能力；：在車行網(wǎng)絡(luò)中等待邊(i,j)∈Wf的最大值；

Fij：在每一次出行中節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的使用費(fèi)用；

：每名乘客在等待邊(i,j)∈Wd上的等待耗費(fèi)；

：每名乘客在服務(wù)邊(i,j)∈Sd上的出行耗費(fèi)；

R：實(shí)例生成的集合；

Bd：在第d對(duì)OD節(jié)點(diǎn)對(duì)上的外生需求；

ρd：在第d對(duì)OD節(jié)點(diǎn)對(duì)上的服務(wù)可靠性，其中ρ={ρd}；

Yij：在車行網(wǎng)絡(luò)中車行邊的總數(shù)量，其中Y={Yij}；

：在乘客網(wǎng)絡(luò)中享受常規(guī)服務(wù)的乘客量，其中X={Xij}；

：在乘客網(wǎng)絡(luò)中享受特別服務(wù)的乘客量，其中Z={Zij}。

1.3 車行網(wǎng)絡(luò)

定義車行網(wǎng)絡(luò)為圖G=(Nf,Af)（見圖1），其中，Nf是該網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，Af是公交車出行的邊集合，Af又包括2個(gè)子集（2層含義）：服務(wù)邊集合Sf和等待邊集合Wf，并且有Af=Sf?Wf。每一條服務(wù)邊都描述了一次公交車出行，并且其始發(fā)站、終點(diǎn)站、出行時(shí)間都會(huì)被相應(yīng)的網(wǎng)絡(luò)節(jié)點(diǎn)所決定。車行邊的成本包括運(yùn)營(yíng)成本（例如：燃料耗費(fèi)、維修費(fèi)用）以及正常出行成本，車行網(wǎng)絡(luò)上的等待邊為非負(fù)整數(shù)，它表示?？吭谝粋€(gè)公交站點(diǎn)的公交車的數(shù)目，假設(shè)等待邊的操作成本可以忽略不計(jì)。

圖1 車行網(wǎng)絡(luò)示意圖

1.4 乘客網(wǎng)絡(luò)

同樣定義乘客網(wǎng)絡(luò)為圖G=(Nd,Ad)（見圖2），其中，Nd是乘客出行的節(jié)點(diǎn)集合，Ad是乘客出行的邊集合。與Af集合相類似，Ad也包括2個(gè)子集（2層含義）：服務(wù)邊集合Sd和等待邊集合Wd，并且有Ad=Sd?Wd。此外，與每個(gè)乘客網(wǎng)絡(luò)圖G=(Nd,Ad)相關(guān)聯(lián)的有1個(gè)人工節(jié)點(diǎn)Md和2個(gè)人工邊：初始邊(Od,Md)和目標(biāo)邊(Md,Dd)。服務(wù)邊定義為乘客在公交站點(diǎn)之間的出行，其出行時(shí)間被網(wǎng)絡(luò)中相應(yīng)的節(jié)點(diǎn)所決定，乘客邊代表出行在公交車上的乘客的數(shù)目，它也會(huì)受到車行服務(wù)能力的影響。另外，等待邊的權(quán)值代表在每個(gè)站點(diǎn)等待的乘客的數(shù)目，等待邊可能由于能力不足而不能滿足所有需求。

圖2 乘客網(wǎng)絡(luò)示意圖

在乘客網(wǎng)絡(luò)中，初始邊由初始節(jié)點(diǎn)和與每1個(gè)特定的OD對(duì)相關(guān)的人工節(jié)點(diǎn)Md構(gòu)造而成，其中初始邊代表在原始節(jié)點(diǎn)處沒有服務(wù)到的乘客的數(shù)目，可以理解為在規(guī)劃周期內(nèi)未對(duì)服務(wù)感到滿意或者不再有需求的乘客數(shù)目。同理乘客網(wǎng)絡(luò)中的目的邊由目的節(jié)點(diǎn)和人工節(jié)點(diǎn)Md構(gòu)造而成，這時(shí)目的邊代表著在規(guī)劃周期內(nèi)所到達(dá)目的節(jié)點(diǎn)的乘客數(shù)目，也可以理解為服務(wù)總需求邊。

1.5 服務(wù)可靠性

較早的研究只是從定性角度討論可靠性這一概念，而并沒有對(duì)其進(jìn)行數(shù)值度量，后來(lái)引入了概率與統(tǒng)計(jì)的方法，可靠性才有了較多的定量的應(yīng)用?？煽啃灾傅氖窍到y(tǒng)在規(guī)定條件下和規(guī)定時(shí)間內(nèi)完成規(guī)定功能的能力。在復(fù)雜網(wǎng)絡(luò)中，可靠性已被作為整體規(guī)劃、設(shè)計(jì)和實(shí)施的重要部分，用來(lái)評(píng)價(jià)網(wǎng)絡(luò)模型的功能和效率。在公交網(wǎng)絡(luò)中可以用服務(wù)可靠性來(lái)分析公交公司服務(wù)網(wǎng)絡(luò)提供服務(wù)的穩(wěn)定水平，用于優(yōu)化和設(shè)計(jì)可靠的公交出行網(wǎng)絡(luò)，從而提高公交網(wǎng)絡(luò)的服務(wù)質(zhì)量，降低成本。

2 需求及服務(wù)模型方案

2.1 固定需求方案

含有固定需求Bd的確定方案可表示為：

定義目標(biāo)函數(shù)為總體耗費(fèi)的最小值，包括運(yùn)營(yíng)成本和乘客耗費(fèi)成本，其主要包含以下4個(gè)部分：

（1）乘坐1次公交車服務(wù)時(shí)間內(nèi)的固定成本；

（2）每次出行的操作耗費(fèi)，例如燃料耗費(fèi)和勞動(dòng)力成本；

（3）乘客的等待時(shí)間耗費(fèi)；

（4）乘客的出行時(shí)間耗費(fèi)。

在這個(gè)目標(biāo)函數(shù)中，忽略了運(yùn)營(yíng)公司的稅收和乘客的票價(jià)費(fèi)用。目標(biāo)函數(shù)中的第1個(gè)和式給出了總的固定成本；第2個(gè)和式給出了總的出行耗費(fèi)成本，應(yīng)注意等待邊是由1個(gè)站點(diǎn)在連續(xù)的2個(gè)時(shí)間點(diǎn)生成的；第3個(gè)和式給出了總的乘客等待時(shí)間耗費(fèi)，其中是每個(gè)乘客在每個(gè)時(shí)間間隔的等待耗費(fèi)；第4個(gè)和式給出了總的乘客出行時(shí)間耗費(fèi)，其中是每個(gè)乘客在服務(wù)邊i到j(luò)上的出行耗費(fèi)。約束條件中，式（2）為確保車行網(wǎng)絡(luò)中每一站點(diǎn)的車行量；式（3）說(shuō)明在操作過程中不得超過最大的容許公交車數(shù)目；式（4）給出了在乘客網(wǎng)絡(luò)中考慮到外生需求時(shí)每個(gè)節(jié)點(diǎn)對(duì)乘客的保護(hù)條件；式（5）結(jié)合了所有的OD對(duì)上服務(wù)邊(i,j)的乘客數(shù)和每個(gè)服務(wù)邊(i,j)上公交車行能力的總乘客量需求；式（6）提供了車行邊(i,j)的上界；式（7）規(guī)定了車行變量必須是整數(shù)。

在公交網(wǎng)絡(luò)服務(wù)設(shè)計(jì)的過程中，目標(biāo)是控制車行變量Yij和乘客變量來(lái)最小化系統(tǒng)的總成本，這一規(guī)劃并沒有明確說(shuō)明在每個(gè)OD出行過程中如何選擇出行方式和出行路徑，也沒有明確地檢測(cè)出車行服務(wù)是直達(dá)還是需要換乘，這些情況都會(huì)在給定的條件（1）～（7）中被整合出來(lái)?？傊?，這一規(guī)劃構(gòu)成了混合整數(shù)線性規(guī)劃。

2.2 二階隨機(jī)方案

下文主要研究那些不確定的需求卻服從一定概率分布的情形。

首先列入兩種服務(wù)類別：一種是固定的公交出行類型的運(yùn)轉(zhuǎn)，即常規(guī)服務(wù)；另一種是盡可能地把這些服務(wù)轉(zhuǎn)包給第三者，即特別服務(wù)。在隨機(jī)發(fā)展過程中，這一構(gòu)想又可劃分為2個(gè)階段：第一階段確定常規(guī)服務(wù)需求，第二階段確定特別服務(wù)需求。在常規(guī)服務(wù)的確定過程中，也必須考慮由特別服務(wù)引發(fā)的預(yù)期耗費(fèi)。一種極端是如果特別服務(wù)能夠以較低的耗費(fèi)成本轉(zhuǎn)包，那么也就不用維持常規(guī)服務(wù)；另一種極端是特別服務(wù)很昂貴，盡管有時(shí)常規(guī)服務(wù)不能被完全利用，但有利于實(shí)現(xiàn)常規(guī)服務(wù)容許下的需求。通過制定常規(guī)服務(wù)時(shí)間表并引入特別服務(wù)，使得總體耗費(fèi)成本的期望值最小，這樣，乘客的隨機(jī)需求就可以通過連續(xù)的概率分布來(lái)描述，而預(yù)期的隨機(jī)特別耗費(fèi)以及乘客出行耗費(fèi)則通過需求實(shí)現(xiàn)過程中的整函數(shù)來(lái)表達(dá)。然而大多數(shù)情況下，必須借助方案模擬來(lái)估計(jì)預(yù)期耗費(fèi)成本，根據(jù)實(shí)際指定的問題選擇適當(dāng)?shù)牟蓸臃椒?。因此，直接在?shí)例模擬的情況下制訂出方案。

假設(shè)方案生成的數(shù)目為n，方案集合定義為，每1個(gè)方案r都有相等的概率，且有，在二階隨機(jī)方案中每1個(gè)下標(biāo)r都代表著1種特殊情形的方案。

令是OD對(duì)d上的隨機(jī)需求，是在方案r中的1個(gè)需求實(shí)現(xiàn)，令A(yù)為特別服務(wù)的單位成本，為方案r下OD對(duì)d上被轉(zhuǎn)包的特別服務(wù)。此外，令為方案r下的乘客變量，確立生成的方案可表示為：

所有的變量均是非負(fù)的。P1是服從二階隨機(jī)方案的類型，為了確定依賴于常規(guī)服務(wù)Y和需求實(shí)現(xiàn)的特別服務(wù)耗費(fèi)，目標(biāo)函數(shù)包含了期望Eˉ(Y)，因此沒有Y也不能被確定先驗(yàn)，這兩種服務(wù)類型的相互作用使公交網(wǎng)絡(luò)的服務(wù)設(shè)計(jì)問題變得更加復(fù)雜。

2.3 隨機(jī)可靠性方案與二階下降法

乘客的不確定需求導(dǎo)致了研究服務(wù)問題的不確定性，為了更加清晰地討論這一不確定性，將乘客需求劃分為2個(gè)部分：一部分是以服務(wù)可靠性規(guī)范為基礎(chǔ)的服務(wù)需求，也即被常規(guī)服務(wù)所肯定的服務(wù)需求；另一部分是超出此規(guī)范的服務(wù)需求，即有特定需求所采取的特別服務(wù)。在這個(gè)問題上服務(wù)可靠性則是作為內(nèi)部變量而存在。定義ρd為服務(wù)可靠性參數(shù)，或者理解為能被常規(guī)服務(wù)所覆蓋的OD對(duì)d上的需求可能性，ρ為ρd的集合表示，令φd為隨機(jī)需求Bˉd的累積分布函數(shù)，則OD對(duì)d上確定能被常規(guī)服務(wù)所覆蓋的需求為，其中在服務(wù)水平Bˉd處常規(guī)服務(wù)被用來(lái)作為優(yōu)化需求，一階段隨機(jī)方案如下：

方案P2是混合整數(shù)線性規(guī)劃，同方案P0的約束條件（1）～（7）確立的條件相同。通過調(diào)整服務(wù)可靠性ρ，更改在Bˉd可覆蓋的需求水平并產(chǎn)生最佳的常規(guī)服務(wù)方案Y。

在第一階段的問題中，設(shè)定固定車行規(guī)模數(shù)目為Nˉ，且有Nˉ≤N，其中出行或者換乘的耗費(fèi)也是固定的?；陔S機(jī)方案的服務(wù)可靠性ρ和P2中確定的最佳的常規(guī)服務(wù)安排Y，針對(duì)每個(gè)需求實(shí)現(xiàn)情況給出第二階段方案：

方案P3中的目標(biāo)函數(shù)包含了特別服務(wù)耗費(fèi)成本、乘客等待時(shí)間耗費(fèi)成本以及乘客出行時(shí)間耗費(fèi)成本。注意到常規(guī)服務(wù)Y或者Yij如上面約束條件所反映的在解決第一階段問題P2時(shí)已經(jīng)被固定并且約束著常規(guī)服務(wù)中的乘客量。所有的超出常規(guī)服務(wù)能力的需求實(shí)現(xiàn)都會(huì)被作為特別服務(wù)，如式（18）所示，P3在形式上類似于P2，是一個(gè)線性規(guī)劃。

特別服務(wù)的期望以及等待時(shí)間的耗費(fèi)都可以由下式給出：

將上述2個(gè)階段結(jié)合可得出如下基于隨機(jī)方案的目標(biāo)函數(shù)式：

對(duì)給定的服務(wù)可靠性ρ，式（19）中前2個(gè)式子是指在P2中提到的常規(guī)服務(wù)耗費(fèi)；Eˉ(ρ)是指特別服務(wù)耗費(fèi)的期望，包括P3解決的乘客等待時(shí)間耗費(fèi)和乘客出行時(shí)間耗費(fèi)。該方案的目標(biāo)是求得最優(yōu)的服務(wù)可靠性指數(shù)ρ，使得式（19）提到的結(jié)合常規(guī)服務(wù)耗費(fèi)、特別服務(wù)耗費(fèi)期望、等待時(shí)間耗費(fèi)和出行時(shí)間耗費(fèi)的總期望值最小。

為求解該函數(shù)，設(shè)計(jì)二階下降方法，通過ρ求得P2并多次反復(fù)求P3直到滿足停止標(biāo)準(zhǔn)。

方案P2和P3通過引入服務(wù)可靠性ρ將常規(guī)服務(wù)Y和特別服務(wù)Z的相互作用分離成二階隨機(jī)方案P1。因此問題的關(guān)鍵是這兩種等價(jià)的構(gòu)想是否能得到等價(jià)的理想方案。首先，研究這兩種方案的可行區(qū)域是否相同；其次，要分析任意基于服務(wù)可靠性的隨機(jī)方案的可行解是否都分布在原始的二階隨機(jī)方案的可行域中，原始的二階隨機(jī)方案的最優(yōu)解是否又會(huì)落在基于服務(wù)可靠性的隨機(jī)方案的可行區(qū)域中，現(xiàn)給出以下命題：

命題1：任意基于服務(wù)可靠性隨機(jī)規(guī)劃方案的可行解對(duì)原始的二階隨機(jī)方案都是可行的。

命題2：對(duì)于概率分布在[0,+∞ )上的隨機(jī)需求問題，任意原始的二階隨機(jī)方案的最優(yōu)解可以被基于服務(wù)可靠性的隨機(jī)方案規(guī)劃生成。

提出的求解過程稱為基于服務(wù)可靠性的下降求解過程，它并不像常規(guī)解法那樣通過減小可行區(qū)域來(lái)找最優(yōu)解，而是通過服務(wù)可靠性ρ來(lái)確定下降方向。一旦常規(guī)服務(wù)Y給定，相應(yīng)的最低成本也即確定。因此首先要找到Y(jié)*，由于Y的離散性質(zhì)，即它的所有元素的影響在同一時(shí)間不可能通過Y直接進(jìn)行線搜索，這也是基于服務(wù)可靠性ρ來(lái)確定目標(biāo)函數(shù)下降方向的原因。對(duì)給定的初值ρ，沿著目標(biāo)函數(shù)下降方向來(lái)尋找最優(yōu)的ρ*。從實(shí)踐的角度來(lái)說(shuō)，ρ的物理意義為常規(guī)服務(wù)攜帶的隨機(jī)需求的可能性，它能更加清楚地幫助初始點(diǎn)ρk解決各類問題。

2.4 ρ的優(yōu)化過程

2.4.1 確定ρ的可行變化范圍

當(dāng)出行的車行規(guī)模上界足夠大（也即和N相對(duì)于需求水平足夠大），ρ的可行域應(yīng)介于[0,1]；當(dāng)出行的車行規(guī)模上界較小，此時(shí)ρ的可行區(qū)域應(yīng)定義為適當(dāng)確保第一階段問題P2的可行性。因此在解決P2問題之前先要計(jì)算出ρ的可行區(qū)域。通過盡可能大地設(shè)置Yij來(lái)獲得最大的總需求使得常規(guī)需求可以覆蓋其相應(yīng)的ρ，也可以求得每個(gè)OD對(duì)和ρd的最大需求，程序步驟描述如下。

（1）通過求解：

來(lái)獲得上界ρ，其受制于方案P2的約束條件。

（2）通過求解：

來(lái)獲得個(gè)別ρd的上界變量，其受制于方案P2的約束條件。

式（20）和式（21）定義了ρ的可行范圍，并將Bˉd定義為決策變量，一旦Bˉd給定，ρ也可以由相應(yīng)的需求累積分布函數(shù)計(jì)算得出。

對(duì)于初始點(diǎn)ρk=(ρdk)，首先通過P2和P3找到總的系統(tǒng)耗費(fèi)，然后通過對(duì)目標(biāo)函數(shù)求偏導(dǎo)來(lái)找ρ的下降方向，這樣能及時(shí)更新ρ以便于更好地進(jìn)行下一次迭代。重復(fù)這一過程直到滿足停止條件，這一過程中每個(gè)變量的下標(biāo)k都代表著迭代次數(shù)。

2.4.2 解決方案示意圖

原始的二階段問題的約束條件離散化后可以由圖3（a）表示，其中包括3個(gè)決策變量：Y（常規(guī)服務(wù)）、X（常規(guī)服務(wù)下的乘客量）、Z（特別服務(wù)下的乘客量）。這3個(gè)變量相互作用與相互制約構(gòu)成了初始的約束條件：將約束條件集分成3個(gè)區(qū)域，左區(qū)僅含Y，包括車行保障和車行規(guī)模約束，也即P1中的式（9）～（12）；中間區(qū)包括Y和X，代表著在常規(guī)服務(wù)下沒有超出車行能力的乘客量，即P1中的式（15）；右區(qū)包括X和Z，意味著乘客的實(shí)際需求包括采用常規(guī)服務(wù)的乘客量X和特別服務(wù)的乘客量Z。對(duì)離散后連續(xù)條件下的隨機(jī)需求，需要考慮各區(qū)域達(dá)到理想狀態(tài)的準(zhǔn)確度，因此，P1會(huì)變得相當(dāng)大導(dǎo)致計(jì)算很難完成，常規(guī)解法通常利用這一問題的特殊結(jié)構(gòu)將其分離成2個(gè)部分：主部分和子部分（見圖3（b）），主部分僅和Y有關(guān)，在每一次迭代中，優(yōu)化子部分會(huì)生成1個(gè)或多個(gè)主部分的約束條件。因此，在每次迭代中隨著計(jì)算的進(jìn)行，主部分的約束條件會(huì)越來(lái)越多，計(jì)算量也會(huì)越來(lái)越大。常規(guī)方法的優(yōu)點(diǎn)是一開始時(shí)的下降速度很快，但越到后期越疲乏。而本文提出的二階下降法也采用類似的原理將原始的問題分解為2個(gè)階段：一階段和二階段（見圖3（c））。一階段問題是混合整數(shù)線性規(guī)劃，而二階段問題是簡(jiǎn)單的線性規(guī)劃，二者相對(duì)于之前的問題都更容易計(jì)算。與常規(guī)解法相比，它們?cè)诿看蔚^程中約束問題的規(guī)模都在逐漸增大，而二階下降法中的一階段問題規(guī)模保持不變，通過不引入額外的約束來(lái)搜索需求方案的服務(wù)可靠性，計(jì)算時(shí)間基本保持一致，這也顯示出了其計(jì)算的優(yōu)勢(shì)，這一點(diǎn)在后續(xù)的數(shù)值仿真中得以證明。另外一個(gè)優(yōu)點(diǎn)是二階下降法可以采用ρ來(lái)作為加速因子用來(lái)加速算法（通常選取已有的或者預(yù)期的服務(wù)可靠性因子），而其他的方法卻不能。

圖3 原始方案及解決方案示意圖

3 算例分析

為了說(shuō)明方法的有效性，引入圖4所示的例子，節(jié)點(diǎn)1,2,3代表在不同時(shí)刻相同的某一公交站點(diǎn)，同樣節(jié)點(diǎn)4和5代表不同時(shí)刻的另外一個(gè)公交站點(diǎn)，變量及相關(guān)定義如圖4所示。

圖4 公交實(shí)例模型

這一問題轉(zhuǎn)化成數(shù)學(xué)模型為：

其中，一階段問題為：

二階段問題為：

在一階段中，利用不同的初始點(diǎn)(ρ1,ρ2)來(lái)比較實(shí)驗(yàn)結(jié)果，取(0,0)到(0.5,0.5)，步長(zhǎng)為0.1。在二階段中，將需求分布離散化來(lái)覆蓋整個(gè)空間OD對(duì)需求。

首先，將2個(gè)均勻分布分割成均等的n份，每個(gè)小的間隔代表著概率為1n的可能性；

然后，列舉出離散需求值集合中的所有可能性組合，生成n2空間，每一個(gè)接合點(diǎn)的可能性為1/n2。例如（）是一個(gè)可能的維系，結(jié)果的精確度取決于離散化的需求分布水平（即n的值）。應(yīng)用最優(yōu)化ρ求解步驟求解該方案，結(jié)果如表1所示。通過改變單位特別服務(wù)耗費(fèi)A可以生成一組不同的常規(guī)服務(wù)方案。結(jié)果顯示，A從10逐漸變到25的過程中，常規(guī)服務(wù)方案中(Y14,Y25)從(0,0)逐漸增加到(1,2)，(0,0)表示放棄定制的常規(guī)服務(wù)而選擇100%依賴特別服務(wù)，(1,2)表示達(dá)到車行規(guī)模最優(yōu)方案。

表1 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果

表1 （續(xù)）

4 數(shù)據(jù)結(jié)果對(duì)比

這一結(jié)果的精準(zhǔn)度依賴于隨機(jī)需求的分布水平，根據(jù)表1，二階下降法得到的總的耗費(fèi)和原始解法得到的結(jié)果非常接近，即使對(duì)于每個(gè)變量A，基于二階下降法可以像原始解法那樣生成相同的常規(guī)服務(wù)安排，但它們之間會(huì)存在微小的差異。結(jié)果表明不同的變量A生成不同的ρ和Y的最優(yōu)值，盡管常規(guī)服務(wù)Y對(duì)基于服務(wù)可靠性的二階下降法和原始解法來(lái)說(shuō)是一致的，但它們可能有不同的服務(wù)可靠性方案，即ρ會(huì)有不同的解或者多解來(lái)生成相同的常規(guī)服務(wù)方案Y。因此，比較二階下降法和原始解法在A=10,A=12,A=15和A=20,A=25時(shí)的最優(yōu)可靠性。在不同的時(shí)間到達(dá)公交站點(diǎn)的OD對(duì)需求在不影響總的常規(guī)服務(wù)耗費(fèi)情況下會(huì)加載等量的公交出行，恰好這些OD對(duì)需求加載方案會(huì)生成不同的常規(guī)服務(wù)。這一結(jié)果表明，有很多種最優(yōu)服務(wù)可靠性組合也會(huì)導(dǎo)致相同的最優(yōu)方案總耗費(fèi)。

5 結(jié)語(yǔ)

本文通過服務(wù)可靠性在隨機(jī)需求條件下建立了一類隨機(jī)公交網(wǎng)絡(luò)服務(wù)設(shè)計(jì)模型，服務(wù)可靠性可以分離出依賴于混合整數(shù)線性規(guī)劃的二階隨機(jī)整數(shù)方案，通過二階下降法規(guī)定不確定的隨機(jī)變量參數(shù)ρ來(lái)求解二階隨機(jī)方案。首先通過在一階段減少混合整數(shù)規(guī)劃中約束條件的數(shù)量，可以節(jié)省大量的計(jì)算時(shí)間，隨后在二階段中模擬出一個(gè)線性規(guī)劃，便可以有效地解決問題。在實(shí)踐層面，該方法可以廣泛應(yīng)用到交通網(wǎng)絡(luò)設(shè)計(jì)中，比如通過制定最優(yōu)化組合的固定航線或者實(shí)行靈活的出行服務(wù)來(lái)使得預(yù)期耗費(fèi)最??；或者在物流方面規(guī)劃出貨車的出行方案以及交互服務(wù)，可以處理一些隨機(jī)的需求溢出。作為基于不確定性的二階隨機(jī)方案，將其擴(kuò)展到大規(guī)模的網(wǎng)絡(luò)仍是一巨大挑戰(zhàn)，如何將用戶均衡原則融合到隨機(jī)方案中將是接下來(lái)研究的重點(diǎn)。

[1]高自友，吳建軍.出行者博弈、網(wǎng)絡(luò)結(jié)構(gòu)與城市交通系統(tǒng)復(fù)雜性[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2010，7（4）：55-64.

[2]鄭嘯，陳建平，邵佳麗，等.基于復(fù)雜網(wǎng)絡(luò)理論的北京公交網(wǎng)絡(luò)拓?fù)湫再|(zhì)分析[J].物理學(xué)報(bào)，2012，61（19）：95-105.

[3]王喆，彭其淵.成都市公交復(fù)雜網(wǎng)絡(luò)拓?fù)涮匦匝芯縖J].交通與計(jì)算機(jī)，2007（2）：39-42.

[4]GAO Z Y,SUN H J,SHAN L L.A Continuous Equilibrium Network Design Model and Algorithm for Transit Systems [J].Transportation Research Part B:Methodological,2004, 38(3):235-250.

[5]SZETO W Y,JIANG Y,WONG K I.Reliability-Based Sto?chastic Transit Assignment with Capacity Constraints:For?mulation and Solution Method[J].Transportation Research Part C:Emerging Technologies,2013(35):286-304.

[6]劉志謙，宋瑞.基于復(fù)雜網(wǎng)絡(luò)理論的廣州軌道交通網(wǎng)絡(luò)可靠性研究[J].交通運(yùn)輸系統(tǒng)工程與信息，2010，10（5）：194-200.

[7]丁小兵.復(fù)雜網(wǎng)絡(luò)理論及其在上海城市軌道交通網(wǎng)絡(luò)可靠性分析評(píng)價(jià)中的應(yīng)用[J].城市軌道交通研究，2012，（11）：50-53.

[8]WANG Z W,LO H K.Multi-Fleet Ferry Service Network Design with Passenger Preferences for Differential Services [J].Transportation Research Part B:Methodological,2008, 42(9):798-822.

[9]BAGLOEE S A,CEDER A.Transit-Network Design Meth?odology for Actual-Size Road Networks[J].Transportation Research Part B:Methodological,2011,45(10):1787-1804.

[10]陸化普，蔚欣欣，卞長(zhǎng)志.OD需求不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型研究[J].公路交通科技，2011，28（5）：128-132.

[11]孫華，高自友，龍建成.不確定OD需求下連續(xù)交通網(wǎng)絡(luò)設(shè)計(jì)的魯棒優(yōu)化模型[J].交通運(yùn)輸系統(tǒng)工程與信息，2011，11（2）：70-76.

[12]范大娟，黃志球，肖芳雄，等.一種需求驅(qū)動(dòng)的服務(wù)行為適配方法[J].四川大學(xué)學(xué)報(bào)：工程科學(xué)版，2014，46（2）：95-104.

[13]徐英俊，程天成.隨機(jī)需求下公交網(wǎng)絡(luò)設(shè)計(jì)的期望值模型與求解算法研究[J].交通標(biāo)準(zhǔn)化，2013（17）：22-25.

Service Reliability of Public Transit Network under Condition of Two-Stage Stochastic Demand

ZHAO Jie1,ZHANG Li2,AN Xin-lei1
(1.School of Mathematics and Physics,Lanzhou Jiaotong University,Lanzhou 730070,China; 2.Department of Basic Courses,Lanzhou Institute of Technology,Lanzhou 730050,China)

The notion of service reliability was introduced.The public transit network model with the stochastic demand was established through taking minimizing the passengers travel cost and bus opera?tion cost as the target.The fixed demand service scheme model and two-stage stochastic scheme model were put forward respectively.The travel choice of passenger for public transit was embodied while the inter relation between stochastic demand and service reliability was reflected by this model.Then the service design of public transit network was analyzed,including the regular service and the particular service.The two-stage stochastic scheme was solved by using two-stage descent method and defining the stochastic parameter of service reliability.The computing time was saved by reducing the number of mixed integer programming during the first stage,and then a linear programming was simulated to solve the two-stage stochastic scheme during the second stage.Finally,the feasibility of this model was veri?fied with instance model.

public transit network;service reliability;two-stage descent method;stochastic scheme;passenger demand

U491.17

：A

：2095-9931（2015）04-0030-08

10.16503/j.cnki.2095-9931.2015.04.005

2015-06-02

國(guó)家自然科學(xué)基金（61364001）；蘭州交通大學(xué)青年科學(xué)研究基金（2014024）；甘肅省自然科學(xué)基金（1310RJZA028）

趙杰（1993—），男，甘肅西和人，碩士研究生，研究方向?yàn)榉蔷€性與復(fù)雜網(wǎng)絡(luò)。E-mail：zhaoj1993@126.com。