王 璐 張小寧 隋 楊 吳 輝

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

1 引言

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

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

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

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

2 問題描述和模型構建

2.1 問題描述

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

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

2.2 模型構建

指標集：

i,j：航班及補油站指標；

k：加油車型號指標；

l：加油車編號指標；

參數(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的到達時間；

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

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

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

決策變量：

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

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

(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)

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

3 Epsilon約束算法設計

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

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

精確epsilon約束算法：

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

4 算例分析和結論

4.1 算例分析

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

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

圖1 仿真實驗中加油站和停機位的坐標

表1 機場加油站和停機位坐標

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

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]，

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

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

4.2 結論

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

[ 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ā)算法的站坪調度系統(tǒng)應用研究[D]. 西安:西北工業(yè)大學,2006.

[ 3 ] 鄭潔，高劍明. 機場地面作業(yè)調度問題研究[J]. 河北北方學院學報(自然科學版)，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 ] 楊文東，陶婧婧，賈玉平. 機坪擺渡車實時調度系統(tǒng)仿真[J].南京航空航天大學學報，2013，45(6):854-858.

[ 7 ] 黃鸝詩. 基于SIMIO的機坪車輛調度仿真研究[D]. 南京：南京航空航天大學，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é)同調度研究[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.