国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2018-02-05 09:02:50張小寧
上海管理科學(xué) 2018年1期
關(guān)鍵詞:停機(jī)位航班約束

王 璐 張小寧 隋 楊 吳 輝

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

1 引言

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

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

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

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

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

2.1 問題描述

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

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

2.2 模型構(gòu)建

指標(biāo)集:

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

k:加油車型號(hào)指標(biāo);

l:加油車編號(hào)指標(biāo);

參數(shù):

N:航班及加油站集合,即N={0,1,…,n};

K:加油車型號(hào)集合,即K={0,1,…,k};

L:加油車編號(hào)集合,即L={0,1,…,l};

ti:航班i的加油時(shí)間;

Qi:航班i的需油量;

Vkl:k型號(hào)l編號(hào)加油車的油罐容量;

ri:航班i的到達(dá)時(shí)間;

aij:加油車從航班i所在停機(jī)位到航班j所在停機(jī)位的行駛時(shí)間;

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

M:一個(gè)非常大的整數(shù),用于輔助建模;

決策變量:

si:航班i的實(shí)際開始加油服務(wù)時(shí)間;

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

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

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

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

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

精確epsilon約束算法:

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

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

4.1 算例分析

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

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

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

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

算例的其他輸入信息包含如下內(nèi)容:機(jī)場(chǎng)地面加油服務(wù)部門指派兩種型號(hào)的三輛罐式加油車進(jìn)行航班加油服務(wù),機(jī)場(chǎng)目前一個(gè)時(shí)段內(nèi)有10架航班等待進(jìn)行加油服務(wù)。航班的信息,即加油車從機(jī)場(chǎng)加油站到每架航班所在停機(jī)位的行駛時(shí)間h(加油車勻速行駛速度為30 km/h),加油車從一架航班所在停機(jī)位到達(dá)另一架航班所在停機(jī)位的行駛時(shí)間a(加油車勻速行駛速度為30 km/h),每架航班加油服務(wù)時(shí)間t,每架航班的需油量Q,每架航班的到達(dá)時(shí)間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分鐘的計(jì)算時(shí)間,在個(gè)人電腦上計(jì)算求得最優(yōu)Pareto前沿解集。如圖2所示,其中橫軸表示目標(biāo)函數(shù)1的取值,縱軸表示目標(biāo)函數(shù)2的取值(最小時(shí)間單位均為1分鐘)。從圖2中可知,當(dāng)航班等待加油服務(wù)總時(shí)間最少為304個(gè)時(shí)間單位時(shí),加油車完成所有航班的加油服務(wù)時(shí)間為384個(gè)時(shí)間單位。以此類推,當(dāng)航班等待加油服務(wù)總時(shí)間為471個(gè)時(shí)間單位時(shí),加油車完成所有航班的加油服務(wù)時(shí)間最少為356個(gè)時(shí)間單位,圖2中所有星號(hào)表示最優(yōu)Pareto前沿上的點(diǎn)。

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

4.2 結(jié)論

本文通過對(duì)航班在機(jī)場(chǎng)過站期間加油車服務(wù)的調(diào)度優(yōu)化問題進(jìn)行研究,以最小化完成所有航班加油服務(wù)時(shí)間和最小化所有航班等待加油時(shí)間為優(yōu)化的雙目標(biāo),利用數(shù)學(xué)規(guī)劃理論建立整數(shù)規(guī)劃模型,并通過epsilon約束算法精確求解算例。本文提出的模型和求解方法雖有助于幫助機(jī)場(chǎng)地面服務(wù)保障部門優(yōu)化其設(shè)備資源提高航班的服務(wù)質(zhì)量,但是如果機(jī)場(chǎng)可用罐式加油車數(shù)量有限,待加油服務(wù)的航班數(shù)量多,此時(shí)的調(diào)度優(yōu)化問題會(huì)變得復(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ī)場(chǎng)地面作業(yè)調(diào)度問題研究[J]. 河北北方學(xué)院學(xué)報(bào)(自然科學(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ī)坪擺渡車實(shí)時(shí)調(diào)度系統(tǒng)仿真[J].南京航空航天大學(xué)學(xué)報(bào),2013,45(6):854-858.

[ 7 ] 黃鸝詩(shī). 基于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]. 交通運(yùn)輸系統(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.

猜你喜歡
停機(jī)位航班約束
全美航班短暫停飛
山航紅色定制航班
金橋(2021年10期)2021-11-05 07:23:10
山航紅色定制航班
金橋(2021年8期)2021-08-23 01:06:24
山航紅色定制航班
金橋(2021年7期)2021-07-22 01:55:10
“碳中和”約束下的路徑選擇
基于網(wǎng)絡(luò)流理論的停機(jī)位分配多目標(biāo)優(yōu)化模型
約束離散KP方程族的完全Virasoro對(duì)稱
基于可變禁忌長(zhǎng)度的優(yōu)化停機(jī)位分配
適當(dāng)放手能讓孩子更好地自我約束
人生十六七(2015年6期)2015-02-28 13:08:38
機(jī)場(chǎng)停機(jī)位容量?jī)?yōu)化問題研究
肥西县| 巴南区| 定日县| 林甸县| 孝义市| 瓦房店市| 德惠市| 彭阳县| 镇赉县| 哈巴河县| 潞西市| 互助| 定远县| 花垣县| 奇台县| 盐城市| 兰溪市| 克山县| 高要市| 百色市| 惠东县| 远安县| 邵东县| 高青县| 东乌珠穆沁旗| 大洼县| 和田市| 柘荣县| 旅游| 九江县| 榆中县| 牡丹江市| 柞水县| 张家口市| 新安县| 根河市| 壤塘县| 乡宁县| 富裕县| 松江区| 磐石市|