基于NSGA-Ⅱ的多目標(biāo)航班登機(jī)口調(diào)度研究

文笑雨，孫海強(qiáng)，王蒙，馮士浩

(鄭州輕工業(yè)大學(xué) 河南省機(jī)械裝備智能制造重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450002)

0 引 言

近幾年，由于旅游業(yè)的快速發(fā)展，民航客運(yùn)量大幅增加，各大機(jī)場(chǎng)相繼出現(xiàn)了候機(jī)緊張的狀況，飛機(jī)在登機(jī)口調(diào)度的不合理性已經(jīng)成為航班延誤的重要原因之一[1]。為了適應(yīng)未來(lái)的發(fā)展，解決登機(jī)口的調(diào)度問(wèn)題，機(jī)場(chǎng)往往都會(huì)新建候機(jī)樓或擴(kuò)大候機(jī)樓的面積，隨之登機(jī)口的數(shù)量也會(huì)相應(yīng)增加。雖然增加登機(jī)口可以緩解候機(jī)緊張的壓力，但是對(duì)中轉(zhuǎn)旅客的航班銜接具有一定的影響，這增加了中轉(zhuǎn)旅客步行時(shí)間，削弱了民航運(yùn)輸?shù)谋憬莩潭萚2]，因此，減少中轉(zhuǎn)旅客的步行時(shí)間對(duì)于機(jī)場(chǎng)管理具有非常重要的意義。

僅考慮登機(jī)口分配的航班-登機(jī)口的優(yōu)化分配問(wèn)題已經(jīng)被很好地解決了[3]，在登機(jī)口調(diào)度過(guò)程中考慮減少中轉(zhuǎn)旅客的步行時(shí)間，屬于多目標(biāo)下的優(yōu)化調(diào)度問(wèn)題。近年來(lái)，多目標(biāo)登機(jī)口的調(diào)度問(wèn)題逐漸成為了研究熱點(diǎn)。A.Drexl 等[4]進(jìn)一步討論H.Ding等[5]的模型，模型中考慮了航空公司對(duì)登機(jī)口的偏好，建立了多目標(biāo)優(yōu)化數(shù)學(xué)模型，最后通過(guò)帕累托模擬退火算法求解；B.Maharjan 等[6]建立了登機(jī)口網(wǎng)絡(luò)流優(yōu)化模型，以最小化飛機(jī)在機(jī)場(chǎng)地面的航空燃油費(fèi)用和總的乘客不滿意度為優(yōu)化目標(biāo)進(jìn)行優(yōu)化；U.Dorndorf 等[7]考慮了登機(jī)可用性約束建立模型，并設(shè)計(jì)啟發(fā)式算法分階段求解;TANG C H等[8]將航班偏好作為優(yōu)化目標(biāo)的主要影響因素進(jìn)行了分析研究；王志清等[2]在圖論的基礎(chǔ)上建立了登機(jī)口的網(wǎng)絡(luò)模型，提出了該模型在使用中的實(shí)用算法，其結(jié)果縮短了旅客步行距離，提高了設(shè)施利用率；WU D等[9]提出了以最小化乘客步行距離和最小化各登機(jī)口被使用量為優(yōu)化目標(biāo)的多目標(biāo)優(yōu)化模型，設(shè)計(jì)了一種基于蟻群協(xié)同策略和信息素更新策略的改進(jìn)蟻群優(yōu)化算法(ICQACO)求解。由上述文獻(xiàn)可知，針對(duì)優(yōu)化分配登機(jī)口的同時(shí)考慮最小化旅客總步行時(shí)間的研究仍很有限。因此，本文針對(duì)多目標(biāo)航班登機(jī)口調(diào)度問(wèn)題開(kāi)展了研究，以最小化登機(jī)口總使用量、最小化旅客總步行時(shí)間為優(yōu)化目標(biāo)，設(shè)計(jì)了這兩個(gè)優(yōu)化目標(biāo)的函數(shù)，提出基于NSGA-Ⅱ算法求解，以快速非支配排序及擁擠距離為適應(yīng)度評(píng)價(jià)方法，根據(jù)柔性作業(yè)車間調(diào)度問(wèn)題與航班登機(jī)口調(diào)度問(wèn)題的共性特點(diǎn)進(jìn)行類比，提出一種問(wèn)題假設(shè)與數(shù)據(jù)處理方法，采用基于工序、基于加工機(jī)器分配的兩部分編碼方法，最后通過(guò)對(duì)實(shí)例的求解，驗(yàn)證所建立數(shù)學(xué)模型和設(shè)計(jì)算法的有效性。

1 多目標(biāo)航班登機(jī)口調(diào)度模型

1.1 問(wèn)題描述

多目標(biāo)航班登機(jī)口調(diào)度問(wèn)題的描述如下：某機(jī)場(chǎng)共有m個(gè)可用登機(jī)口，其中國(guó)際廳T擁有r個(gè)登機(jī)口(可?？咳我夂桨嗲揖哂谐鋈刖彻δ?，國(guó)內(nèi)廳S 擁有k個(gè)登機(jī)口(僅可?？匡w往國(guó)內(nèi)的航班)，國(guó)際廳T與國(guó)內(nèi)廳S之間存在一段距離，如圖1所示，對(duì)于中轉(zhuǎn)旅客需步行一段路程。已知n個(gè)航班在登機(jī)口上的啟用與停用時(shí)間。本文的調(diào)度目標(biāo)是在上述已知條件下確定各個(gè)航班的登機(jī)口位置、確定登機(jī)口各個(gè)航班停靠順序，使得多種性能指標(biāo)得到兼顧，從而確定一組均衡解。

為了形象描述多目標(biāo)航班登機(jī)口調(diào)度問(wèn)題，以9個(gè)航班的?？啃畔槔?表1)，該機(jī)場(chǎng)有5個(gè)登機(jī)口，其中T廳2個(gè)(M1，M2)，S廳3個(gè)(M3，M4，M5)，則9個(gè)航班5個(gè)登機(jī)口的調(diào)度問(wèn)題求解包括兩部分：確定9個(gè)航班的登機(jī)口；確定5個(gè)登機(jī)口當(dāng)天所有航班的?？宽樞颉１?給出了該問(wèn)題的一種求解結(jié)果。

圖1 國(guó)際廳與國(guó)內(nèi)廳位置示意圖

Fig.1 Schematic diagram of the international and domestic offices

表1 9個(gè)航班的?？啃畔?/p>

表2 9個(gè)航班5個(gè)登機(jī)口調(diào)度問(wèn)題的求解結(jié)果

1.2 數(shù)學(xué)模型

針對(duì)多目標(biāo)航班登機(jī)口調(diào)度問(wèn)題，本文以最小化登機(jī)口總使用量和最小化旅客最大總步行時(shí)間為性能指標(biāo)，建立如下條件假設(shè)：

(1)同一登機(jī)口同一時(shí)刻只能?？恳患茱w機(jī)。

(2)不論S廳還是T廳登機(jī)口?？康娘w機(jī)必須在同一登機(jī)口出發(fā)。

(3)航班在各個(gè)登機(jī)口的啟用與停用時(shí)間已知且相同。

這兩種性能指標(biāo)的目標(biāo)函數(shù)定義如下。

(1)f1：最小化登機(jī)口總使用量(sum)

(1)

(2)f2:最小化旅客最大總步行時(shí)間(Tp)

minTp={maxPTj，j=1，…，m},

(2)

pnj，k為j登機(jī)口k航班的中轉(zhuǎn)人數(shù)；twalk步行時(shí)間；PTj為j登機(jī)口所有航班的總步行時(shí)間。

決策變量包括登機(jī)口的選擇決策xk，r、登機(jī)口航班的排序決策yj，k，k′以及中轉(zhuǎn)旅客步行時(shí)間的決策Ωj，k。

(3)

式中,xk，j=1 時(shí)為k航班在j登機(jī)口?？?，xk，j=0時(shí)為k航班不?？吭趈登機(jī)口。

(4)

式中,yj，k，k′=1時(shí)為j登機(jī)口k航班在k′航班之前?？?，yj，k，k′=0時(shí)為j登機(jī)口k航班在k′航班之后?？俊?/p>

(5)

式中：Ωj，k=1時(shí)為j登機(jī)口的k航班不是T廳到達(dá)T廳出發(fā)，即k航班的中轉(zhuǎn)旅客需要一定的步行時(shí)間，Ωj，k=0時(shí)為j登機(jī)口的k航班是T廳到達(dá)T廳出發(fā)，k航班上的中轉(zhuǎn)旅客不需要步行。

S.T.同一登機(jī)口各航班的?？繒r(shí)間順序約束

(Cj，k-Cj，k′-tj，k)×xk，j×xk′，j×yj，k，k′≥0, (6)

式中：Cj，k，Cj，k′為j登機(jī)口k航班和k′航班的出發(fā)時(shí)間;tj，k為j登機(jī)口k航班的?？繒r(shí)長(zhǎng)。

每個(gè)航班僅能選擇一個(gè)登機(jī)口?？?/p>

(7)

式中，Mk為k航班可停靠的登機(jī)口集合。

1.3 問(wèn)題假設(shè)與數(shù)據(jù)處理

柔性作業(yè)車間調(diào)度問(wèn)題中每個(gè)工件包含多道工序，調(diào)度目標(biāo)是為每道工序選擇最合適的加工機(jī)器、確定每臺(tái)機(jī)器上各工件工序的最佳加工順序及開(kāi)完工時(shí)間，對(duì)于航班登機(jī)口調(diào)度問(wèn)題，各航班的到達(dá)、出發(fā)時(shí)間是預(yù)先確定的(工件的開(kāi)完工時(shí)間已確定)，調(diào)度的目標(biāo)是確定每個(gè)航班最合適的登機(jī)口(每道工序選擇最合適的加工機(jī)器)、確定每個(gè)登機(jī)口當(dāng)天停靠飛機(jī)的最佳順序(每臺(tái)機(jī)器上各工件的加工順序)。由于航班登機(jī)口調(diào)度與柔性作業(yè)車間調(diào)度存在一些共性特點(diǎn)，因此本文將航班登機(jī)口調(diào)度問(wèn)題與柔性作業(yè)車間調(diào)度問(wèn)題進(jìn)行類比，并做出如下問(wèn)題假設(shè)：

(1)各航班的到達(dá)、出發(fā)時(shí)間是預(yù)先確定的，基于此可將停靠時(shí)間段互不交叉的航班假設(shè)為同一工件中的不同工序，將?？繒r(shí)間段發(fā)生沖突的航班假設(shè)為不同工件的工序。

(2)每個(gè)登機(jī)口同一時(shí)間段內(nèi)只能?？恳患芎桨?，類似于每臺(tái)機(jī)器上同一時(shí)間僅能加工一個(gè)工件，故將所有的登機(jī)口設(shè)為各個(gè)工件的加工機(jī)器。

以表1中9個(gè)航班的?？啃畔槔?，根據(jù)問(wèn)題假設(shè)，對(duì)9個(gè)航班進(jìn)行隨機(jī)分配，確定各個(gè)航班的工件號(hào)，按照時(shí)間的先后順序?qū)w屬于各個(gè)工件的航班進(jìn)行排列，確定各個(gè)航班的工序號(hào)，如表4所示。

表4 9個(gè)航班的工件歸屬信息

2 基于NSGA-Ⅱ求解的多目標(biāo)航班登機(jī)口調(diào)度問(wèn)題

NSGA-Ⅱ(A Non-dominated Sorting Genetic Algorithm-II)算法是WU D等[9]于 2000 年在 NSGA 的基礎(chǔ)上提出的。它是目前最流行的多目標(biāo)優(yōu)化算法之一，廣泛應(yīng)用于諸多組合優(yōu)化問(wèn)題。該算法可同時(shí)兼顧多個(gè)優(yōu)化目標(biāo)。

2.1 編碼、解碼與初始化

對(duì)于多目標(biāo)航班登機(jī)口調(diào)度，編碼由兩部分組成：第一部分采用基于工序的編碼方法[10]；第二部分采用基于機(jī)器分配的編碼方法[11]。具體編碼操作如下。

(1)基于工序的編碼。該編碼方法是以染色體基因序列中某工件號(hào)的出現(xiàn)次數(shù)定義該工件待加工的工序號(hào)，染色體基因的個(gè)數(shù)為所有工件的工序的總數(shù)，即當(dāng)日航班總數(shù)。表4給出了9個(gè)航班的工件歸屬信息，設(shè)表5的1條染色體基因序列為[1 2 1 2 3 2 3 1 3]，該染色體共有9個(gè)基因，其中3個(gè)1依次代表著歸屬于工件J1的3個(gè)航班分別為O1(GN001)、O2(GN004)、O3(GN007)，染色體中2，3為歸屬于工件J2、J3的航班。

(2)基于機(jī)器分配的編碼。基于機(jī)器分配編碼的基因序列長(zhǎng)度為工序總數(shù)l(當(dāng)日航班總數(shù))，分別用工序號(hào)1，2，…，l表示。根據(jù)l道工序形成了l個(gè)可選機(jī)器的子集{S1，S2，…，Si，…，Sl}，Si為第i個(gè)工序的加工機(jī)器集合，即第i個(gè)航班登機(jī)口集合，表示為{m1i，m2i，…，mni}，Si中每個(gè)元素均為登機(jī)口。

基于機(jī)器分配編碼的基因序列表示為[g1，g2，…，gi，…，gl]，gi為集合Si中的第gi個(gè)登機(jī)口mgi。以表4工件歸屬信息為例，染色體基因序列[1 2 1 2 3 2 3 1 3]中的第二個(gè)基因2代表著歸屬于工件J2的航班O1(GN002)。由表1可知，該航班擁有兩個(gè)登機(jī)口S2={1，2}，若設(shè)機(jī)器基因序列[2 1 2 1 2 1 2 1 3]，則g2=1，可確定航班O1(GN002)的登機(jī)口為S2中的第1個(gè)登機(jī)口M1，以此類推，可確定染色體序列中各個(gè)航班的登機(jī)口，如圖2所示。

圖2 基于機(jī)器分配編碼的解碼過(guò)程

基于機(jī)器分配編碼的機(jī)器序列確定各個(gè)航班的登機(jī)口為解碼第一步，第二步按基于工序編碼的染色體序列確定登機(jī)口各個(gè)航班的?？宽樞?，從而完成整個(gè)解碼過(guò)程。本文在解碼過(guò)程中又引入了插入式貪婪算法[12]，增加登機(jī)口?？康暮桨?，減少登機(jī)口的總使用量。

NSGA-Ⅱ算法種群中每個(gè)個(gè)體都代表著一種可行的調(diào)度方案，按照上述的編碼方法，每個(gè)個(gè)體都包含兩段序列(染色體序列、加工機(jī)器序列)，均采用隨機(jī)初始化的方法生成基因序列，若加工機(jī)器序列中存在不滿足約束要求的基因，則對(duì)該基因進(jìn)行隨機(jī)更換，直到滿足約束要求為止，最終通過(guò)解碼操作確定各個(gè)航班?？康牡菣C(jī)口、登機(jī)口各個(gè)航班的?？宽樞?。

2.2 適應(yīng)度評(píng)價(jià)

適應(yīng)度反映了個(gè)體適應(yīng)環(huán)境的能力，適應(yīng)度好的個(gè)體將有更多的機(jī)會(huì)遺傳到下一代。本文采用NSGA-Ⅱ中的快速非支配排序、擁擠距離作為評(píng)價(jià)方法比較種群個(gè)體的優(yōu)劣[13]。種群中非支配等級(jí)低的個(gè)體的適應(yīng)度優(yōu)于非支配等級(jí)高的個(gè)體，對(duì)于同一等級(jí)中的個(gè)體，擁擠距離大的個(gè)體具有更好的適應(yīng)度值。

2.3 基于NSGA-Ⅱ算法求解的總流程

本文提出基于NSGA-Ⅱ算法求解的多目標(biāo)航班登機(jī)口的優(yōu)化調(diào)度問(wèn)題的詳細(xì)步驟如下。

圖3 基于NSGA-Ⅱ算法求解的總流程

步驟1 設(shè)定NSGA-Ⅱ算法的參數(shù)：算法迭代次數(shù)Genmax，種群數(shù)目N，選擇概率Ps，交叉概率Pc，變異概率Pm，Pareto解集最大數(shù)目MaxSize。

步驟2 對(duì)當(dāng)日所有的航班進(jìn)行數(shù)據(jù)處理，確定所有航班的工件號(hào)、工序號(hào)。

步驟3 初始化N個(gè)個(gè)體，形成父代種群P；令Gen=0。

步驟4 對(duì)種群P中的每個(gè)個(gè)體采用基于插入式貪婪算法的解碼操作，解碼后計(jì)算登機(jī)口總使用量(sum)、旅客最大總步行時(shí)間(Tp)。

步驟5 根據(jù)個(gè)體的評(píng)價(jià)值，對(duì)種群P的所有個(gè)體進(jìn)行快速非支配排序及擁擠距離計(jì)算，每個(gè)個(gè)體擁有兩個(gè)屬性，即非支配等級(jí)和擁擠距離。

步驟6 更新Pareto解集。

步驟6.1 如果當(dāng)前Pareto解集為空時(shí)，將當(dāng)前種群中非支配等級(jí)為1的個(gè)體(irank=1)存入Pareto解集；如果當(dāng)前種群P中irank=1的個(gè)體數(shù)目大于MaxSize，按照擁擠距離從大到小依次填入Pareto解集中。

步驟6.2 如果當(dāng)前Pareto解集不為空時(shí)，在種群P中剔除與當(dāng)前Pareto解集中相同的個(gè)體，將剔除后種群P中irank=1的個(gè)體和Pareto解集中的個(gè)體存入種群Ptemp中，對(duì)種群Ptemp進(jìn)行快速非支配排序及擁擠距離計(jì)算，如果種群Ptemp中irank=1的個(gè)體數(shù)目大于Pareto解集MaxSize，按照擁擠距離依次填入Pareto解集中，否則直接將irank=1的個(gè)體存入Pareto解集。

步驟7 依據(jù)錦標(biāo)賽選擇法，優(yōu)先選擇非支配等級(jí)低的個(gè)體染色體，相同等級(jí)下選擇擁擠距離大的個(gè)體，對(duì)種群P中的前M個(gè)個(gè)體進(jìn)行選擇；采用文獻(xiàn)[12]的操作分別對(duì)種群P中其他個(gè)體的染色體序列、機(jī)器序列進(jìn)行交叉和變異操作，生成新種群P。

步驟8 去除種群P中與種群P中相同的個(gè)體，將種群P個(gè)體和種群P個(gè)體合并為種群PN。

步驟9 根據(jù)種群PN中個(gè)體適應(yīng)度值，選擇N個(gè)個(gè)體，形成種群P。

步驟10 令Gen=Gen+1，如果Gen>Genmax，輸出Pareto解集，否則跳轉(zhuǎn)到步驟5。

3 實(shí)例驗(yàn)證

3.1 實(shí)例信息

以某機(jī)場(chǎng)當(dāng)日51個(gè)航班15個(gè)登機(jī)口調(diào)度問(wèn)題為例，對(duì)本文中的數(shù)學(xué)模型及求解算法進(jìn)行驗(yàn)證。通過(guò)數(shù)據(jù)處理，得到了51個(gè)航班的工件歸屬及?？啃畔?，如表5所示。

表6為登機(jī)口分布情況，根據(jù)表5 中各航班的出發(fā)類型，可知各航班?？康牡菣C(jī)口范圍，表7為中轉(zhuǎn)旅客在各廳之間步行時(shí)間。

表5 51個(gè)航班的工件歸屬及停靠信息

續(xù)表5

表6 登機(jī)口分布情況

表7 各廳之間的中轉(zhuǎn)時(shí)間

3.2 計(jì)算結(jié)果與分析

針對(duì)多目標(biāo)航班登機(jī)口調(diào)度問(wèn)題，使用Visual C++進(jìn)行編程，計(jì)算機(jī)型號(hào)Intel(R)Core(TM)i5-7400 CPU @ 3.00 GHz，4.00 G運(yùn)行內(nèi)存，算法參數(shù)設(shè)置如表7所示。

表7 參數(shù)設(shè)置

使用提出的NSGA-Ⅱ算法，求解獨(dú)立運(yùn)行20次得到一組 Pareto解集，如表8所示。

表8 Pareto解集

從表8可以清楚看出，隨著登機(jī)口總使用量的增加，各登機(jī)口的旅客最大總步行時(shí)間不斷減小，這說(shuō)明這兩個(gè)優(yōu)化目標(biāo)是矛盾的。為了進(jìn)一步說(shuō)明兩優(yōu)化目標(biāo)之間的矛盾關(guān)系，按登機(jī)口總使用量的增序排列了各個(gè)Pareto解，如圖4所示。由圖4可見(jiàn)，登機(jī)口的總使用量和旅客最大總步行時(shí)間并非線性關(guān)系，如果僅僅采用單目標(biāo)優(yōu)化算法求解，則無(wú)法兼顧兩個(gè)目標(biāo)。使用本文提出的NSGA-Ⅱ算法求解，以快速非支配排序及擁擠距離計(jì)算為評(píng)價(jià)方法，可以最終確定一組Pareto解集，該解集中的每個(gè)解都能夠兼顧這兩個(gè)優(yōu)化目標(biāo)，登機(jī)口的調(diào)度員可以根據(jù)機(jī)場(chǎng)的當(dāng)日情況選擇合理調(diào)度方案，以節(jié)省登機(jī)口的使用量或旅客的步行時(shí)間。圖5給出了序號(hào)8解的航班調(diào)度圖，該解為登機(jī)口旅客總步行時(shí)間最小的解，圖5中的J1.1表示歸屬于工件1的第一個(gè)航班，即NV675(5∶00—7∶00)在登機(jī)口1?？浚渌念愅?。

圖4 Pareto解集中各均衡解的分布

圖6為序號(hào)8解各登機(jī)口的航班量，圖7 為該解各登機(jī)口的旅客總步行時(shí)間。

圖5 Pt 最小解的航班調(diào)度圖

圖6 各登機(jī)口的航班量

圖7 各登機(jī)口旅客的總步行時(shí)間

表9 各優(yōu)化目標(biāo)的最小值

為了驗(yàn)證NSGA-Ⅱ算法對(duì)于單個(gè)目標(biāo)函數(shù)的優(yōu)化，本文使用遺傳算法(GA)分別對(duì)這兩個(gè)優(yōu)化目標(biāo)進(jìn)行求解，求解結(jié)果如表9所示。由表9可知，本文采用NSGA-Ⅱ算法求得的Pareto解集包含了單目標(biāo)優(yōu)化時(shí)的最小值。對(duì)于單個(gè)目標(biāo)函數(shù)的優(yōu)化，NSGA-Ⅱ算法的優(yōu)化效果比基于GA的優(yōu)化結(jié)果好。

4 結(jié) 論

針對(duì)多目標(biāo)航班登機(jī)口的調(diào)度問(wèn)題，建立了以登機(jī)口總使用量最小、旅客最大總步行時(shí)間最小為優(yōu)化目標(biāo)的多目標(biāo)數(shù)學(xué)模型，設(shè)計(jì)了登機(jī)口總使用量、旅客最大總步行時(shí)間的目標(biāo)函數(shù)，并基于NSGA-Ⅱ算法求解。根據(jù)柔性作業(yè)車間調(diào)度問(wèn)題與航班登機(jī)口調(diào)度問(wèn)題的共性特點(diǎn)進(jìn)行類比，提出了一種問(wèn)題假設(shè)與數(shù)據(jù)處理方法，有效地將所有的航班變換成各工件的工序，將各個(gè)登機(jī)口變換成加工機(jī)器，結(jié)合類比的問(wèn)題采用基于工序的編碼方法、基于機(jī)器分配的編碼方法，最后通過(guò)對(duì)某機(jī)場(chǎng)51個(gè)航班15個(gè)登機(jī)口的調(diào)度問(wèn)題進(jìn)行求解，驗(yàn)證了所建立模型和提出算法的可行性。該研究有助于推動(dòng)運(yùn)籌學(xué)技術(shù)在機(jī)場(chǎng)登機(jī)口管理中的應(yīng)用，為機(jī)場(chǎng)管理者提供決策依據(jù)，同時(shí)也提高機(jī)場(chǎng)的服務(wù)質(zhì)量。