電動公交車輛調(diào)度問題研究綜述

沈吟東 陳晨

摘 ?要：政府大力推動電動公交發(fā)展以促進(jìn)城市節(jié)能減排，同時(shí)也為公交運(yùn)營帶來了挑戰(zhàn)。車輛調(diào)度是公共交通運(yùn)營計(jì)劃中的一個(gè)關(guān)鍵問題，優(yōu)化電動公交車輛調(diào)度方案不僅有助于降低公交企業(yè)運(yùn)營成本，而且可以改善服務(wù)水平，讓廣大出行群眾受益。文章首先對電動公交車輛調(diào)度問題及其數(shù)學(xué)模型進(jìn)行了闡述，然后總結(jié)歸納了現(xiàn)有的車輛調(diào)度研究及電動公交車輛調(diào)度研究的成果，最后展望了電動公交車輛調(diào)度未來的研究方向。

關(guān)鍵詞：電動車;車輛調(diào)度問題;公共交通;綜述

中圖分類號：F570 ? ?文獻(xiàn)標(biāo)識碼：A

Abstract： Our government vigorously accelerates the development of electric buses to promote urban energy conservation and emission reduction. It is effective but also brings challenges to bus operations. In public transport， the vehicle scheduling problem is a key issue. Optimizing the electric bus scheduling plan will not only help reduce the operating costs of public transportation companies， but also improve the service level and benefit the passengers. This paper firstly describes the electric bus scheduling problem and its mathematical model， then summarizes the existing vehicle scheduling research and the electric vehicle scheduling research， and finally looks forward to the future research direction of electric vehicle scheduling.

Key words： electric vehicle; vehicle scheduling problem; public transport; review

0 ?引 ?言

近年來，隨著我國城市化和交通機(jī)動化的進(jìn)程不斷加快，能源匱乏、環(huán)境污染與經(jīng)濟(jì)增長之間的矛盾日益加劇。在此關(guān)頭，電動汽車以其節(jié)能、清潔和環(huán)保等優(yōu)勢被各國廣泛關(guān)注，國內(nèi)外眾多國家與城市都在大力推動其發(fā)展以促進(jìn)城市節(jié)能減排。

2012年，在國務(wù)院印發(fā)的《節(jié)能與新能源汽車產(chǎn)業(yè)發(fā)展規(guī)劃（2012-2020年）》文件中，明確指出在由汽車需求量增長帶來的能源緊張和環(huán)境問題日益突出情況下，純電動汽車是我國新能源汽車和汽車工業(yè)轉(zhuǎn)型的主要戰(zhàn)略取向[1]。2015年，交通運(yùn)輸部、財(cái)政部、工業(yè)和信息化部聯(lián)合印發(fā)了《新能源公交車推廣應(yīng)用考核辦法（試行）》，直接對各?。▍^(qū)、市）每自然年度內(nèi)（2015～2019年）新增及更換的公交車中新能源公交車的比重制定了目標(biāo)，加快了新能源汽車在公交領(lǐng)域的推廣應(yīng)用[2]。2017年，工業(yè)和信息化部、發(fā)展改革委、科技部聯(lián)合印發(fā)的《汽車產(chǎn)業(yè)中長期發(fā)展規(guī)劃》中指出，要加快新能源汽車技術(shù)研發(fā)及產(chǎn)業(yè)化、加大新能源汽車推廣應(yīng)用力度，逐步提高公共服務(wù)領(lǐng)域新能源汽車使用比例[3]。2020年，交科院發(fā)布的《2019年度中國新能源公交車推廣應(yīng)用研究報(bào)告》顯示，截至2019年底，全國公交車總量在69萬多臺，其中新能源車占比59%，并且2019年度新增及更換公交車6.9萬輛，其中96%為新能源公交車，電池類型以磷酸鐵鋰為主。

王雪然等[4]對純電動公交車基于能源鏈的全生命周期CO2減排效果研究中得出結(jié)論：在相同的運(yùn)營環(huán)境下，純電動公交車相較于柴油公交車，在能源鏈全生命周期能夠減少61.20%的CO2排放量。其中，直接排放階段，純電動車可實(shí)現(xiàn)100%減排;間接排放階段，可實(shí)現(xiàn)46.09%減排。公共汽車是城市交通基礎(chǔ)設(shè)施的重要組成部分，除了中國，世界各地的城市越來越多地將電動公交車視為減少當(dāng)?shù)乜諝馕廴镜囊环N方式，巴黎和阿姆斯特丹等城市也已經(jīng)設(shè)定了在未來幾年改用零排放巴士的目標(biāo)。

然而純電動車在公交領(lǐng)域的應(yīng)用有別于傳統(tǒng)燃油公交，由于動力電池性能限制，純電動公交的續(xù)駛里程范圍和長充電時(shí)間特性，以及充電的相關(guān)配套設(shè)施建設(shè)情況使得純電動公交在車輛調(diào)度過程中需要考慮更多的約束，不能簡單地去把傳統(tǒng)燃油公交的車輛調(diào)度方案套用于純電動公交。因此，有必要針對電動公交展開其車輛調(diào)度問題研究，編制出科學(xué)合理的車輛調(diào)度方案。這不僅有助于降低公交企業(yè)運(yùn)營成本，而且能夠改善公交運(yùn)營和服務(wù)水平，讓廣大出行群眾受益。

1 ?電動公交車輛調(diào)度問題概述

作為公共交通運(yùn)營計(jì)劃中的一個(gè)關(guān)鍵問題，公交車輛調(diào)度問題（Vehicle Scheduling Problem，VSP）的目的是以運(yùn)營時(shí)刻表為基礎(chǔ)，制定覆蓋所有單程的有序的行車計(jì)劃。要求每個(gè)單程被且僅被某一輛車執(zhí)行一次，其目標(biāo)通常是最小化總運(yùn)營成本。由于國內(nèi)的城市公交車逐漸被電動公交車取代，而傳統(tǒng)燃油公交的車輛調(diào)度方案不能直接套用于純電動公交運(yùn)營中，因此新的挑戰(zhàn)涌現(xiàn)出來了。相較于傳統(tǒng)的基于燃油公交的車輛調(diào)度問題，由于電動汽車存在低續(xù)駛里程和長充電時(shí)間兩個(gè)特性且實(shí)際充電站相關(guān)配套設(shè)施建設(shè)有限，因此電動公交車輛調(diào)度問題（Electric Vehicle Scheduling Problem，EVSP）將更加復(fù)雜。

1.1 ?問題分析

電動公交車輛調(diào)度問題基于給定每日發(fā)車時(shí)刻表（其中包含每個(gè)單程的發(fā)車時(shí)刻、起點(diǎn)站、終點(diǎn)站等信息）、電動公交的車型信息（其中包含額定載客量，整備質(zhì)量，電池總儲電量等信息）等，目標(biāo)是求解得到總運(yùn)營成本最小的車輛調(diào)度方案。電動公交車輛調(diào)度方案的制定需滿足以下限制：

（1）每個(gè)單程任務(wù)都必須被執(zhí)行，被且僅被一輛車執(zhí)行一次;

（2）同一輛車的兩個(gè)相鄰單程任務(wù)之間允許空駛和等待，但是會產(chǎn)生相應(yīng)的連接成本;

（3）車輛電量低時(shí)，需及時(shí)去充電站補(bǔ)充電量，絕對不能使公交車在路上耗完電量;

（4）車輛從車場出發(fā)開始執(zhí)行一天的任務(wù)，執(zhí)行完所有的任務(wù)后返回車場。

燃油車輛續(xù)航高，在公交車輛調(diào)度問題中通常忽略加油過程。然而純電動公交車電池容量有限不足以滿足城市一整天的運(yùn)營需求，白天運(yùn)營過程中電量不足時(shí)需及時(shí)補(bǔ)充電量。一般，電動車補(bǔ)充電量的方式主要分為以下三種：

（1）整車慢充。采用低電流對電動車進(jìn)行充電，技術(shù)成熟，建設(shè)成本低，且對電池的損害小，但是所需時(shí)間長。

（2）整車快充。采用高電流為電動車進(jìn)行充電，所需時(shí)間較短，但是建設(shè)成本較高，并且高電流充電對電池?fù)p害大。

（3）更換電池。采用專業(yè)的操作裝置，取下車上儲電不足的電池，換上充好電的備用電池，整個(gè)過程在十分鐘左右。所需時(shí)間最短，但是技術(shù)要求高且建設(shè)成本高。

目前，公交運(yùn)營企業(yè)的主流充電方案是夜間慢充將車輛充滿電，白天運(yùn)營過程中在需要時(shí)采用快充模式補(bǔ)充電量。換電模式需配備若干備用電池以及配備專用的操作設(shè)備，雖耗時(shí)最短，但由于成本高昂，很少采用。慢充模式則耗時(shí)過長，僅適合夜間充電，若用于運(yùn)營過程中充電則會導(dǎo)致車輛資源不能很好的利用。

1.2 ?問題建模

為了盡可能地將問題描述清楚，對如下術(shù)語給出定義：

（1）單程：對應(yīng)時(shí)刻表上的一趟發(fā)車任務(wù)，應(yīng)具有首末站地點(diǎn)、發(fā)車時(shí)間、單程服務(wù)時(shí)間、單程耗電量等屬性。

（2）車次鏈：一輛車的全天行車計(jì)劃，包括從車場出發(fā)，然后按照發(fā)車時(shí)間先后執(zhí)行完全部單程任務(wù)，最后返回車場。

（3）空駛：車輛在非運(yùn)營路段的行駛，包括某單程終點(diǎn)與下一單程起點(diǎn)不同時(shí)兩銜接車次間的空駛、首末站與車場的空駛。

（4）等待：車輛完成前一單程任務(wù)后，在下一單程的出發(fā)地點(diǎn)停留等待再發(fā)車的時(shí)間。

本文將車輛調(diào)度問題常重構(gòu)為網(wǎng)絡(luò)流模型，表示為一個(gè)有向圖G=N，A。節(jié)點(diǎn)的集合N包含車場節(jié)點(diǎn)集合D和單程節(jié)點(diǎn)集合T?；〉募螦包含五種弧：出場弧DO=i，j|i∈D， j∈T;返場弧DI=i，j|i∈T， j∈D;直接連接弧TL

=i，j|i∈T， j∈T，且中途不返回車場;返場連接弧DR=i，j|i∈T， j∈T，且中途返回車場d∈D等待;充電連接弧RL

=i，j|i∈T， j∈T，且中途去充電站充電。

現(xiàn)實(shí)情況中，當(dāng)一條單程鏈中的兩個(gè)銜接單程間的時(shí)間跨度過長（如兩個(gè)小時(shí)以上），任務(wù)車輛會被要求返場等待，因此存在返場連接弧。當(dāng)車輛電量不足時(shí)，需要去充電站補(bǔ)充電量后才能繼續(xù)執(zhí)行后續(xù)單程任務(wù)，因此也存在充電連接弧。電動公交車輛調(diào)度問題的網(wǎng)絡(luò)流模型表示見圖1。

圖1表示了電動公交車輛調(diào)度問題的網(wǎng)絡(luò)流模型，其中圓柱形表示車場節(jié)點(diǎn)，橢圓表示單程節(jié)點(diǎn)。對于車場節(jié)點(diǎn)集合D

？哿N，車場中的車輛可以在任意時(shí)刻，從所屬車場出發(fā)，并最終返回所屬車場。對于單程節(jié)點(diǎn)集合T？哿N，每一個(gè)單程包含計(jì)劃出發(fā)時(shí)間、起點(diǎn)站、終點(diǎn)站，以及單程服務(wù)過程的電量消耗等信息。對于弧的集合A，每一條弧包含出發(fā)地、目的地、空駛時(shí)間、等待時(shí)間，以及對應(yīng)的電量變化等信息。在時(shí)空網(wǎng)絡(luò)中，通過五種類型的弧，單程節(jié)點(diǎn)集合被串成若干條車次鏈，每一條車次鏈被一輛車執(zhí)行。

1.3 ?數(shù)學(xué)模型

網(wǎng)絡(luò)流模型中，通過流量守恒公式和決策變量的取值共同約束單程任務(wù)的覆蓋（即約束每個(gè)單程都被執(zhí)行，且僅被執(zhí)行一次）。給定一組節(jié)點(diǎn)N=D∪T和一組弧A=DO∪DI∪TL∪RL∪DR，以及一組充電站R，可以將電動公交車輛調(diào)度問題建模為：

2 ?車輛調(diào)度研究綜述

目前針對電動公交車輛調(diào)度問題的研究相對較少，但是國內(nèi)外學(xué)者已經(jīng)對城市常規(guī)公交的車輛調(diào)度問題進(jìn)行了大量的研究，并且取得了許多優(yōu)秀的研究成果?？紤]到電動公交車輛調(diào)度問題是車輛調(diào)度問題的擴(kuò)展，可以采用相同的求解思路，本文分別從車輛調(diào)度研究和電動車輛調(diào)度研究這兩部分展開文獻(xiàn)綜述。

2.1 ?車輛調(diào)度研究

自20世紀(jì)60年代起，交通與運(yùn)籌優(yōu)化等領(lǐng)域的學(xué)者們就開始了對車輛調(diào)度問題的研究。根據(jù)停放車輛的車場數(shù)，可以將車輛調(diào)度問題劃分為單車場車輛調(diào)度問題（Single Depot Vehicle Scheduling Problem，SD-VSP）和多車場車輛調(diào)度問題（Multi Depot Vehicle Scheduling Problem，MD-VSP）。早期的研究工作集中在單車場車輛調(diào)度問題[5-8]上。單車場車輛調(diào)度問題即只有一個(gè)車場，所有車輛從該車場出發(fā)并最終返回該車場，通常被重構(gòu)為指派模型[5]，最小分解模型[7]或網(wǎng)絡(luò)流模型[8]。單車場車輛調(diào)度問題可以看作是多車場車輛調(diào)度問題的一種特例，自90年代起，更多的研究開始關(guān)注于多車場車輛調(diào)度問題[9-12]。多車場車輛調(diào)度問題即有多個(gè)車場，每個(gè)車場有自己的車輛，一般規(guī)定所有車輛從所屬車場出發(fā)并最終返回所屬車場，通常被重構(gòu)為多商品網(wǎng)絡(luò)流模型[9]或集合分割模型[11]。與此同時(shí)，學(xué)者們對于車輛調(diào)度問題的研究，都是從不同角度、不同方向開展，各有側(cè)重。例如，考慮燃料約束[13-14]，考慮多車型[15-17]，考慮多目標(biāo)[18-19]，將車輛—調(diào)度問題與時(shí)刻表問題集成求解[20-22]，將車輛調(diào)度問題與駕駛員調(diào)度問題集成求解[23-25]，考慮方案準(zhǔn)點(diǎn)率水平[26-28]等。

公交車輛調(diào)度問題作為一個(gè)整數(shù)規(guī)劃問題，已被證明為是NP難問題[9]，其求解方法主要分為兩大類：

（1）整數(shù)規(guī)劃（Integer Linear Programming， ILP）方法，通常輔助以啟發(fā)式方法。Bertossi等[29]使用了松弛拉格朗日啟發(fā)式算法對多車場調(diào)度問題進(jìn)行求解，同時(shí)證明了該問題是一個(gè)NP難問題。Ribeiro等[30]建立了帶有限制約束的集分割模型，并用列生成算法進(jìn)行了求解，算例結(jié)果表明求解算法具有很好的魯棒性。Amar等[31]提出了一種改進(jìn)的列生成算法以求解具有高度退化特性的大規(guī)模實(shí)例。Oukil等[32]致力于在線性規(guī)劃框架內(nèi)加速列生成，將列生成、變量預(yù)處理、穩(wěn)定變量結(jié)合起來以求解大規(guī)模的多車場車輛調(diào)度問題。作為精確算法的一種，ILP算法求解效果好，但是在求解速度上，以及在大規(guī)模問題上的求解能力具有較大局限性。

（2）智能優(yōu)化方法（如啟發(fā)式方法和超啟發(fā)式方法等）。智能優(yōu)化算法雖然不能保證求得整數(shù)規(guī)劃問題的最優(yōu)解，但是卻能在短時(shí)間（通常多項(xiàng)式時(shí)間）內(nèi)給出一個(gè)較好的可行解，結(jié)合領(lǐng)域知識能夠很好地應(yīng)用于大規(guī)模組合優(yōu)化問題的求解[33]。張飛舟等[34]采用遺傳算法的一點(diǎn)和二點(diǎn)交叉方式，求解了三種不同規(guī)模的車輛調(diào)度方案。Shen and Xia[35]應(yīng)用2-opt策略，設(shè)計(jì)了基于禁忌搜索的車輛調(diào)度方法。姚艷君[36]將禁忌搜索算法獨(dú)有的記憶思想引入到遺傳算法的搜索過程中，從而對車輛調(diào)度問題進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明該混合算法的求解質(zhì)量優(yōu)于遺傳算法。Pepin等[37]對比分析了分支定界算法、拉格朗日啟發(fā)式算法、列生成法、大規(guī)模鄰域搜索算法、禁忌搜索算法五種算法在求解車輛調(diào)度問題中的應(yīng)用，發(fā)現(xiàn)其中列生成法的求解質(zhì)量最優(yōu)，但求解時(shí)間較長，而基于大規(guī)模鄰域搜索的啟發(fā)式方法求解速度快且質(zhì)量不錯(cuò)。

2.2 ?電動車輛調(diào)度研究

純電動公交車輛調(diào)度問題可以看作是帶有續(xù)航里程約束和充電需求的車輛調(diào)度問題。其研究起步較晚，多數(shù)研究開始于近十年。按照補(bǔ)充電量的模式主要分為三類：基于換電模式的電動公交車輛調(diào)度、基于整車充電模式的電動公交車輛調(diào)度，以及基于混合充電模式的電動公交車輛調(diào)度。

2011年，靳莉[38]在對電動公交車電池狀態(tài)與運(yùn)營匹配關(guān)系的研究中，根據(jù)車載系統(tǒng)的實(shí)時(shí)監(jiān)控?cái)?shù)據(jù)，對純電動汽車的續(xù)駛里程、充放電特性等進(jìn)行了分析， 基于混合充電模式對單車場電動公交車輛調(diào)度問題建立了一個(gè)以車隊(duì)規(guī)模最小化和總空駛距離最小化的兩目標(biāo)模型，并采用遺傳算法對實(shí)例問題進(jìn)行求解，驗(yàn)證了模型和算法的適用性。隨后在2012年，周斌[39]將遺傳算法與模擬退火算法相結(jié)合，對混合充電模式下的單車場電動公交車輛調(diào)度問題進(jìn)行了求解。2013年，Zhu and Chen[40]基于換電模式研究了單車場的電動公交車輛調(diào)度問題，建立了一個(gè)以車隊(duì)規(guī)模最小化和總換電次數(shù)最小化的兩目標(biāo)模型，并采用非支配排序遺傳算法的基本思想，設(shè)計(jì)了一種改進(jìn)的多目標(biāo)優(yōu)化方法。2015年，孟越[41]基于換電模式研究了多車場的電動公交車輛調(diào)度問題，統(tǒng)籌考慮車隊(duì)規(guī)模、空駛時(shí)間、等待時(shí)間，且通過轉(zhuǎn)化為各種費(fèi)用將該多目標(biāo)問題轉(zhuǎn)化單目標(biāo)問題，并建立了以單程鏈為變量的集分割模型，應(yīng)用遺傳算法進(jìn)行了求解。2016年，Wen等[42]基于允許部分充電的整車充電模式，研究了多車場的電動公交車輛調(diào)度問題，首要目標(biāo)是車隊(duì)規(guī)模盡可能的小，其次是空駛距離盡可能小，并采用了自適應(yīng)大規(guī)模鄰域搜索算法對問題進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明，該算法可以為大規(guī)模實(shí)例提供很好的解，也可以為小規(guī)模實(shí)例提供最優(yōu)或接近最優(yōu)的解。2017年，徐剛[43]利用IC卡數(shù)據(jù)和GPS數(shù)據(jù)的時(shí)間同步性轉(zhuǎn)換得到客流數(shù)據(jù)，從而建立了一個(gè)乘客出行成本最小化和公交企業(yè)收益最大化的多目標(biāo)優(yōu)化模型，并采用了改進(jìn)的遺傳模擬退火算法基于整車充電模式對模型進(jìn)行求解。2018年，高佳寧[44]將分時(shí)電價(jià)納入考慮，即將用電成本納入考慮，基于改進(jìn)的遺傳算法分別求得了整車充電模式和換電模式下綜合成本最小的車輛調(diào)度方案。

值得注意的是，上述研究均將單程服務(wù)時(shí)間視為固定常數(shù)，即在已知每一個(gè)單程的出發(fā)和到達(dá)時(shí)間的基礎(chǔ)上展開調(diào)度方案的編制。然而，實(shí)際的道路交通情況千變?nèi)f化，因此編制出的調(diào)度方案在實(shí)際運(yùn)營中難以獲得令人滿意的準(zhǔn)時(shí)性。此外，電動公交車的能耗與道路交通狀況有關(guān)，如果電動車在行駛過程中耗盡電量無法前行，其對公交公司的負(fù)面影響將非常大。最近，Tang等[45]基于不確定的交通情況展開了在整車充電模式下對單車場電動公交車輛調(diào)度問題的研究，提出了一個(gè)靜態(tài)模型和一個(gè)動態(tài)模型，并基于分支定價(jià)算法對兩個(gè)模型進(jìn)行求解。其中，靜態(tài)模型引入了一種緩沖距離策略來規(guī)避出行時(shí)間的不確定性帶來的不利影響，而動態(tài)模型則將一天劃分為若干個(gè)時(shí)段，利用不斷更新的道路交通狀況和車輛運(yùn)營情況，動態(tài)優(yōu)化下一時(shí)段的車輛調(diào)度方案。

3 ?總結(jié)與展望

相較于燃油公交車輛調(diào)度，電動公交車輛調(diào)度需要額外考慮續(xù)航里程約束和充電需求，給公交運(yùn)營帶來了挑戰(zhàn)。并且，電動公交車輛調(diào)度方案在現(xiàn)實(shí)中執(zhí)行時(shí)涉及的影響因素非常多且關(guān)系復(fù)雜，涉及到路面交通情況、客流量、電池的充放電效率、電池容量衰減等問題。因此，電動公交車輛調(diào)度問題的建模和求解方法上仍有很大的研究空間，將來可以考慮在以下方向上擴(kuò)展這項(xiàng)研究：首先，可以從問題角度考慮多車型、更靈活的充電方案，或是與時(shí)刻表問題或駕駛員調(diào)度問題集成求解，或是如何在不確定的交通情況下提高方案的準(zhǔn)點(diǎn)率水平等。其次，可以從算法角度研究電動公交車輛調(diào)度問題更好的下限。

參考文獻(xiàn)：

[1] 國務(wù)院. 《節(jié)能與新能源汽車產(chǎn)業(yè)發(fā)展規(guī)劃（2012-2020年）》國發(fā)（2012）22號[Z]. 2012.

[2] 交通運(yùn)輸部，財(cái)政部，工業(yè)和信息化部. 《新能源公交車推廣應(yīng)用考核辦法（試行）》交運(yùn)發(fā)（2015）164號[Z]. 2015.

[3] 工業(yè)和信息化部，發(fā)展改革委，科技部. 《汽車產(chǎn)業(yè)中長期發(fā)展規(guī)劃》工信部聯(lián)裝（2017）53號[Z]. 2017.

[4] 王雪然，劉文峰，張龍文，等. 基于能源鏈的純電動公交車全生命周期CO2減排效果研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2019，19（1）：19-25.

[5] ?Saha J L. An Algorithm for Bus Scheduling Problems[J]. Journal of the Operational Research Society， 1970，21（4）：463-474.

[6] ?Freling R， Wagelmans A P M， José M. et al. Models and Algorithms for Single-Depot Vehicle Scheduling[J]. Transportation Science， 2001，35（2）：165-180.

[7] ?Equi L， Gallo G， Marziale S， et al. A combined transportation and scheduling problem[J]. European Journal of Operational Research， 1997，97（1）：94-104.

[8] ?Billington L. Routing and scheduling of vehicles and crews[J]. Computers & Operations Research， 1983，10（2）：63-67.

[9] ?Bertossi A A， Carraresi P， Gallo G. On some matching problems arising in vehicle scheduling models[J]. Networks， 2010，17（3）：271-281.

[10] ?Kliewer N， Mellouli T， Suhl L. A time-space network based exact optimization model for multi-depot bus scheduling[J]. European Journal of Operational Research， 2006，175（3）：1616-1627.

[11] ?Pepin A S， Desaulniers G， Hertz A， et al. A comparison of five heuristics for the multiple depot vehicle scheduling problem[J]. Journal of Scheduling， 2009，12（1）：17-30.

[12] ?Haghani A， Banihashemi M. Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints[J]. Transportation Research Part A， 2002，36（4）：309-333.

[13] ?Wang H， Shen J. Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints[J]. Applied Mathematics & Computation， 2007，190（2）：1237-1249.

[14] ?Baumann B M， Washington G， Glenn B C， et al. Mechatronic design and control of hybrid electric vehicles[J]. Mechatronics IEEE/ASME Transactions on， 2000，5（1）：58-72.

[15] ?Ralf Bornd？觟rfer， Andreas L？觟bel， Weider S. A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit[C] // Hickman M， Mirchandani P， Voss S. Computer-aided Systems in Public Transport. Springer Berlin Heidelberg， 2008：3-24.

[16] ?Ceder A A. Public-transport vehicle scheduling with multi vehicle type[J]. Transportation Research Part C Emerging Technologies， 2011，19（3）：485-497.

[17] 李細(xì)霞. 公交線路車輛調(diào)度優(yōu)化模型研究[D]. 武漢：華中科技大學(xué)（碩士學(xué)位論文），2007.

[18] ?Zuo X， Chen C， Tan W， et al. Vehicle Scheduling of an Urban Bus Line via an Improved Multiobjective Genetic Algorithm[J]. IEEE Transactions on Intelligent Transportation Systems， 2015，16（2）：1030-1041.

[19] ?Zhi-gang LIU， Jin-sheng SHEN. Regional Bus Operation Bi-level Programming Model Integrating Timetabling and Vehicle Scheduling[J]. Systems Engineering-Theory & Practice， 2007，27（11）：135-141.

[20] 劉志剛. 城市公共交通區(qū)域運(yùn)營調(diào)度系統(tǒng)協(xié)同優(yōu)化問題研究[D]. 北京：北京交通大學(xué)（博士學(xué)位論文），2009.

[21] ?Schiewe P. Integrating Timetabling and Vehicle Scheduling[C] // Integrated Optimization in Public Transport Planning， 2020.

[22] ?Freling R， Huisman D， Wagelmans A P M. Models and Algorithms for Integration of Vehicle and Crew Scheduling[J]. Journal of Scheduling， 2003，6（1）：63-85.

[23] ?Haase K， Desaulniers G， Desrosiers J. Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems[J]. Transportation Science， 2001，35（3）：286-303.

[24] ?Shen Y， Xia J. Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation[J]. International Transactions in Operational Research， 2009，16（2）：227-242.

[25] ?Yan S， Tang C H. An Integrated Framework for Intercity Bus Scheduling Under Stochastic Bus Travel Times[J]. Transportation Science， 2008，42（3）：318-335.

[26] ?Yindong Shen， Jia Xua， Jingpeng Li. A probabilistic model for vehicle scheduling based on stochastic trip times[J]. Transportation Research Part B， 2016，85：19-31.

[27] ?He F， Yang J， Li M. Vehicle scheduling under stochastic trip times： An approximate dynamic programming approach[J]. Transportation Research Part C Emerging Technologies， 2018，96：144-159.

[28] ?Huisman D， Freling R， Wagelmans A P M. Multiple-Depot Integrated Vehicle and Crew Scheduling[M]. INFORMS， 2005.

[29] ?Bertossi A A， Carraresi P， Gallo G. On some matching problems arising in vehicle scheduling models[J]. Networks， 2010，17（3）：271-281.

[30] ?Ribeiro C C， Fran？觭ois Soumis. A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem[M]. INFORMS， 1994.

[31] ?Amor H M T B， Desrosiers J， Frangioni A. On the Choice of Explicit： Stabilizing Terms in Column Generation[J]. Discrete Applied Mathematics， 2009，157（6）：1167-1184.

[32] ?Oukil A， Amor H B， Desrosiers J， et al. Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems[J]. Computers & Operations Research， 2007，34（3）：817-834.

[33] 王凌. 智能優(yōu)化算法及其應(yīng)用[M]. 柏林：施普林格出版社，2001.

[34] 張飛舟，晏磊，范躍祖，等. 智能交通系統(tǒng)中的公交車輛調(diào)度方法研究[J]. 中國公路學(xué)報(bào)，2003（2）：83-86.

[35] ?Shen Y， Xia J. Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation[J]. International Transactions in Operational Research， 2009，16（2）：227-242.

[36] 姚艷君. 智能公交車輛調(diào)度系統(tǒng)的設(shè)計(jì)與優(yōu)化[D]. 沈陽：沈陽工業(yè)大學(xué)（碩士學(xué)位論文），2010.

[37] ?Pepin A S， Desaulniers G， Hertz A， et al. A comparison of five heuristics for the multiple depot vehicle scheduling problem[J]. Journal of Scheduling， 2009，12（1）：17-30.

[38] 靳莉. 電動公交車電池狀態(tài)與運(yùn)營匹配關(guān)系研究[D]. 北京：北京交通大學(xué)（碩士學(xué)位論文），2011.

[39] 周斌. 基于改進(jìn)遺傳算法的電動公交車行車調(diào)度研究[D]. 長沙：長沙理工大學(xué)（碩士學(xué)位論文），2012.

[40] ?Zhu C， Chen X. Optimizing battery electric bus transit vehicle scheduling with battery exchanging： Model and case study[J]. Procedia-Soc. Behav. Sci， 2013，96：2725-2736.

[41] 孟越. 純電動公交車區(qū)域行車計(jì)劃編制模型及算法研究[D]. 南京：東南大學(xué)（碩士學(xué)位論文），2015.

[42] ?M Wen， E Linde， S Ropke， et al. An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem[J]. Computers and Operations Research， 2016，76（12）：73-83.

[43] 徐剛. 城市純電動公交車調(diào)度優(yōu)化問題研究[D]. 南京：南京理工大學(xué)（碩士學(xué)位論文），2017.

[44] 高佳寧. 考慮分時(shí)電價(jià)的純電動公交行車計(jì)劃編制方法研究[D]. 北京：北京交通大學(xué)（碩士學(xué)位論文），2018.

[45] ?Xindi Tang， Xi Lin， Fang He. Robust scheduling strategies of electric buses under stochastic traffic conditions[J]. Transportation Research Part C， 2019，105（8）：163-182.

收稿日期：2021-01-15

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目“基于隨機(jī)運(yùn)營時(shí)間的公交魯棒車輛調(diào)度研究”（71571076）

作者簡介：沈吟東（1965-），女，安徽合肥人，華中科技大學(xué)人工智能與自動化學(xué)院，教授，博士生導(dǎo)師，研究方向：運(yùn)籌與優(yōu)化、公共交通規(guī)劃與調(diào)度、智能公交系統(tǒng);陳 ?晨（1997-），女，湖北黃岡人，華中科技大學(xué)人工智能與自動化學(xué)院碩士研究生，研究方向：運(yùn)籌與優(yōu)化、電動公交車輛調(diào)度。