基于雙層規(guī)劃的公交網(wǎng)絡(luò)潛在運(yùn)輸能力確定

吳 磊，董柯洋 ,周小祥

(1. 重慶交通大學(xué) 交通運(yùn)輸學(xué)院，重慶 400074； 2. 重慶交通大學(xué) 信息化辦公室，重慶 400074； 3. 重慶交通大學(xué) 產(chǎn)學(xué)研合作處，重慶 400074)

0 引 言

公交網(wǎng)絡(luò)的潛在運(yùn)能，又稱為潛在運(yùn)力，是指相對(duì)現(xiàn)狀乘客輸送情況，在公交企業(yè)運(yùn)營成本和出行者利益達(dá)到平衡時(shí)，公交網(wǎng)絡(luò)在單位時(shí)間內(nèi)所能增大的乘客數(shù)[1]。

國外方面，針對(duì)不同的公交網(wǎng)絡(luò)設(shè)計(jì)方案，評(píng)價(jià)其潛在運(yùn)能是一個(gè)十分必要且復(fù)雜的課題。迄今為止，國外在公交網(wǎng)絡(luò)潛在運(yùn)能評(píng)價(jià)問題方面做了大量研究，但目前仍處于探索階段，一些學(xué)者提出了很多有建設(shè)性的模型和算法，O.CATS 等[2]、K.WINTER 等[3]、B.BEVRANI等[4]和Y.HADAS等[5]都從乘客需求和運(yùn)輸服務(wù)供給的平衡角度分析了公交網(wǎng)絡(luò)的潛在運(yùn)能的計(jì)算方法；另外，A. HUANG等[6]、A.MOHAMMAD等[7]也針對(duì)公交網(wǎng)絡(luò)運(yùn)能相關(guān)的使用問題，提出了對(duì)應(yīng)的公交網(wǎng)絡(luò)設(shè)計(jì)和優(yōu)化方案。

國內(nèi)研究方面，由于公交網(wǎng)絡(luò)的基礎(chǔ)建設(shè)還未完善，故對(duì)整個(gè)公交網(wǎng)絡(luò)能力的研究還處于起步階段，涉及到網(wǎng)絡(luò)潛在運(yùn)能的文獻(xiàn)比較少。杜則行健[8]建立了基于換乘樞紐的多模式交通網(wǎng)絡(luò)運(yùn)能協(xié)調(diào)研究方法，但研究只涉及到運(yùn)能協(xié)調(diào)方面，未能研究公交網(wǎng)絡(luò)潛在運(yùn)能；在此基礎(chǔ)上，四兵鋒等[9]分析了城市多方式交通平衡配流問題，并采用雙層規(guī)劃方法構(gòu)造了基于系統(tǒng)最優(yōu)的城市公交專用道網(wǎng)絡(luò)設(shè)計(jì)模型，但也未能研究網(wǎng)絡(luò)潛在運(yùn)能的問題；柳伍生等[10]則將乘客需求最大的兩個(gè)節(jié)點(diǎn)連接起來作為初始線路,采用蟻群算法對(duì)初始線路進(jìn)行迭代改進(jìn)，從而構(gòu)建了最優(yōu)的公交網(wǎng)絡(luò)，但是僅僅針對(duì)總出行時(shí)間最短和運(yùn)營成本最小化展開研究，沒有深入到影響公交網(wǎng)絡(luò)運(yùn)能因素層面上。

上述文獻(xiàn)對(duì)公交網(wǎng)絡(luò)潛在運(yùn)能的研究局限于某一條具體線路、點(diǎn)或某一種具體的公共交通設(shè)備，而公交網(wǎng)絡(luò)能力的充分發(fā)揮需要兼顧運(yùn)營者和出行者之間的利益，筆者根據(jù)公交系統(tǒng)的具體特點(diǎn)，首先對(duì)公交網(wǎng)絡(luò)進(jìn)行描述，進(jìn)而構(gòu)造一個(gè)雙層規(guī)劃模型來描述公交網(wǎng)絡(luò)潛在運(yùn)能的確定問題：在考慮公交出行者隨機(jī)路徑選擇的條件下，實(shí)現(xiàn)路徑流量的擴(kuò)張滿足運(yùn)營者成本最小化，研究的網(wǎng)絡(luò)潛在運(yùn)能體現(xiàn)了出行者和運(yùn)營者之間的利益平衡。

1 符號(hào)定義

2 出行者費(fèi)用及運(yùn)營成本

公交網(wǎng)絡(luò)中，某一條弧的乘客廣義費(fèi)用(用時(shí)間成本體現(xiàn))，可以用弧上的行程時(shí)間ta(xa)、等待時(shí)間wa(xa)及里程票價(jià)費(fèi)用ma來表示：

ca(xa)=ta(xa)+wa(xa)+γma

(1)

式中：ca(xa)為弧a上的廣義費(fèi)用；ta(xa)為弧a上的行程時(shí)間；wa(xa)為弧a上的等待車時(shí)間；γ為時(shí)間價(jià)值轉(zhuǎn)化系數(shù)，min/＄；ma為弧a上的里程票價(jià)費(fèi)用，ma=laΨ，la為弧a的距離，Ψ為單位里程票價(jià)費(fèi)率，＄/km。

弧a上的行程時(shí)間是流量的函數(shù)，可用BPR函數(shù)來表示[11]：

(2)

弧a上的等車時(shí)間可以用式(3)表示[12]：

(3)

式中：E[ha]為弧a上公交車輛的到達(dá)時(shí)間間隔的期望；σa為弧a上公交車輛的到達(dá)時(shí)間間隔的方差。

由于弧a上運(yùn)送一位乘客所需的平均運(yùn)營成本和弧上的擁擠程度相關(guān)，即弧的流量越小，所需的單位乘客運(yùn)營成本就越?。环粗驮酱?，故它可以用式(4)來表示：

(4)

式中：Ba(xa)為弧a上的單位乘客運(yùn)營成本；ba為不擁擠狀態(tài)下弧a上的單位乘客固定運(yùn)營成本，￥/prs；μ、λ為自定義參數(shù)，表示單位乘客運(yùn)營成本和弧上乘客量的關(guān)系。

對(duì)于公交網(wǎng)絡(luò)來說，一般地，單位乘客的運(yùn)營成本與弧上乘客的流量通常情況下不是簡單的正相關(guān)關(guān)系，即單位乘客運(yùn)營成本函數(shù)不應(yīng)該是乘客流量的單調(diào)遞增函數(shù)，而應(yīng)該是個(gè)分段函數(shù)，即當(dāng)服務(wù)成本小于固定成本時(shí)，流量越大單位乘客運(yùn)營成本越低；當(dāng)由于乘客數(shù)量增加導(dǎo)致的服務(wù)成本大于固定成本時(shí)，乘客量越大，運(yùn)營成本就增大。由于筆者目標(biāo)是探討公交網(wǎng)絡(luò)的潛在運(yùn)能，及需要考慮乘客流量很大的情況，服務(wù)成本超過了固定成本，所以直接將單位乘客的運(yùn)營成本視作乘客流量的單調(diào)遞增函數(shù)，也是在乘客量很大的情況下，探討公交網(wǎng)絡(luò)能繼續(xù)承載多大的客流。

3 雙層規(guī)劃模型

公交網(wǎng)絡(luò)設(shè)計(jì)過程中，需要考慮運(yùn)營者和用戶之間的利益權(quán)衡，運(yùn)營者通常希望用最小成本來運(yùn)送最大的客流量，而出行者則希望獲得最優(yōu)出行策略，即每個(gè)出行者都選擇自己認(rèn)為的最小費(fèi)用路徑進(jìn)行出行，雙方?jīng)Q策的結(jié)果最終會(huì)達(dá)到一個(gè)平衡，通常情況下，雙層規(guī)劃模型可以描述這種運(yùn)營者和出行者之間的平衡關(guān)系，上層規(guī)劃使運(yùn)營者能夠花費(fèi)最小的運(yùn)營成本來獲得最大的擴(kuò)張流量；下層則為用戶的隨機(jī)平衡配流模型。

3.1 上層模型

上層模型為運(yùn)營者決策模型，即采用最小的運(yùn)營成本能夠使得OD兩點(diǎn)間的增廣流量最大，為一個(gè)最小費(fèi)用最大流模型：

(5)

(6)

(7)

0≤xa+Δxa≤ka, ?a∈A

(8)

(9)

(10)

(11)

(12)

上層規(guī)劃(ULP)可以采用文獻(xiàn)[13]所描述的構(gòu)造賦權(quán)弧法構(gòu)造有向圖進(jìn)行求解。

3.2 下層模型

下層模型主要反映用戶的最優(yōu)策略，即當(dāng)每個(gè)用戶都認(rèn)為自己選擇的路徑的出行費(fèi)用達(dá)到最小時(shí)，路網(wǎng)達(dá)到平衡狀態(tài)[14]。筆者分析公交運(yùn)輸網(wǎng)絡(luò)的潛在運(yùn)能，因此筆者從更為宏觀的角度來進(jìn)行出行路徑選擇，即利用SUE模型來分配客流。相較動(dòng)態(tài)交通分配模型而言，這一方式也許不能很好的刻畫交通擁堵情況，但SUE模型以網(wǎng)絡(luò)中用戶均衡為目標(biāo)進(jìn)行客流分配而不考慮更為細(xì)節(jié)的運(yùn)行情況，因此適用于筆者從規(guī)劃層面來衡量運(yùn)輸網(wǎng)絡(luò)的潛在運(yùn)力。

由Y.SHEFFI[14]以及C.FISK[15]提出的SUE模型能很好地說明隨機(jī)分配的特性并消除了均一用戶特性假設(shè)的不足，其模型為：

(13)

(14)

(15)

(16)

其中：式(14)為增廣OD需求量守恒約束；式(15)為路徑增廣流量非負(fù)約束；式(16)為弧和路徑流量關(guān)系約束。

下層規(guī)劃(LLP)的求解算法有兩種。兩種算法在計(jì)算時(shí)間和復(fù)雜度上的區(qū)別不大，筆者采用雙層規(guī)劃模型的算法來求解(LLP)，其步驟見文獻(xiàn)[14]。

3.3 雙層規(guī)劃模型的求解算法

基于3.1節(jié)、3.2節(jié)所提出的雙層模型，多方式公交網(wǎng)絡(luò)潛在運(yùn)能的計(jì)算可以通過上、下層模型不斷的求解迭代來完成。

4 算例分析

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

首先采用現(xiàn)狀OD進(jìn)行用戶隨機(jī)平衡分配，得到如圖2的公交網(wǎng)絡(luò)乘客流量圖。

圖2 初次分配得到的網(wǎng)絡(luò)流量Fig. 2 Resulted network flow of the first allocation

圖3 初次分配得到的G*Fig. 3 Resulted G* of the first allocation

圖4 首次迭代得到的增廣鏈流量Fig. 4 Resulted of the first iteration

圖5 二次迭代的結(jié)果Fig. the second iteration

根據(jù)圖5和各個(gè)弧的載運(yùn)能力ka，重新計(jì)算得到3條最小費(fèi)用流增廣鏈上的流量如圖6。

圖6 二次迭代的增廣鏈流量結(jié)果Fig. 6 Resulted of the second iteration

圖7 最終的網(wǎng)絡(luò)流量解Fig. 7 The final solution of network flow

圖8 迭代過程的變化Fig. 8 Variation of during the iteration

從圖8可知算法滿足收斂條件。最終的得到OD量為3 261.50，故OD之間的潛在運(yùn)能Δqrs=3 261.50-2 500.00=761.50 prs/h。

從圖7可知，當(dāng)公交網(wǎng)絡(luò)達(dá)到最小費(fèi)用流與隨機(jī)配流之間的平衡時(shí)，局部弧如O—D(L4)、3—D(L1)的流量超過了弧的容量(載運(yùn)能力)，這說明運(yùn)營者和出行者都會(huì)接受這種擁擠的現(xiàn)象，即局部路段的擁擠不會(huì)影響運(yùn)營者和出行者利益平衡點(diǎn)的出現(xiàn)；相反，消除這些路段的擁擠，使得運(yùn)營者所期望的最大運(yùn)能未能實(shí)現(xiàn)，他們將無法獲得最大運(yùn)營效益。另外地，如果在其它未達(dá)到載運(yùn)能力的弧上進(jìn)行流量擴(kuò)展，即令它們的流量都達(dá)到載運(yùn)能力ka，出行者的每一條路徑都將出現(xiàn)擁擠的狀況，無法體現(xiàn)路徑選擇的利益差別。這種情況表明，圖7中弧上的流量是運(yùn)營者和出行者利益平衡時(shí)的最大流。

5 大算例測試

為驗(yàn)證筆者提出的模型和算法，筆者使用經(jīng)典的Sioux Falls網(wǎng)絡(luò)來進(jìn)行大算例測試。這個(gè)大算例包括522個(gè)OD對(duì)，24個(gè)節(jié)點(diǎn)以及76個(gè)路段。該網(wǎng)絡(luò)的示意如圖9。

圖9 大算例Sioux Falls示意Fig. 9 Schematic diagram of Sioux Falls in case study

線路1：1—3—4—5—6—8—9；線路2：3—12—11—14—15—19—20；線路3：5—9—8—16—17—19；線路4：16—10—11—12—13；線路5：2—6—8—7—18—16—17—19；線路6：22—23—14—11—4；線路7：6—8—7—18—20—21；線路8：10—11—14—23—22—21—24。

這8條公交線路可以對(duì)向開行。除此之外，模型和算法中其他參數(shù)與4節(jié)中取值相同。

表1 路段屬性Table 1 Attributes of road section

表2 OD矩陣Table 2 OD matrix

應(yīng)用筆者所建立的模型及使用的算法，最終得到收斂后的結(jié)果，見表3，見圖10。

表3 部分路段流量Table 3 The flow of part of road section

圖10 大算例中迭代過程的變化Fig. 10 Variation of during the iteration in case study

從圖10中可以看到算法可以收斂，并得到OD量25 102，與案例中類似，可以得到網(wǎng)絡(luò)中潛在運(yùn)能Δqrs=25 102-19 244=5 858 prs/h。

從表3中同樣可以看到部分路段以及出現(xiàn)了流量大于弧容量的情況，即這些路段的擁擠是運(yùn)營者和出行者可以容忍的平衡點(diǎn)，提高這些路段的運(yùn)能雖然可以提升出行者的出行體驗(yàn)，但會(huì)造成公交企業(yè)不能獲得更大的收益。

從本案例可以看到，筆者的研究可以分析計(jì)算出公交網(wǎng)絡(luò)中未被充分利用的運(yùn)力。如前所述，其他相關(guān)研究往往期望通過運(yùn)營管理手段，如調(diào)整時(shí)刻表，使用運(yùn)能更大的車輛等方式加大公交網(wǎng)絡(luò)的服務(wù)能力。但在尚未明確網(wǎng)絡(luò)潛在剩余運(yùn)力的情況下，這些措施有時(shí)是盲目的。如文中案例所示，在一些路段已經(jīng)達(dá)到飽和的情況下，擴(kuò)大這一路段的運(yùn)能是常見的思路，如加密這一路段的公交開行頻次或換用載客量更大的車輛，但這一措施可能導(dǎo)致運(yùn)輸企業(yè)的投資無法獲得期望的收益，而為其他尚未完全飽和的路段擴(kuò)能卻可能在提升路網(wǎng)整體運(yùn)輸能力的同時(shí)保證公交企業(yè)的獲益。

6 結(jié) 語

通過綜合考慮公交運(yùn)營和出行服務(wù)兩個(gè)角度，基于雙層規(guī)劃的公交網(wǎng)絡(luò)尋找運(yùn)營和出行者利益平衡點(diǎn)，并提出了雙層模型的求解方法，研究了公交網(wǎng)絡(luò)潛在能力。然而，公交網(wǎng)絡(luò)潛在運(yùn)能的確定是一個(gè)復(fù)雜的過程，將在后續(xù)的研究中分析網(wǎng)絡(luò)瓶頸點(diǎn)對(duì)公交網(wǎng)絡(luò)潛在運(yùn)能擴(kuò)張的影響、乘客對(duì)網(wǎng)絡(luò)和費(fèi)用感知程度與公交網(wǎng)絡(luò)載運(yùn)能力之間的關(guān)系。另外，公交運(yùn)營不僅只是考慮客運(yùn)量最大化，還需考慮城市發(fā)展規(guī)劃等多方面因素，對(duì)于出行者而言也不僅只是考慮出行成本最低，還會(huì)考慮出行距離、換乘次數(shù)等因素，所提出的公交客流隨機(jī)分配也存在一定局限性，這將會(huì)在后續(xù)的研究中繼續(xù)修正并完善。