過站保障車輛集中式調度的單親遺傳算法

朱新平,韓松臣

(1.中國民用航空飛行學院空中交通管理學院,四川 廣漢 618307; 2.四川大學空天科學與工程學院,四川 成都 610065)

飛機過站保障是指在飛機停靠機位期間,地服部門為其提供的航油加注、行李裝卸等保障服務.過站保障通常需調度各種保障車輛,其基本任務就是在車輛資源和標準作業流程約束下為飛機指派保障車輛及作業時段,盡可能減少由保障造成的航班延誤.因此,飛機過站保障是保證后續航班生產按計劃展開的重要工作.以往研究以過站保障流程改進為主,多采用貝葉斯網絡[1]、Petri網[2-4]、AOE (activity on edge)網絡[5]等方法.過站保障車輛調度問題可分為:(1) 多種車輛完成某一架飛機過站保障作業的調度[5];(2) 某種車輛完成多架飛機某一類保障作業的調度[6-10];(3) 多種車輛完成多架飛機多個保障作業的調度[11].本文研究第(3)類問題.有學者將其視為車間調度問題[8,10,12]或車輛路徑規劃問題[13].Leeuwen等人則采用簡單時間網絡建模過站保障過程,并分析保障車輛需求規模[14-15].總體來看,以往解決方法所給模型參數較多、求解復雜.

針對多架飛機多個保障作業的保障車輛調度,以集中式統一調度為背景,本文采用單親遺傳算法來求解,考慮車輛調度規則設計遞階式染色體編碼結構,將過站保障作業約束和車輛指派約束以直觀、易于理解的形式描述,并設計基于車輛可調度能力空間概念的染色體解碼方法.

1　問題分析與建模

1.1　問題分析

過站保障過程中,車輛在未分配任務時位于停放區,分配任務后會行駛至機位作業,且不同型號車輛具有不同保障能力.過站保障車輛調度過程(如圖1所示)需滿足:(1) 作業時序關系約束.某些作業任務不能同時展開,應滿足前后繼關系約束,而有些任務可同時展開.典型作業時序關系約束見表1.(2) 車輛指派規則約束.不同機型同一類作業所需保障車輛數量及作業耗時會存在差異.某機場過站保障車輛指派規則見表2.(3) 過站時間約束.保障作業應盡量在飛機計劃的過站時段內完成,以免影響下一航段飛行.由此可見,過站保障車輛調度是一類涉及多車輛協同、多作業任務串行與并發共存的調度問題.

圖1　飛機過站保障車輛調度過程Fig.1　Scheduling process of service vehicle for aircraft turnaround

1.2　數學模型

設在某時段內有n架飛機S={Si}(i=1,2,…,n)需開展過站保障,第i架飛機過站時段為[ti,0,ti,2]、需調度車輛完成的過站作業集r={rj}(j=1,2,…,k),第i架飛機的第j個保障作業記為Jij,Jij耗時為時間區間[t1,t2](0

(1)

ti,e=max{tij},

(2)

tvp-tivh+M(1-uivh)≥tij,

(3)

tij-td,ij≥ts,ij，

(4)

式中:α,β,γ為轉換系數,將時間轉化為保障成本費用;ti,e為飛機Si過站保障實際結束時間;ti,1為飛機Si過站計劃結束時間;若車輛h先完成Si的任務,緊接著完成Sv(v=1,2,…,n,v≠i)的任務,則uivh=1,否則uivh=0;tivh為車輛h從Si所在機位行駛至Sv所在機位的耗時;th為車輛h從停放區、客貨區或加油區行駛至機位耗時;tij為Si的作業任務rj的實際完成時間;tvp為飛機Sv的保障作業rp(p=1,2,…,k,p≠j)實際開始時間;M為一個足夠大的數;td,ij為飛機Si保障作業rj耗時;ts,ij為飛機Si保障作業rj計劃開始時間.式(1)為過站保障車輛調度優化的目標函數; 式(2)為求得飛機最后一個保障作業完成時間;式(3)為保證車輛在飛機之間的作業時序關系得到滿足;式(4)為保證單一作業的耗時需求得到滿足.

表1　某機場飛機過站保障作業任務編號、時序約束、耗時及所需車輛類型Tab.1　Task code,temporal constraint,time consumption,and service vehicle for aircraft turnaround in one airport

注：“—”表示不需要車輛；“*”表示相應車輛僅在飛機停靠遠機位時需要.

表2　某機場飛機過站保障車輛配備規則及車輛總量參照表Tab.2　Scheduling rules and total number of vehicle for aircraft turnaround service in one airport

2　遞階式編碼結構單親遺傳算法

2.1　染色體編碼

采取兩級遞階式染色體編碼結構,如圖2(a)所示.第1級為控制基因串g,各基因位可用需要調度車輛的作業任務編號表示;第2級為參數基因串c,各基因位是給第1級控制基因中對應任務指派的車輛編號.染色體分成若干片段,每一個片段對應一架飛機的過站保障車輛調度方案,其中：gi為飛機Si的作業任務編碼,長度記為li1;ci為飛機Si的保障車輛編碼,長度記為li2.

基于兩種策略產生染色體編碼:(1) 策略1:就近指派(minimum transition,MIN_T),即距離待保障飛機最近的車輛優先被調度;(2) 策略2:使用率均衡(average load,AVE_L),即盡可能保證同類車輛機會均等地被調度.對飛機Si,將需使用保障車輛的作業任務編號組成任務集Ti={Jij},任務Jij的可調度車輛編號組成集合,用B(Jij)表示.若3架飛機任務集分別為T1={1,2,3},T2={1,2,4},T3={1,3,4},車輛集為B(1)={1,2,3},B(2)={4,5,6},B(3)={7,8,9}.用所給編碼方法基于AVE_H策略編碼一個染色體，如圖2(b)所示.

2.2　種群初始化

定義1作業Jij的前序作業集P(Jij)為滿足飛機過站保障作業時序關系約束,將作業Jij開始之前必須完成的作業的集合定義為其前序作業集.P(Jij)=P(Jio)∪…∪P(Jis).其中,Jio,…,Jis為Jij的緊前作業,o,s∈{1,2,…,k}

定義2作業Jij的相容作業集O(Jij)為在滿足過站保障作業時序關系和可用車輛資源約束下,允許與Jij同時展開的作業集合,定義為其相容作業集.Jij與Jiw為相容作業,也就是Jij與Jiw無作業時序關系約束,且Q(Jij)≤N(Rq),Q(Jiw)≤N(Rq).

步驟1對控制基因染色體片段gi的第z個基因位置,從任務集Ti中隨機選取一個任務Jij,并依據表1求解該作業對應的前序作業集P(Jij),若P(Jij)中所有任務編號均已編入gi,則將Jij作為染色體片段gi中第z個基因位基因,同時,若任務Jij的相容作業集O(Jij)≠φ,則將O(Jij)中的所有任務編號也編入gi,轉步驟2;否則,重新步驟1.

步驟2對參數基因染色體片段ci,依據步驟1 確定的任務Jij及車輛配備規則(見表2)確定任務Jij所需車輛數量Q(Jij);從車輛集B(Jij)中基于MIN_T策略或AVE_L策略隨機選取Q(Jij)個不同的車輛編號,將其作為片段ci中連續Q(Jij)個基因位基因;同理,確定O(Jij)中各任務所需車輛總數量?及相應車輛編號,進而確定染色體片段ci中連續?個基因位基因;轉步驟3.

步驟3若z

步驟4若i

(b) 遞階式染色體編碼示例圖2　保障車輛調度的兩級遞階式染色體編碼結構及示例Fig.2　Two-level hierarchical chromosome coding structure for service vehicle scheduling and the coding example

2.3　染色體解碼

定義3車輛可調度能力空間定義為車輛可供調度開展機位保障的時段[ts,te]的集合,記為Π.

染色體解碼主要考慮基于作業時序關系約束,某個作業任務允許開始時,指派的保障車輛能否及時到達相應機位進而確定作業實際開展時段.基于車輛可調度能力空間概念的染色體解碼算法如下:

步驟1對控制基因染色體片段gi,取其中第j個基因位gi(j),其實質代表某一作業任務.

步驟3對參數基因染色體片段ci,從其中取出為作業gi(j)指派的車輛編號集合φ(gi(j)).

步驟4對車輛h∈φ(gi(j)),取對應的可調度能力空間Πh中時長大于ρ的時段集合P;并確定車輛h由前一個保障任務所在機位行駛至當前任務機位的耗時ζ.

步驟5將集合P中各時段按起始時間由小至大排序,并取第一個時段[ts,te].

步驟8同理,對φ(gi(j))中的其它車輛,復步驟4～7.

步驟9對控制基因染色體片段gi中的其他基因位,重復步驟1～8;否則,轉步驟10.

步驟10若i

以圖2(b)中前兩架飛機任務1的染色體解碼過程進行說明.圖中:x1為隨機迭足;x2為基因換位的掉作位置.假設車輛在機位間由停放區行駛至機位的耗時均為5 min,飛機過站時段分別為[5,68]和[12,82],保障任務1耗時為6 min,所有車輛初始可調度能力空間為{[0,200]}.對控制基因g1(1)={1}和參數基因c1(1)={1,2},由于車輛1需由停放區行駛至機位方可開展作業,故解碼后飛機1的作業任務1的保障時段為[5,11],此時,車輛1、2的可調度能力空間分別更新為Π1={[11,200]}、Π2={[11,200]};對控制基因g2(1)={1}和參數基因c2(1)={1,3},由于車輛1完成任務g1(1)后行駛至飛機2所在機位的時刻為11+5=16>12,故調度車輛1完成作業任務g2(1)的時段為[16,22]，車輛3開展飛機2的作業任務1的時段為[12,18];對應地,車輛1、3的可調度能力空間分別更新為Π1={[22,200]},Π3={[0,7],[18,200]}.同理,可完成染色體所有基因位的解碼操作.

2.4　換位變異算子設計

設計一種新的換位變異混合算子,具體做法為:

步驟1選擇種群中任一染色體,其所含控制基因串和參數基因串分別為g、c.

步驟2隨機選擇對應飛機Si的控制基因染色體片段gi和參數基因染色體片段ci.

步驟3隨機選取片段gi上基因位gi(x1)和gi(x2)并進行換位操作,若新生成的基因片段符合作業時序約束(見表1),則步驟4;否則,繼續步驟3.

步驟4考慮遞階式染色體編碼中下級基因受上級基因的控制,將參數基因片段中對應于控制基因位gi(x1)和gi(x2)的參數基因串ci(x1)和ci(x2)也進行換位操作，其中，x1、x2為隨機選定的基因位.

步驟5對參數基因串c,隨機選取兩個參數基因片段ck和cy,將兩個片段中分別對應于同一種作業任務的參數基因串ck(x3)和cy(x4)進行換位操作，其中，x3、x4為隨機選定的基因位.

步驟6對種群中的所有染色體均重復步驟1～5.

步驟3～4對控制基因染色體片段采取段內換位變異(見圖3(a)、(b)),以滿足作業時序關系約束;步驟5對參數基因染色體片段采取段間換位變異(見圖3(c)、(d)),以滿足車輛指派規則約束.

2.5　適應度函數

機位保障過程中,飛機未在過站時段結束之前完成保障產生的懲罰費用和車輛行駛費用之和為

(5)

為簡化問題,將式(5)中第3項納入機位作業耗時.因此,本文單親遺傳算法的染色體適應值函數為

(6)

2.6　選擇算子

采用輪盤賭選擇策略,并同時加入最優保持策略以保證算法的全局收斂性.

3　算法驗證

為驗證算法有效性,對表3中過站飛機開展保障車輛調度優化.具體作業流程、車輛配備規則及可調度車輛信息見表1和表2.種群規模NNIND=30,遺傳代數GGEN=30,換位變異概率NMUX=0.8.計算遺傳算法適應度函數值時,α=1.00，β=0.02.采取MIN_T策略和AVE_L策略分別產生初始種群,相應調度優化結果分別如圖4(a)、(b)所示,展示了每一保障車輛的具體作業時段.

表3　飛機過站信息Tab.3　Aircraft turnaround information

由圖4可知：

在兩種策略下,最后一道保障作業(即牽引車作業)完成時間相近,即過站保障造成的飛機延誤水平較為接近;在就近指派策略下,同一車輛工作時段更為密集,意味著車輛行駛時間相對要少,更利于降低保障成本.

(a)MIN＿T策略(b)AVE＿L策略圖4　兩種策略下的過站保障車輛作業時段甘特圖Fig．4　Ganttchartforservicevehiclesoperationbasedontwovehicledispatchingstrategies

考慮不同架次并基于上述兩種策略各運行50次,得到的結果見表4.由表4可知：針對不同保障架次,與AVE_L策略相比,MIN_T策略在過站保障延誤方面平均改進4%,在車輛行駛時間方面平均改進40%,這與圖4對比分析的結果是一致的;在遺傳代數和計算耗時方面,不同架次下相差不大,表明本文算法可適用不同規模的問題求解.同時,現場采集的實際數據表明,與MIN_T和AVE_L策略相比,現場人工指派策略(current,CUR)在過站保障延誤方面同它們均較為相近,而在車輛行駛時間方面,MIN_T策略較CUR策略平均改進11%,CUR策略較AVE_L平均改進30%.因此,為提高車輛的運行保障效益,可采用本文所給調度算法和MIN_T策略.

表4　不同調度策略下的過站保障車輛優化調度結果Tab.4　Optimized scheduling results based on different service vehicle scheduling strategies

將傳統遺傳算法(traditional genetic algorithm,TGA)與本文單親遺傳算法(partheno genetic algorithm,PGA)進行比較.兩種算法種群規模30,遺傳代數30,染色體編碼和解碼方式相同.TGA的交叉和變異概率通過反復試驗試湊確定,其中在交叉概率為0.7,變異概率為0.2時,TGA解決該問題的收斂速度較快.結果表明,兩種算法在不同架次下均能較快收斂.采取兩種算法并基于MIN_T策略的種群最優解和均值變化趨勢如圖5、6.

圖5　傳統遺傳算法優化性能Fig.5　Convergence effect of Traditional Genetic Algorithm

圖6　本文單親遺傳算法優化性能Fig.6　Convergence effect of partheno-genetic algorithm

由圖5可知,本文所給PGA收斂速度優于TGA.表5給出了不同架次下采用兩種算法開展調度的過站保障延誤情況.由表5可知,在架次較少時,TGA與PGA所得結果較接近,但隨著架次增多,PGA明顯優于TGA.

表5　不同過站飛機架次下的車輛調度TGA和PGA結果比較Tab.5　Scheduling results comparison between TGA and PGA for different numbers of turnaround aircraft　min

4　結　論

(1) 遞階式染色體編碼綜合考慮保障作業任務時序約束和車輛指派規則約束,可直觀描述保障車輛調度過程;(2) 換位變異算子采取控制基因染色體片段段內換位變異和參數基因染色體片段段間換位變異相結合的方式,避免了非法染色體產生,可有效壓縮尋優空間,提高求解效率;(3) 提出保障車輛可調度能力空間概念并設計相應解碼算法,保障解碼結果的可用性.所給算法對過站保障車輛集中式調度有效.今后可考慮飛機過站時段不確定性和作業任務耗時的動態性來研究保障車輛調度優化問題.

參考文獻:

[1]丁建立,趙鍵濤,曹衛東.基于貝葉斯網的航班過站時間動態估計[J].南京航空航天大學學報,2015,47(4):517-524.

DING Jianli,ZHAO Jiantao,CAO Weidong.Dynamic estimtion about turnaround time of flight based on Bayesian network[J].Journal of Nanjing University of Aeronautics and Astronautics,2015,47(4):517-524.

[2]VIDOSAVLJEVIC A,TOSIC V.Modeling of turnaround process using Petri Nets[C]∥Proc.of the 14th ATRS World Conference.Porto:EUROCONTROL,2010:1-13.

[3]MIQUEL A,ALEXEY N,CESAR T.A simulation model to improve air cargo operations in passenger aircraft[C]∥Proc.of the 2010 Summer Computer Simulation Conference.San Diego:IEEE Press,2010:446-451.

[4]FRANCISCO F,MIQUEL E,JENARO N.Use of colored petri nets to model aircraft turnaround at an airport[C]∥Proc.of the 6th International Conference on Scientific Computing to Computational Engineering.Athens:[s.n.]， 2014:1-8.

[5]孫瑞山,張子仝.基于CPM停機坪航班保障工作方法研究[J].中國民航大學學報,2011,29(5):23-29.

SUN Ruishan,ZHANG Zitong.Study on apron flight service work method based on CPM[J].Journal of Civil Aviation University of China,2011,29(5):23-29.

[6]NORIN A,GRANBERG A G,YUAN D,et al.Airport logistics-a case study of the turn-around process[J].Journal of Air Transport Management,2012,20(3):31-34.

[7]DU J Y,BRUNNER J O,KOLISCH R.Planning towing processes at airport more efficiently[J].Transportation Research Part E,2014,70(1):293-304.

[8]CHEUNG A,LP W H,LU D.An aircraft service scheduling model using genetic algorithms[J].Journal of Manufacturing Technology Management,2005,16(1):109-119.

[9]YUQUAN D,QIAN Z.ACO-IH:An improved ant colony optimization algorithm for airport ground service scheduling[C]∥Proc.of IEEE International Conference on Industrial Technology.Chengdu:[s.n.],2008:1-6.

[10]姚韻,朱金福,柏明國.航班過站地面服務的優化調度算法[J].信息與控制,2007,36(4):486-492.

YAO Yun,ZHU Jinfu,BAI Mingguo.An optimization scheduling algorithm for flight turnaround ground service[J].Information and Control,2007,36(4):486-492.

[11]茍晶晶.機場規劃所需地勤保障車輛最低數量預測[J].中國民航飛行學院學報,2015,27(2):50-53.

GOU Jingjing.Prediction of the minimum requirement of ground vehicles for airport planning[J].Journal of Civil Aviation Flight University of China,2015,27(2):50-53.

[12]王芹,樊瑋.飛機地面作業提前/拖期調度研究[J].計算機工程與應用,2008,44(10):214-216.

WANG Qin,FAN Wei.Research on earliness/tardiness scheduling about airplane ground job operation[J].Computer Engineering and Applications,2008,44(10):214-216.

[13]樊琳琳.大型機場地勤服務中的車輛調度問題的初步研究[D].沈陽:東北大學,2009.

[14]VAN LEEUWEN P,LEN OEI L,BUZING P.Adaptive temporal planning at airports[R ].Amsterdam:National Aerospace Laboratory NLR,2007.

[15]VAN LEEUWEN P,WITTEVEEN C.Temproal decoupling and determining resource needs of autonomous agents in the airport turnaround process[R].Amsterdam:National Aerospace Laboratory NLR,2009.