唐春艷，楊凱強(qiáng)，鄔 娜

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

0 引 言

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

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

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

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

1 模型構(gòu)建

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

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

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

1.2 符號(hào)設(shè)定

p——車庫(kù)序號(hào)，p∈{1,2}；

h——純電動(dòng)公交車輛編號(hào)，h∈H，H為車輛集合；

R——時(shí)刻表中的班次集合；

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

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

i,j——班次序號(hào)，i,j=0 表示純電動(dòng)公交車駛?cè)胲噹?kù)或駛出車庫(kù)；

L——線路長(zhǎng)度(km)；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)車輛使用成本.

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

(2)空駛成本.

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

(3)換電成本.

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

(4)誤時(shí)成本.

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

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

求解式(6)可得

誤時(shí)成本C(tj)為

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

純電動(dòng)公交車運(yùn)營(yíng)1 d的總誤時(shí)成本為

1.4 約束條件

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

2 求解算法

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

2.1 染色體

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

2.2 適值函數(shù)

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

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

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

2.3 交叉與變異

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

3 實(shí)例分析

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

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

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

圖2 交 叉Fig.2 Cross

圖3 變 異Fig.3 Variation

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

3.2 結(jié)果分析

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

圖5 收斂圖Fig.5 Convergence graph

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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