過站保障車輛集中式調(diào)度的單親遺傳算法

朱新平,韓松臣

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

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

針對(duì)多架飛機(jī)多個(gè)保障作業(yè)的保障車輛調(diào)度,以集中式統(tǒng)一調(diào)度為背景,本文采用單親遺傳算法來求解,考慮車輛調(diào)度規(guī)則設(shè)計(jì)遞階式染色體編碼結(jié)構(gòu),將過站保障作業(yè)約束和車輛指派約束以直觀、易于理解的形式描述,并設(shè)計(jì)基于車輛可調(diào)度能力空間概念的染色體解碼方法.

1　問題分析與建模

1.1　問題分析

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

圖1　飛機(jī)過站保障車輛調(diào)度過程Fig.1　Scheduling process of service vehicle for aircraft turnaround

1.2　數(shù)學(xué)模型

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

(1)

ti,e=max{tij},

(2)

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

(3)

tij-td,ij≥ts,ij，

(4)

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

表1　某機(jī)場飛機(jī)過站保障作業(yè)任務(wù)編號(hào)、時(shí)序約束、耗時(shí)及所需車輛類型Tab.1　Task code,temporal constraint,time consumption,and service vehicle for aircraft turnaround in one airport

注：“—”表示不需要車輛；“*”表示相應(yīng)車輛僅在飛機(jī)?？窟h(yuǎn)機(jī)位時(shí)需要.

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

2　遞階式編碼結(jié)構(gòu)單親遺傳算法

2.1　染色體編碼

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

基于兩種策略產(chǎn)生染色體編碼:(1) 策略1:就近指派(minimum transition,MIN_T),即距離待保障飛機(jī)最近的車輛優(yōu)先被調(diào)度;(2) 策略2:使用率均衡(average load,AVE_L),即盡可能保證同類車輛機(jī)會(huì)均等地被調(diào)度.對(duì)飛機(jī)Si,將需使用保障車輛的作業(yè)任務(wù)編號(hào)組成任務(wù)集Ti={Jij},任務(wù)Jij的可調(diào)度車輛編號(hào)組成集合,用B(Jij)表示.若3架飛機(jī)任務(wù)集分別為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策略編碼一個(gè)染色體，如圖2(b)所示.

2.2　種群初始化

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

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

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

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

步驟3若z

步驟4若i

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

2.3　染色體解碼

定義3車輛可調(diào)度能力空間定義為車輛可供調(diào)度開展機(jī)位保障的時(shí)段[ts,te]的集合,記為Π.

染色體解碼主要考慮基于作業(yè)時(shí)序關(guān)系約束,某個(gè)作業(yè)任務(wù)允許開始時(shí),指派的保障車輛能否及時(shí)到達(dá)相應(yīng)機(jī)位進(jìn)而確定作業(yè)實(shí)際開展時(shí)段.基于車輛可調(diào)度能力空間概念的染色體解碼算法如下:

步驟1對(duì)控制基因染色體片段gi,取其中第j個(gè)基因位gi(j),其實(shí)質(zhì)代表某一作業(yè)任務(wù).

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

步驟4對(duì)車輛h∈φ(gi(j)),取對(duì)應(yīng)的可調(diào)度能力空間Πh中時(shí)長大于ρ的時(shí)段集合P;并確定車輛h由前一個(gè)保障任務(wù)所在機(jī)位行駛至當(dāng)前任務(wù)機(jī)位的耗時(shí)ζ.

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

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

步驟9對(duì)控制基因染色體片段gi中的其他基因位,重復(fù)步驟1～8;否則,轉(zhuǎn)步驟10.

步驟10若i

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

2.4　換位變異算子設(shè)計(jì)

設(shè)計(jì)一種新的換位變異混合算子,具體做法為:

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

步驟2隨機(jī)選擇對(duì)應(yīng)飛機(jī)Si的控制基因染色體片段gi和參數(shù)基因染色體片段ci.

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

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

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

步驟6對(duì)種群中的所有染色體均重復(fù)步驟1～5.

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

2.5　適應(yīng)度函數(shù)

機(jī)位保障過程中,飛機(jī)未在過站時(shí)段結(jié)束之前完成保障產(chǎn)生的懲罰費(fèi)用和車輛行駛費(fèi)用之和為

(5)

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

(6)

2.6　選擇算子

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

3　算法驗(yàn)證

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

表3　飛機(jī)過站信息Tab.3　Aircraft turnaround information

由圖4可知：

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

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

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

表4　不同調(diào)度策略下的過站保障車輛優(yōu)化調(diào)度結(jié)果Tab.4　Optimized scheduling results based on different service vehicle scheduling strategies

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

圖5　傳統(tǒng)遺傳算法優(yōu)化性能Fig.5　Convergence effect of Traditional Genetic Algorithm

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

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

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

4　結(jié)　論

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

參考文獻(xiàn):

[1]丁建立,趙鍵濤,曹衛(wèi)東.基于貝葉斯網(wǎng)的航班過站時(shí)間動(dòng)態(tài)估計(jì)[J].南京航空航天大學(xué)學(xué)報(bào),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ī)坪航班保障工作方法研究[J].中國民航大學(xué)學(xué)報(bào),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]姚韻,朱金福,柏明國.航班過站地面服務(wù)的優(yōu)化調(diào)度算法[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ī)場規(guī)劃所需地勤保障車輛最低數(shù)量預(yù)測[J].中國民航飛行學(xué)院學(xué)報(bào),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ī)地面作業(yè)提前/拖期調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用,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]樊琳琳.大型機(jī)場地勤服務(wù)中的車輛調(diào)度問題的初步研究[D].沈陽:東北大學(xué),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.