何昕，宮獻鑫

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

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

何昕，宮獻鑫

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

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

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

0 引言

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

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

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

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

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

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

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

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

1.2 模型假設

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

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

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

4)一個位置對應一個通用機場。

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

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

(1)

(2)

(3)

xj∈{0,1} j∈M

(4)

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

(5)

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

2 啟發(fā)式算法

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

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

(6)

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

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

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

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

表1 候選機場及服務范圍

根據(jù)建立的目標函數(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)絡覆蓋模型，得到用最少的3個通用機場覆蓋區(qū)域內(nèi)所有需求點的結(jié)果,且確保每個需求點的需求都能滿足，使效益最大化，計算的機場布局合理，符合區(qū)域內(nèi)機場初步布局的要求。算例可驗證基于啟發(fā)式算法的通用機場網(wǎng)絡覆蓋模型的合理性。

5 結(jié)論

運用通用機場網(wǎng)絡覆蓋模型對通用機場的初步布局進行研究，采用啟發(fā)式算法對布局問題進行求解，最后得出科學合理的通用機場布局方案。通用機場網(wǎng)絡覆蓋模型以成本最小化、效益最大化為目標，模型中的需求集中點的業(yè)務量即通航的需求量，可以體現(xiàn)通航機場選擇機場地點的人口、經(jīng)濟等因素，如要進一步科學準確地研究通用機場布局，則在此模型的基礎上考慮經(jīng)濟、政治、地理等因素。算例分析表明通用機場網(wǎ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].南昌航空大學學報(社會科學版),2012,14(2):19-24.

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

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

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

[6]曲德凱.直升機機場區(qū)域網(wǎng)絡布局及選址研究[D].北京：北京航空航天大學,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.

責任編輯：周澤民

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