基于MOPSO的民航電動特種車輛充電調(diào)度策略

高建樹，陳 煜，趙志民

（中國民航大學(xué)a.機場學(xué)院；b.電子信息與自動化學(xué)院，天津 300300）

隨著中國民航業(yè)的迅猛發(fā)展，航班數(shù)量急速增長，這就要求機場航班地面保障服務(wù)有更高的效率。據(jù)相關(guān)資料[1]顯示，地面特種車輛調(diào)度失誤是航班延誤主要原因之一，因此提升特種車輛調(diào)度的準(zhǔn)確性，減少調(diào)度失誤是民航特種車輛正常運行的主要任務(wù)。而隨著中國民用航空局“油改電”項目的實施，中國機場燃油特種車輛將逐步被電動特種車輛替代[2]。電動特種車輛與燃油特種車輛有著明顯區(qū)別，傳統(tǒng)的燃油特種車輛補給一次燃油即可進(jìn)行多次航班地面保障服務(wù)，所以傳統(tǒng)的燃油特種車輛無需考慮自身的能源補給。而電動特種車輛受限于電池技術(shù)導(dǎo)致充電時間較長和續(xù)航能力較差，所以考慮機場電動特種車輛充電時長的特種車輛調(diào)度管理成為航班地面保障服務(wù)研究的關(guān)鍵問題之一。

目前，國內(nèi)外對特種車輛的調(diào)度研究主要采用單車單航班調(diào)度的方式[3-6]，此類調(diào)度方式可以快速地解決某一種特種車輛的調(diào)度問題，但對于整個機場特種車輛的調(diào)度效率較低。針對多類型特種車輛的調(diào)度，相關(guān)學(xué)者采用智能算法建立調(diào)度模型并進(jìn)行求解[7-9]，但仍存在忽視不同類型特種車輛進(jìn)行航班保障服務(wù)任務(wù)之間的時間約束關(guān)系的問題。隨著機場電動特種車輛增加，部分學(xué)者針對電動特種車輛進(jìn)行了相關(guān)研究[10-11]，但僅考慮了電動特種車輛的充電問題，沒有解決多航班保障任務(wù)之間的次序問題，無法體現(xiàn)航班保障服務(wù)任務(wù)之間嚴(yán)格的次序關(guān)系。

目前針對特種車輛的相關(guān)研究大多基于單一車型進(jìn)行調(diào)度或針對傳統(tǒng)的燃油特種車輛進(jìn)行研究，由于電動特種車輛自身充電所耗時間遠(yuǎn)大于傳統(tǒng)的燃油特種車輛，所以傳統(tǒng)的燃油特種車輛調(diào)度策略并不適用于當(dāng)前應(yīng)用更為廣泛的電動特種車輛的調(diào)度。因此，對民航電動特種車輛充電調(diào)度的研究，在嚴(yán)格遵守航班保障任務(wù)次序關(guān)系的前提下，結(jié)合磷酸鐵鋰電池“淺充淺放”模式的實際使用方式，通過對一段時間內(nèi)航班任務(wù)所需服務(wù)車輛的耗電情況的整體計算，將航班地面保障服務(wù)任務(wù)合理分配給機場內(nèi)的電動特種車輛，使得電動特種車輛可以依據(jù)其航班保障任務(wù)的耗電量進(jìn)行準(zhǔn)確的充電補給，進(jìn)而避免了車輛因充電時間過長而過多占用充電樁和因充電時間過短導(dǎo)致車輛頻繁充電的情況出現(xiàn)，進(jìn)而達(dá)到提升充電樁的使用效率，降低車輛總體充電時長的目的，最終提升車輛調(diào)度的準(zhǔn)確性。本文采用多目標(biāo)粒子群優(yōu)化（MOPSO，multi-objective particle swarm optimization）算法，運用Matlab 進(jìn)行編程并求解模型。粒子群優(yōu)化算法有很多優(yōu)點，包括目的性強、尋優(yōu)方向清晰、收斂速度快、與其他算法更容易結(jié)合[12]，目前該算法在電動車輛有序充電問題[13-14]中運用成熟，本文提到的民航電動特種車輛充電調(diào)度也同屬于該問題，有一定的延續(xù)性。通過對模型求解最終實現(xiàn)了減少特種車輛數(shù)量和降低充電時長的目的，可為民航電動特種車輛充電調(diào)度問題的研究提供借鑒。

1 民航電動特種車輛充電調(diào)度建模

1.1 問題描述

通常在航班離港前，需由多種民航特種車輛來完成排除污水、更換清水、配備餐飲、裝載貨物、乘客換乘等一系列航班地面保障服務(wù)。

以下針對6 種不同類型的電動特種車輛的充電調(diào)度管理進(jìn)行相關(guān)研究。給定需要進(jìn)行航班地面保障服務(wù)的飛機數(shù)量，以及可進(jìn)行航班保障服務(wù)任務(wù)的各種電動特種車輛數(shù)量，在航班地面保障服務(wù)之前，確定各電動特種車輛的服務(wù)次序（對于同一航班的不同航班保障任務(wù)，食品車必須優(yōu)先于擺渡車完成航班保障任務(wù)，擺渡車必須優(yōu)先于客梯車完成航班保障任務(wù)）及其充電時間，建立民航電動特種車輛充電調(diào)度模型，制定每輛特種車輛的服務(wù)開始時間窗，最終完成民航電動特種車輛與等待服務(wù)的航班匹配。

1.2 參數(shù)描述

M={1，2，…，m}表示電動特種車輛種類集合；

Ni表示第i 種電動特種車輛的數(shù)量；

Cij表示第i 種電動特種車輛第j 輛車；

F={1，2，…，f}表示需進(jìn)行航班地面保障服務(wù)的航班集合；

P={1，2，…，p}表示可供電動特種車輛進(jìn)行電量補給的充電樁集合；pij表示第i 種電動特種車輛第j輛車在p 充電樁進(jìn)行充電；

Tijb和Tije分別表示第i 種電動特種車輛第j 輛車開始充電的時間和完成充電的時間；

Tijf和Tij(f+1)分別表示第i 種電動特種車輛第j 輛車服務(wù)航班f 的結(jié)束時間和服務(wù)航班f+1 的開始時間；

Sc表示電動特種車輛充電速率；

Eij和Eijsoc分別表示第i 種電動特種車輛第j 輛車在充電期間增加的電量和剩余的電量；

Qif表示航班f 的第i 種電動特種車輛服務(wù)所需電量（無負(fù)載運行電量和航班保障服務(wù)電量）；

αif和βif分別表示航班f 接受第i 種電動特種車輛的航班保障服務(wù)的最早開始時間和最晚開始時間；

xijf表示第i 種電動特種車輛第j 輛車是否正在進(jìn)行航班f 保障服務(wù)任務(wù)，即

yijf表示完成航班f 保障任務(wù)的第i 種電動特種車輛第j 輛車是否繼續(xù)進(jìn)行下一航班保障任務(wù)，即

1.3 模型規(guī)則制定

針對民航電動特種車輛進(jìn)行充電調(diào)度管理研究，并制定如下規(guī)則：①每種電動特種車輛數(shù)量給定并不再改變；②每種電動特種車輛服務(wù)時間給定并不再改變；③任一特種車輛的航班保障服務(wù)開始后，完成之前不會中斷；④任一架航班的每種服務(wù)一次只需要一輛特種車輛完成；⑤每個充電樁可同時為兩個電動特種車輛進(jìn)行充電；⑥同一車輛完成的相鄰兩個航班保障任務(wù)之間需預(yù)留5 min 空余時間。

1.4 電動特種車輛充電調(diào)度模型構(gòu)建

1）目標(biāo)函數(shù)

最小化電動特種車輛總數(shù)量，即

最小化電動特種車輛充電時間，即

2）約束條件

式（3）表示每架航班只能由一種類型車輛中的一輛特種車輛進(jìn)行服務(wù)；式（4）表示同一輛電動特種車輛同一時間僅可進(jìn)行一個航班的保障服務(wù)任務(wù)或無航班保障服務(wù)任務(wù)；式（5）表示第i 種電動特種車輛第j 輛車完成充電后5 min 內(nèi)要開始航班f 的航班保障任務(wù)；式（6）表示當(dāng)yijf=1，則可以進(jìn)行下一航班保障任務(wù)，當(dāng)yijf=0，則選擇充電樁進(jìn)行充電；式（7）表示航班f + 1 任務(wù)開始時間應(yīng)在航班f 任務(wù)完成之后5 min；式（8）表示充電樁p 最多可為2 輛電動特種車輛同時進(jìn)行充電；式（9）表示充電期間第i 種電動特種車輛第j 輛車補充的電量。

2 電動特種車輛調(diào)度模型求解

上述所提的民航電動特種車輛充電調(diào)度管理問題是一個組合優(yōu)化問題。對于這類優(yōu)化問題，通常很難通過數(shù)學(xué)方法得到一個最精確的解，由于問題規(guī)模增大，所以通常只能得到問題的多個可行解，即“非劣解”，稱其為Pareto 最優(yōu)解，且多目標(biāo)組合優(yōu)化問題一般會得到多個Pareto 最優(yōu)解。

目前，大規(guī)模的組合優(yōu)化問題常用群智能算法來解決，常用的群智能算法有粒子群優(yōu)化、蟻群優(yōu)化、魚群算法等。而粒子群優(yōu)化算法更適合本研究的特性。因此，在解決民航電動特種車輛充電調(diào)度管理問題時，采用多目標(biāo)粒子群優(yōu)化算法進(jìn)行求解。

2.1 多目標(biāo)粒子群優(yōu)化算法

標(biāo)準(zhǔn)的粒子群優(yōu)化算法的流程如圖1 所示。

圖1 粒子群優(yōu)化算法流程圖Fig.1 Flow chart of particle swarm optimization algorithm

（1）設(shè)置種群參數(shù)、變量范圍等相關(guān)參數(shù)，并隨機將一群含有位置和速度信息的粒子均勻分布在給定的尋優(yōu)空間中并進(jìn)行初始化。

（2）計算群體中每個粒子的適應(yīng)度值。

（3）對每個粒子的適應(yīng)度值都要與之前找到的最優(yōu)適應(yīng)度值進(jìn)行比較，如果當(dāng)前位置較好，則將個體最優(yōu)位置設(shè)置為這個粒子的位置，然后更新種群最優(yōu)位置。

（4）根據(jù)粒子速度和位置更新公式更新粒子的速度和位置如下

式中：i 表示粒子序號；k 表示迭代次數(shù)；d 表示D 維空間中坐標(biāo)序號；c1和c2是取值范圍為1～2 的常數(shù)，用于表示個體和種群歷史信息對粒子運動行為的影響；rand 是0～1 的隨機數(shù)表示個體最優(yōu)位置表示種群最優(yōu)位置；xk表示粒子當(dāng)前的位置。式（10）包括3 個組成部分：第1 部分表示粒子當(dāng)前速度，為下一代粒子提供飛行指示；第2 部分表示粒子認(rèn)知，避免落入局部最優(yōu)求解的情況出現(xiàn)；第3 部分表示粒子受群體信息影響進(jìn)行交互式學(xué)習(xí)。

（5）判斷給定的終止條件是否滿足。若滿足，則停止，并輸出最終得到的結(jié)果；否則回到步驟（2）繼續(xù)檢索。

2.2 模型求解

考慮航班保障任務(wù)所需電量的民航電動特種車輛充電調(diào)度的具體求解步驟如下。

（1）航班時刻表統(tǒng)計。對某機場當(dāng)日航班離港時刻進(jìn)行記錄。

（2）航班保障任務(wù)車輛次序規(guī)定。根據(jù)相關(guān)規(guī)定對不同類型航班保障任務(wù)車輛的次序進(jìn)行規(guī)定。

（3）機場內(nèi)信息系統(tǒng)數(shù)據(jù)輸入。機場內(nèi)信息系統(tǒng)數(shù)據(jù)包括電動特種車輛數(shù)量、電池容量、起始剩余電量信息和充電樁數(shù)量及其充電功率大小等。

（4）參數(shù)設(shè)置。設(shè)置多目標(biāo)粒子群優(yōu)化算法參數(shù)，其中種群規(guī)模設(shè)置為100，最大迭代次數(shù)設(shè)置為50。

（5）種群編碼與初始化。種群采用整數(shù)編碼，種群維度為航班數(shù)量×所需車輛種類數(shù)目，每個個體元素表示該航班分配的各類車輛的編號。初始種群在車輛編號范圍內(nèi)隨機生成，計算初始適應(yīng)度，每個個體的適應(yīng)度值有兩個，即電動特種車輛種類數(shù)量和電動特種車輛充電時間，同時個體需滿足約束條件。

（6）確定是否已經(jīng)達(dá)到最大循環(huán)迭代次數(shù)，如果未達(dá)到迭代次數(shù)，則將迭代次數(shù)增加1，然后轉(zhuǎn)到步驟（5）以更新調(diào)度策略。

（7）計算完成，輸出最終達(dá)到滿足條件的結(jié)果。

3 實驗數(shù)據(jù)

針對上述民航電動特種車輛充電調(diào)度管理這一課題的研究，利用多目標(biāo)粒子群優(yōu)化算法，并通過Matlab2018b 軟件進(jìn)行仿真。以國內(nèi)某機場一天中7:45—22:40 內(nèi)的航班離港時刻數(shù)據(jù)為例，實現(xiàn)該機場民航電動特種車輛的調(diào)度管理，并驗證民航電動特種車輛充電調(diào)度模型和多目標(biāo)粒子群優(yōu)化算法的可行性。

3.1 民航電動特種車輛數(shù)據(jù)

該機場此時間段內(nèi)有擺渡車10 輛、行李傳送帶車25 輛、客梯車15 輛、清水車15 輛、污水車15 輛、食品車10 輛，總計90 輛民航電動特種車輛可為離港航班的地面保障服務(wù)使用。車輛行駛速度為20 km/h[15]。所有車輛電量剩余初始值在35%～65%內(nèi)隨機分布。上述車輛從20%（欠電狀態(tài)）到100%（滿電狀態(tài)）的充電時間為3.5 h。車輛進(jìn)行一次航班保障服務(wù)任務(wù)所需電量為：擺渡車3%；行李傳送帶車4%；客梯車4%；清水車2%；污水車2%；食品車3%。該時間內(nèi)有10 個充電樁（20 個充電槍）可為上述車輛進(jìn)行充電。車輛在電量≤20%時前往充電樁充電，電量為20%～60%之間的車輛可在空閑時間超過30 min 時進(jìn)行充電，其中電量最低的優(yōu)先充電。

3.2 航班保障服務(wù)數(shù)據(jù)

經(jīng)過對國內(nèi)某機場調(diào)研，該機場在當(dāng)日7:45—22:40 之間的航班離港時間如表1 所示。表2 分別為擺渡車、行李傳送帶車、客梯車、清水車、污水車、食品車對各離港航班進(jìn)行地面保障服務(wù)開始時間窗，每輛車須在時間窗內(nèi)開始對航班進(jìn)行服務(wù)。

表1 部分航班離港時刻表Tab.1 Departure schedule of some flights

表2 航班保障服務(wù)開始時間窗Tab.2 Time window for the start of the flight support service

不同類型航班地面保障車輛所需的平均服務(wù)時間均有所不同，根據(jù)具體的機場調(diào)研得到擺渡車、行李傳送帶車、客梯車、清水車、污水車及食品車單次進(jìn)線航班保障服務(wù)任務(wù)的平均時間分別為：15、15、15、5、5、10 min。

6 種類型特種車輛的調(diào)度分別屬于客艙服務(wù)和貨艙服務(wù)，由于在服務(wù)期間服務(wù)對象相同的需要遵守一定的次序關(guān)系，各類型航班保障車輛之間的次序關(guān)系如圖2 所示，其中，清水車須在污水車服務(wù)結(jié)束之后進(jìn)行，食品車完成服務(wù)之后，擺渡車與客梯車開始進(jìn)行工作，行李傳送帶車單獨服務(wù)于貨倉，無需考慮其次序關(guān)系。

圖2 各類型航班保障服務(wù)車輛次序關(guān)系Fig.2 Sequence relationship of vehicles for various types of flight support services

4 實驗結(jié)果分析

采用MOPSO 算法對所述民航電動特種車輛充電調(diào)度模型進(jìn)行求解，在最終得到的車輛總數(shù)量及充電時間的Pareto 解中選取3 組解，如表3 所示。

表3 車輛總數(shù)量及充電時間的Pareto 解Tab.3 Pareto solution of total number of vehicles and charging time

針對所得的Pareto 解，對最終方案選取的原則為：首先要滿足在航班離港時間之前，各類型車輛盡可能地在服務(wù)時間窗內(nèi)完成航班保障任務(wù)，同時盡可能減少特種車輛的數(shù)量及特種車輛的充電時長。經(jīng)過比較，最終選取車輛總數(shù)量為85 輛，充電時間為5 230 min這組解。

在該組解中：所有民航電動特種車輛的初始電量在35%～65%之間隨機分布如表4 所示；各類型民航電動特種車輛每輛車對應(yīng)的服務(wù)航班編號如圖3 所示；各類型車輛每輛車的充電時間如圖4 所示。

表4 電動特種車輛初始剩余電量Tab.4 Initial residual power of electric special vehicles

以圖3（a）及圖4（a）中4 號擺渡車為例，在這一時間段的航班保障任務(wù)開始之前，4 號擺渡車所剩電量為39.36%，在其完成7 號航班的乘客輸送任務(wù)之后，該輛擺渡車選擇在7:05—9:33 之間的時間段內(nèi)進(jìn)行148 min 的充電，這段時間所補給的電量足夠4號擺渡車完成其在當(dāng)日9:33—22:40 時間段內(nèi)剩余的航班保障服務(wù)任務(wù)。

圖3 電動特種車輛服務(wù)對應(yīng)航班號Fig.3 The flight number corresponding to the electric special vehicle service

圖4 電動特種車輛充電時間Fig.4 Charging time of electric special vehicles

根據(jù)整體航班保障服務(wù)任務(wù)所需電量的計算與統(tǒng)計，使得每輛民航電動特種車輛的服務(wù)任務(wù)及充電時長有了更明確規(guī)定。其中在當(dāng)日的航班保障服務(wù)期間共有52 輛電動特種車輛在此時間段內(nèi)需要補充電量，若不對充電時長進(jìn)行規(guī)定，車輛每次充電都達(dá)到滿電狀態(tài)才停止充電，則所需總充電時長為6 124 min；而當(dāng)電動特種車輛根據(jù)后續(xù)航班保障任務(wù)所需消耗的電量進(jìn)行對應(yīng)的電量補給，則總體充電時長縮短至需5 230 min，相比較節(jié)省了14.60%的充電時長，為112個航班提供服務(wù)時，減少了5 輛電動特種車輛。

5 結(jié)語

為了適應(yīng)當(dāng)前機場特種車輛從燃油車輛轉(zhuǎn)電動車輛的趨勢，通過分析航班地面保障任務(wù)的業(yè)務(wù)流程，對不同類型民航電動特種車輛進(jìn)行次序約束，結(jié)合航班離港時間及充電樁的使用，以減少機場民航電動特種車輛的數(shù)量和充電時長為目的，采用MOPSO 算法，利用Matlab 仿真驗證所述的民航電動特種車輛充電調(diào)度模型，實驗證明，所提調(diào)度策略不僅減少了民航特種車輛數(shù)量還可以明顯縮短車輛的充電時長，較好地解決了民航電動特種車輛充電調(diào)度問題。

在實際工作中可能還會有天氣環(huán)境等因素影響機場車輛調(diào)度，下一步將對此進(jìn)行深入研究。