飛機(jī)指派問(wèn)題優(yōu)化模型及算法研究
李耀華，譚娜
中國(guó)民航大學(xué)航空工程學(xué)院，天津300300
摘 要：為了提高航空企業(yè)飛機(jī)排班計(jì)劃的自動(dòng)化水平，分析了航空企業(yè)飛機(jī)排班計(jì)劃編制流程，將這個(gè)復(fù)雜組合優(yōu)化問(wèn)題分解為3個(gè)組合優(yōu)化問(wèn)題，重點(diǎn)研究了其中的飛機(jī)指派優(yōu)化問(wèn)題，歸納了要考慮的主要約束條件，以優(yōu)化理論為基礎(chǔ)，針對(duì)飛機(jī)排班計(jì)劃優(yōu)化問(wèn)題中的關(guān)鍵問(wèn)題飛機(jī)指派問(wèn)題建立了飛機(jī)指派優(yōu)化模型，模型考慮了飛機(jī)與航班之間在機(jī)型、飛行區(qū)域、器流量等條件上的匹配要求，井給出了模型約束條件的編碼方法，同時(shí)根據(jù)大量實(shí)際生產(chǎn)數(shù)據(jù)給出相應(yīng)的懲罰系數(shù)表為求解模型，構(gòu)造了一種自適應(yīng)單親遺傳算法，算法選用了適合模型的遺傳算子，采用動(dòng)態(tài)調(diào)整遺傳算子操作概率的方式加快優(yōu)化速度采用航空公司的實(shí)際航班數(shù)據(jù)進(jìn)行仿真實(shí)例研究結(jié)果表明，該模型和算法切買可行。
關(guān)鍵詞：生產(chǎn)計(jì)劃；排班調(diào)度；飛機(jī)指派；遺傳算法
中圖分類號(hào)：tp 29 文獻(xiàn)標(biāo)識(shí)碼：a
l引言
飛機(jī)排班是航空公司生產(chǎn)計(jì)劃中的一項(xiàng)控制性工作，由于認(rèn)識(shí)到飛機(jī)排班工作在航空運(yùn)輸生產(chǎn)中的重要性和復(fù)雜性，歐美的許多大型航空公司從20世紀(jì)80年代開始在生產(chǎn)中廣泛采用專門的飛機(jī)調(diào)度管理系統(tǒng)來(lái)管理這項(xiàng)工作。在中國(guó)，隨著各航空公司機(jī)隊(duì)規(guī)模的擴(kuò)大，航班量的增長(zhǎng)，特別是航線網(wǎng)的日益大型化和復(fù)雜化，人工排班的落后方式已難以滿足運(yùn)營(yíng)管理工作的要求，因此實(shí)現(xiàn)飛機(jī)排班工作的自動(dòng)化已大勢(shì)所趨。從國(guó)內(nèi)來(lái)看，由于航空公司前幾年規(guī)模普遍偏小，因此對(duì)生產(chǎn)計(jì)劃管理工作缺乏重視，計(jì)劃方式簡(jiǎn)單、粗放，因而對(duì)生產(chǎn)計(jì)劃管理方面的研究非常有限。
近幾年來(lái)，隨著運(yùn)營(yíng)規(guī)模的擴(kuò)大，航空運(yùn)輸市場(chǎng)的開放，市場(chǎng)競(jìng)爭(zhēng)不斷加劇，航空公司逐漸意識(shí)到加強(qiáng)生產(chǎn)計(jì)劃管理工作的重要性和急迫性，但是總體來(lái)說(shuō)，關(guān)于飛機(jī)調(diào)度管理方面的理論研究還處于起步階段。
為了提高生產(chǎn)調(diào)度的自動(dòng)化永平，本文針對(duì)目前航空公司排班計(jì)劃現(xiàn)狀，分析了飛機(jī)排班計(jì)劃編制流程，著重研究了其中的飛機(jī)指派問(wèn)題，建立了飛機(jī)指派優(yōu)化模型，同時(shí)，構(gòu)造了一種自適應(yīng)單親遺傳算法快速求解此模型。
2飛機(jī)指派優(yōu)化模型
1)問(wèn)題提出 針對(duì)飛機(jī)排班問(wèn)題，國(guó)內(nèi)外有關(guān)學(xué)者進(jìn)行了相應(yīng)的研究，文獻(xiàn)[4]概括了飛機(jī)指派問(wèn)題中的一些基本概念、模型和算法，并指出了進(jìn)一步的研究方向。文獻(xiàn)[5]提出了一種基于傳遞閉包法的進(jìn)／離場(chǎng)航班分類方法考慮4種不同因素的條件下建立了航班分類模型，并給出了各類航班單位時(shí)間延誤成本的計(jì)算公式。文獻(xiàn)[6]以航班總收益****化為目標(biāo)，提出了一個(gè)針對(duì)單樞紐機(jī)場(chǎng)航線網(wǎng)絡(luò)的lagrangian松馳算法，但是對(duì)于大多航空公司需要多種機(jī)型混合排班的情況并不太適用。文獻(xiàn)[1]針對(duì)單樞紐航線網(wǎng)絡(luò)的特點(diǎn)，以所需飛機(jī)數(shù)最少，航班在樞紐機(jī)場(chǎng)的過(guò)站銜接最緊湊為目標(biāo)，提出了描述航班銜接問(wèn)題的最小費(fèi)用****流網(wǎng)絡(luò)模型。文獻(xiàn)[2]針對(duì)機(jī)場(chǎng)航班延誤問(wèn)題進(jìn)行了研究，文獻(xiàn)[3]研究了起降航班的排序問(wèn)題，都沒(méi)有涉及飛機(jī)排班調(diào)度中的飛機(jī)指派問(wèn)題。
飛機(jī)排班的實(shí)質(zhì)就是根據(jù)市場(chǎng)部下達(dá)的航班計(jì)劃、每架飛機(jī)的技術(shù)狀況以及飛機(jī)調(diào)度指令，為每個(gè)航班指定一架具體執(zhí)行的飛機(jī)。一般地，航空公司首先要向航班管理部門申請(qǐng)航班，在獲得批準(zhǔn)后作為本公司的執(zhí)行航班；然后，計(jì)劃部門針對(duì)本公司要執(zhí)行的所有航班，綜合考慮公司所擁有的飛機(jī)情況、飛機(jī)調(diào)度的諸多約束等條件來(lái)編制飛機(jī)的排班計(jì)劃，在保證航班正常運(yùn)行的前提下實(shí)現(xiàn)效益****他，這是一個(gè)復(fù)雜的組合優(yōu)化問(wèn)題。
由于近年來(lái)航空公司機(jī)隊(duì)規(guī)模不斷擴(kuò)大，航班量在日益增長(zhǎng)，而大多航空公司編制飛機(jī)排班計(jì)劃都是采用人工或半人工的方式，因此飛機(jī)排班問(wèn)題成了航空公司發(fā)展中迫切需要解決的一個(gè)問(wèn)題。
目前，飛機(jī)排班的具體方法如下：
①首先根據(jù)公司的所有航班信息，將所有航班編制為若于個(gè)航班串，所謂航班串就是將本航空公司的一個(gè)到港航班與另一個(gè)離港航班銜接起來(lái)，生成若干個(gè)可以由一架飛機(jī)去執(zhí)行的航班連接，每一個(gè)稱為一個(gè)“航班串”。
②針對(duì)編制好的航班串計(jì)劃，對(duì)每一個(gè)航班串指派執(zhí)行飛機(jī)。
|
