基于启发式算法的通用机场初步布局研究

何昕，宫献鑫

(中国民用航空飞行学院空中交通管理学院，四川广汉618307)

基于启发式算法的通用机场初步布局研究

何昕，宫献鑫

(中国民用航空飞行学院空中交通管理学院，四川广汉618307)

通用机场是提供通用航空器服务的基础保障设施，通用机场布局规划为通用航空市场发展提供强有力的支撑。在机场选址备选方案基础上，以成本最小化、效益最大化为目标，建立通用机场网络覆盖模型，采用启发式算法对模型进行求解。通过算例验证模型和算法的合理性，并提出通用机场布局方案。结果表明，基于启发式算法的通用机场网络覆盖模型可应用于区域内通用机场初步布局研究。

民航运输；通用机场；机场布局；网络覆盖模型；启发式算法；最优化

0 引言

通用机场布局规划与优化是我国发展通用航空市场的一个重要问题。通用航空发展的关键是通用机场的准确定位、科学布局。2016年5月国务院办公厅印发《关于促进通用航空业发展的指导意见》(以下简称《意见》)，统筹协调通用航空与公共运输航空，优化规划布局，合理确定标准，完善审核程序，分类推进通用机场建设，解决“落地难”问题。《意见》突出通用航空问题导向，重点提出加快通用机场建设。到2020年，地级以上城市拥有通用机场或兼顾通用航空服务的运输机场将达500个以上，覆盖区域内的农产品主产区、主要林区、旅游景区。近几年来，我国的通用机场在建数量和总体数量明显增多，但是由于前期通用机场标准不明确、政策法规不健全、规划布局方法不完善等原因，导致现有的通用机场总量少，分布不均衡，难以满足通用航空市场的需求。据不完全统计，截至2015年，我国内地有许可证的通用机场(不含起降点)共61家[1]，因此我国通用机场的建设显得尤为迫切。

目前，我国学者大多针对通用机场的发展战略、总体规划、通用机场的需求结构等方面进行研究。冯晓平[4]提出基于区域资源的通用机场发展战略框架。孟海涛[5]提出按建设规模大小、使用频次、起降机型的类别、机场所在位置等因素确立通用机场。冯晓平[3]分析目前通用机场发展的关键制约因素，如空域制约、多部门管理、产业制度不完善、政府意识弱等。我国学者对通用机场的布局规划进行评估分析较少。杨文捷等[7]对通用航空紧急救援场点的布局进行分析。曲德凯[8]提出构建直升机机场网络布局及选址模型理论框架和应用方法。由于我国通用航空发展较晚，机场布局结构和优化分析不够深入。我国计划在短时间内建设大量通用机场以适应通用航空业的巨大需求，因此，通用机场的布局方法研究至关重要。

本文探索通用机场布局规划方法，在机场选址备选方案基础上，建立通用机场网络覆盖模型，解决通航机场的初步布局问题，实现覆盖区域内需求点目标和机场的合理布局。机场网络覆盖模型属于带有复杂约束的NP-hard问题，采用启发式算法对模型进行求解，通过具体算例进行计算，并给出通用机场布局方案。

1 通用机场网络覆盖模型

1.1 通用机场覆盖问题的描述

覆盖模型是确定一组服务设施来满足需求量已知的需求点。覆盖模型最早由Toregas[7]用于解决紧急服务设施的选址问题，它能很好地解决在满足覆盖所有需求点的前提下，通用机场的建设个数或建设费用最小的问题。

假设建立每个通用机场的成本相同，为达到成本最小、利益最大的目标，需用最小数量的机场去覆盖所有农产品主产区、主要林区、旅游景区等需求点。由于地形和通用航空器的燃油容量的限制，每个通用机场都有其最大服务半径。通常，位于需求点密集的机场最大服务半径较小，而位于需求点稀疏的机场最大服务半径相对较大。对于区域通用机场的初步布局，首先根据建设通用机场基本原则确定初始机场布局方案，在满足需求点需求的条件下，从候选机场中选择若干个位置最终确定机场的地址，并使所设立的通用机场数目最小，如图1。其次，根据范围内需求点的密集度、业务量配备通用机场。

通用机场候选地址；农产品主产区、主要林区、旅游景区等需求；通用机场服务边界图1 通用机场覆盖示意图

1.2 模型假设

1)忽略地租等因素的影响，认为建设每个机场的成本相同；

2)不考虑区域内管制因素的影响；

3)通用机场的规模能够满足需求点的需求量；

4)一个位置对应一个通用机场。

1.3 机场网络覆盖模型的建立

通用机场初步布局转化为在N个需求点中选择M个建立通用机场，使其以最少的通用机场确保每个需求点都能得到完全的满足。基于以上建立通用机场网络覆盖模型：

(1)

(2)

(3)

xj∈{0,1} j∈M

(4)

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

(5)

式(1)使通用机场数量最少，式(2)确保通用机场服务满足所有需求点，式(3)是对机场服务能力的限定，式(4)约束在候选地点最多建设一个通用机场。

2 启发式算法

模型为NP-hard问题，在实际问题中，需求点和候选机场数值较大，枚举法或分枝定界法[8-9]无法较好地求得模型最优解，因此，采用启发式算法来对模型进行求解。

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)，转第2步。

3 算例分析

在对某区域进行通用机场的初步布局研究时，应采集实际位置和需求数据。算例中的位置和机场布局为假设值，拟定通用机场的最大服务半径为60 km，使成本最小、效益最大，应尽可能少设立机场。将区域内所有农产品主产区、主要林区、旅游景区等归纳为9个需求点，假设第6需求点由于地形原因或其他因素不适合通用机场的选址原则，其他均可作为候选机场地址来考虑，如图2所示。

图2 通用机场服务区域示意图(单位：km)

服务区域示意图中线段上数字表示需求集中点之间的距离，单位为km。令N={1，2，3，4，5，6，7，8，9}，M={1，2，3，4，5，6，7，8，9},用最短路法求得上图中两点间的最短路，再根据最大服务半径为60 km以及第6个集中点不适宜设立机场的约束条件，可确定A(j)和B(i)，根据模型服务能力的约束条件公式，保证机场服务能力满足需求点的需求量，如表1所示。

表1 候选机场及服务范围

根据建立的目标函数，按照启发式算法对算例进行求解，得到计算结果，如表2所示。

表2 机场规划结果优化

采用通用的线性0-1整数规划Matlab算法进行计算，计算结果如表3所示。

表3 Matlab计算机场规划结果

通过对比可以看出，由于其计算数据少，机场位置选择一致，表2的求解的结果更为合理。运用启发式算法求解机场网络覆盖模型，得到用最少的3个通用机场覆盖区域内所有需求点的结果,且确保每个需求点的需求都能满足，使效益最大化，计算的机场布局合理，符合区域内机场初步布局的要求。算例可验证基于启发式算法的通用机场网络覆盖模型的合理性。

5 结论

运用通用机场网络覆盖模型对通用机场的初步布局进行研究，采用启发式算法对布局问题进行求解，最后得出科学合理的通用机场布局方案。通用机场网络覆盖模型以成本最小化、效益最大化为目标，模型中的需求集中点的业务量即通航的需求量，可以体现通航机场选择机场地点的人口、经济等因素，如要进一步科学准确地研究通用机场布局，则在此模型的基础上考虑经济、政治、地理等因素。算例分析表明通用机场网络覆盖模型可应用于区域内通用机场初步布局的研究。

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

[2]冯晓平.基于资源的区域通用机场发展研究[J].南昌航空大学学报(社会科学版),2012,14(2):19-24.

[3]孟海涛.我国通用机场分类情况综述[J].商业经济，2012(8):82-85.

[4]冯晓平.我国通用机场发展的制约因素及环境分析[J].西安航空技术高等专科学校学报,2012,30(3):21-26.

[5]杨文捷,刘世江.通用航空紧急救援场点布局研究[J].中国民用航空,2009(6):27.

[6]曲德凯.直升机机场区域网络布局及选址研究[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