丁建立　孫彩蘋　李永華　王家亮

(1.中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院　天津　300300)(2.中國民航大學(xué)中歐航空工程師學(xué)院　天津　300300)

?

基于混合時間窗的航空貨運車輛動態(tài)調(diào)度模型*

丁建立1孫彩蘋2李永華1王家亮1

(1.中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院天津300300)(2.中國民航大學(xué)中歐航空工程師學(xué)院天津300300)

摘要由于某些不確定的因素,航班可以提前到達,也可以導(dǎo)致延誤,面向航班服務(wù)的特種車輛的高效動態(tài)調(diào)度就很難解決,論文把時間窗引入車輛調(diào)度過程中,對不在航班規(guī)定時間內(nèi)完成的服務(wù)進行一定的懲罰,建立了帶時間窗約束下特種車輛調(diào)度數(shù)學(xué)模型。結(jié)合機場實際運營情況考慮的目標(biāo)函數(shù)和約束條件,在初始優(yōu)化得到的車輛調(diào)度解的基礎(chǔ)上,根據(jù)收到的動態(tài)航班信息,利用局部優(yōu)化策略進行再次優(yōu)化,從而為機場特種車輛的優(yōu)化調(diào)度提供決策支持。實驗結(jié)果表明,和機場的實際車輛調(diào)度情況相比較,車輛使用數(shù)目優(yōu)化可達25%左右,且實時性較好,而與未加時間窗的調(diào)度模型相比優(yōu)化16%。

關(guān)鍵詞混合時間窗口; 優(yōu)化策略; 航空貨運特種車輛; 動態(tài)調(diào)度模型

Class NumberTP319

1引言

隨著為飛機進行服務(wù)的特種車輛不斷增多,合理高效地調(diào)度管理越來越多的機坪地面特種車輛,成為大家所關(guān)注的熱點問題[1]。樊琳琳采用啟發(fā)式算法在未考慮航班延誤的情況下對地面特種車輛進行初步的調(diào)度[2];高原等利用粒子群算法提出針對多航班多服務(wù)的調(diào)度模型[3];姚韻利用基于設(shè)備能力差的啟發(fā)式算法求解對于航班未按計劃時間進港的車輛調(diào)度模型[4];針對于地面特種車輛的調(diào)度,傳統(tǒng)的靜態(tài)調(diào)度模型的是假設(shè)在機場的運行時段內(nèi),所有進離場航班未考慮航班延誤的情況下建立調(diào)度模型[5～6],該類靜態(tài)模型與實際運行情況差距較大,需要根據(jù)實時航班動態(tài)信息及時對地面特種車輛進行有效合理的調(diào)度,從而達到動態(tài)調(diào)度。

2航空貨運特種車輛動態(tài)優(yōu)化調(diào)度模型的建立

2.1問題描述與假設(shè)

停在指定停機位的飛機接受服務(wù)順序大致為:電源車-登機橋-升降平臺車或傳送帶車-行李拖車-食品車-清水車或污水車-垃圾車-推車[7～8]。主要研究貨運特種車輛為:航空集裝器升降平臺車、貨運傳送帶車、平板、拖車。

由于飛機地面特種車輛不同于一般車輛,其在機場運行存在特定的時間和特定的路線,做如下假設(shè):

1) 所有裝卸車有固定停車位。

2) 車輛總數(shù)有限。

3) 特種車輛全程勻速行駛,15km/h。

4) 機坪特種車輛按照空管指定路線行駛。

5) 特種車輛進行服務(wù)過程不可以中斷。

6) 對于同種裝卸服務(wù),同類型車輛的裝載量相同。

2.2混合時間窗約束的引入

地面特種車輛的作業(yè)時間比較靈活,解決該問題,本文提出混合時間窗進行約束,對不在航班規(guī)定時間內(nèi)完成的服務(wù)進行一定的懲罰。航班到達時間分為以下三種情況:

1) 當(dāng)航班由于某些原因而導(dǎo)致延誤進港或者提前進港,該種情況下,考慮該航班到達時間是否超出可以接受成本懲罰的范圍,如果可以接受,則正常處理;否則繼續(xù)按照以下兩種航班到達時間方式進行局部性的調(diào)整和優(yōu)化;

2) 當(dāng)航班按計劃時間提前到達,搜尋附近是否有空閑的特種車輛,如果有,且車輛到達及服務(wù)開始時間在提前時間范圍之內(nèi),則輸入該需求,否則繼續(xù)等待,直到有特種車輛對其進行服務(wù);

3) 當(dāng)航班由于天氣,管制或者人為因素導(dǎo)致飛機延誤,且懲罰成本超過承受范圍,特種車輛則無需繼續(xù)等待服務(wù),可以退出該次服務(wù),對其他滿足時間要求的進港航班進行服務(wù)。

在某個時間段內(nèi),航班晚于或早于該時段到達,在可接受范圍內(nèi),接受一定的成本懲罰,超出該時間段,成本超出可接受的懲罰范圍[9～10],此時對調(diào)度方案進行局部調(diào)整[11]。

2.3基于混合時間窗特種車輛調(diào)度模型建立

根據(jù)假設(shè)和停機坪的實際運營情況,建立機坪特種車輛調(diào)度模型如下:

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

(1)

約束條件

(2)

如果Til≤Tjl≤Til+Fil+Tij

則yil+yjl≤1

(3)

(4)

(5)

(6)

Xijl(Til+Fil+Tij-Tjl)≤0

(7)

(8)

ail≤Til≤bil,i=1,2,…,N,l=1,2,…,L

(9)

ajl≤bil+Tij+Fil≤bjl,

i=1,2,…,N,j=1,2,…,N,l=1,2,…,L

(10)

(11)

其中,決策變量為

式(1)為車輛總使用費用最低。式(2)為同一個航班服務(wù)的同種車輛只有一輛[8]。式(3)為同一輛車任意時刻只能為一架航班服務(wù)。式(4)為從車庫出發(fā)的車輛總數(shù)不得超過L。式(5)～式(6)為特種車輛出發(fā)地和目的地只有一個。式(7)為l車為后一航班服務(wù)需要在完成對前一航班的該類服務(wù),且勻速行駛到下一航班所在位置所需時間。式(8)為車輛開始服務(wù)的時間不得早于服務(wù)允許開始的時間。式(9)～式(11)為混合時間窗約束。

3模型遺傳算法求解過程

1) 遺傳算法。按照計劃時間進港的航班信息數(shù)據(jù)進行預(yù)分配調(diào)度階段,設(shè)計遺傳算法,得到調(diào)度模型的預(yù)分配方案。

Step1:染色體編碼,采用0-1二進制編碼方式,由{0,1}構(gòu)成的符號集表示染色體的二進制編碼串,變量為車輛數(shù)目與航班時刻,變量總數(shù)為即編碼串長度為L+L*N(L為機坪特種車輛總數(shù)目,N為某一時間段內(nèi)車輛所需進行服務(wù)的航班的總數(shù)目),設(shè)定變量值即基因值為0或1,前L個基因上的數(shù)值0或者1代表車輛的是否在服務(wù)狀態(tài),后L個基因位上的變量值為0或者1時,代表是否可以得到被服務(wù)的航班,如果第m的基因位值為1,將(m-L)/N,得到的余數(shù)極為哪架次的航班被服務(wù),如果基因位值為0,將不做處理。

Step2:確定適應(yīng)度函數(shù)。為了滿足遺傳算法需要求得適應(yīng)度函數(shù)最大染色體的目的[12～13],將適度函數(shù)轉(zhuǎn)換成目標(biāo)函數(shù)的倒數(shù)形式,經(jīng)過試驗表明該種轉(zhuǎn)換方式有利于最優(yōu)解的產(chǎn)生。適應(yīng)度函數(shù)如下:

Step3:進行選擇,交叉,變異等操作。

(1)選擇算子。采用隨機遍歷采樣的方式,基于輪盤賭選擇的一種隨機選擇方式,與輪盤賭選擇方式的不同之處是只進行一次輪盤賭選擇[14～15]。

(2)交叉算子。運用單點交叉的交叉方式,原理在染色體上隨機產(chǎn)生一個基因位,在該基因位點進行染色體交叉重組[16～18]。

(3)變異算子。采用二進制編碼離散變異的變異方式。

Step4:更新適應(yīng)度函數(shù)。

Step5:判斷是否滿足終止條件,即是否達到適應(yīng)度函數(shù)值最大,如果滿足條件,進行步驟6,否則繼續(xù)重復(fù)Step3、Step4。

Step6:譯碼。根據(jù)編碼方式進行譯碼[19]。

Step7:輸出貨運機坪特種車輛的調(diào)度結(jié)果。

2) 實時局域優(yōu)化調(diào)度算法如下:

在初始優(yōu)化得到的車輛靜態(tài)調(diào)度解的基礎(chǔ)上,根據(jù)收到的動態(tài)航班信息,提出局部優(yōu)化算法進行再次優(yōu)化,從而為機場特種車輛的優(yōu)化調(diào)度提供決策支持。對于每一架航班i(1≤i≤N),得到其實際的到達時間Ti,設(shè)成本懲罰時間窗為[ti-ε1,ti+ε2],ti為航班計劃到達時間。

輸入:每個航班的實時信息(實際到達時間),該航班對應(yīng)的車輛的預(yù)分配方案

Begin

For each i

If 按照式(11)進行成本懲罰,并且正常處理

Else

If 等待直至有空閑特種車輛為其服務(wù)

Else 已分配的車輛退出該次服務(wù),釋放車輛資源

End If

End if

End for

End

輸出:每個航班的實時局域優(yōu)化調(diào)度結(jié)果

4實驗仿真結(jié)果分析

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

選用數(shù)據(jù)為北京首都機場T3航站樓的某一時段的航班數(shù)據(jù)進行實驗。主要包括航班數(shù)據(jù)和車輛信息數(shù)據(jù)。

表1　航班信息表

根據(jù)所建立的模型,所獲得的貨運特種車輛信息包括車輛類型,數(shù)量,行駛速度限制,派車費,行駛費,如表2所示。

表2　貨運特種車輛信息表

車輛進行服務(wù)的時間窗為10min,可以接受航班到達時間與計劃進港時間的差值為10min,在這個時段到達的航班,車輛正常進行服務(wù)將不接受時間窗懲罰,當(dāng)最早和最晚到達時間與不接受懲罰的時間窗差值為10分鐘時,需要對其進行一定的成本懲罰。

4.2實驗結(jié)果

選取種群大小:200迭代次數(shù):250交叉概率:0.9變異概率:0.03進行實驗。得到各類車輛的服務(wù)結(jié)果,由于車輛種類多,選取平臺車的調(diào)度結(jié)果說明。

表3　車號與服務(wù)航班號結(jié)果

調(diào)度策略結(jié)果如圖1所示。

圖1　平臺車車輛調(diào)度結(jié)果圖

由圖1可以看出,平臺車起始服務(wù)時間和結(jié)束服務(wù)的時間,以及連續(xù)為幾架次航班進行服務(wù)。

圖2　8號航班調(diào)度結(jié)果圖

列舉某個航班,對該航班進行服務(wù)的所有特種車輛的調(diào)度策略圖加以顯示。8號,計劃進港時間為9:03,實際進港時間為9:18,該航班的各種車輛調(diào)度結(jié)果策略圖如圖2所示:由圖2可以看出各種不同種類的貨運特種車輛,為同一架次航班服務(wù)開始以及服務(wù)終止的時間。由圖可以看出,各類特種車輛服務(wù)開始的時間以及服務(wù)的先后順序。

4.3結(jié)果對比分析

如果未加時間窗的車輛靜態(tài)調(diào)度,條件假設(shè)與動態(tài)調(diào)度模型一致,但是缺少時間窗約束。選取平臺車做實驗結(jié)果對比,通過實驗結(jié)果,可以明顯地觀察到,本文提出的混合時間窗口動態(tài)優(yōu)化模型與未加時間窗的車輛調(diào)度模型相比,帶有時間窗的調(diào)度模型利用局部優(yōu)化策略的結(jié)果與機場的實際車輛調(diào)度情況,車輛使用數(shù)目減少25%,且車輛調(diào)度的變化趨勢大致相同,實時性較好,而未加時間窗的調(diào)度模型優(yōu)化16%,變化趨勢與實際調(diào)度情況有差距實時性略差。

圖3　實驗結(jié)果對比圖

由此可以看出所建立模型的明顯優(yōu)勢,帶有時間窗的調(diào)度模型在航班延誤的情況下,可以根據(jù)實時的航班數(shù)據(jù),根據(jù)航班所延誤的時間長短決定是否對機坪特種車輛進行調(diào)度,一方面節(jié)約的資源的使用,另一方面符合調(diào)度的實時性。而不帶時間窗的調(diào)度模型,由于未考慮時間不確定因素,假定航班準(zhǔn)點到達與機場的實際情況有一定差距,所以得出結(jié)果的實時性略差。

5結(jié)語

本文根據(jù)機場的實際運行情況,提出了混合時間窗約束下特種車輛調(diào)度數(shù)學(xué)模型。該模型考慮的目標(biāo)函數(shù)和約束條件更加符合機場的實際運營情況。在初始優(yōu)化得到的車輛調(diào)度解的基礎(chǔ)上,根據(jù)動態(tài)航班信息利用局部優(yōu)化策略進行進一步的調(diào)整。最終得到了車輛調(diào)度結(jié)果,與實際情況相符,大大節(jié)約了資源,具有十分重要的意義。然而,本文中還有某些方面需要進一步研究。比如對需要消耗資源的特種車輛的調(diào)度、時間窗的改變等問題,都需要今后繼續(xù)深入探討。

參 考 文 獻

[1] W H. Ip, Member, IEEE, Dingwei Wang, Member, IEEE, and Vincent Cho. Aircraft Ground Service Scheduling Problems and Their Genetic Algorithm With Hybrid Assignment and Sequence Encoding Scheme[J]. 2013,7(4):649-657.

[2] 樊琳琳.大型機場地勤服務(wù)中的車輛調(diào)度問題的初步研究[D].沈陽:東北大學(xué),2009.

FAN Linlin. A preliminary study of special vehicle scheduling problem at airport[D]. Shenyang: Dongbei University,2009.

[3] 高原,王新茹,丁建立.基于改進粒子群算法的機場多航班多服務(wù)調(diào)度策略[J].航空計算技術(shù),2008,38(3):5-9.

GAO Yuan, WANG Xinru ,DING Jianli. The scheduling Tactics of multi-service for more flight Based on the Improved Particle Swarm Algorithm[J]. Aeronautical Computing Technique,2008,38(3).

[4] 姚韻.航空公司不正常航班管理和調(diào)度算法研究[D].南京:南京航空航天大學(xué),2006.

YAO Yun. Flight management and scheduling algorithm for abnormal Airlines[D]. Nanjing: Nanjing Aeronautics and Astronautics University,2006.

[5] M. Haouari, N. Aissaoui, F. Z. Mansour. Network flow-based approaches for integrated aircraft fleeting and routing[J]. Eur. J Oper. Res.,2009,193(2):591-599.

[6] 洪聯(lián)系.帶時間窗口動態(tài)車輛路徑規(guī)劃模型及其求解算法[J].計算機工程與應(yīng)用,2012,48(4):244-248.

HONG Lianxi. Dynamic Vehicle Routing Model with Time Windows Programming and its Algorithm[J]. Computer Engineering and Applications,2012,48(4):244-248.

[7] 蔣波.基于遺傳算法的帶時間窗車輛路徑優(yōu)化問題研究[D].北京:北京交通大學(xué),2010.

JIANG Bo. Vehicle Routing Problems with Time Windows Based on Genetic Algorithm[D]. Beijing: Beijing Transport University,2010.

[8] 林清巖.智能交通中車輛最優(yōu)路徑規(guī)劃策略研究[D].長春:吉林大學(xué),2013.

LIN Qingyan. Optimal Path Planning Strategy of vehicle in Intelligent Transportation System[D]. Changchun: Jilin University,2013.

[9] W H. Ip, Member, IEEE, Dingwei Wang, Member, IEEE, and Vincent Cho. Aircraft Ground Service Scheduling Problems and Their Genetic Algorithm With Hybrid Assignment and Sequence Encoding Scheme[J]. 2013,7(4):649-657.

[10] Marc Reimann, Karl Doemer. Richard F. Haiti. D-Ants; Savings Based Ants divide and collquer the vehicle routing problem[J]. Computers & Operations Research,2004,31(4):563-591.

[11] Li Tong. A stochastic assignment model using dynamic schedule-based network[J]. Transportation Research,2009,33(2):102-121.

[12] 邱平.車輛路徑問題研究[D].大連:大連海事大學(xué),2007.

QIU Ping. The reseach of vehicle routing problem[D]. Dalian: Dalian Maritime University,2007.

[13] Wang X B, Li Y j. Research on VRPTW of optimization based on improved two phase algorithm under electronic commerce[J]. Chinese J of Msnsgement Science,2007,15(6):52-59.

[14] 葛顯龍,王旭,代應(yīng).基于改進遺傳算法的有時間窗車輛調(diào)度問題研究[J].計算機應(yīng)用研究,2011,28(2):445-447.

GE Xianlong, WANG Xu, DAI Ying. Studies of vehicle scheduling problem based on Improved Genetic Algorithm with time windows[J]. The Application and Research of Computer,2011,28(2):445-447.

[15] 馬永杰,云文霞.遺傳算法研究進展[J].計算機應(yīng)用研究,2012,29(4):1201-1205.

MA Yongjie, YUN Wenxia. Development in Genetic Algorithm[J]. The Research of Computer Application,2012,29(4):1201-1205.

[16] 郎茂祥.用單親遺傳算法求解配送車輛調(diào)度問題的研究[J].交通與計算機,2006,24(1):119-122.

LANG Maoxiang. Research of distribution vehicle routing problem with single parent genetic algorithm[J]. Transportation and Computer,2006,24(1):119-122.

[17] 鞏敦衛(wèi),孫曉燕.變搜索區(qū)域多種群遺傳算法[J].控制理論與應(yīng)用,2006,23(2):256-260.

GONG Dunwei, SUN Xiaoyan. Multi-population Genetic Algorithm of Changeable search area[J]. Theory and Applications of Control,2006,23(2):256-260.

[18] Mitchell M. An Introuduction to Genetic Algorithms[M]. Cambridge, MA: MIT Press,1996.

[19] 劉淳安,王宇平.基于新模型的多目標(biāo)遺傳算法[J].西安電子科技大學(xué)學(xué)報,2005,32(2):260-267.

LIU Chunan, WANG Yuping. A new multi-objective genetic algorithm based on model[J]. Xi’an University of Electronic Technology,2005,32(2):260-267.

Dynamic Optimization Scheduling Model Based on Mixed Time Window for Air Freight Special Vehicles

DING Jianli1SUN Caiping2LI Yonghua1WANG Jialiang1

(1. School of Computer Applications and Software, Civil Aviation University of China, Tianjin300300)(2. Sino-Europe Institute of Aviation Engineering, Civil Aviation University of China, Tianjin300300)

AbstractAccording to some uncertain factors, flights can arrive early and also can be lead to delays, the efficient dynamic scheduling of special vehicles for flight services is difficult to resolve, the paper introduces the time windows vehicle scheduling process, the flights that don’t arrival within the specified time the service must be punished, and establishs a special mathematical vehicle scheduling model with time window constraints. Combined with the actual airport operations, considering objective function and constraints, on the basis of initial vehicle scheduling optimization solution and the dynamic flight information received, local optimization strategies are used to optimize again, so as to optimize the scheduling of special vehicles to provide support to airport decision. Experimental results show that compared with actual situation of the airport vehicle scheduling, vehicle using number optimization can reach 25%, and the change trend of vehicle scheduling is almost the same with good real-time performance, so the manpower cost is reduced, meanwhile but the model without the time widows can reach only 16%.

Key Wordsmixing time window, optimization strategies, special cargo vehicles, dynamic scheduling model

* 收稿日期:2015年11月9日,修回日期:2015年12月25日

基金項目:民航局科技創(chuàng)新引導(dǎo)資金專項(編號:MHRD20150107);中國民航大學(xué)中央高?；痦椖?編號:3122015C020,3122014P004)資助。

作者簡介:丁建立,男,博士,教授,研究方向:民航智能信息處理與航空物聯(lián)網(wǎng)。孫彩蘋,女,碩士,研究方向:航空物流。李永華,女，碩士,講師,研究方向:航空物流。王家亮,男，博士,講師,研究方向:民航信息系統(tǒng)。

中圖分類號TP319

DOI:10.3969/j.issn.1672-9722.2016.05.014