定制公交多目標魯棒優化模型與算法

陶 浪，馬昌喜

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

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

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

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

1 問題描述

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

2 模型構建

2.1 模型假設

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

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

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

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

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

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

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

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

2.2 符號定義

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

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

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

Z——所有的節點集合，Z=Zi∪Zj；

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

dij——節點i到節點j的距離；

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

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

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

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

Qk——定制公交車輛的限載人數；

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

tik——k車在i點的等待發車時間；

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 建立模型

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

2.3.1 目標函數

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

同等轉換：

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

乘客的出行時間包括四個方面，分別為服務i節點的第k輛車的等待發車時間、車輛從i節點到j節點的行駛時間、乘客的上、下車時間及在乘客上、下車點的等車時間。

考慮到服務時間窗，在定制公交車輛不在規定的時間窗內到達時，需要對運營公司做出相應的懲罰。懲罰之后目標函數一轉換為：

2.3.2 約束條件

(1)車輛的容量限制

(2)到達時間限制

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

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

(4)車輛服務完某一節點后返回發車中心

3 設計算法

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

3.1 設計算法

3.1.1 編碼與解碼

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

圖1 編碼示意圖

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

3.1.2 遺傳算子的設計

首先，給模型的任意一個初始解i定義兩個參數ni和si，ni表示支配個體i的解的數量，si為個體i支配的解的數量。然后利用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層為空，則停止計算；否則，轉到(2)。

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

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

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

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

①選擇算子

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

②交叉算子

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

③變異算子

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

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

圖2 算法流程圖

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

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

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

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

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

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

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

4 實例研究

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

圖3 蘭州市城關區部分路網圖

上車點出發時間窗上車點人數上車點編號出發時間窗上車點人數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 乘客下車點信息表

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

對公交車的行駛路徑進行優化時，不能同時達到乘客出行時間最小及運營公司利益最大，需要以系統整體最優為優化目標。再對模型進行求解其魯棒解時得出兩組不同的pareto解，在控制車輛服務乘客上、下車點相同的情況下，得到的行駛路線不同。在pareto解1中，車輛1的乘客的出行時間比pareto解2的節約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解的分析可知，系統解的魯棒性逐漸增加，會對解的最優性產生影響，甚至是犧牲解的最優性。縱觀上述例子，采用定制公交出行方式，能夠節約出行時間，降低經營成本，增加公司收益。

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

注:圖中三角形代表乘客下車點；正方形代表乘客上車點；圓圈代表某線路上的節點。粗虛線代表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 結語

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

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

[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]張敏捷，馮 偲，呂晨曦，等.定制公交線路優化模型及求解算法[A].中國智能交通協會.2014第九屆中國智能交通年會大會論文集[C].中國智能交通協會，2014，8.

[7]巫威眺.不確定環境下公交網絡協同調度的魯棒性及控制策略[D].廣州：華南理工大學，2015.

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

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

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

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

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

[13]涂文苑.定制公交的現網規劃研究[D].北京：北京交通大學，2016.

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

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