陶 浪，馬昌喜

(蘭州交通大學交通運輸學院，甘肅 蘭州 730070)

由于采取公交出行的方式能夠有效減少道路交通資源的浪費，提高人均交通資源占有率，因此，亟需尋找一種能夠被乘客普遍接受的公共交通出行方式。目前，國內(nèi)市場上公交出行方式主要有市場占有率較大的常規(guī)公交和逐漸起步的定制公交。常規(guī)公交存在運行速度低、運行質(zhì)量差、車輛換乘不方便、乘客舒適度低及效率低下等缺點；定制公交安全、快捷、舒適、環(huán)保，能夠有效彌補常規(guī)公交的缺陷。發(fā)展定制公交能夠緩解人均道路資源占有率低與公共道路交通資源不足之間的矛盾。

國外對定制公交的研究較早，始于20世紀70年代，國內(nèi)起步較遲。國內(nèi)外在定制公交的研究上已經(jīng)取得了一些成果。在國外，Ahmed El Fassi等人指出需要不斷地優(yōu)化定制公交路網(wǎng)布局及增加場站容量來適應(yīng)逐漸增加的乘客量，提出一種基于離散仿真時間的方法來達到乘客滿意度高，并且使用車輛數(shù)最小的目的來為決策者提供意見[1]；Alexandre de Lorimier以加拿大蒙特利爾市定制公交為例研究影響車輛使用的決定因素，為路網(wǎng)的擴寬提供指導意見[2]；Rahul Nair建立了平衡網(wǎng)絡(luò)模型探討決定定制公交系統(tǒng)的最優(yōu)配置的因素，運營公司以乘客在距離其最近的上車點上車的前提來確定車輛泊位、車站容量及車輛數(shù)量使利益最大化[3]；Michael Duncan指出雖然定制公交在美國獲得了大力支持，并且節(jié)約了相當一部分的社會資源，但是并沒有達到其極限，通過合理恰當?shù)膬?yōu)化方式還能節(jié)約其他潛在成本，降低運營費用[4]；T Liu和A Ceder研究定制公交在中國的發(fā)展歷史，并分析了在中國發(fā)展定制公交的利與弊[5]。在國內(nèi)，張敏捷等通過分析定制公交的服務(wù)模式構(gòu)建了定制公交的線路規(guī)劃模型，使用蟻群算法求解模型[6]；巫威眺在論文中從“點，線，面”的角度，以一體化干擾的思想，多層次、全方位探討了如何在不確定環(huán)境下提高網(wǎng)絡(luò)協(xié)同調(diào)度的魯棒性[7]；胡列格，安桐等使用K-means聚類分析方法及范圍覆蓋公式確定了定制公交站點的選址和布局[8]；邱豐等針對可變線路式公交的特殊性，設(shè)計了以預(yù)約需求為主的第一階段路徑優(yōu)化模型及以實時需求為服務(wù)目標的第二階段模型的兩階段車輛調(diào)度模型，分別使用模擬退火與啟發(fā)式插入算法進行了求解[9]；林葉倩等考慮公交公司的運營成本和乘客出行費用，從系統(tǒng)成本最優(yōu)的角度出發(fā)，建立了可變線路式公交調(diào)度模型，并使用最近插入法獲得初始解，依托遺傳算法求解模型[10]；梁玉潔從大連交通現(xiàn)狀出發(fā)，考慮天氣因素建立了大連水上公交設(shè)計模型，利用pareto優(yōu)化的啟發(fā)式遺傳算法進行求解[11]；王姣通過對定制公交開行存在的線路中車輛的配置數(shù)目、車輛的?？空军c、車輛到達每一個站點的時間等問題進行分析，建立了對應(yīng)的模型，并利用改進的免疫遺傳算法求解模型[12]；涂文苑對定制公交線網(wǎng)進行了研究[13]；王云鵬引入時間成本因素，對城市通勤班車的路線及站點布設(shè)進行研究[14]。

綜上所述，國內(nèi)對于定制公交的線路設(shè)計、站點布設(shè)等方面已經(jīng)取得了一些成果，不過對于定制公交系統(tǒng)關(guān)于乘客等車時間的不確定性及系統(tǒng)的魯棒性并未展開深入研究。魯棒性是對系統(tǒng)穩(wěn)定性的評判依據(jù)，研究定制公交系統(tǒng)的魯棒性有助于確定隨著乘客等車時間的波動定制公交該如何調(diào)度，能更好地與實際問題聯(lián)系起來，從而為解決實際問題提供科學依據(jù)。

1 問題描述

路網(wǎng)客戶需求量大，超過單輛定制公交車核載人數(shù)時，必須由多輛公交車協(xié)調(diào)完成乘客的接送任務(wù)。因此，問題描述為：路網(wǎng)上有且僅有一個定制公交發(fā)車中心，有多個乘客上下車點，所有公交均由發(fā)車中心出發(fā)，每輛公交可服務(wù)多個乘客上下車點，每個上下車點僅需一輛公交車服務(wù)，每輛公交車服務(wù)完所負責的乘客上下車點后返回發(fā)車中心。

2 模型構(gòu)建

2.1 模型假設(shè)

(1)定制公交車輛的核載人數(shù)給定；

(2)路網(wǎng)上需要搭載定制公交的人數(shù)足夠多；

(3)每個乘客上下車點的人數(shù)已知；

(4)發(fā)車中心與各個乘客上車點之間，各乘客上、下車點之間的行駛時間；

(5)任意上車點的人數(shù)不超過定制公交核載人數(shù)；

(6)車輛在線路上的行駛時間設(shè)為確定值；

(7)各交通節(jié)點乘客等車時間設(shè)為不確定值并利用合適的區(qū)間值來表示；

(8)乘客出行的單位時間成本確定。

2.2 符號定義

建立模型時運用的符號如下定義：

Zi—— 定制公交的配送中心，Zi={i|i=0}；

Zj——乘客的上、下車點，Zj={j|j=1，2，…n}；

Z——所有的節(jié)點集合，Z=Zi∪Zj；

V——定制公交的車輛集合，V={K|k=1，2，…k}；

dij——節(jié)點i到節(jié)點j的距離；

p1——定制公交載客時的運輸費用系數(shù)；

p2——定制公交空載時的運輸費用系數(shù)；

P——車輛的固定使用費用；

M——被派送出發(fā)的定制公交的數(shù)量，配送中心的車輛足夠多；

Qk——定制公交車輛的限載人數(shù)；

tjk——在乘客上、下車點j的等車時間標稱值，該點由第k輛車服務(wù)；

tik——k車在i點的等待發(fā)車時間；

tp——每位乘客的平均上車時間；

δjk——乘客上、下車點的乘客等車時間相對于標稱等車時間的偏差值，并且此點由k車服務(wù)，δjk≥0；

Jk——第k行中所有受可變等車時間tjk的列下標j構(gòu)成的集合；

Sk——第k行中受可變等車時間的影響而發(fā)生改變的等車時間的列下標j構(gòu)成的集合；

Γk——魯棒控制參數(shù)，控制解的保守程度，Γk∈[0，|Jk|]；

v——定制公交車輛的行駛速度；

Tj——定制公交車輛到達乘客上、下車點的時刻，Tj=Ti+Hi+Tij；

Hi——乘客需求點i的服務(wù)時間，包括乘客等車時間和乘客上、下車時間；

PE——當定制公交車輛早于最早時間到達乘客上、下車點的單位時間的懲罰值；

PL——當定制公交車輛晚于最遲時間到達乘客上、下車點的單位時間的懲罰值；

[ETi，LTi]——乘客上、下車點所要求的車輛到達時間窗；

pijk——車輛k從節(jié)點i到節(jié)點j時，節(jié)點i的上、下車人數(shù)，k∈V，pijk≥0；

w——運營公司的總收入。

2.3 建立模型

考慮運營公司和乘客兩個群體的基本訴求。運營公司追求其利益最大化，也就是說在運營過程中要使投入的資源最少，產(chǎn)生的效益最大；乘客是定制公交的服務(wù)對象，在考慮選擇以定制公交作為其出行方式并且能夠接受相應(yīng)的出行費用的前提下，乘客追求其出行時間盡可能的少?；诖?，本文在乘客等車時間不確定的前提下，以最小化乘客的出行時間，最小化運營公司的經(jīng)營費用為目標，考慮乘客上、下車點的服務(wù)時間窗、車輛的容量限制等約束條件，對不確定時間定制公交路徑優(yōu)化系統(tǒng)的魯棒性進行分析，建立了定制公交路徑優(yōu)化的魯棒模型。

2.3.1 目標函數(shù)

(1)最大化運營公司的總收入

同等轉(zhuǎn)換：

(2)最小化乘客的出行時間

乘客的出行時間包括四個方面，分別為服務(wù)i節(jié)點的第k輛車的等待發(fā)車時間、車輛從i節(jié)點到j(luò)節(jié)點的行駛時間、乘客的上、下車時間及在乘客上、下車點的等車時間。

考慮到服務(wù)時間窗，在定制公交車輛不在規(guī)定的時間窗內(nèi)到達時，需要對運營公司做出相應(yīng)的懲罰。懲罰之后目標函數(shù)一轉(zhuǎn)換為：

2.3.2 約束條件

(1)車輛的容量限制

(2)到達時間限制

定制公交須在乘客上下車點的服務(wù)時間窗內(nèi)到達，若早到或晚到，則在目標函數(shù)中加入懲罰函數(shù)。

(3)一個乘客上、下車點由一輛車服務(wù)

(4)車輛服務(wù)完某一節(jié)點后返回發(fā)車中心

3 設(shè)計算法

考慮時間不確定的定制公交魯棒優(yōu)化模型為多目標模型，傳統(tǒng)的單目標遺傳算法不足以解決此問題，應(yīng)采用更先進的遺傳算法。NSGA-Ⅱ算法是在NSGA算法的基礎(chǔ)上，通過嵌入快速非支配排序算法、精英保留策略及擁擠距離計算等技術(shù)，逐漸成為解決np-hard的多目標問題的一種常用算法。由于本文所建立模型擁有最小化乘客出行時間與最小化經(jīng)營成本兩個目標，屬于多目標，所以采用NSGA-Ⅱ算法。在NSGA-Ⅱ算法的基礎(chǔ)上通過改進編碼方式，使之更符合考慮時間不確定的定制公交魯棒優(yōu)化模型的求解。

3.1 設(shè)計算法

3.1.1 編碼與解碼

編碼方式采取自然數(shù)編碼[15]。首先，對有需求的網(wǎng)絡(luò)節(jié)點隨機進行自然數(shù)編號并按照由大到小的方式排序，放在集合Z中，Z={1，2，3，…，z}，z表示第z個乘客上、下車點。乘客上、下車點的服務(wù)順序為T=(t1t2t3…tz}。設(shè)置集合M和集合N，分別表示已經(jīng)訪問的乘客上、下車點與未方位的交通節(jié)點，初始化M和N，M={?}，N={t1，t2，t3，…，tz}。接著按服務(wù)順序訪問T的各個節(jié)點，并在N中確定該節(jié)點在未訪問節(jié)點中的順序，并寫進集合O中，同時在N中刪除該節(jié)點，在M中加入該節(jié)點。對T的各個節(jié)點訪問完畢之后，集合O中存放的就是T對應(yīng)的基因型。假設(shè)網(wǎng)絡(luò)中有9個節(jié)點，服務(wù)順序T=(4 3 7 5 2 8 1 9 6)，其編碼方式如圖1所示。

圖1 編碼示意圖

由上述編碼圖可知，服務(wù)順序為T=(4 3 7 5 2 8 1 9 6)的基因型O=(435323212)。解碼的過程與編碼相反，反編碼過程進行就能得到基因型O=(4 3 5 3 2 3 2 1 2)的解的個體，其服務(wù)順序為T=(4 3 7 5 2 8 1 9 6)。不同的乘客上、下車點服務(wù)順序，會導致乘客總體出行時間與經(jīng)營公司的運營成本不一樣，遍歷所有不同的服務(wù)順序，找到使得系統(tǒng)最優(yōu)的pareto解。

3.1.2 遺傳算子的設(shè)計

首先，給模型的任意一個初始解i定義兩個參數(shù)ni和si，ni表示支配個體i的解的數(shù)量，si為個體i支配的解的數(shù)量。然后利用ni和si對個體進行非支配前沿排序，具體方法如下：

(1)在所有的解中找到ni=0的解，并將它放在第一非支配前沿F1。

(2)因為第Fk-1層非支配前沿所有的解的ni=0，在第k-1層中逐個訪問si集合每個個體j，并計算個體j的nj和sj，將所有nj=0的個體放在第Fk層非支配前沿。

(3)令k=k+1，如果第Fk+1層為空，則停止計算；否則，轉(zhuǎn)到(2)。

群體中某個個體的擁擠距離是指將具有相同非支配前沿的個體，依據(jù)其不同的目標函數(shù)值，對個體進行排序，并累加與其相鄰的兩個個體的平均距離值。令i∈I，I代表與i處于同一非支配前沿的解的集合。具體操作如下：

(1)對于每個不同的非支配前沿的個體，初始化其擁擠距離為零，即?i∈I，I[i]d=0。

(2)計算每個個體的第m個目標函數(shù)值并按照第m個目標函數(shù)值對不同非支配前沿的個體按照從小到大的順序進行排序。

(3)對于任意的一非支配前沿，對其不同的目標值進行排序之后，處于兩個臨界邊緣的值規(guī)定為無窮大。n為處于相同非支配前沿的個體數(shù)目。I1d=Ind=。

①選擇算子

依據(jù)上述介紹的非支配前沿的確定方法以及擁擠距離的計算流程，可以肯定群體中每個個體擁有兩個參數(shù)，分別為非支配前沿Fk及擁擠距離id。依據(jù)Fk和id對個體進行選擇。在群體中隨機選擇兩個個體i和j，如果Fi≤Fj且id>jd，那么個體i優(yōu)于個體j，記作i>j；否則j>i。重復上述步驟選擇過程，直到選出popsize個個體。

②交叉算子

本文采用了自然數(shù)編碼方式，而采用單點交叉的方式產(chǎn)生一條新的服務(wù)順序，不會產(chǎn)生新的不可行解，且單點交叉簡單，容易操作，故而在本文中采用單點交叉就能滿足求解需要。

③變異算子

為保證變異之后不產(chǎn)生不可行解，變異后的編碼方式對應(yīng)著一條可實際操作的服務(wù)順序，在本文中采取均勻變異算子。假設(shè)變異的概率為Pm，某個體的基因型為O=(1 2 3…m)，其中某基因i(1≤i≤m)發(fā)生變異，變異后i的等位基因只能從Oi=(1，2，3，…m-i+1)中選取。

3.2 NSGA-Ⅱ算法步驟與流程圖

圖2 算法流程圖

針對于不同的具體問題，應(yīng)該制定出不同的算法步驟與流程(見圖2)。以下為關(guān)于定制公交魯棒優(yōu)化模型的NSGA-Ⅱ算法步驟。

step1：隨機生成大小為popsize的種群Rt，t=0；

step2：利用快速非支配排序法進行排序，并給每個個體指定與非支配前沿相匹配的適應(yīng)值大小，計算個體的擁擠距離；

step3：通過變異，選擇，重組等操作，產(chǎn)生子代種群Qt，t=0；

step4：合并父代與子代種群，令Rt=Rt∪Qt，并依據(jù)非支配前沿與擁擠距離進行排序；

step5：對Rt進行精英選擇策略產(chǎn)生新的父代種群Rt+1，重新計算Rt+1種群的擁擠距離；

step6：重復上述操作，若未達到迭代終止條件，則繼續(xù)；否則，輸出模型的最優(yōu)pareto解。

4 實例研究

本文選取蘭州市城關(guān)區(qū)某區(qū)域路網(wǎng)進行實例研究。定制公交空載時費用15 元/km，載客時費用35 元/km，固定使用費用200元，懲罰費用均為20 元/h；車輛行駛速度v=20 km/h。在總計49個節(jié)點的路網(wǎng)中選取20個節(jié)點，其中12個作為乘客上車點，其他作為乘客下車點。上車點、下車點的編號以及每個需求點的乘客數(shù)量如表1、表2所示。每兩點之間的距離表示在路網(wǎng)圖上(見圖3)。

圖3 蘭州市城關(guān)區(qū)部分路網(wǎng)圖

上車點出發(fā)時間窗上車點人數(shù)上車點編號出發(fā)時間窗上車點人數(shù)27:00-7:3013177:00-7:30947:10-7:408257:20-7:401276:40-7:107317:00-7:206106:50-7:2011347:00-7:3012137:00-7:3016426:30-7:008197:10-7:356477:00-7:3010

表2 乘客下車點信息表

運用本文所介紹的算法進行求解，通過分析，設(shè)計合適的遺傳算子來求解定制公交多目標魯棒優(yōu)化模型。遺傳算法相關(guān)參數(shù)設(shè)置如下：popsize=50，pc=0.4，pm=0.1，MAXGen=200，定制公交限載人數(shù)Qk=40，通過出行人數(shù)，可以確定總共需要3輛公交車才能滿足路網(wǎng)中乘客的需求。以visual studio 2013為實驗平臺，多次運行程序，求得定制公交以乘客時間最小以及運營公司盈利最大為目標時的行駛路徑。見圖4和下頁表3。

對公交車的行駛路徑進行優(yōu)化時，不能同時達到乘客出行時間最小及運營公司利益最大，需要以系統(tǒng)整體最優(yōu)為優(yōu)化目標。再對模型進行求解其魯棒解時得出兩組不同的pareto解，在控制車輛服務(wù)乘客上、下車點相同的情況下，得到的行駛路線不同。在pareto解1中，車輛1的乘客的出行時間比pareto解2的節(jié)約5.6%，車輛1運營公司總費用比pareto解2高9.9元；車輛2的乘客的出行時間比pareto解2的高6.5%，車輛2運營公司總費用比pareto解2低5.2元；車輛3的乘客的出行時間比pareto解2的高9.7%，車輛3運營公司總費用比pareto解2高10元。通過對pareto解的分析可知，系統(tǒng)解的魯棒性逐漸增加，會對解的最優(yōu)性產(chǎn)生影響，甚至是犧牲解的最優(yōu)性?？v觀上述例子，采用定制公交出行方式，能夠節(jié)約出行時間，降低經(jīng)營成本，增加公司收益。

圖4 定制公交的運行路線圖

注:圖中三角形代表乘客下車點；正方形代表乘客上車點；圓圈代表某線路上的節(jié)點。粗虛線代表pareto解1、3中車輛1的行駛路線；細虛線代表pareto解2中車輛1的行駛路線，部分與1、3重疊；粗點畫線代表pareto解1中車輛2的行駛路線；細點畫線代表pareto解2、3中車輛2的行駛路線，部分與2、3重疊；粗實線代表pareto解1中車輛3的行駛路徑；中實線代表pareto解2中車輛3的行駛路徑；細實線代表pareto解3中車輛3的行駛路徑

表3 模型的pareto解集表

5 結(jié)語

(1)本文綜合考慮車輛的容量限制、乘客的上下車時間窗、乘客的等車時間不確定、一個交通需求點僅且只由一輛車服務(wù)、車輛服務(wù)完一條線路返回發(fā)車中心等因素，以最小化運營公司的經(jīng)營費用、最小化乘客的出行時間為優(yōu)化目標，建立了定制公交多目標魯棒優(yōu)化模型，并設(shè)計了解決定制公交多目標魯棒模型的多目標遺傳算法，通過遺傳算法獲得模型的pareto解。得出考慮乘客在上車點等車時間的不確定性的情況下，合理規(guī)劃定制公交的出行路線能夠節(jié)約乘客的出行時間，并且能夠為運營公司帶來效益。

(2)本文將定制公交在路網(wǎng)中的行駛速度假定為一固定值，未考慮路網(wǎng)中交通阻抗的變化對定制公交車輛運行速度的影響，對于仿真的結(jié)果存在一定影響。下一步將會對非固定行駛速度下定制公交系統(tǒng)的魯棒性進行研究。

[1]Ahmed El Fassi，Anjali Awasthi，Marco Viviani.Evalua-tion of carsharing network’s growth strategies through discrete event simulation[J].Expert Systems With Applications，2012，39(8)：6692-6705.

[2]Alexandre de，Lorimier Ahmed，M El-Geneidy.Understanding the Factors Affecting Vehicle Usage and Availability in Carsharing Networks：A Case Study of Communauto Carsharing System from Montréal，Canada[J].International Journal of Sustainable Transportation，2013，7(1)：35-51.

[3]R Nair，E Miller-Hooks.Equilibrium network design of shared-vehicle systems[J].European Journal of Operational Research，2014，235(1)：47-61.

[4]M Duncan.The cost saving potential of carsharing in a US context[J].Transportation，2011，38(2)：363-382.

[5]T Liu，A Ceder.Analysis of a new public-transport-service concept：Customized bus in China[J].Transport Policy，2015，39(1)：63-76.

[6]張敏捷，馮 偲，呂晨曦，等.定制公交線路優(yōu)化模型及求解算法[A].中國智能交通協(xié)會.2014第九屆中國智能交通年會大會論文集[C].中國智能交通協(xié)會，2014，8.

[7]巫威眺.不確定環(huán)境下公交網(wǎng)絡(luò)協(xié)同調(diào)度的魯棒性及控制策略[D].廣州：華南理工大學，2015.

[8]胡列格，安 桐，王 佳，等.城市定制公交合乘站點的布局研究[J].徐州工程學院學報(自然科學版)，2016(1)：27-32.

[9]邱 豐，李文權(quán)，沈金星.可變線路式公交的兩階段車輛調(diào)度模型[J].東南大學學報(自然科學版)，2014(5)：1078-1084.

[10]林葉倩，李文權(quán)，邱 豐，等.可變線路式公交車輛調(diào)度優(yōu)化模型[J].交通信息與安全，2012(5)：14-18+33.

[11]梁玉潔.大連水上公交線路的設(shè)計與魯棒優(yōu)化[D].大連：大連海事大學，2014.

[12]王 姣.定制公交行車站點規(guī)劃與時刻表編制研究[D].北京：北京交通大學，2016.

[13]涂文苑.定制公交的現(xiàn)網(wǎng)規(guī)劃研究[D].北京：北京交通大學，2016.

[14]王云鵬.企業(yè)通勤班車線路優(yōu)化研究[D].大連：大連海事大學，2013.

[15]關(guān)志華.非支配排序遺傳算法(NSGA)算子分析[J].管理工程學報，2004(1)：56-60.