基于啟發(fā)式算法的通用機場初步布局研究

何昕，宮獻(xiàn)鑫

(中國民用航空飛行學(xué)院空中交通管理學(xué)院，四川廣漢618307)

基于啟發(fā)式算法的通用機場初步布局研究

何昕，宮獻(xiàn)鑫

(中國民用航空飛行學(xué)院空中交通管理學(xué)院，四川廣漢618307)

通用機場是提供通用航空器服務(wù)的基礎(chǔ)保障設(shè)施，通用機場布局規(guī)劃為通用航空市場發(fā)展提供強有力的支撐。在機場選址備選方案基礎(chǔ)上，以成本最小化、效益最大化為目標(biāo)，建立通用機場網(wǎng)絡(luò)覆蓋模型，采用啟發(fā)式算法對模型進行求解。通過算例驗證模型和算法的合理性，并提出通用機場布局方案。結(jié)果表明，基于啟發(fā)式算法的通用機場網(wǎng)絡(luò)覆蓋模型可應(yīng)用于區(qū)域內(nèi)通用機場初步布局研究。

民航運輸；通用機場；機場布局；網(wǎng)絡(luò)覆蓋模型；啟發(fā)式算法；最優(yōu)化

0 引言

通用機場布局規(guī)劃與優(yōu)化是我國發(fā)展通用航空市場的一個重要問題。通用航空發(fā)展的關(guān)鍵是通用機場的準(zhǔn)確定位、科學(xué)布局。2016年5月國務(wù)院辦公廳印發(fā)《關(guān)于促進通用航空業(yè)發(fā)展的指導(dǎo)意見》(以下簡稱《意見》)，統(tǒng)籌協(xié)調(diào)通用航空與公共運輸航空，優(yōu)化規(guī)劃布局，合理確定標(biāo)準(zhǔn)，完善審核程序，分類推進通用機場建設(shè)，解決“落地難”問題?！兑庖姟吠怀鐾ㄓ煤娇諉栴}導(dǎo)向，重點提出加快通用機場建設(shè)。到2020年，地級以上城市擁有通用機場或兼顧通用航空服務(wù)的運輸機場將達(dá)500個以上，覆蓋區(qū)域內(nèi)的農(nóng)產(chǎn)品主產(chǎn)區(qū)、主要林區(qū)、旅游景區(qū)。近幾年來，我國的通用機場在建數(shù)量和總體數(shù)量明顯增多，但是由于前期通用機場標(biāo)準(zhǔn)不明確、政策法規(guī)不健全、規(guī)劃布局方法不完善等原因，導(dǎo)致現(xiàn)有的通用機場總量少，分布不均衡，難以滿足通用航空市場的需求。據(jù)不完全統(tǒng)計，截至2015年，我國內(nèi)地有許可證的通用機場(不含起降點)共61家[1]，因此我國通用機場的建設(shè)顯得尤為迫切。

目前，我國學(xué)者大多針對通用機場的發(fā)展戰(zhàn)略、總體規(guī)劃、通用機場的需求結(jié)構(gòu)等方面進行研究。馮曉平[4]提出基于區(qū)域資源的通用機場發(fā)展戰(zhàn)略框架。孟海濤[5]提出按建設(shè)規(guī)模大小、使用頻次、起降機型的類別、機場所在位置等因素確立通用機場。馮曉平[3]分析目前通用機場發(fā)展的關(guān)鍵制約因素，如空域制約、多部門管理、產(chǎn)業(yè)制度不完善、政府意識弱等。我國學(xué)者對通用機場的布局規(guī)劃進行評估分析較少。楊文捷等[7]對通用航空緊急救援場點的布局進行分析。曲德凱[8]提出構(gòu)建直升機機場網(wǎng)絡(luò)布局及選址模型理論框架和應(yīng)用方法。由于我國通用航空發(fā)展較晚，機場布局結(jié)構(gòu)和優(yōu)化分析不夠深入。我國計劃在短時間內(nèi)建設(shè)大量通用機場以適應(yīng)通用航空業(yè)的巨大需求，因此，通用機場的布局方法研究至關(guān)重要。

本文探索通用機場布局規(guī)劃方法，在機場選址備選方案基礎(chǔ)上，建立通用機場網(wǎng)絡(luò)覆蓋模型，解決通航機場的初步布局問題，實現(xiàn)覆蓋區(qū)域內(nèi)需求點目標(biāo)和機場的合理布局。機場網(wǎng)絡(luò)覆蓋模型屬于帶有復(fù)雜約束的NP-hard問題，采用啟發(fā)式算法對模型進行求解，通過具體算例進行計算，并給出通用機場布局方案。

1 通用機場網(wǎng)絡(luò)覆蓋模型

1.1 通用機場覆蓋問題的描述

覆蓋模型是確定一組服務(wù)設(shè)施來滿足需求量已知的需求點。覆蓋模型最早由Toregas[7]用于解決緊急服務(wù)設(shè)施的選址問題，它能很好地解決在滿足覆蓋所有需求點的前提下，通用機場的建設(shè)個數(shù)或建設(shè)費用最小的問題。

假設(shè)建立每個通用機場的成本相同，為達(dá)到成本最小、利益最大的目標(biāo)，需用最小數(shù)量的機場去覆蓋所有農(nóng)產(chǎn)品主產(chǎn)區(qū)、主要林區(qū)、旅游景區(qū)等需求點。由于地形和通用航空器的燃油容量的限制，每個通用機場都有其最大服務(wù)半徑。通常，位于需求點密集的機場最大服務(wù)半徑較小，而位于需求點稀疏的機場最大服務(wù)半徑相對較大。對于區(qū)域通用機場的初步布局，首先根據(jù)建設(shè)通用機場基本原則確定初始機場布局方案，在滿足需求點需求的條件下，從候選機場中選擇若干個位置最終確定機場的地址，并使所設(shè)立的通用機場數(shù)目最小，如圖1。其次，根據(jù)范圍內(nèi)需求點的密集度、業(yè)務(wù)量配備通用機場。

通用機場候選地址；農(nóng)產(chǎn)品主產(chǎn)區(qū)、主要林區(qū)、旅游景區(qū)等需求；通用機場服務(wù)邊界圖1 通用機場覆蓋示意圖

1.2 模型假設(shè)

1)忽略地租等因素的影響，認(rèn)為建設(shè)每個機場的成本相同；

2)不考慮區(qū)域內(nèi)管制因素的影響；

3)通用機場的規(guī)模能夠滿足需求點的需求量；

4)一個位置對應(yīng)一個通用機場。

1.3 機場網(wǎng)絡(luò)覆蓋模型的建立

通用機場初步布局轉(zhuǎn)化為在N個需求點中選擇M個建立通用機場，使其以最少的通用機場確保每個需求點都能得到完全的滿足?；谝陨辖⑼ㄓ脵C場網(wǎng)絡(luò)覆蓋模型：

(1)

(2)

(3)

xj∈{0,1} j∈M

(4)

0≤yij≤1 i∈N,j∈M

(5)

式(1)使通用機場數(shù)量最少，式(2)確保通用機場服務(wù)滿足所有需求點，式(3)是對機場服務(wù)能力的限定，式(4)約束在候選地點最多建設(shè)一個通用機場。

2 啟發(fā)式算法

模型為NP-hard問題，在實際問題中，需求點和候選機場數(shù)值較大，枚舉法或分枝定界法[8-9]無法較好地求得模型最優(yōu)解，因此，采用啟發(fā)式算法來對模型進行求解。

1)確定A(j)和B(i)，令：

(6)

3)確定機場的服務(wù)覆蓋范圍。

將A(j′)中的元素按B(i)的模從小到大的順序指派給j′，直至j′的容量Dj′=0或A(j′)為空。對于i∈A(j′)且yi1，將i指派給j′的方法為：

若di(1-yi)≤Dj′，則yij=1-yi，yi=1，Dj=Dj-dj(1-yi)且在A(j′)和N中剔除需求點i；

4)若N為空，則停止；否則，更新A(j)和B(i)，轉(zhuǎn)第2步。

3 算例分析

在對某區(qū)域進行通用機場的初步布局研究時，應(yīng)采集實際位置和需求數(shù)據(jù)。算例中的位置和機場布局為假設(shè)值，擬定通用機場的最大服務(wù)半徑為60 km，使成本最小、效益最大，應(yīng)盡可能少設(shè)立機場。將區(qū)域內(nèi)所有農(nóng)產(chǎn)品主產(chǎn)區(qū)、主要林區(qū)、旅游景區(qū)等歸納為9個需求點，假設(shè)第6需求點由于地形原因或其他因素不適合通用機場的選址原則，其他均可作為候選機場地址來考慮，如圖2所示。

圖2 通用機場服務(wù)區(qū)域示意圖(單位：km)

服務(wù)區(qū)域示意圖中線段上數(shù)字表示需求集中點之間的距離，單位為km。令N={1，2，3，4，5，6，7，8，9}，M={1，2，3，4，5，6，7，8，9},用最短路法求得上圖中兩點間的最短路，再根據(jù)最大服務(wù)半徑為60 km以及第6個集中點不適宜設(shè)立機場的約束條件，可確定A(j)和B(i)，根據(jù)模型服務(wù)能力的約束條件公式，保證機場服務(wù)能力滿足需求點的需求量，如表1所示。

表1 候選機場及服務(wù)范圍

根據(jù)建立的目標(biāo)函數(shù)，按照啟發(fā)式算法對算例進行求解，得到計算結(jié)果，如表2所示。

表2 機場規(guī)劃結(jié)果優(yōu)化

采用通用的線性0-1整數(shù)規(guī)劃Matlab算法進行計算，計算結(jié)果如表3所示。

表3 Matlab計算機場規(guī)劃結(jié)果

通過對比可以看出，由于其計算數(shù)據(jù)少，機場位置選擇一致，表2的求解的結(jié)果更為合理。運用啟發(fā)式算法求解機場網(wǎng)絡(luò)覆蓋模型，得到用最少的3個通用機場覆蓋區(qū)域內(nèi)所有需求點的結(jié)果,且確保每個需求點的需求都能滿足，使效益最大化，計算的機場布局合理，符合區(qū)域內(nèi)機場初步布局的要求。算例可驗證基于啟發(fā)式算法的通用機場網(wǎng)絡(luò)覆蓋模型的合理性。

5 結(jié)論

運用通用機場網(wǎng)絡(luò)覆蓋模型對通用機場的初步布局進行研究，采用啟發(fā)式算法對布局問題進行求解，最后得出科學(xué)合理的通用機場布局方案。通用機場網(wǎng)絡(luò)覆蓋模型以成本最小化、效益最大化為目標(biāo)，模型中的需求集中點的業(yè)務(wù)量即通航的需求量，可以體現(xiàn)通航機場選擇機場地點的人口、經(jīng)濟等因素，如要進一步科學(xué)準(zhǔn)確地研究通用機場布局，則在此模型的基礎(chǔ)上考慮經(jīng)濟、政治、地理等因素。算例分析表明通用機場網(wǎng)絡(luò)覆蓋模型可應(yīng)用于區(qū)域內(nèi)通用機場初步布局的研究。

[1]通航委.《中國通用航空發(fā)展報告2015》正式發(fā)[EB/OL].(2016-05-24)[2016-06-01].www.cannews.com.cn/2016/0524/154289.shtml.

[2]馮曉平.基于資源的區(qū)域通用機場發(fā)展研究[J].南昌航空大學(xué)學(xué)報(社會科學(xué)版),2012,14(2):19-24.

[3]孟海濤.我國通用機場分類情況綜述[J].商業(yè)經(jīng)濟，2012(8):82-85.

[4]馮曉平.我國通用機場發(fā)展的制約因素及環(huán)境分析[J].西安航空技術(shù)高等?？茖W(xué)校學(xué)報,2012,30(3):21-26.

[5]楊文捷,劉世江.通用航空緊急救援場點布局研究[J].中國民用航空,2009(6):27.

[6]曲德凱.直升機機場區(qū)域網(wǎng)絡(luò)布局及選址研究[D].北京：北京航空航天大學(xué),2012.

[7]TOREGAS C SWAIN R,ReVelle C,et al.The location of emergency service facilities[J]Opera-tions Research,1971,19:1366.

[8]DASKIN M S.Network and discrete location:models algorithms and applications[M].New York :Wiley Interscience,1995.

[9]BALAS E,CARREREA M C.A dynamic subgradient-based branch-and-bound procedure for set covering[J].Operations Research,1996,44:875-880.

責(zé)任編輯：周澤民

General Aviation Aerodrome Preliminary Construction Based on Heuristic Algorithm

HE Xin,GONG Xianxin

(Civil Aviation Flight University of China，Guanghan 618307)

General airport aerodrome is a general aircraft service infrastructure,and aviation aerodrome construction lays a solid foundation for the development of general aviation market.Based on airport site selection options,an overlay network model was established to minimize cost and maximize benefit.A heuristic algorithm was applied for an optimal solution with a calculating example solved.The results illustrate that the general aviation aerodrome construction based on the overlay network model is feasible and efficient at the preliminary stage.

civil aviation transportation;general aviation aerodrome;aerodrome construction;network coverage model;heuristic algorithm;optimization

10．3969/j．issn．1671?0436．2016．06．006

2016- 09-28

何昕(1979— )，女，博士研究生，副教授。

V351

A

1671- 0436(2016)06- 0026- 04