基于遺傳算法的機(jī)場(chǎng)特種車輛調(diào)度應(yīng)用研究

楊 玨

(中國(guó)民航大學(xué) 基礎(chǔ)實(shí)驗(yàn)中心，天津 300300)

0 引 言

航班在機(jī)場(chǎng)過站期間，機(jī)場(chǎng)需要利用特種車輛(如清潔車、配餐車、加油車、行李車等)，為航班提供加注燃油、配餐、裝卸行李貨物等地面保障服務(wù)。車輛的優(yōu)化調(diào)度對(duì)提高航班正點(diǎn)率和資源利用率至關(guān)重要?，F(xiàn)階段國(guó)內(nèi)民航機(jī)場(chǎng)對(duì)特種車輛的調(diào)度還是基于人工編排的單車服務(wù)單航班的調(diào)度方式。這種調(diào)度方式效率低下，車輛資源的利用率不高，在航班密集的時(shí)候，極易造成航班延誤。因此為了保障機(jī)場(chǎng)內(nèi)所有過站航班都能按時(shí)接受高質(zhì)量的地面保障服務(wù)，需要對(duì)機(jī)場(chǎng)的特種車輛調(diào)度進(jìn)行研究。

機(jī)場(chǎng)特種車輛調(diào)度是帶時(shí)間窗約束的車輛路徑問題(vehicle routing problem with time window，VRPTW)[1-3]。機(jī)場(chǎng)地面服務(wù)保障部門需要安排合理的車輛行駛路線為航班提供及時(shí)的地面保障服務(wù)，實(shí)現(xiàn)在車輛續(xù)駛路程、車輛載運(yùn)量和航班時(shí)間窗等的約束條件下，所需車輛數(shù)最少、車輛總行駛距離最短和車輛調(diào)度總成本最少的目標(biāo)。Thangiah[4]和Joe[5]都曾應(yīng)用遺傳算法求解VRPTW問題,前者的目標(biāo)是使總的服務(wù)成本最小,而后者的目標(biāo)有兩個(gè),首先是使用最少的車輛,其次是在使用最少車輛的前提下使總成本最小。

文中以機(jī)場(chǎng)地面燃油加注業(yè)務(wù)為研究對(duì)象。首先，依據(jù)燃油加注業(yè)務(wù)構(gòu)建加油車輛調(diào)度的數(shù)學(xué)模型；然后，利用遺傳算法對(duì)模型進(jìn)行求解，與文獻(xiàn)[4-5]相比，文中目標(biāo)是在保證航班無延誤的前提下，使車輛調(diào)度總成本最小。該方法同樣適用于與燃油加注調(diào)度規(guī)則相似的配餐和加注清水服務(wù)的車輛調(diào)度，只需根據(jù)實(shí)際情況調(diào)整最大車載容量限制和最大車輛行駛距離等參數(shù)。

1 問題描述和數(shù)學(xué)模型

以為航班提供燃油加注服務(wù)業(yè)務(wù)為研究對(duì)象，帶時(shí)間窗的機(jī)場(chǎng)加油車輛調(diào)度問題可以簡(jiǎn)述為：機(jī)場(chǎng)有N個(gè)航班F={1,2,…,n}等待燃油加注服務(wù)，l輛加油車V={1,2,…,l}，加油車的最大行駛路程為Q，規(guī)劃加油車為航班服務(wù)的路徑方案，保證航班加油服務(wù)的及時(shí)性，實(shí)現(xiàn)加油車總行駛距離最短以及調(diào)度成本最低的目標(biāo)。

參數(shù)定義：

Ti—航班i所需的加油服務(wù)時(shí)長(zhǎng)；

dij—停機(jī)位i到停機(jī)位j間的距離；

sik—表示第k輛車為航班i加油的開始時(shí)刻，令s0k=0；如果第k輛車不為航班i加油，則sik沒有意義，k∈V。

ai—航班燃油加注服務(wù)的時(shí)間窗下限(最早開始加油時(shí)刻)；

bi—航班燃油加注服務(wù)的時(shí)間窗上限(最晚開始加油時(shí)刻)；

第k輛加油車服務(wù)完第i個(gè)航班后為第j個(gè)航班服務(wù)；

其他

數(shù)學(xué)模型表示為：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

xijk∈{0,1},?i,j∈N,?k∈V

(7)

在上述表達(dá)式中，式1是目標(biāo)函數(shù)，表示加油車輛的行駛路徑、航班的延誤時(shí)間以及車輛加油服務(wù)等待時(shí)間的加權(quán)平均值最??；式2保證每個(gè)航班僅能接受一次服務(wù)；式3表示加油車須滿足的行駛路程限制；式4～6表示車輛從車場(chǎng)出發(fā)，完成航班的燃油加注服務(wù)后，回到車場(chǎng)；式7表示航班以及車輛的整數(shù)化約束。

2 遺傳算法設(shè)計(jì)

2.1 算法原理

遺傳算法[6]是一種解決最優(yōu)化問題的有效方法。該算法模擬了達(dá)爾文的遺傳選擇和生物進(jìn)化的過程，最早由美國(guó)Michigan大學(xué)的J.Holland教授提出。

遺傳算法從一個(gè)初始種群的隨機(jī)狀態(tài)開始搜索。種群由若干被稱為“染色體”的個(gè)體構(gòu)成，每個(gè)個(gè)體都是問題的一個(gè)解。個(gè)體在種群衍化過程中不斷更新，這種更新稱為遺傳。通過“適應(yīng)值”指標(biāo)衡量種群中個(gè)體的優(yōu)劣，通過遺傳算子(交叉、變異)生成被稱為后代種群的個(gè)體，通過“適應(yīng)值”對(duì)后代個(gè)體進(jìn)行篩選，以保持種群的規(guī)模固定。經(jīng)過不斷迭代，算法最終會(huì)收斂在某個(gè)“適應(yīng)值”最好的個(gè)體，從而得出問題的最優(yōu)解或近優(yōu)解。

2.2 算法步驟

遺傳算法流程如圖1所示。

圖1 遺傳算法流程

2.3 帶時(shí)間窗的機(jī)場(chǎng)特種車輛調(diào)度問題的遺傳算法的設(shè)計(jì)

2.3.1 編碼方式與初始化種群

為了使染色體能夠簡(jiǎn)單地表示VRPTW問題的解，采用自然數(shù)編碼[7]方式。用0表示車場(chǎng)，用1,2,…,L表示待服務(wù)的航班任務(wù)。假設(shè)機(jī)場(chǎng)有一個(gè)車場(chǎng)，有K臺(tái)車，則最多存在K條航班服務(wù)路徑，每條服務(wù)路徑都始于車場(chǎng)，也終于車場(chǎng)。為了在一個(gè)染色體中反映出多條服務(wù)路徑，采用增加K-1個(gè)虛擬車場(chǎng)的方法，這K-1個(gè)虛擬車場(chǎng)分別用自然數(shù)L+1,L+2,…,L+K-1表示。這L+K-1個(gè)互不重復(fù)的自然數(shù)的排列就構(gòu)成一個(gè)染色體，并對(duì)應(yīng)一種航班服務(wù)路徑方案。

例如，現(xiàn)有8個(gè)航班(1,2,…,8)需要服務(wù)，則染色體A={0,1,4,6,2,9,3,5,7,8,10}中9,10為添加的虛擬車場(chǎng)，并且加油車輛數(shù)為2，服務(wù)的路徑分別為k1,k2。子路徑k1為：0-1-4-6-2-0；子路徑k2為：0-3-5-7-8-0。

2.3.2 適應(yīng)值評(píng)估

為了滿足生物“優(yōu)勝略汰”的進(jìn)化目的，必須對(duì)每個(gè)染色體進(jìn)行適應(yīng)值評(píng)價(jià)。染色體的適應(yīng)值決定了其在群體中的生存能力。對(duì)于航班加油服務(wù)，主要有兩個(gè)約束：(1)時(shí)間窗約束，即車輛到達(dá)航班i位置的時(shí)間既不能早于ai，也不能遲于bi；(2)車輛的續(xù)航能力約束，即某個(gè)車輛行駛的總距離不能超過車輛最大行駛路程限制。因此，在滿足上面約束的前提下，對(duì)染色體k構(gòu)造出下面的評(píng)價(jià)函數(shù):

k2*max{sik-bi,0}+k3*dij]

(8)

其中，k1,k2,k3為權(quán)重系數(shù)，滿足0≤k1,k2,k3≤1且k1+k2+k3=1。式中的前兩項(xiàng)分別為加油服務(wù)車輛的等待與加油服務(wù)的延誤時(shí)間，第三項(xiàng)考慮的是距離因素，從航班i的位置到下一個(gè)航班j位置之間的距離。

2.3.3 選擇操作

選擇操作是指在種群中選擇優(yōu)化的個(gè)體或者選擇通過配對(duì)交叉產(chǎn)生的新個(gè)體的操作。每個(gè)個(gè)體被選擇的概率與其適應(yīng)值成正比，適應(yīng)值大的個(gè)體被選擇的可能性大，適應(yīng)值小的個(gè)體被淘汰的可能性大。選擇的方法常見的有輪盤賭選擇[8]以及最佳個(gè)體保存選擇策略[9]，文中采用后者。

2.3.4 交叉操作

基于航班任務(wù)與虛擬車場(chǎng)共同排列編碼方法產(chǎn)生的染色體中的元素是互不重復(fù)的自然數(shù)，若采用簡(jiǎn)單的一點(diǎn)交叉或多點(diǎn)交叉算子，必然以極大概率產(chǎn)生不能服務(wù)所有航班的調(diào)度方案。文中采用部分匹配交叉[10]方法。定義隨機(jī)產(chǎn)生的兩個(gè)交叉點(diǎn)之間的區(qū)域?yàn)槠ヅ鋮^(qū)域，使用位置交換操作交換兩個(gè)位串的匹配區(qū)域。

例如，對(duì)染色體A={0,1,4,6,2,9,3,5,7,8,10}與染色體B={0,5,7,6,9,1,3,2,4,8,10}進(jìn)行交叉操作。

(1)隨機(jī)選取交叉點(diǎn)2,6。

A=0 14 6 2 9 35 7 8 10

B=0 57 5 9 1 32 4 8 10

(2)進(jìn)行交叉操作。

A=0 17 5 9 1 35 7 8 10

B=0 54 6 2 9 3 24 8 10

(3)對(duì)染色體A去除重復(fù)。

A=0 14 6 9 2 35 7 8 10

(4)對(duì)染色體B去除重復(fù)。

B=0 51 6 7 9 32 4 8 10

2.3.5 變異操作

遺傳算法利用變異算子[10-11]實(shí)現(xiàn)變異操作。當(dāng)遺傳算法通過交叉操作接近最優(yōu)解鄰域時(shí)，利用變異操作可以使算法加速向最優(yōu)解收斂，從而提高算法的局部隨機(jī)搜索能力，另外，引入變異操作也是為了維持群體的多樣性，以防止算法過早收斂。

例如，對(duì)染色體A={0,1,4,6,2,9,3,5,7,8,10}進(jìn)行變異操作。

(1)隨機(jī)選取交叉點(diǎn)2,6。

A=0 146 2 935 7 8 10

(2)交換。

A=0 136 2 945 7 8 10

3 算例分析

為了驗(yàn)證算法的有效性，利用機(jī)場(chǎng)的實(shí)際航班數(shù)據(jù)，實(shí)現(xiàn)機(jī)場(chǎng)燃油加注車輛的調(diào)度。

3.1 數(shù)據(jù)采集

該機(jī)場(chǎng)每天約有300個(gè)進(jìn)出港航班。加油車的平均速度設(shè)定為20 km/h，最大行駛路程設(shè)定為50 km。由于只需為離港航班提供燃油加注服務(wù)，因此選取了該機(jī)場(chǎng)某天的147個(gè)離港航班數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

3.1.1 停機(jī)位距離

停機(jī)位是指航空器在機(jī)場(chǎng)停機(jī)坪停泊的位置。為了避免剮蹭航空器，加油車輛在停機(jī)坪上必須按照規(guī)定的路線行駛。停機(jī)位的位置關(guān)系決定了加油車輛的行駛距離。該機(jī)場(chǎng)的停機(jī)坪有63個(gè)停機(jī)位，表1列出了部分停機(jī)位間的距離(m)，其中D表示車場(chǎng)。

3.1.2 離港航班加油服務(wù)時(shí)間窗

離港航班加油服務(wù)時(shí)間窗是指為航班提供加油服務(wù)的最早開始時(shí)刻(或稱加油服務(wù)時(shí)間窗下限，單位：時(shí)刻)和最晚開始時(shí)刻(或稱加油服務(wù)時(shí)間窗上限，單位：時(shí)刻)限制的時(shí)間范圍，加油車輛必須在這個(gè)時(shí)間范圍內(nèi)開始為航班提供燃油加注服務(wù)，否則將可能導(dǎo)致航班延誤。

表1 停機(jī)位間的距離

按照民航局地面服務(wù)規(guī)范：燃油加注保障服務(wù)應(yīng)在航班開始登機(jī)前5分鐘完成，航班一般在計(jì)劃離港時(shí)間前30分鐘開始登機(jī)。依據(jù)該服務(wù)規(guī)范，確定航班加油服務(wù)的時(shí)間窗下限和時(shí)間窗上限。

參數(shù)定義：

ai—加油服務(wù)時(shí)間窗下限(最早開始加油時(shí)刻)；

bi—加油服務(wù)時(shí)間窗上限(最晚開始加油時(shí)刻)；

td—離港航班計(jì)劃時(shí)刻；

Ti—加油服務(wù)時(shí)長(zhǎng)。

離港航班加油服務(wù)時(shí)間窗：

ai=td-Ti

(9)

bi=td-Ti-35

(10)

按照式9和式10可以計(jì)算每個(gè)離港航班的加油服務(wù)時(shí)間窗。為了便于計(jì)算，將時(shí)間統(tǒng)一轉(zhuǎn)化為分鐘。部分離港航班的加油服務(wù)時(shí)間窗如表2所示。

表2 離港航班加油服務(wù)時(shí)間窗(部分)

3.2 結(jié)果分析

利用Matlab工具軟件實(shí)現(xiàn)文中算法。采用軟時(shí)間窗約束，允許加油車輛等待被服務(wù)航班，允許加油服務(wù)延誤。若將航班延誤的懲罰系數(shù)設(shè)以最大值，則可表示此解不可行，即在選擇過程中此解會(huì)被淘汰，即不允許加油服務(wù)延誤。

為了使結(jié)果能最大限度地趨于最優(yōu)值，將所有方案的種群最大規(guī)模設(shè)為200，迭代次數(shù)設(shè)為200。

方案一：隨機(jī)生成種群，分別用不同的交叉算子和變異算子進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果如表3所示。

表3 遺傳算法求解結(jié)果

方案二：利用最近插入法[12]生成初始種群的初值，實(shí)驗(yàn)結(jié)果如表4所示。

表4 利用最近插入法生成初始種群的 遺傳算法求解結(jié)果

方案三：利用禁忌搜索法[13]生成初始種群的初值，實(shí)驗(yàn)結(jié)果如表5所示。

方案一中由于遺傳算法的初始解為隨機(jī)解，而初始種群規(guī)模不大且遺傳代數(shù)不夠，導(dǎo)致最終解質(zhì)量較差。方案二求解的路徑長(zhǎng)度為61 300 m，等待時(shí)間為321.3 min，延誤時(shí)間為0 min。方案三求解的路徑長(zhǎng)度29 240 m,等待時(shí)間為761.941 2 min，延誤時(shí)間為0 min。方案二與方案三均可用遺傳算法使解進(jìn)一步優(yōu)化且能得到較優(yōu)解。

表5 利用禁忌搜索法生成初始種群的 遺傳算法求解結(jié)果

選取方案二中(如表4所示)第3次運(yùn)行的結(jié)果作為最優(yōu)值，車輛總路程為65 200 m，無延誤時(shí)間，等待時(shí)間為265.8 min，而單車單航班服務(wù)方式總路程為88 320 m，車輛的總行駛路程減少26.2%。

4 結(jié)束語

根據(jù)機(jī)場(chǎng)燃油加注保障服務(wù)的業(yè)務(wù)構(gòu)建了燃油加注車輛調(diào)度的數(shù)學(xué)模型，利用基于不同搜索策略的遺傳算法求出滿足軟時(shí)間窗限制且調(diào)度成本最低的車輛調(diào)度解決方案。通過對(duì)最大車載容量限制，最大車輛行駛距離以及適應(yīng)值函數(shù)設(shè)置不同的參數(shù),該解決方案也適用于機(jī)場(chǎng)提供配餐服務(wù)和加注清水服務(wù)的車輛調(diào)度。

在航班保障服務(wù)實(shí)際運(yùn)行中，由于航班計(jì)劃時(shí)刻容易受到天氣、航路管制等因素的影響，車輛的調(diào)度方案要根據(jù)航班時(shí)刻的變化做適時(shí)調(diào)整。后期需要在該靜態(tài)調(diào)度方案的基礎(chǔ)上，對(duì)車輛的動(dòng)態(tài)調(diào)度[14]做進(jìn)一步研究。