楊 敏，黎 彧，王 建，王立超

（東南大學交通學院，江蘇 南京 211189）

新能源汽車在公交領域得到了逐步推廣，但是在短時間內很難迅速實現(xiàn)公交系統(tǒng)的全面“電氣化”，燃油公交與電動公交的混合運行仍將普遍存在。不同類型的公交車輛動力特性、能源類別和消耗特征存在巨大差異。當前，大多數(shù)燃油公交的續(xù)駛里程能夠滿足一天的運營要求，但以燃油為動力能源的公交車輛，在運行過程會產生大量的碳排放，環(huán)境污染嚴重；而電動公交車輛雖然使用清潔能源，但由于電池容量限制，車輛需在運營期間多次充電，空駛里程增多，需配置更多的車輛來滿足服務需求，致使運營經濟成本提高。因此在混合車隊運營環(huán)境下，如何平衡燃油公交的碳排放成本與電動公交的經濟成本成為公交行業(yè)管理者亟需解決的問題。

本研究的重心在于混合公交車隊組成和車輛調度問題。當前，對于混合公交車隊車輛配置問題研究較多，Santos等［1］和Li等［2］以電動車輛購置成本和運營收入盈虧平衡為基礎，提出了混合公交車隊配置優(yōu)化方法。Grijalva等［3］從二氧化碳排放的角度分析了電動公交取代傳統(tǒng)燃油公交后對環(huán)境的改善作用。Teng等［4］在管理公交車隊時，通過尋求最佳替代車輛數(shù)取代傳統(tǒng)燃油公交車，實現(xiàn)碳排放的降低。以上對混合公交車隊調度的研究止步于車隊組成管理，事實上車隊組成管理是混合公交調度方案生成的前提，因此對于車輛配置的研究不僅要考慮路線運行參數(shù)的約束，還要在后續(xù)調度方案研究中綜合考慮經濟成本和環(huán)境成本對車輛配置優(yōu)化的影響。而與混合公交車隊調度方案生成相關的研究具有以下順承關系：基于傳統(tǒng)公交車隊調度方法對給定車隊進行調度優(yōu)化是混合公交車隊調度研究的基礎，大多以車隊規(guī)模最小或運營成本最小為優(yōu)化目標，并未將燃油公交產生的碳排放納入到運營成本中［5-7］。隨后，相關研究者將車輛配置納入考慮，Paul等［8］將電動公交總運營里程最大作為電動公交和柴油公交運行計劃生成目標，但忽略了電動公交電池容量限制所帶來的空駛里程增加等方面的問題。之后在純電動公交車隊的調度研究引入充電因素，Wang等［9］和Hall等［10］研究不同充電技術對純電動公交運行計劃的影響，建立以充電成本最小為目標的優(yōu)化模型，將其作為線性規(guī)劃問題求解生成調度方案。孟越［11］和高佳寧［12］在調度模型中重點考慮電動公交的續(xù)航里程和充電時間約束，基于遺傳算法得到運營成本最小的行車計劃。Dreier等［13］構造了特定線路和特定時間的駕駛情景，設計降低能耗的插電式混合動力雙鉸接公交車隊的充電調度優(yōu)化策略。隨著充電因素的引入，部分學者在進行混合公交車隊調度時進一步考慮車隊配置與充電方式之間的關系，Li等［14］和Rinaldi等［15］在電動公交日間充電約束下，應用整數(shù)線性規(guī)劃方法生成運營經濟成本最小的混合公交車隊調度方案。根據(jù)已有公交車隊調度方面的研究可知，混合公交車隊由于車輛類型配置差異，致使不同類型公交車輛在運行過程中表現(xiàn)出不同的經濟成本和環(huán)境成本傾向性，但混合公交車隊調度研究在建立優(yōu)化模型時，更側重電動公交的經濟效益，對環(huán)境成本未給予重視。針對當前混合公交車隊調度研究中未同時考慮經濟成本和環(huán)境成本對系統(tǒng)運營所造成的影響等問題，在此將環(huán)境成本和經濟成本同時考慮在內作為混合公交車隊調度方案的目標函數(shù)，以期實現(xiàn)混合公交車隊調度方案在提高車輛利用率的同時，降低運營成本和碳排放，從而解決混合車隊調度過程中因單純追求經濟優(yōu)勢導致碳排放增加與單純追求環(huán)保優(yōu)勢而降低經濟效益之間的矛盾。

以碳排放權交易管理辦法的實施為契機，本研究針對混合公交車隊的運營調度，量化電動公交的減排效益，考慮燃油公交的碳排放成本和電動公交的空載成本，建立綜合運營成本最小化模型，并設計嵌套禁忌搜索的改進遺傳算法進行求解，以確定混合公交車隊的最優(yōu)車隊組成和生成相應的調度方案，在減少碳排放的同時最大限度地保持經濟優(yōu)勢。

1 模型建立

1.1 問題描述

公交車輛調度中關鍵問題之一是合理編排車輛執(zhí)行公交時刻表的車次任務順序。本研究的主要研究對象為固定線路下的混合公交車隊，其調度問題可表述為：針對固定公交線路下的混合車隊運行，根據(jù)場站和線路信息來編制公交車次表。電動公交車輛集合E={k|k=1，2，…，K}和燃油公交車輛集合O={h|h=1，2，…，H}共同構成場站儲備公交車輛，如圖1所示，其中k為電動公交車輛編號，K為公交車隊中電動公交車輛的總數(shù)；h為燃油公交車輛編號，H為公交車隊中燃油公交車輛的總數(shù)。根據(jù)給定的公交時刻表，從電動公交車輛集合E和燃油公交車輛集合O中選擇車輛執(zhí)行時刻表中的車次i，N為一天內公交行車計劃的總車次數(shù)。

圖1 混合公交車隊配車模式Fig.1 Allocation model of mixed bus fleet

雖然電動公交運行過程中不產生尾氣污染，隨著更多的燃油公交被電動公交所取代，電動公交的購買投資及燃油公交舊車處理致使財政投入明顯增加，并且電動公交往返場站充電將帶來車隊總空駛里程的增加。在此需對公交場站儲備集合中的車輛類型和數(shù)量配置進行討論，從而為運營車隊是否需要進一步增加電動公交代替燃油公交提供決策參考，這也是生成公交行車計劃的重要前提。一味增加電動公交車輛的數(shù)量極有可能導致運營成本的大幅增加，因此通過管理方式合理安排混合車隊不同時段的運營方案，使現(xiàn)有車隊取得更大運營效益是非常必要的。混合公交車隊調度需要解決以下兩個問題：①在車隊組成方面，每種類型的車輛占比，即確定K和H的值；②在車隊運行方面，各車輛類型應執(zhí)行的車次，即確定執(zhí)行車次i的車輛類型。

本研究的混合公交車隊調度問題將基于以下假設展開：

（1）公交場站配備足夠數(shù)量的慢充充電樁，各公交站臺未配備充電設施，電動公交在儲能量低于設定值時需返回場站進行充電，充滿后重新投入運營。

（2）為保證電動公交的正常運營，電動公交在執(zhí)行車次作業(yè)期間不返回場站充電。

（3）公交線路運營速度穩(wěn)定。

本研究混合公交車隊調度模型的相關符號如表1所示。

表1 模型參數(shù)定義Tab.1 Definition of model parameter

1.2 問題模型化

本研究將混合公交車隊的車輛集合表示為V={x1，x2，…，x j，…，x J}，J為公交車隊的車輛總數(shù)，則有J=K+H。為了保證公交運行的可靠性，每個車次必須由指定車輛執(zhí)行，考慮線路發(fā)車間隔、線路長度、線路運營速度以及電動公交的充電時間等約束對線路運行中混合公交車隊的最小規(guī)模進行確定。線路混合車隊最小規(guī)模上界的確定將按照車輛類型進行分別討論。

（1）確定燃油公交上界。在一天的運營過程中燃油公交不需要返回場站，所以當公交車隊全部為燃油公交時，只要保證車輛數(shù)量滿足發(fā)車間隔和線路運營時間要求即可

（2）確定電動公交上界。在一天的運營過程中當電動公交剩余能量不滿足執(zhí)行完整車次時，電動公交需提前返回場站進行能量補給，此時需調動其他車輛維持該車次鏈的正常運營。假設公交車隊全部為電動公交時，車輛數(shù)在滿足發(fā)車間隔和線路運營時間約束的同時，還需考慮充電時間的限制，即

車隊調度方案采用矩陣形式定義X=[X1，X2，…，XN-1，XN]，X為公交車隊調度方案，包含公交線路運營一天內N個車次的車輛調度情況。對于生成混合公交車隊行車計劃的數(shù)學模型設計主要包含兩步，其中Step1為基于電動公交和燃油公交運行能耗模型分別建立公交運營成本模型，具體見1.2.1；Step2為聯(lián)立Step1建立的電動公交和燃油公交運營成本模型，以公交車隊綜合運營成本最小為目標建立求解函數(shù)，具體見1.2.2。

1.2.1 成本分析

在構建不同類型公交成本模型中需首先建立能耗模型，為了降低模型的復雜程度在此選用平均能耗進行計算，公交車輛的平均能耗可以參考車輛制造商公布的數(shù)據(jù)［16］。由此建立行駛里程與單位行駛里程能耗的線性模型［17-18］：電動公交能耗模型為Ee=l iqe；燃油公交能耗模型為Eo=l iqo。

（1）基于碳排放建立燃油公交成本模型。燃油公交成本Mo包括燃油公交車輛使用成本Mo，1和能源消耗成本Mo，2，以及在行駛過程中產生的碳排放成本Mo，3。按照工作量法計算公交車輛的使用成本；燃油公交的燃油成本主要產生于執(zhí)行車次的過程，與燃油公交的燃油消耗量及燃油單價有關，Mo，2=EoPo；燃油公交碳排放成本的測算通過碳排放因子來計算燃油碳含量，然后結合碳成本轉化系數(shù)確定：Mo，3=EoFoγ。由此構建燃油公交成本模型如下：

（2）基于減排效益建立電動公交成本模型。電動公交由于采用清潔能源，在運營過程中不產生碳排放成本，因此可將其作為減排效益納入電動公交成本模型中。相較于燃油公交的續(xù)航能力及能源補給效率，電動公交因受電池容量的限制，使其在返回場站進行能量補給的過程中產生了更多的空載成本。

電動公交的成本Me包含電動公交車輛使用成本Me，1和能源消耗成本Me，2，以及考慮電動公交替代燃油公交運營減少的碳排放作為電動公交的減排效益|Me，3|。按照工作量法計算電動公交的使用成本在測算電動公交的能耗成本時引入分時電價Pe(t)，引導電動公交錯峰充電，Me，2=EePe(t)；將電動公交取代燃油公交運營減少的碳排放Mo，3部分作為電動公交的減排效益|Me，3|，并且在計算電動公交替代燃油公交運營實現(xiàn)的減排效益時扣除電動公交運營過程中產生的額外空載碳排放，即Me，3=-(l i-2θlS)qoFoγ，其中θ∈{0，1}，θ為電動公交電池剩余容量的約束，每個變量值可以是0或1，分別代表該電動車輛需不需要返回場站進行能量補給，0代表不需要，1代表需要。θ值取決于電動公交的電池剩余量Ur，Ur具體表達方式為：電動公交行駛n個往返車次后返回至場站充電，Ur=Ue-2(nlL+lS)qe，當Ur＞(2lL+lS)qe時，θ=0；Ur≤(2lL+lS)qe時，θ=1。

由此構建電動公交的成本模型為

1.2.2 目標函數(shù)

在Step2中，根據(jù)Step1所建立的電動公交和燃油公交運行能耗與成本模型，以公交車隊綜合運營成本最小為目標，目標函數(shù)如式（5）所示。

式中：Z為混合公交車隊全天運營成本。電動公交政策傾向系數(shù)w表示受當?shù)叵嚓P政策影響，公交企業(yè)運營使用電動公交執(zhí)行車次的傾向。引入電動公交政策偏向系數(shù)作為調度方案中電動公交運營成本權重，通過調整w值，使生成的混合公交車隊調度方案實現(xiàn)不同優(yōu)化效果。并給定如下約束條件式（6）～（13）。

約束（6）為車輛類型判斷；約束（7）為車輛執(zhí)行狀態(tài)判斷；約束（8）保證每個車次必須有車輛運行，且只有一輛車運行；約束（9）表示車輛類型為燃油公交（x j=0）時，比較第j輛燃油公交所執(zhí)行的車次i和 車 次i′（x j，i=1，x j，i′=1）對 應 的 時 間 之 差（|T(i)-T(i′)|）與燃油公交完整執(zhí)行一個車次所需時間二者的大小，保證第j輛燃油公交所執(zhí)行的車次時間間隔大于線路運營時間；約束（10）為電動公交電量約束，剩余電量至少保證公交車輛能夠返回場站和一個完整車次的運行；約束（11）為電動公交充電時間約束，式中|T(i)-T(i′)|為該輛電動公交相鄰運行車次的時間間隔；約束（12）為混合公交車隊中電動公交車輛數(shù)量規(guī)模約束；約束（13）為混合公交車隊中燃油公交車輛數(shù)的規(guī)模約束。

顯然，所構建的模型為NP（nondeterministic polynomial，非確定性多項式）問題，由于電動公交與燃油公交的能源供應、用車成本差異導致公交調度問題解的規(guī)模擴大以及計算復雜化，傳統(tǒng)的優(yōu)化求解方法遇到了很大困難，啟發(fā)式算法是目前求解NP問題較為有效的方法，相關研究學者成功利用遺傳算法［19］和自適應大鄰域搜索算法［20-21］求解電動汽車車隊的旅行商問題，這為混合公交車隊調度問題的求解提供了有力的參考。

2 算法

針對NP問題的求解，由美國Holland教授提出的遺傳算法作為一種全局優(yōu)化搜索算法在公交車隊的優(yōu)化調度問題中可以在相對較短的時間內找到最優(yōu)解，其中包括電動公交車隊的車輛調度和電動公交車隊的充電調度［22-23］。由于遺傳算法采用適應度值的大小來決定個體是否被復制的選擇機制，容易形成近親繁殖，造成算法的局部搜索和過早收斂，從而導致全局尋優(yōu)失敗。而由美國Glover提出的禁忌搜索是一種用來跳脫局部最優(yōu)解的搜索方法，擴展了局部鄰域搜索。禁忌搜索通過記憶功能，在搜索過程中每當最優(yōu)解被作為搜索方向后，允許將未搜索過的次優(yōu)解作為新的搜索方向，使得搜索跳脫局部最優(yōu)。禁忌搜索為許多組合優(yōu)化問題提供了近似最優(yōu)解，在公交乘務人員排班［24］和路徑規(guī)劃［25］中被證明了它的可行性和有效性。但禁忌搜索對初始解具有較強的依賴性，當初始解較差時，收斂速度將會降低。因此在遺傳算法中嵌入禁忌搜索，允許求解過程選擇非最優(yōu)解能夠在很大程度上幫助遺傳算法避免“早熟收斂”問題的出現(xiàn)，同時保證了算法收斂速度，提高了遺傳算法的全局尋優(yōu)能力。

2.1 算法框架

求解優(yōu)化模型采用的算法，整體框架設計如圖2所示。

圖2 遺傳禁忌搜索算法流程Fig.2 Flow of genetic tabu searching algorithm

2.2 算法設計

2.2.1 初始解產生

利用遺傳算法從初始種群C(X)中產生一個較好的初始解X，使禁忌搜索能夠從一個較好的起點開始，既能避免遺傳算法陷入局部最優(yōu)，又能提高禁忌搜索的收斂速度。首先對公交調度方案進行染色體編碼，需要包含混合公交車隊運營的兩部分信息：①執(zhí)行哪些車次；②執(zhí)行車次對應的公交車輛。按照一天公交運營車次的時間順序進行染色體編碼，僅需構造1條染色體，即可包含①、②的信息，如圖3所示。

圖3 染色體編碼示例Fig.3 Examples of chromosome coding

采用隨機方法產生初始個體，然后進行選擇、交叉以及變異等遺傳操作，產生新種群作為禁忌搜索的初始種群，如圖4所示。

圖4 種群初始化流程Fig.4 Process of individualized initialization

適應度的大小決定著進化方向，由于本文的優(yōu)化問題屬于求目標函數(shù)最小的優(yōu)化問題，適應度值越小，其保留下來的概率越大。如式（14）所示，定義式（5）為染色體適應度函數(shù)。

2.2.2 禁忌表建立與突破

禁忌表T是禁忌搜索實現(xiàn)跳脫局部最優(yōu)解的核心要素，它包含禁忌表長度TL的確定和禁忌對象的選擇。TL過長導致收斂速度減慢，計算復雜程度增加；TL過短容易陷入局部最優(yōu)［26］。所以為了降低取值對收斂迭代的次數(shù)和方案與最優(yōu)解接近程度的影響，在后續(xù)仿真中將會對比TL不同取值下的收斂效果從而確定禁忌長度。如圖2所示，每次回選搜索域中的最優(yōu)解作為禁忌對象，禁忌對象將不作為尋優(yōu)搜索的新方向，當禁忌對象的適應度小于歷史記錄最低適應度時，即滿足藐視準則時，可以突破禁忌將其作為尋優(yōu)搜索的下一步方向。

2.2.3 搜索鄰域構造

采用轉移法和交換法構建搜索鄰域，轉移法為在同一車次把車次任務轉移到相鄰的車輛，如圖5所示；交換法為不同車次任務交換執(zhí)行車輛，如圖6所示。兩種鄰域結構互為補充，盡可能拓寬算法搜索的解空間從而避免陷入局部最優(yōu)。

圖5 轉移構造鄰域Fig.5 Transfer method of constructing neighborhood

圖6 交換構造鄰域Fig.6 Change method of constructing neighborhood

2.2.4 停止準則判斷

給定最大迭代數(shù)maxg，當?shù)螖?shù)達到maxg或者搜索域的解全部被列為禁忌對象時，結束搜索。

3 結果和討論

3.1 案例數(shù)據(jù)

選取云南省文山州1路作為本節(jié)的實例研究。公交線路運營情況如表2所示，配備的公交車輛技術參數(shù)如表3所示［27］。為了引導電動公交錯峰充電，參考城市分時電價模式進行公交充電需求管理。在分時電價機制的基礎上，基于不同時段電價確定不同充電成本，根據(jù)公交運行時刻表和公交動力能源差異，合理配置車輛規(guī)模和排班計劃。實例選取線路所在城市的分時電價如式（15）所示

表2 線路運營相關參數(shù)Tab.2 Related parameters of bus line operation

表3 公交車輛技術參數(shù)Tab.3 Technical parameters of bus

測算燃油公交碳排放成本時，主要參考中國能源統(tǒng)計年鑒以及碳交易的成交額確定相關參數(shù)［28］，如表4所示。

表4 碳排放相關參數(shù)Tab.4 Parameters related to carbon emissions

3.2 調度方案分析

為了驗證本研究所提出的調度方案優(yōu)化方法的有效性和優(yōu)越性，使用Matlab 2016進行仿真。設置相同的參數(shù)對比傳統(tǒng)遺傳算法和本研究所提出的基于嵌套禁忌搜索的改進遺傳算法，圖7為兩種算法的目標函數(shù)值收斂曲線。由圖7可知，當禁忌表長度設置為6時，基于嵌套禁忌搜索的改進遺傳算法相比于傳統(tǒng)遺傳算法求解精度提高了12%左右；此外，雖然基于嵌套禁忌搜索的改進遺傳算法收斂速度較慢，但該算法跳脫了局部最優(yōu)，全局尋優(yōu)能力更強，更適合最優(yōu)解的搜索。

圖7 算法收斂過程對比Fig.7 Comparison of convergence processes between algorithms

電動公交政策傾向系數(shù)w的取值大小反映了公交車隊調度決策傾向，在不同w取值下生成的最優(yōu)調度方案空駛里程和碳排放量如圖8所示。從空駛里程變化曲線可以看出，w取值越靠近0.5，總空駛里程數(shù)越小，此時生成的方案車輛利用率越高；從碳排放量變化曲線可以看出，隨著w取值增大，碳排放量也隨之增大，對應方案減排效益越低。故當調度決策傾向于提高公交車隊車輛利用率減少空駛里程時，應該設置較大的w；當調度決策傾向于提高公交車隊減排效益時，應該設置較小的w?？紤]到本次研究的目標是實現(xiàn)綜合運營成本最小，進一步討論不同w取值下生成的最優(yōu)調度方案綜合運營成本變化，如圖9所示。由圖9可以看出，當w=0.15時，調度方案的綜合運營成本最低，故本次研究將對基于w=0.15生成的調度方案進行分析。

圖8 不同w取值下方案車隊總空駛里程和總碳排放量的變化曲線Fig.8 Curves of empty driving distance and carbon emission of schemes at different values of w

圖9 不同w取值下方案綜合運營成本變化曲線Fig.9 Curves of comprehensive operation cost of schemes at different values of w

生成初始解部分算法參數(shù)設置如下：種群規(guī)模為30；交叉概率為0.8；變異概率為0.2，禁忌搜索算法部分參數(shù)選取如下：TL=6，maxg=2 000，w=0.15，求解優(yōu)化目標函數(shù)得到的調度方案如圖10所示，其中黑色矩形表示電動公交的車次行程，灰色矩形表示燃油公交的車次行程。按圖10所示的調度方案排班，此時混合公交車隊綜合運營成本最小，為每天1549.7元。顯然，如圖11所示的優(yōu)化調度方案中，電動公交執(zhí)行車次任務分配數(shù)量遠高于燃油公交，提高了新能源公交的利用，減少車隊中現(xiàn)有燃油公交使用，盡可能實現(xiàn)混合公交車隊減排效益最大化。同時，在優(yōu)化模型中引入分時電價機制，通過調節(jié)電動公交執(zhí)行車次任務的時段，引導電動公交錯峰充電，節(jié)約充電成本。圖12為調度方案中分時電價與電動公交執(zhí)行車次任務的時段關系。圖12實線為研究線路所在城市的分時電價機制，虛線為在不同電價時段電動公交執(zhí)行的車次任務數(shù)量占該時段總車次任務數(shù)量的比例，對比發(fā)現(xiàn)谷時段的車次任務全由電動公交執(zhí)行；上午峰時，電動公交執(zhí)行的車次任務數(shù)量占該時段總車次任務數(shù)量的比例大幅下降，為一天運營中最低的時段；中午平時階段，電動公交執(zhí)行的車次任務數(shù)量占該時段總車次任務數(shù)量的比例回升；下午峰時，電動公交執(zhí)行的車次任務數(shù)量占該時段總車次任務數(shù)量的比例再次下降。調度方案整體與分時電價機制相對應，呈現(xiàn)與電價錯峰執(zhí)行任務的效果。

圖10 混合公交車隊調度方案Fig.10 Scheduling plan for mixed bus fleet

圖11 不同類型公交車輛分配任務數(shù)量Fig.11 Number of tasks assigned to different types of buses

圖12 分時電價與電動公交執(zhí)行車次任務時段的關系Fig.12 Relationship between the time-of-use electricity price and the task period of electric buses

4 結論

本研究針對燃油公交與電動公交共存系統(tǒng)中的能源消耗與調度優(yōu)化問題，根據(jù)公交路線運行參數(shù)配置混合公交車隊的車輛類型和數(shù)量，綜合考慮電動公交空載成本和燃油公交碳排放成本，并將分時電價機制引入電動公交充電調度中，構建公交車隊調度運營成本優(yōu)化模型，生成最優(yōu)車次鏈，主要成果如下：

（1）聯(lián)立不同類型公交成本建立混合公交車隊綜合運營成本，以綜合運營成本最小為優(yōu)化目標，由此生成的調度方案能有效降低車隊中燃油公交車任務分配比例，提高了車隊運營減排效益，同時分時電價機制的引入實現(xiàn)了電動公交與用電高峰時段錯峰充電，節(jié)約了電動公交的充電成本。

（2）本文所提出的基于嵌套禁忌搜索的改進遺傳算法有效克服了傳統(tǒng)遺傳算法易陷入局部最優(yōu)的缺陷，提高了算法的求解精度。

（3）公交運營企業(yè)可以根據(jù)自身情況和城市交通現(xiàn)狀，通過采用不同的電動公交政策傾向系數(shù)值，使生成的調度方案滿足不同的決策目標，實現(xiàn)電動公交減排效益與車輛利用率之間的平衡。

本文在進行混合公交車隊調度、分析車隊運營成本時主要從車輛技術特征（如能源補給方式差異）展開，后續(xù)可以進一步考慮人員（如司機）成本，使生成的調度方案更全面地服務公交運營系統(tǒng)。

作者貢獻聲明：

楊 敏：研究概念生成，研究目標制定，實驗方式設計。

黎 彧：初稿撰寫，計算機程序設計，實驗結果分析。

王 建：論文審閱與修訂。

王立超：研究數(shù)據(jù)整理。