電動與燃油車型混合運營公交配車計劃編制研究

鄭明軒

（廣州市城市規(guī)劃勘測設(shè)計研究院,廣東 廣州 510000）

0 引言

隨著社會經(jīng)濟(jì)的快速發(fā)展，我國城鎮(zhèn)化也實現(xiàn)了飛躍式的進(jìn)步，但交通擁堵與污染也成了國內(nèi)各大城市必須面對的通病，而科學(xué)合理推進(jìn)常規(guī)公交運營則是解決上述問題的重要手段。常規(guī)公交運營研究通常包括四個研究對象[1]，分別是線網(wǎng)、時刻表、配車計劃和司乘排班，其中配車計劃編制是指基于已知時刻表，確定具體車次的執(zhí)行車輛的過程，科學(xué)合理編制配車計劃，是提升常規(guī)公交靜態(tài)調(diào)度效率的重要手段。當(dāng)前，盡管純電動公交車占比逐步提升，但受相關(guān)資產(chǎn)管理限制，部分城市仍有一定數(shù)量的燃油公交車在途運行，如何合理編制電動與燃油車型混合運營的公交配車計劃值得關(guān)注。

1 國內(nèi)外研究現(xiàn)狀

按照研究對象劃分，公交配車計劃研究可以分為三個階段，分別是常規(guī)燃油公交車配車計劃研究、純電動公交車配車計劃研究以及多車型的公交配車計劃研究。第一階段，自Gavish[2]等首次提出公交配車計劃問題，國內(nèi)外學(xué)者開展了廣泛研究，相繼提出了網(wǎng)絡(luò)流[3]、集分割[4]等建模思路，為后續(xù)研究打下了堅實的基礎(chǔ)；第二階段，伴隨純電動公交車投入運營，部分學(xué)者開展了相關(guān)情景下的研究，提出了不同充電策略[5]對配車計劃的影響，并有學(xué)者進(jìn)一步研究了[6]無線充電模式的配車計劃編制問題；第三階段，近年來，逐漸有學(xué)者關(guān)注到了電動與燃油車型混合運營的問題，并將續(xù)航里程[7]、碳排放[8]等約束納入配車計劃編制過程中，為公交企業(yè)實際運營提供了良好的理論基礎(chǔ)。目前，電動與燃油公交車混合運營的研究較少，且主要專注于單線路情景下的配車計劃研究問題，與未來公交企業(yè)區(qū)域調(diào)度、多線路運營的發(fā)展方向仍存在一定差距，開展多線路運營情境下的電動與燃油公交車混合運營研究具有一定的現(xiàn)實意義。

2 電動與燃油車型混合運營公交配車計劃建模

2.1 問題描述

配車計劃研究的核心目標(biāo)是在明確時刻表的前提下，以最低的運營成本完成相應(yīng)車次任務(wù)的運營工作。運營車型方面，目前電動公交車主要采用快充、慢充和換電三種方式進(jìn)行電能補(bǔ)充，其中換電方式能夠在較短時間內(nèi)為車輛補(bǔ)充電能，并能合理利用夜間的峰谷電價，在大型樞紐公交車場具有推廣的可行性，因此研究假設(shè)所有電動車型均為換電式公交。運營成本方面，可分為兩個主要來源，一是車輛使用成本，即使用一輛公交車每日的必要支出，可看作其生命周期成本平攤至每一天的支出；二是碳排放成本，保護(hù)生態(tài)環(huán)境是企業(yè)的社會責(zé)任之一，燃油公交車往往會產(chǎn)生更多的碳排放，因此通過設(shè)立碳排放成本，能夠更有效地引導(dǎo)公交企業(yè)加快發(fā)展純電動公交。運營模式方面，多線路運營模式能夠有效提升公交運營效率，是未來公交企業(yè)可能采用的主要運營模式，開展相關(guān)研究更能適應(yīng)行業(yè)遠(yuǎn)期發(fā)展方向。綜上所述，該文將重點關(guān)注多線路運營模式下，燃油與換電車型混合運營的公交配車計劃研究。

2.2 模型假設(shè)

基于前文明確的研究目標(biāo)，該文將建立基于以下假設(shè)條件的配車計劃模型：①不會出現(xiàn)延誤的情況；②不需要考慮換電過程排隊情況；③同類車型參數(shù)一致。

2.3 模型建立

（1）目標(biāo)函數(shù)，式中Z為目標(biāo)值；Ze、Zo分別為電動車型與燃油車型的綜合成本：

（2）時間窗約束，即限制車輛必須按序按時執(zhí)行車次任務(wù)。式中xki表示車次任務(wù)i由車輛k執(zhí)行；ykij表示表示車輛k執(zhí)行車次任務(wù)i之后直接執(zhí)行車次任務(wù)j；tij表示車次任務(wù)i的終點站到車次任務(wù)j起點站的空駛時間；分別為車次任務(wù)i的發(fā)車和到達(dá)時間；t＇為最小停站時間：

（3）純電動車約束，即限制純電動車輛執(zhí)行任務(wù)時必須滿足續(xù)航里程和換電時間的要求。式中，lki表示純電動車輛k最近一次換電至執(zhí)行完成車次任務(wù)i后的行駛里程；Li為車次任務(wù)i的里程；si為車次任務(wù)i的終點站至換電站的里程；Lmax為純電動公交車最大續(xù)航里程：

（4）現(xiàn)實約束，即要求燃油公交車不進(jìn)出換電站以及純電動公交車進(jìn)出車場前不直接前往換電站，其中M為一極大值：

（5）決策變量，即車次的執(zhí)行情況與車次任務(wù)間的銜接情況：

3 求解算法設(shè)計

3.1 常規(guī)遺傳算法設(shè)計

配車計劃編制問題屬于NP問題，精確算法往往存在時間復(fù)雜度較大的缺陷，不適宜求解復(fù)雜情景下的實際問題，而遺傳算法等啟發(fā)式算法對求解此類問題有著良好的應(yīng)用，因此該文設(shè)計了相應(yīng)遺傳算法用于求解配車計劃問題。

3.1.1 編碼設(shè)計

合理的編碼設(shè)計有助于提高算法運行效率，強(qiáng)化算法性能。電動與燃油車型混合運營公交配車計劃問題既需要關(guān)注各車次的執(zhí)行車輛，也需要關(guān)注各車輛所屬的車型。據(jù)此，該文設(shè)計了如下編碼，其中前n位為任務(wù)車輛編碼，即對應(yīng)車次的執(zhí)行車輛編號，而后m位車型編碼，即相應(yīng)編號車輛屬于燃油公交車還是純電動公交車。

3.1.2 適應(yīng)度設(shè)計

該文所研究的目標(biāo)為最小成本的配車計劃，因此對應(yīng)個體的目標(biāo)函數(shù)值越小，適應(yīng)度越高。因此，令

Fig=eM-fig為第g代 中個體i的適應(yīng)度，其中M為一較大值，fig為第g代 中個體i的目標(biāo)函數(shù)值。

3.1.3 初始種群生成

完全隨機(jī)方法是一種常用的初始種群生成方法，其生成的各個體往往差異較大，有利于展現(xiàn)遺傳算法群體尋優(yōu)的特點。該文使用基于ε-貪心策略的初始種群生成方法，首先假設(shè)所有車輛均為純電動公交車，并據(jù)此隨機(jī)生成編碼前n位；若滿足相關(guān)運營約束，則將各車輛為純電動公交車的成本列為cost2，為燃油公交車的成本列為cost1，并將cost2/（cost1+cost2）列為該車輛的貪心概率，通過生成隨機(jī)數(shù)，并判斷隨機(jī)數(shù)與貪心策略的大小，依次確定各車輛的車型。重復(fù)以上操作，直到達(dá)到算法預(yù)先設(shè)定的種群數(shù)。

3.1.4 遺傳操作

選擇操作，錦標(biāo)賽法是遺傳算法中一種常見的選擇策略，即隨機(jī)選出兩個個體，其中適應(yīng)度更高的參與交叉操作。交叉操作，配車計劃的核心在于各車輛對應(yīng)的車次鏈，因此交叉操作可以將車次鏈作為交叉對象。從兩個交叉?zhèn)€體中分別選擇一條車次鏈，并按照兩車為相同車型或兩車為不同車型的情況進(jìn)行分別交叉，再將交叉后的車次鏈分別返回原個體，即可獲得一對新的個體。變異操作，根據(jù)編碼特點，可以分別對個體編碼的前n位和后m位進(jìn)行變異，即通過前n位編譯從而改變車次的執(zhí)行車輛，通過后m位變異，改變車次的執(zhí)行車型。算法終止原則，當(dāng)遺傳代數(shù)達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)時，算法終止。

3.2 算法改進(jìn)

遺傳算法容易出現(xiàn)“早熟”“后期進(jìn)化速度慢”等缺陷，面對配車計劃這類復(fù)雜問題時，此類缺陷可能會限制算法的優(yōu)化效果，因此常常會引入其他啟發(fā)式方法進(jìn)行算法優(yōu)化。

3.2.1 基于自適應(yīng)思想的適應(yīng)度設(shè)計與遺傳操作接受準(zhǔn)則

通過設(shè)立與遺傳代數(shù)相關(guān)的適應(yīng)度計算方法和遺傳操作接受準(zhǔn)則，一方面能夠在遺傳早期避免“早熟”的問題，以免提前收斂于局部最優(yōu)解，另一方面也能提高后期進(jìn)化速度，加快遺傳后期的收斂進(jìn)度。通過引入kg-1作為遺傳第g代的自適應(yīng)參數(shù)，進(jìn)而將原適應(yīng)度Fig優(yōu)化為新的適應(yīng)度，并設(shè)立作第g代交叉和變異操作過程中獲得新個體的接受概率，既保障了遺傳初期新基因片段出現(xiàn)的可能性，也盡可能地保留了遺傳后期出現(xiàn)的優(yōu)秀個體。

3.2.2 重插入操作

按照精英保留策略，保證每一代中一定數(shù)量最優(yōu)秀的個體能夠不經(jīng)過選擇、交叉、變異操作進(jìn)入下一代，確保父代中優(yōu)秀的基因片段完整地保留進(jìn)子代。

4 實例分析

4.1 實例說明

北京四惠公交樞紐配套建設(shè)有一個公交場站和一個換電站，滿足該文的研究條件。北京公交475路、363路、455路起點站位于四惠公交樞紐，終點站之間距離1～4 km，線路全長11～15 km，符合純電動公交車運營能力范圍。具體空間距離如表1所示。

表1 場站間距 /km

參考相關(guān)研究[9]，假設(shè)燃油車型和純電動車型的單日使用成本分別為188元和398元，單位里程能耗成本分別為1.7元/km和0.6元/km，并假設(shè)燃油車型每千米碳排放成本為0.3元。

以某工作日為例，上述三條線路全天共開行918車次，按照50車次為一組，從中隨機(jī)選取200車次進(jìn)行算法驗證。

4.2 結(jié)果分析

分別使用常規(guī)遺傳算法和改進(jìn)遺傳算法對上述200車次算例進(jìn)行求解，算例運算結(jié)果如表2所示。

表2 運算結(jié)果

隨著車次數(shù)量增加，配車計劃的求解難度也隨之增加，而改進(jìn)遺傳算法的優(yōu)勢也較常規(guī)遺傳算法進(jìn)一步凸顯。其中收斂代數(shù)方面，改進(jìn)遺傳算法收斂代數(shù)平均早于常規(guī)遺傳算法9.17%；求解結(jié)果方面，改進(jìn)遺傳算法的目標(biāo)函數(shù)值平均低于常規(guī)遺傳算法1.99%。綜上所述，通過引入自適應(yīng)算法等優(yōu)化思路，改進(jìn)后的遺傳算法優(yōu)化速度高于常規(guī)遺傳算法，優(yōu)化效果也優(yōu)于常規(guī)遺傳算法。

5 結(jié)語

隨著我國公交運營企業(yè)智能化水平不斷提升，如何高效編制各種情境下的公交配車計劃成為企業(yè)發(fā)展必須要面臨的問題。該文以電動與燃油車型公交配車計劃為研究目標(biāo)，并建立了相關(guān)模型。研究表明，遺傳算法能夠較好地求解電動與燃油車型公交車混合運營的問題，而通過引入自適應(yīng)等優(yōu)化策略，能夠進(jìn)一步提高遺傳算法的科學(xué)性，能夠加快該NP問題的求解效率。實驗成果證明，筆者的相關(guān)研究成果對公交企業(yè)實際開展配車計劃編制工作具有一定的現(xiàn)實意義，能夠為公交企業(yè)的實際運營工作提供一定指導(dǎo)作用。