鄭明軒

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

0 引言

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

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

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

2 電動(dòng)與燃油車型混合運(yùn)營(yíng)公交配車計(jì)劃建模

2.1 問(wèn)題描述

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

2.2 模型假設(shè)

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

2.3 模型建立

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

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

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

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

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

3 求解算法設(shè)計(jì)

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

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

3.1.1 編碼設(shè)計(jì)

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

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

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

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

3.1.3 初始種群生成

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

3.1.4 遺傳操作

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

3.2 算法改進(jìn)

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

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

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

3.2.2 重插入操作

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

4 實(shí)例分析

4.1 實(shí)例說(shuō)明

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

表1 場(chǎng)站間距 /km

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

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

4.2 結(jié)果分析

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

表2 運(yùn)算結(jié)果

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

5 結(jié)語(yǔ)

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