機(jī)場罐式加油車服務(wù)調(diào)度雙目標(biāo)優(yōu)化研究

王 璐 張小寧 隋 楊 吳 輝

(1. 上海民航職業(yè)技術(shù)學(xué)院，上海 200232；2. 同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，上海 200092；3. 東華大學(xué) 旭日工商管理學(xué)院，上海 200051)

1 引言

近年，隨著民航業(yè)的快速發(fā)展，機(jī)場規(guī)模和業(yè)務(wù)量日益擴(kuò)大，繁忙機(jī)場面臨的運行效率較低、地面設(shè)備調(diào)配不足的瓶頸問題日益突出?？焖賾?yīng)對機(jī)場基本業(yè)務(wù)，不僅能保障航班正常運行、提高乘客滿意度，也能有效降低機(jī)場與航空公司的成本，使場面作業(yè)高效運行。如何在資源設(shè)備有限的情況下，充分利用現(xiàn)有資源快速完成地面作業(yè)，是當(dāng)前機(jī)場與航空公司共同面臨的問題之一。

航班地面服務(wù)是機(jī)場運行的重要環(huán)節(jié)。航班地面服務(wù)調(diào)度主要指對各種航班地面保障車輛的合理調(diào)度。在大型樞紐機(jī)場，航班的起落具有短時、高密度的特點，對地面服務(wù)的需求較為集中，調(diào)度不當(dāng)有可能造成航班延誤，造成不必要的損失。地面設(shè)備作業(yè)具有嚴(yán)格的流程性，如加油車因存在安全隱患，只有當(dāng)加油服務(wù)完成后才能進(jìn)行上客服務(wù)，且不同類型航班所需的服務(wù)時間不同，因此保障加油車的合理調(diào)度為實現(xiàn)后續(xù)地面正常作業(yè)奠定了基礎(chǔ)。

目前，關(guān)于機(jī)場地面服務(wù)的調(diào)度問題，國內(nèi)外已有很多的研究。Angus Cheung等(2005)[1]以最小化車輛總流轉(zhuǎn)時間為目標(biāo)，分別進(jìn)行了牽引車、清水車、清潔車的單獨調(diào)度。王博濤(2006)[2]采用分解策略和多目標(biāo)權(quán)衡策略將機(jī)場站坪調(diào)度分為機(jī)位指派和機(jī)坪保障設(shè)施調(diào)度問題。鄭潔等(2008)[3]研究了機(jī)場服務(wù)設(shè)備的利用率問題，運用妥協(xié)約束法和遺傳算法使得設(shè)備總流經(jīng)時間最少。Xing Z等(2012)[4]基于博弈論對機(jī)場除冰車的調(diào)度進(jìn)行了研究。Norin A等(2012)[5]以最小化由除冰服務(wù)引起的航班延誤、最小化除冰車的行駛距離為目標(biāo)對除冰車的優(yōu)化調(diào)度進(jìn)行了研究。楊文東等(2013)[6]以最小化車輛工作量、車輛行駛距離和車輛數(shù)為目標(biāo)，建立了機(jī)場擺渡車的調(diào)度仿真模型。黃鸝詩(2013)[7]采用了SIMIO分別對加油車和擺渡車的調(diào)度進(jìn)行仿真，以平衡設(shè)備工作量和航班延誤最少為優(yōu)化目標(biāo)建立了優(yōu)化模型。Jia Yan Du等(2014)[8]研究了航班過站作業(yè)中的拖車作業(yè)調(diào)度，以最小化運營成本為優(yōu)化目標(biāo)、以拖車運營限制為約束建立了MIP模型，使用了列代啟發(fā)式算法對模型進(jìn)行求解。馮霞等(2016)[9]以至少需要的保障車輛數(shù)目和服務(wù)總開始時間最早為目標(biāo)，研究構(gòu)建了遠(yuǎn)機(jī)位航班加油服務(wù)和上客服務(wù)的協(xié)同調(diào)度模型，并給出了基于多目標(biāo)遺傳算法的模型求解。

本文在研究機(jī)場罐式加油車為航班加油服務(wù)問題的基礎(chǔ)上，建立了考慮每架航班所在停機(jī)位與機(jī)場加油站之間的距離和加油車在停機(jī)位之間的移動時間在內(nèi)的整數(shù)規(guī)劃模型，提出了以最小化完成航班加油服務(wù)時間和最小化航班等待加油時間的雙目標(biāo)規(guī)劃模型，進(jìn)而開發(fā)epsilon約束算法精確求解所建立的雙目標(biāo)規(guī)劃模型獲得Pareto前沿，并通過數(shù)值例子說明模型的有效性和算法可行性。文章在第二部分詳細(xì)介紹了本文所研究的問題并構(gòu)建了整數(shù)規(guī)劃模型；第三部分設(shè)計了epsilon約束算法；第四部分以一個算例驗證了模型的可行性和算法的有效性并最后給出結(jié)論。

2 問題描述和模型構(gòu)建

2.1 問題描述

為保證航班的正常安全飛行，航班在機(jī)場過站期間需接受一系列的地面服務(wù)，此時機(jī)場相關(guān)部門會調(diào)用機(jī)場地面設(shè)備開始對航班進(jìn)行一系列的地面服務(wù)，地面設(shè)備有行李車、加油車、擺渡車等。機(jī)場在一個時段內(nèi)會有多個航班?？吭诓煌耐C(jī)位，當(dāng)航班?？糠€(wěn)定，地面設(shè)備開始作業(yè)。加油車不同于行李車、擺渡車等，加油車存在一定的安全隱患，航班需完成下客服務(wù)后再進(jìn)行加油服務(wù)。因此，當(dāng)航班完成下客服務(wù)后，罐式加油車開往飛機(jī)機(jī)翼加油處，將罐內(nèi)的航空燃油安全、快速地輸入飛機(jī)油箱。現(xiàn)機(jī)場大部分停機(jī)位有機(jī)井口，航班加油可通過管線加油車直接加油，少數(shù)停機(jī)位沒有機(jī)井，需要使用罐式加油車為航班加油。因罐式加油車容量有限，一次最多只能服務(wù)有限個航班，當(dāng)前多數(shù)機(jī)場的罐式加油車一次可服務(wù)至少兩架航班，所以如何使機(jī)場加油車以盡可能低的成本高效率地完成地面加油服務(wù)作業(yè)，同時降低航班因機(jī)場地面作業(yè)延誤而帶來的經(jīng)濟(jì)損失，提高航空公司的服務(wù)質(zhì)量，是目前機(jī)場亟需解決的問題，也是本文的研究重點。

本文以機(jī)場罐式加油車為研究對象，以下簡稱加油車。機(jī)場無機(jī)井停機(jī)位在某個時間段內(nèi)停有數(shù)架航班等待進(jìn)行加油服務(wù)，現(xiàn)機(jī)場停有不同型號、不同數(shù)量的加油車，地面加油服務(wù)相關(guān)部門根據(jù)某一時段內(nèi)機(jī)場所有降落航班的需油量指派加油車進(jìn)行加油服務(wù)，所有被指派的加油車油量能充分滿足該時段所有待加油服務(wù)航班的需油量。加油車在機(jī)場加油站注滿油后駛向停機(jī)位為航班加油，完成一個航班的加油服務(wù)后，加油車再開往下一個停機(jī)位為另一架航班進(jìn)行加油服務(wù)，直到該加油車所剩的油量不能滿足其余還未加油航班的需油量。針對加油車在油罐容量有限的條件下對所有航班進(jìn)行加油服務(wù)，使得加油車在有效成本范圍內(nèi)加油效率最大化且航班等待加油服務(wù)時間最小化，因此，本文以航班最小化完成所有航班加油服務(wù)時間為第一個目標(biāo)，以所有航班等待加油時間最小為第二個目標(biāo)。其中假設(shè)：(1)加油車勻速行駛；(2)加油車注油時間不計；(3)停機(jī)位之間的距離小于停機(jī)位到加油站的距離。

2.2 模型構(gòu)建

指標(biāo)集：

i,j：航班及補(bǔ)油站指標(biāo)；

k：加油車型號指標(biāo)；

l：加油車編號指標(biāo)；

參數(shù)：

N：航班及加油站集合，即N={0,1,…,n}；

K：加油車型號集合，即K={0,1,…,k}；

L：加油車編號集合，即L={0,1,…,l}；

ti：航班i的加油時間；

Qi：航班i的需油量；

Vkl：k型號l編號加油車的油罐容量；

ri：航班i的到達(dá)時間；

aij：加油車從航班i所在停機(jī)位到航班j所在停機(jī)位的行駛時間；

a0i：加油車從加油站到航班i所在停機(jī)位的行駛時間；

M：一個非常大的整數(shù)，用于輔助建模；

決策變量：

si：航班i的實際開始加油服務(wù)時間；

基于上述參數(shù)和變量的定義，機(jī)場加油車調(diào)度優(yōu)化模型建立如下，其中，i或j為0表示機(jī)場加油站：

(1)

(2)

{i≠j}∈N，k∈K,l∈L

(3)

{i≠j}∈N，k∈K,l∈L

(4)

{i≠j}∈N，k∈K,l∈L

(5)

(6)

(7)

{i≠j},∈N，k∈K,l∈L

(8)

{i≠j},∈N，k∈K,l∈L

(9)

(10)

(11)

(12)

{i≠j}∈N，k∈K,l∈L

(13)

(14)

si≥ri,i∈N

(15)

(16)

(17)

(18)

(19)

(20)

(21)

目標(biāo)函數(shù)(1)表示最小化所有航班加油服務(wù)完成時間；目標(biāo)函數(shù)(2)表示最小化所有航班等待加油服務(wù)時間；約束(3)表示被同一輛加油車服務(wù)的兩架航班，后續(xù)航班的加油開始時間不晚于前面航班的加油完成時間；約束(4)和(5)表示航班被某輛加油車服務(wù)的順序；約束(6)和(7)表示航班沒有被某加油車服務(wù)時其順序號為0；約束(8)和(9)表示兩架航班都被同一輛加油車服務(wù)且是緊鄰先后關(guān)系時其加油順序也是緊鄰；約束(10)和(11)表示所有加油車都是從機(jī)場加油站出發(fā)進(jìn)行加油服務(wù)；約束(12)和(13)表示加油車服務(wù)兩個航班一定存在先后順序；約束(14)表示所有航班緊鄰的先后順序之和等于加油航班數(shù)；約束(15)表示航班實際加油時間不晚于航班到達(dá)時間；約束(16)、(17)和(18)表示航班被加油車服務(wù)與兩架航班被同一輛加油車先后服務(wù)和緊鄰服務(wù)之間的關(guān)系；約束(19)表示被某輛加油車服務(wù)的所有航班總需油量不大于該輛加油車的油罐容量；約束(20)和(21)表示決策變量的取值范圍。

3 Epsilon約束算法設(shè)計

為了精確求解該雙目標(biāo)優(yōu)化問題，即獲得最優(yōu)Pareto前沿，本文使用Epsilon約束算法對所建立的雙目標(biāo)模型進(jìn)行優(yōu)化求解。Epsilon約束算法是求解多目標(biāo)優(yōu)化最為常用的精確算法。為了說明該精確求解雙目標(biāo)所使用的epsilon約束算法，首先介紹Pareto占優(yōu)概念。對于最小化雙目標(biāo)函數(shù)而言，Pareto占優(yōu)關(guān)系(<2)可以定義為：如果說一個可行解X占優(yōu)于另一個可行解Y(其中X，Y為向量)，那么一定有f1(X)≤ f1(Y)和f2(X)≤ f2(Y)并且要求至少一個不等式取為嚴(yán)格小于號。在目標(biāo)函數(shù)可行解空間里所有未被占優(yōu)的點構(gòu)成了Pareto前沿(Pareto Front)。在這個前沿上，任意兩個點間不存在占優(yōu)關(guān)系。這個解集包含了一系列不同的點(每個點為一個二元組)，這些點用于決策者進(jìn)行雙目標(biāo)函數(shù)值間的權(quán)衡。Epsilon約束法的思想是通過轉(zhuǎn)化一個目標(biāo)為約束，構(gòu)建并求解一系列epsilon約束問題。這一系列epsilon約束問題間是通過逐步減少的epsilon值來聯(lián)系起來的(請參看Berube等[10])。為了描述epsilon約束法，還需要定義下面三類點：

由于我們建立的雙目標(biāo)模型中兩個目標(biāo)都是最小化并且目標(biāo)函數(shù)值都為整數(shù)，epsilon約束算法可以表達(dá)如下。

精確epsilon約束算法：

步驟4：通過從集合F’中移除被占優(yōu)的點，得到Pareto前沿F。

4 算例分析和結(jié)論

4.1 算例分析

為驗證模型的可行性和求解算法的高效性，設(shè)計如下算例。假設(shè)機(jī)場在某一時段內(nèi)有10架航班停在無機(jī)井的停機(jī)位等待加油服務(wù)，我們以1分鐘為一個最小時間單位。利用Matlab 2014編寫epsilon約束算法(調(diào)用CPLEX12.6求解單一epsilon問題)在個人電腦(i5CPU，3.0GHz處理器)上進(jìn)行精確求解。

本文按照圖1的機(jī)場航班所在停機(jī)位坐標(biāo)信息進(jìn)行仿真實驗，表1是機(jī)場加油站和航班所在停機(jī)位對應(yīng)的坐標(biāo)位置，表格中的單位為km。例如在表1中，標(biāo)號0是機(jī)場加油站，在圖1中也可以找到對應(yīng)加油站的位置。

圖1 仿真實驗中加油站和停機(jī)位的坐標(biāo)

表1 機(jī)場加油站和停機(jī)位坐標(biāo)

算例的其他輸入信息包含如下內(nèi)容：機(jī)場地面加油服務(wù)部門指派兩種型號的三輛罐式加油車進(jìn)行航班加油服務(wù)，機(jī)場目前一個時段內(nèi)有10架航班等待進(jìn)行加油服務(wù)。航班的信息，即加油車從機(jī)場加油站到每架航班所在停機(jī)位的行駛時間h(加油車勻速行駛速度為30 km/h)，加油車從一架航班所在停機(jī)位到達(dá)另一架航班所在停機(jī)位的行駛時間a(加油車勻速行駛速度為30 km/h)，每架航班加油服務(wù)時間t，每架航班的需油量Q，每架航班的到達(dá)時間r，每輛罐式加油車的油罐容量V，隨機(jī)生成如下：

t：[21 25 25 21 21 23 27 23 25 21]，

Q：[15000 1700 17000 15000 15000 16000 18000 16000 17000 15000]，

r：[39 58 24 72 11 57 39 49 19 24]，

V：[55000 55000 60000]，

h：[18 26 28 26 30 26 30 20 36 34]，

經(jīng)過不到3分鐘的計算時間，在個人電腦上計算求得最優(yōu)Pareto前沿解集。如圖2所示，其中橫軸表示目標(biāo)函數(shù)1的取值，縱軸表示目標(biāo)函數(shù)2的取值(最小時間單位均為1分鐘)。從圖2中可知，當(dāng)航班等待加油服務(wù)總時間最少為304個時間單位時，加油車完成所有航班的加油服務(wù)時間為384個時間單位。以此類推，當(dāng)航班等待加油服務(wù)總時間為471個時間單位時，加油車完成所有航班的加油服務(wù)時間最少為356個時間單位，圖2中所有星號表示最優(yōu)Pareto前沿上的點。

圖2 最優(yōu)Pareto前沿解

4.2 結(jié)論

本文通過對航班在機(jī)場過站期間加油車服務(wù)的調(diào)度優(yōu)化問題進(jìn)行研究，以最小化完成所有航班加油服務(wù)時間和最小化所有航班等待加油時間為優(yōu)化的雙目標(biāo)，利用數(shù)學(xué)規(guī)劃理論建立整數(shù)規(guī)劃模型，并通過epsilon約束算法精確求解算例。本文提出的模型和求解方法雖有助于幫助機(jī)場地面服務(wù)保障部門優(yōu)化其設(shè)備資源提高航班的服務(wù)質(zhì)量，但是如果機(jī)場可用罐式加油車數(shù)量有限，待加油服務(wù)的航班數(shù)量多，此時的調(diào)度優(yōu)化問題會變得復(fù)雜。如何解決該種情況下加油車服務(wù)的調(diào)度優(yōu)化，是今后進(jìn)一步的研究方向。

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

[ 2 ] 王博濤. 基于遺傳與啟發(fā)算法的站坪調(diào)度系統(tǒng)應(yīng)用研究[D]. 西安:西北工業(yè)大學(xué),2006.

[ 3 ] 鄭潔，高劍明. 機(jī)場地面作業(yè)調(diào)度問題研究[J]. 河北北方學(xué)院學(xué)報(自然科學(xué)版)，2008,24(6):60-62.

[ 4 ] XING Z，LIAN G. Cooperative game theoretical research for aircraft deicing operation scheduling[C]. Intelligent Control and Automation. IEEE,2012:2407-2411.

[ 5 ] NORIN A, VARBRAND P. Scheduling de-icing vehicles within airport logistics: a heuristic algorithm and performance evaluation[J]. Journal of the Operational Research Society,2012,63(8):1116-1125.

[ 6 ] 楊文東，陶婧婧，賈玉平. 機(jī)坪擺渡車實時調(diào)度系統(tǒng)仿真[J].南京航空航天大學(xué)學(xué)報，2013，45(6):854-858.

[ 7 ] 黃鸝詩. 基于SIMIO的機(jī)坪車輛調(diào)度仿真研究[D]. 南京：南京航空航天大學(xué)，2013.

[ 8 ] Du J Y, BRUNNER J O, KOLISCH R,Planning towing processes at airports more efficiently[J].Transportation Research Part E: Logistics and Transportation Review, 2014, 70(1):293-304.

[ 9 ] 馮霞，任子云. 基于遺傳算法的加油車和擺渡車協(xié)同調(diào)度研究[J]. 交通運輸系統(tǒng)工程與信息，2016(2):155-163.

[10] BERUBE J F, GENDREAU M, Potvin J Y. An exact ε-constraint method for bi-objective combinatorial optimization problems: application to the traveling salesman problem with profits[J]. European Journal of Operational Research, 2009,194(1): 39-50.