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

鄭明軒

（廣州市城市規劃勘測設計研究院,廣東 廣州 510000）

0 引言

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

1 國內外研究現狀

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

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

2.1 問題描述

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

2.2 模型假設

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

2.3 模型建立

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

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

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

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

（5）決策變量，即車次的執行情況與車次任務間的銜接情況：

3 求解算法設計

3.1 常規遺傳算法設計

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

3.1.1 編碼設計

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

3.1.2 適應度設計

該文所研究的目標為最小成本的配車計劃，因此對應個體的目標函數值越小，適應度越高。因此，令

Fig=eM-fig為第g代 中個體i的適應度，其中M為一較大值，fig為第g代 中個體i的目標函數值。

3.1.3 初始種群生成

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

3.1.4 遺傳操作

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

3.2 算法改進

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

3.2.1 基于自適應思想的適應度設計與遺傳操作接受準則

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

3.2.2 重插入操作

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

4 實例分析

4.1 實例說明

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

表1 場站間距 /km

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

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

4.2 結果分析

分別使用常規遺傳算法和改進遺傳算法對上述200車次算例進行求解，算例運算結果如表2所示。

表2 運算結果

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

5 結語

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