單線純電動公交車輛柔性調(diào)度優(yōu)化

唐春艷，楊凱強，鄔 娜

(1.大連海事大學(xué)交通運輸工程學(xué)院，遼寧大連116026；2.長安大學(xué)運輸工程學(xué)院，西安710064)

0 引 言

純電動公交車與燃油公交車動力系統(tǒng)不同，故在運行參數(shù)等方面相差較大.燃油公交車的續(xù)駛里程一般能滿足1 d的運營需求，而純電動公交車受電池容量影響續(xù)駛里程短，且充電時間較長.因此，燃油公交車的運營調(diào)度模式不適用于純電動公交車.

純電動公交車輛調(diào)度主要研究成果有：楊揚等[1]將班次任務(wù)、公交場站和充電站作為節(jié)點，班次間的空駛作為邊，把電動公交車的調(diào)度問題轉(zhuǎn)化為網(wǎng)絡(luò)模型；Li 等[2]對電動公交車的3 種充電方式進(jìn)行定性分析，探討不同動力能源下公交車運營成本，分析電動公交車充電對電網(wǎng)的潛在影響；Li等[3]提出新額外成本效益方法，解決多能源動力混合公交車輛調(diào)度問題；Wen等[4]研究不同電量狀態(tài)的純電動公交車調(diào)度，采用自適應(yīng)大鄰域搜索啟發(fā)式算法(ALNS)進(jìn)行求解；Tang 等[5]考慮公交車輛運行受城市道路交通狀況影響，提出純電動公交車輛魯棒性調(diào)度模型；Hall 等[6]研究整充、換電池、快充等不同充電方式下，純電動公交車輛調(diào)度模型；Niekerk 等[7]提出電池衰退下的純電動公交車輛調(diào)度模型.現(xiàn)有研究成果側(cè)重純電動公交車嚴(yán)格執(zhí)行時刻表準(zhǔn)點發(fā)車，即剛性調(diào)度，這可能因純電動公交車充電時間長錯過最佳接續(xù)發(fā)車班次，使調(diào)度所需要車輛數(shù)增加，進(jìn)而增加公交運營成本.

國內(nèi)外在燃油公交車柔性調(diào)度方面有一定研究，但主要關(guān)注公交線路動態(tài)調(diào)整、實時需求方面的柔性調(diào)度，較少涉及允許存在誤時發(fā)車的柔性調(diào)度.劉昱崗等[8]提出基于實時需求的夜間公交柔性調(diào)度，通過采集夜間公交出行需求，考慮夜間公交服務(wù)水平和運營成本建立多目標(biāo)優(yōu)化模型；張飛舟等[9]提出公交車輛動態(tài)調(diào)度策略與在線調(diào)整方法，研究運營車輛出現(xiàn)意外事故、故障及延誤等情況時應(yīng)急調(diào)度措施和方案；Ceder[10]研究基于逆差函數(shù)方法的柔性車輛調(diào)度，以減少車輛使用數(shù)量；Nourbakhsh等[11]對低需求地區(qū)的運輸系統(tǒng)進(jìn)行研究，以系統(tǒng)成本最小建立模型，并提出柔性路徑的選擇方法.

綜上，本文研究允許存在誤時發(fā)車的純電動公交車柔性調(diào)度，即允許車輛誤時發(fā)車情況下，盡可能調(diào)度公交車接續(xù)最近發(fā)車班次.在分析發(fā)車延誤帶來公交運營外部成本的基礎(chǔ)上，如乘客放棄乘坐此線路的公交，公交公司聲譽受損等成本，構(gòu)建車輛誤時成本函數(shù)；考慮更換電池方式補充電能，構(gòu)建單線純電動公交的車輛柔性調(diào)度優(yōu)化模型，并設(shè)計遺傳算法求解.

1 模型構(gòu)建

1.1 問題描述及基本假設(shè)

研究單一公交線路的純電動公交車調(diào)度問題，線路雙向運營.車輛運營成本主要包括車輛使用成本、空駛成本和充電成本.因允許誤時發(fā)車，在運營成本中需考慮誤時帶來的外部成本，即因發(fā)車延誤造成公交公司負(fù)面影響的成本.

模型基本假設(shè)如下：①純電動公交車采用更換電池方式充電，②發(fā)站均有充電設(shè)施和車庫，③每輛車均從車庫駛出，執(zhí)行完全天班次任務(wù)后返回車庫，即中途不返回車庫，④不考慮道路擁堵等情況.

1.2 符號設(shè)定

p——車庫序號，p∈{1,2}；

h——純電動公交車輛編號，h∈H，H為車輛集合；

R——時刻表中的班次集合；

|R|——R中元素個數(shù)；

|H|——H中元素個數(shù)，0 ≤ |H|≤ |R|；

i,j——班次序號，i,j=0 表示純電動公交車駛?cè)胲噹旎蝰偝鲕噹欤?/p>

L——線路長度(km)；

D——純電動公交車在一次充滿電且保留安全應(yīng)急電量情況下，正常載客所能行駛的最大距離(km)；

C1——一輛純電動公交車1 d 使用成本(元/d)，即一輛車購置成本與使用期內(nèi)的維修成本均攤到每天的固定成本值；

C2——純電動公交車每千米空駛成本(元/km)；

C3——純電動公交車更換一次電池成本(元/次)，包括電池充電費用與操作費用；

T——純電動公交車從開始使用到退役的服務(wù)時間(d)；

Ta——載客行駛完一趟班次所需時間(min)；Tb——始發(fā)站發(fā)車準(zhǔn)備時間(min)；

Tc——公交車更換電池所需時間(min)；

Bi——班次i的發(fā)車時間(min)；

si——班次i的發(fā)車站點；

ei——班次i的到達(dá)站點；

Lei,sj——班次i到達(dá)點和班次j發(fā)車點之間的行駛里程，若為同一站點Lei,sj=0 ，否則為空駛，Lei,sj=αL，其中，α為同等耗電量下空駛距離與正常載客行駛距離的折算系數(shù)，0<α<1；

Tei,sj——班次i到達(dá)點和班次j發(fā)車點之間的行駛時間，若為同一站點Tei,sj=0 ，否則為空駛，Tei,sj=βTt，其中，β為同等運行里程下空駛時間與正常載客行駛時間的折算系數(shù)，0<β<1；

σ——允許誤時發(fā)車的最大延誤時間(min)，將班次延誤發(fā)車時間限制在合理范圍內(nèi)；

——從車庫p出發(fā)的車輛h在執(zhí)行完班次i時，累計行駛里程數(shù)，與決策變量有關(guān)；

——從車庫p出發(fā)的車輛h在執(zhí)行完班次i時剩余電量所能行駛里程數(shù)，與變量有關(guān)；

——從車庫p出發(fā)的車輛h在執(zhí)行完班次i時，需要更換電池，否則為0，與變量有關(guān)；

1.3 模型目標(biāo)函數(shù)

以公交車輛總運營成本最小為目標(biāo)函數(shù)，即每天總運營成本(由車輛使用成本Z1，總空駛成本Z2，總換電成本Z3和總誤時成本Z4組成)乘以純電動公交車使用年限T.

(1)車輛使用成本.

車輛使用成本為每天使用車輛數(shù)與車輛使用成本之積.

(2)空駛成本.

空駛成本是1 d 車輛總空駛里程與空駛單位距離成本的乘積.

(3)換電成本.

換電成本是1 d 換電總次數(shù)與純電動公交車更換一次電池成本的乘積.

(4)誤時成本.

發(fā)車誤時對公交運營企業(yè)造成負(fù)面影響，包括乘客放棄乘坐此線路公交，公交企業(yè)聲譽受損等，將負(fù)面影響量化，構(gòu)建誤時成本函數(shù).延誤時間tj為公交車執(zhí)行j班次實際發(fā)車時間與時刻表中規(guī)定發(fā)車時間之差，班次j的誤時時間tj為

tj≤0 時，不存在誤時，C(tj)=0；tj＞0 時，誤時成本C(tj) 隨延誤時間變化與已有誤時成本成正比，設(shè)比例為k，即

求解式(6)可得

誤時成本C(tj)為

隨tj增大，誤時成本呈指數(shù)增加.表明，k值越大，公交公司越看重誤時發(fā)車帶來的負(fù)面影響.

純電動公交車運營1 d的總誤時成本為

1.4 約束條件

式(10)和式(11)表示每個班次有且僅被一輛公交車執(zhí)行一次；式(12)表示每輛公交車最多從車庫駛出一次；式(13)表示從車場出發(fā)公交車的班次鏈；式(14)～式(16)分別表示公交車h在執(zhí)行完某班次時，累計行駛里程數(shù)，剩余電量所能行駛里程數(shù)，是否需要更換電池；式(17)表示同一輛公交車執(zhí)行班次i后執(zhí)行班次j時，其延誤時間不高于允許的最大延誤時間σ(σ=0 時，不存在延誤發(fā)車，為剛性調(diào)度模型；σ＞0 時，允許誤時發(fā)車，為柔性調(diào)度模型)；式(18)表示是取值約束.

2 求解算法

純電動公交車柔性調(diào)度為NP-hard問題，采用遺傳算法求解，根據(jù)模型特征設(shè)計算法求解初始種群、適應(yīng)度函數(shù)、交叉和變異操作.

2.1 染色體

染色體編碼需包含純電動公交車的3 部分信息：①執(zhí)行哪些班次，②執(zhí)行班次的先后順序，③所屬發(fā)車站.為滿足上述信息，需構(gòu)造3條染色體.實際上，公交車先執(zhí)行班次的時間必定早于后執(zhí)行班次，故將班次按發(fā)車時間先后順序從小到大排列，使用重新排序的時刻表后，僅需構(gòu)造2 條染色體包含①③信息即可，極大地縮小了解空間.如圖1所示：染色體1為純電動公交車對應(yīng)班次基因段，班次1由編號9#的公交車執(zhí)行，班次114由編號6#的公交車執(zhí)行；染色體2為公交車所屬發(fā)車站基因段，編號1#的公交車屬于1發(fā)車站，編號22#的公交車屬于2發(fā)車站.

2.2 適值函數(shù)

染色體適值函數(shù)定義為

式中：Cmax是一個較大正數(shù)，保證適應(yīng)度值非負(fù).適應(yīng)度值越大，其保留下來的概率越高.

圖1 染色體表達(dá)方式Fig.1 Chromosome expression

2.3 交叉與變異

選擇兩點交叉，隨機設(shè)置兩個交叉點對父代染色體進(jìn)行兩兩配對，然后對部分基因進(jìn)行交換得到新染色體，如圖2所示.選擇換位變異，隨機生成兩個基因索引值，然后交換兩個索引值位置上的基因，如圖3所示.

3 實例分析

以上海市金山區(qū)莘金專線進(jìn)行數(shù)值分析，如圖4 所示，線路為雙向運行，上行線路自金山汽車站起，至莘莊地鐵南廣場站；反之為下行線路.

3.1 基本數(shù)據(jù)

莘金專線基礎(chǔ)數(shù)據(jù)來自中國公交信息網(wǎng)(http://www.bus-info.cn/)與8684 公交查詢網(wǎng)(https://www.8684.cn/).上行線路始發(fā)時間為04:35，06:05-06:55 發(fā)車間隔為10 min，最后一班車18:30 發(fā)車，與上一班車間隔20 min，其他時段發(fā)車間隔均為15 min；下行線路始發(fā)時間為06:00，06:00-07:00發(fā)車間隔為20 min，08:45-09:15 發(fā)車間隔為10 min，最后一班車20:00 發(fā)車，其他時段發(fā)車間隔為15 min.對上行線路始發(fā)時間從早至晚依次進(jìn)行編號，如上行路線04:35 編號為1，04:50 編號為2，18:30編號為57；下行線路始發(fā)時間編號接續(xù)上行線路編號，并從早至晚進(jìn)行編號，06:00 編號為58，20:00 編號為114，共114 趟班次.L=52.4 km，Ta=80 min.T=1 825 d，即5年，每輛純電動公交車購置成本為100萬元(車輛售價160萬元，政府每輛車補貼60萬元)，平均每輛車使用期內(nèi)的維修成本為20 萬元，則C1=657.53 元/d.α=0.80，β=0.80，k=1.20，Tc=5 min，Tb=5 min，σ=5 min，公交車充電電價為0.82 元/(°)，平均耗電率1 (°)/km，則C2=0.66 元/km ；D=220 km ，更換電池的操作費用取10元/次，則C3=180 元[12-13].

圖2 交 叉Fig.2 Cross

圖3 變 異Fig.3 Variation

圖4 莘金專線Fig.4 Shenjin bus line

3.2 結(jié)果分析

使用Python 語言編程，選用處理器Inter(R)Core(TM)i5-4200U，內(nèi)存為4 G 的計算機.遺傳算法種群規(guī)模為200，交叉概率0.70，變異概率0.02，算法終止條件為最優(yōu)個體的適應(yīng)度和群體適應(yīng)度不再變化.計算得到不同車輛數(shù)的總成本值，車輛數(shù)為24時總成本最小，收斂圖如圖5所示，計算結(jié)果如表1 所示，最小總成本為3 653.99 萬元，1 d 運行中產(chǎn)生25 次空駛，更換電池16 次，延誤時間16 min.

圖5 收斂圖Fig.5 Convergence graph

表1 柔性調(diào)度結(jié)果Table 1 Flexible scheduling results

表2給出24輛車的執(zhí)行班次鏈及每輛車所屬發(fā)車站，其中，1 代表金山汽車站車庫，2 代表莘莊地鐵南廣場站車庫.如編號11的車輛從1始發(fā)，依次執(zhí)行班次15、25 與85 后進(jìn)行更換電池操作，再依次執(zhí)行班次43、99與112，返回2.

3.3 柔性調(diào)度與剛性調(diào)度對比

式(17)的誤時上限σ=0 時，模型為剛性調(diào)度模型.求得剛性調(diào)度車輛數(shù)為27輛時總成本最小，計算結(jié)果如表3 所示，總成本為3 983.69 萬元，在1 d運行中產(chǎn)生29次空駛，更換電池17次.與剛性調(diào)度相比，柔性調(diào)度節(jié)約用車3 veh，總成本減少329.70萬元，可見柔性調(diào)度優(yōu)于剛性調(diào)度.

表2 柔性調(diào)度班次鏈Table 2 Flexible scheduling trip chain

表3 剛性調(diào)度結(jié)果Table 3 Inflexible scheduling results

3.4 靈敏度分析

對σ進(jìn)行靈敏度分析，不同σ值對應(yīng)的車輛使用數(shù)量及總誤時如圖6 所示. 計算發(fā)現(xiàn)，σ＜2 min 時，車輛使用數(shù)量不變且?guī)缀醪淮嬖谡`時發(fā)車，其調(diào)度結(jié)果接近于剛性調(diào)度結(jié)果.

圖6 誤時上限σ 與最優(yōu)車輛數(shù)及總誤時Fig.6 Delay time upper limit σ-optimal number of vehicles and total delay times

如圖7 所示，隨著σ增大，車輛使用數(shù)與總成本整體呈下降趨勢.當(dāng)σ＜4 時，總成本下降速度最快；σ＞4 時，總成本下降速度變慢.表明延誤上限取值小于一定閥值時，對運營成本影響較大.

圖7 誤時上限σ 與總成本Fig.7 Delay time upper limit σ-total cost

4 結(jié) 論

本文研究允許誤時發(fā)車的單線純電動公交車輛柔性調(diào)度優(yōu)化模型，設(shè)計遺傳算法求解，并以上海市莘金專線進(jìn)行數(shù)值實驗.結(jié)果表明，與剛性調(diào)度相比，允許誤時發(fā)車的柔性調(diào)度能夠減少純電動公交車輛使用數(shù)量及總運營成本，進(jìn)而提高公交車輛使用效率.此外，當(dāng)誤時上限取值小于2 min時，車輛使用數(shù)量不變且?guī)缀醪淮嬖谡`時發(fā)車，柔性調(diào)度結(jié)果接近于剛性調(diào)度結(jié)果；隨誤時上限取值增大，車輛使用數(shù)與總成本整體呈下降趨勢，當(dāng)誤時上限取值少于一定閥值時，對運營成本影響較大.

本文以單條線路為基礎(chǔ)研究純電動公交車輛柔性調(diào)度模型，未考慮多線路的區(qū)域性純電動公交車輛柔性調(diào)度，將在下一步研究中體現(xiàn).