楊 玨

(中國民航大學(xué) 基礎(chǔ)實驗中心，天津 300300)

0 引 言

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

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

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

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

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

參數(shù)定義：

Ti—航班i所需的加油服務(wù)時長；

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

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

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

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

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

其他

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

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

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

(7)

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

2 遺傳算法設(shè)計

2.1 算法原理

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

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

2.2 算法步驟

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

圖1 遺傳算法流程

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

2.3.1 編碼方式與初始化種群

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

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

2.3.2 適應(yīng)值評估

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

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

(8)

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

2.3.3 選擇操作

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

2.3.4 交叉操作

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

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

(1)隨機選取交叉點2,6。

A=0 14 6 2 9 35 7 8 10

B=0 57 5 9 1 32 4 8 10

(2)進行交叉操作。

A=0 17 5 9 1 35 7 8 10

B=0 54 6 2 9 3 24 8 10

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

A=0 14 6 9 2 35 7 8 10

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

B=0 51 6 7 9 32 4 8 10

2.3.5 變異操作

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

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

(1)隨機選取交叉點2,6。

A=0 146 2 935 7 8 10

(2)交換。

A=0 136 2 945 7 8 10

3 算例分析

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

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

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

3.1.1 停機位距離

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

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

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

表1 停機位間的距離

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

參數(shù)定義：

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

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

td—離港航班計劃時刻；

Ti—加油服務(wù)時長。

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

ai=td-Ti

(9)

bi=td-Ti-35

(10)

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

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

3.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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