整車充電模式下的純電動公交行車計劃優(yōu)化

熊 杰，白宸宇，李向楠，陳艷艷

(1. 北京工業(yè)大學 北京市交通工程重點實驗室，北京100124； 2. 民航機場規(guī)劃設(shè)計研究總院有限公司，北京 100101)

0 引 言

純電動公交能源利用率高、環(huán)境污染小，乘坐舒適，在城市交通中發(fā)揮著重要的作用。公交調(diào)度計劃是公共交通運營的重要依據(jù)，直接影響到公交企業(yè)的運營效率。行車計劃的優(yōu)化是公交調(diào)度過程中的核心問題，關(guān)系到車輛資源的優(yōu)化配置和精細化管理。如何對純電動公交的行車計劃進行科學地編制，是亟待研究和解決的問題。

目前，國內(nèi)外對于公交行車計劃編制問題的研究可根據(jù)車場數(shù)分為兩類：單車場與多車場的行車計劃編制。B. GAVISH等[1]和R.FRRELING等[2]將單車場行車計劃編制問題表述為指派問題，即在滿足特定指派要求條件下，給各個車輛派遣車次任務(wù)，使指派方案的總行駛費用最低；M. MESQUITA等[3]和A.LOBEL[4]將多車場行車計劃編制問題表述為網(wǎng)絡(luò)流模型，即在網(wǎng)絡(luò)中找到滿足約束條件的多個網(wǎng)絡(luò)流，使每個節(jié)點有唯一一條流經(jīng)過，和單車場相比，多車場車輛調(diào)度問題的約束條件更多，算法求解難度更高。

公交行車計劃編制問題常用的求解算法有拉格朗日松弛啟發(fā)式算法、列生成算法、分枝定價法等。公交調(diào)度問題是NP-hard問題，可行解數(shù)量巨大，啟發(fā)式算法是解決該問題的重要方法。例如M.WEN等[5]以減少公交車輛數(shù)和降低空駛成本為目標，采用自適應(yīng)大規(guī)模鄰域搜索算法(ALNS)對多場站公交調(diào)度問題進行了優(yōu)化分析；H.GERHARD[6]將公交調(diào)度問題描述為含有時間窗的混合車輛路徑問題，研究了多種公交車型，并通過分支定價算法以及混合啟發(fā)式算法得出了車隊規(guī)模最小和旅客出行成本最低的最優(yōu)解；R.MATTHIAS等[7]建立了以車輛數(shù)最少及充電成本最低為目標的優(yōu)化模型，比較分析了由單一車型以及混合車型組成的車隊對總成本的影響，運用整數(shù)線性規(guī)劃方法和遺傳算法(GA)求出了最優(yōu)行車方案；孟越[8]引入了時空網(wǎng)絡(luò)的概念，對空駛弧進行簡化，采用遺傳算法對區(qū)域內(nèi)多條公交線路進行優(yōu)化調(diào)度；ZUO Xingquan等[9]在車輛調(diào)度過程中采用了改進的多目標遺傳算法，為每個目標分配適當?shù)臋?quán)重以獲得能夠平衡不同目標的Pareto最優(yōu)解；ZHANG Jian等[10]建立了等間隔的單車場車輛調(diào)度模型，結(jié)合實例對智能公交的運營進行優(yōu)化；TANG Chunyan等[11]在對單線路的車輛調(diào)度過程中運用了逆差函數(shù)(DF),采取不同措施對個別行程進行調(diào)整從而減少所需車輛數(shù)。

此外，也有學者在優(yōu)化車輛行車計劃的同時兼顧了時刻表的調(diào)整。C. AVISHAI[12]研究了混合車型下的公交時刻表編制方法，均衡考慮了乘客及公交企業(yè)的利益；J. OMAR等[13]構(gòu)建了以乘客換乘效率最高和車輛數(shù)最小為目標的模型，對單場站多線路的公交行車計劃和時刻表進行協(xié)同優(yōu)化；LIU Tao等[14]運用逆差函數(shù)，在不同客流分配下對時刻表及行車計劃進行了同步優(yōu)化，提升了服務(wù)的連續(xù)性。

綜上，國內(nèi)外學者對公交行車計劃編制問題做了大量的研究，取得了豐碩的成果。然而這些研究大多針對常規(guī)公交，對于純電動公交的研究相對較少。筆者以純電動公交為研究對象，在整車充電模式下，對區(qū)域內(nèi)多條電動公交線路的行車計劃進行優(yōu)化。純電動公交調(diào)度模型的約束條件更多，求解難度更大。在建模上，考慮續(xù)駛里程、時間及車次銜接等約束條件，建立了以減少車輛數(shù)和空駛成本為目標的模型。在算法求解方面，筆者利用遺傳算法對模型求解，有效改善了交叉和變異算子的設(shè)計。最后通過實例分析，驗證了該模型的有效性。

1 純電動公交調(diào)度模型構(gòu)建

1.1 問題描述

研究區(qū)域內(nèi)包含一個充電站、若干發(fā)車場站與若干條公交線路。車輛可在任意場站與充電站之間空駛以執(zhí)行不同線路的車次，從而實現(xiàn)公交跨線調(diào)度。一套行車計劃涵蓋了所有車輛在一天內(nèi)的車次安排，其表示方法是若干條車次鏈，每條車次鏈即每輛車在一天內(nèi)按時間順序排列的行車計劃。

純電動公交行車計劃的優(yōu)化問題可描述為：給定發(fā)車時刻表及其他相關(guān)信息，在符合一系列約束條件的前提下，指派各個車輛執(zhí)行時刻表中的班次，使全部車次都被覆蓋，且每個班次任務(wù)有唯一車輛執(zhí)行。

在編制純電動公交行車計劃時，要以區(qū)域發(fā)車時刻表為基礎(chǔ)，將各場站與充電站之間的空駛距離及其他相關(guān)信息作為輸入數(shù)據(jù)；并選取合適的調(diào)度模型及算法進行求解，最終輸出各條車次鏈。

1.2 模型假設(shè)

在問題的模型化過程中，筆者對實際情況做如下說明和假設(shè)：

1)場站內(nèi)的電動公交車為單一車型，車輛不存在延誤。

2)在一天的運營周期內(nèi)，車輛在執(zhí)行車次期間需及時整車?？砍潆?，車輛每次充電的時間和電價為定值，且充電樁數(shù)量充足。

1.3 目標函數(shù)

目標函數(shù)包含車輛購置成本W(wǎng)f和空駛成本W(wǎng)d。其中，車輛成本為一次性投資，而空駛成本為持續(xù)性成本損耗，需將兩者按照復(fù)利公式轉(zhuǎn)化為年值。目標函數(shù)表示為：

(1)

式中：μd為空駛成本的權(quán)重系數(shù)；μf為車輛成本權(quán)重系數(shù)；p為資金年回收率；m為車輛使用年限。

車輛購置成本W(wǎng)f表示為：

(2)

式中：k代表純電動公交車；i代表車次；N為車次集合；V為車輛集合；uf為單位車輛購置成本；xkoi為0～1變量；o代表場站。

空駛成本W(wǎng)d包含兩類：場站與充電站之間的空駛Wd1與不同場站之間的空駛Wd2。分別表示為：

(3)

(4)

式中：ud為單位里程的空駛成本，其中包含了單位里程空駛所耗費的電量、人力成本以及車輛的折損成本等，為一個固定常數(shù)；lc,oi為充電站至車次i發(fā)車場站的空駛距離；ldj,c為車次j終到場站至充電站的空駛距離;ldi,oj為車次i終到場站至車次j發(fā)車場站的空駛距離；xij為0～1變量。

1.4 約束條件

模型的約束條件分為車次銜接約束、車次時間約束和電量約束3類。

1.4.1 車次銜接約束條件

(5)

(6)

(7)

(8)

式中：xkij和xkoi為0～1變量；式(5)、式(6)表示每個班次均有且僅有一輛車執(zhí)行；式(7)為車次鏈的網(wǎng)絡(luò)連通性約束；式(8)表示從場站發(fā)出的車輛在執(zhí)行完一系列班次后必須返回場站。

1.4.2 車次時間約束條件

(9)

(10)

1.4.3 電量約束條件

Ej≤(ERi-hij)·xij+E0(1-xij),?i,j∈N

(11)

式中:Ej為車次j消耗的電量；ERi為車輛執(zhí)行完車次i后的剩余電量；hij為車輛在車次i，j之間的電量消耗；E0為初始電量；Ej、ERi和hij均為百分比電量，三者均在[0,1]之間；式(11)表示車輛在執(zhí)行車次j前的電量水平應(yīng)不低于車次j消耗的電量。

2 純電動公交行車計劃優(yōu)化算法

遺傳算法模擬了生物在自然中優(yōu)勝劣汰適者生存的進化過程，是基于進化論發(fā)展起來的一種隨機全局優(yōu)化搜索算法。算法從一個隨機初始化的種群出發(fā)，經(jīng)過逐代的選擇、交叉和變異等遺傳操作，使種群不斷進化直到產(chǎn)生最優(yōu)解。

2.1 編碼方式設(shè)計

編碼方式如下：假設(shè)時刻表中一共有n個車次，每條染色體以從1到n的不同排列來表示行車計劃，其中插入C表示充電事件(Charge),V表示新增一輛車(Vehicle)。例如染色體 [1 8 V 2 32 C 59 V 3 16…]表示車輛1執(zhí)行了任務(wù)1、8，車輛2依次執(zhí)行了任務(wù)2、32、59，并在執(zhí)行完車次32之后進行充電，車輛3依次執(zhí)行了任務(wù)3、16。

2.2 初始可行解的生成

在種群初始化之前，要根據(jù)車次信息生成一個n×n的0～1矩陣，表示在時間約束上每個車次之后所能連接的車次。在安排每輛車的后續(xù)車次時，需考慮以下兩個判定條件：

1)上一班次的結(jié)束時間+相應(yīng)的空駛時間<下一班次的開始時間；

2)剩余電量-空駛電量>下一班次消耗電量+返回場站消耗的電量。

若兩個條件都滿足，可從符合條件的車次集合中隨機選擇一個車次連在該車輛當前完成的最后一個車次之后；若只滿足條件1不滿足條件2，可對該車輛充電，若同時符合上一任務(wù)的結(jié)束時間+空駛時間+充電時間<下一任務(wù)開始時間，可給該車輛繼續(xù)安排車次；若兩個條件均不滿足，則需要新增車輛。

初始可行解生成的算法流程如表1。

表1 初始可行解的生成算法

2.3 適應(yīng)度函數(shù)的設(shè)計

遺傳算法依據(jù)個體的適應(yīng)度高低進行搜索。個體目標函數(shù)值越小，代表該個體的適應(yīng)度越高，被選擇的概率越大?？蓪⒛繕撕瘮?shù)的倒數(shù)作為適應(yīng)度函數(shù)。

求解目標函數(shù)時，染色體中所含V的個數(shù)代表車輛數(shù)，再乘以單位車輛成本即可得到車輛成本；將染色體中每兩個相鄰車次之間的空駛距離從頭至尾累加求出總空駛里程，再乘以單位里程的成本可得出總空駛成本。兩項成本之和為目標函數(shù)W。適應(yīng)度函數(shù)f(i)表示為:

(12)

2.4 遺傳操作

2.4.1 選擇

選擇是指從種群中選擇優(yōu)質(zhì)個體作為繁殖后代的父代的過程。選擇操作常見的方法有輪盤賭法、隨機遍歷抽樣法、無放回隨機選擇等。筆者采用了輪盤賭法。

在選擇之前，需確定種群規(guī)模Nind和代溝GGAP。代溝指每代種群中有Nind×(1-GGAP)個父代直接進入下一代種群，即在選擇中加入了精英保留策略，將適應(yīng)度最高的個體保留了下來。

每個個體被選擇的概率p(i)表示為：

(13)

選擇策略如下：

Step1:每轉(zhuǎn)一次輪盤會產(chǎn)生一個在[0,1]之間服從均勻分布的隨機數(shù);

Step2:在種群中遍歷搜索，直至選中p(i)大于該隨機數(shù)的個體，該個體落入選擇區(qū)間，本次轉(zhuǎn)輪盤結(jié)束;

Step3:繼續(xù)下一次轉(zhuǎn)輪盤，直到選出Nind×GGAP個染色體。

2.4.2 交 叉

交叉模擬了生物在進化過程中的基因重組，指按照一定的概率從父代種群中隨機選擇染色體，以某種方式交換染色體的部分基因從而產(chǎn)生新個體的過程。交叉是遺傳算法的核心內(nèi)容，提高了算法的全局搜索能力。

在交叉過程中，包含了兩個主要操作：重復(fù)車次的刪除以及未涵蓋車次的重新插入。在車次的重新插入過程中，以染色體中的V和C為節(jié)點，將其劃分為若干個區(qū)塊(block)，每個區(qū)塊都代表著一個滿足電量要求、期間不需充電的車次序列。

對于每一個待插入的車次，經(jīng)最初計算和篩選后，有若干個符合時間和續(xù)航里程約束的區(qū)塊可作為備選方案。筆者隨后采用了模糊綜合評價方法對這些備選方案進行了綜合評價，最終決策產(chǎn)生一個最佳方案。需要考慮的決策指標分別為：①車次插入?yún)^(qū)塊之后的總電量消耗；②車次插入?yún)^(qū)塊之后產(chǎn)生的空駛里程；③待插入車次與block中車次的時間間隔。

該3項指標均為負指標，且分別占有不同的權(quán)重。通過計算每個方案的加權(quán)相對偏差距離，可得出一個最優(yōu)方案。

對車次的重新插入的過程如表2。

表2 交叉算子中的重新插入算法

交叉的整體策略如下：

Step1:從種群中隨機選取兩個染色體作為父代；

Step2:任選一條車次鏈作為交叉點，父代1與父代2在交叉點的基因序列分別記為cross1和cross2；

Step3:將父代1中所含的交叉基因cross1與cross2中的車次序號刪去；

Step4:將cross2插入父代1的交叉點位置；

Step5:將cross1中的每個車次重新插入到父代1中，得到一個新的子代；

Step6:以同樣的步驟對父代2進行交叉。

交叉算子的具體過程如表3。

表3 交叉算子

2.4.3 變 異

變異模擬了生物在遺傳進化中的基因突變過程，是生成新個體的輔助方法，提高了遺傳算法的局部搜索能力。變異策略如下：

Step1:生成一個在[0,1]之間服從均勻分布的隨機數(shù)，若該數(shù)小于變異概率，則進行變異，否則繼續(xù)下一次循環(huán);

Step2:隨機選取一個染色體作為變異對象，任選一條車次鏈作為變異的基因片段;

Step3:將變異基因從染色體中刪去;

Step4:將染色體劃分為若干個區(qū)塊(block);

Step5:在符合時間和電量約束的前提下，采用模糊綜合評價方法進行比較后，將變異基因中包含的車次逐個重新插入到某一個區(qū)塊中；

Step6:更新每個區(qū)塊的開始、結(jié)束時間；

Step7:按照時間的先后順序，連接若干個區(qū)塊，得到一條新染色體。

2.5 終止原則設(shè)計

經(jīng)過選擇、交叉和變異后產(chǎn)生的新種群又重新開始了下一代的遺傳操作，直至達到最大的迭代次數(shù)，算法流程結(jié)束。在設(shè)計終止原則時，算法迭代次數(shù)一般在100～500之間取值。在整個進化過程中，種群規(guī)模不變，群體性能經(jīng)過若干代進化后逐漸趨于最佳，最終得到的種群即為最優(yōu)群體。

3 實例分析

3.1 實驗參數(shù)

以在北京魯谷場站充電的472路、473路和79路3條線路作為研究對象。472路、473路的發(fā)車場站在魯谷場站，79路的發(fā)車場站在廖公莊站。3條線路全天共352個車次，車輛續(xù)駛里程為60 km，每次充電時間為30 min。在當前方案下，車輛未實行跨線調(diào)度，3條線路共使用86輛車，線路基本信息如表4。

表4 線路基本信息

運用MATLAB求解時，為方便計算及算法操作，充電事件C和新增車輛V需用不同于車次序號(1～352)的數(shù)字來賦值。筆者令V=0，C=0.1。各場站間的空駛距離如表5。

表5 各場站間的空駛距離

實驗運行的相關(guān)參數(shù)設(shè)置如表6。

表6 實驗參數(shù)

3.2 結(jié)果分析

利用遺傳算法對3條線路全天352個車次的行車計劃進行優(yōu)化求解，使用MATLAB2016a在Win10環(huán)境中運行，得到了目標函數(shù)值的迭代曲線如圖1。

優(yōu)化結(jié)果中，車隊規(guī)模為70輛。每輛車在執(zhí)行完當天一系列車次后，最終返回場站進行充電。經(jīng)過優(yōu)化后的車輛行車計劃可表示為如下車次鏈(部分)：

車輛1:車次1→60→134→充電→186→211→298→充電

車輛2:車次2→101→189→227→充電

車輛3: 車次3→84→160→221→充電

車輛4: 車次4→58→110→充電→153→238→276→303→充電

車輛5: 車次5→29→138→263→充電

車輛6: 車次6→217→348→充電

車輛7: 車次7→175→213→291→充電

車輛8: 車次8→94→充電→130→158→194→243→317→充電

……

……

車輛65: 車次83→128→177→充電→226→284→325→充電

車輛66: 車次86→133→165→202→充電→247→296→335→充電

車輛67: 車次90→167→203→充電

車輛68: 車次102→131→241→充電

車輛69: 車次106→155→192→250→充電

車輛70: 車次141→174→228→271→充電

將經(jīng)過算法優(yōu)化后的結(jié)果與現(xiàn)狀進行對比如表7，投入使用的公交車由原先的86輛降為70輛，空駛成本也降低了。表明對車輛實行區(qū)域跨線優(yōu)化調(diào)度，可以使行車安排更加合理，車輛資源得到更好的利用。運營總成本由16 325萬元降至14 312萬元，降幅約12%，提高了公交企業(yè)的運營效率。

表7 優(yōu)化結(jié)果與現(xiàn)狀的對比

4 結(jié) 語

筆者結(jié)合純電動公交車的特性，將純電動公交行車計劃編制問題轉(zhuǎn)化成了增加續(xù)駛里程和充電時間等約束的常規(guī)公交調(diào)度問題，對多場站多線路的電動公交車輛實施區(qū)域跨線調(diào)度。在運用遺傳算法求解的過程中有所創(chuàng)新，采用獨特的混合整數(shù)編碼方式對行車計劃進行描述，并引入了區(qū)塊的概念，在區(qū)塊的層面上來實施交叉和變異等遺傳操作，且在交叉決策過程中采用了模糊綜合評價方法，提高了該復(fù)雜優(yōu)化問題的解決效率和交叉算法的科學性。最后對472路、473路和79路3條公交線路進行案例分析，算法優(yōu)化結(jié)果相比現(xiàn)有行車方案減少了16輛車，總成本降低了約12%。證明筆者構(gòu)建的模型及算法可有效解決公交行車計劃編制問題，對純電動公交的優(yōu)化調(diào)度具有重要的現(xiàn)實意義和指導(dǎo)作用。