基于多目标规划的低空飞行服务站选址

陈华群, 熊 静, 黄炬凯

(1.中国民航飞行学院空中交通管理学院，广汉 618307；2.西南交通大学交通运输与物流学院，成都 610041)

低空飞行服务站是指为低空飞行活动提供飞行计划的申报审批、航空情报、航空气象、告警和协助救援等服务的机构，是保障低空空域飞行安全必不可少的部门。低空改革政策引领带动下，截至2019年底中国通航飞行达112.5万h 同比增长13.8%，通航企业近五百家，通航飞机数量达到约 3 000架，建设国家级航空产业基地10个、地方航空产业园26个；民航局2018年发布了《低空飞行服务保障体系建设总体方案》，使得低空飞行服务站逐步推广。因此迫切需要形成一套行之有效的科学选址理论和方法，合理规划站点的选址位置、数量和运营规模，实现低空飞行的安全性和经济性。

美国、澳大利亚和加拿大在低空飞行服务领域处于世界领先，美国联邦航空局针对低空飞行设置了一百多座低空飞行服务站，实现了从计划申请到飞行中情报气象等自动服务[1]。中国低空发展起步较晚，自2012年起，分别在沈阳、珠海、深圳和海南进行了试点，多地开展建设并摸索了飞行服务站管理模式。中国众多专家学者对低空飞行服务进行了研究。朱丹彤[2]将运营发展模式理论优化中国通用航空飞行服务站的系统运营并对服务流程进行仿真，周雪松等[3]提出了建立低空飞行服务站综合信息平台的思路，黄晶晶[4]提出了复杂低空飞行安全态势的评估方法。上述研究聚焦于低空飞行服务站的运营和功能，均并未涉及低空飞行站点设置理论依据和方法。与低空飞行服务站的选址相似的场站选址问题如消防站、邮政所、物流配送站等，中外众多学者进行了大量的研究，黄川等[5]提出了基于水域精细划分的雷达站选址配置优化；王兵等[6]运用免疫算法对后方仓库选址进行建模与仿真；Uddin等[7]提出运用决策支持对复杂城市系统中消防站综合选址和配置进行研究。

相较于传统站点选址多偏重考虑经济成本，将服务响应时间、服务覆盖区域和重复覆盖纳入选址目标，通过系统分析低空飞行服务流程，明确低空飞行服务的需求特征，构建选址评价体系，建立数学模型和遗传搜索算法，实现低空飞行服务站选址的多目标全局优化。

1 低空飞行服务流程

低空飞行是距地面100～1 000 m之间的飞行，适用于训练、伞降、空投、侦察、强击和农林等作业。低空飞行服务内容包括：飞行计划受理和飞行报备，低空飞行所需信息的服务如气象信息、飞行情报、航行情报，以及协助搜寻救援服务。低空飞行服务站需向用户确保各种服务信息及情报的可获得性、全面性、准确性、实时性和安全性，提供服务时需考虑安全程度最高、成本代价最小的最优效果，建立了基于飞行过程的服务流程，如图1所示。

图1 低空飞行服务流程Fig.1 The process of low altitude flight service

通过低空飞行服务流程图可知：飞行服务站为低空飞行提供的服务贯穿整个飞行过程，且兼具着紧急情况下的告警和协助搜寻救援工作。因此，低空飞行服务站所能提供的服务必须覆盖飞行需求范围，通过系统分析和合理界定低空飞行需求，使站点设置的数量和规模更优化。

2 低空飞行服务需求

低空空域服务和管理的对象是通用航空的各项飞行活动，飞行需求因社会经济活动需要而使用航空器在规定空域范围内、给定时段内实现位移转移的要求。因此分析低空飞行服务需求时，应充分考虑其飞行时间、位移转换空间及与之相关的诸多不确定的需求，将其界定为派生性需求；科学、全面地分析低空飞行服务需求为飞行服务站选址提供定性和定量的决策支持作用。

2.1 不定期的时间需求

由于飞行设备和飞行业务性质的原因，开展低空飞行活动的时间需求不同于民航运输，飞行时间需求的特点具有：白天、天气晴朗、飞行时段持续较短。现考虑低空飞行的用户对飞行服务时效性要求，即考虑飞行需求量随着昼夜交替、天气变化的反应时间的增大而产生的相应衰退。通过跟踪调查和统计，采用Python对中国南方某地区通航活动时间分布规律进行大数据分析[8]，得到各季节在不同时间段的需求占比结果如图2所示。

图2 不同季节的低空飞行时间需求占比Fig.2 The percent of low altitude flight time request in different season

2.2 经济活动聚集的安全超障空间需求

低空飞行需求是人类经济活动过程中产生的一种派生性需求，与其所涉及地区人类经济活动的空间分布具有一致性，而经济活动在本质上具有空间集聚特征，因此低空空域飞行空间需求的分布是以通航机场或起降点之间为需求集聚区，从通航机场或起降点之间实现空域之间的区域飞行方式。根据相似飞行空间需求将该区域总飞行空间需求区域分为多个飞行空间需求次区域，选取需求次区域的几何中心来代表离散飞行空间需求点；转换后飞行空间的需求区域被转化为单个空间需求点的集合，用网络节点代替需求区域，采用聚类方法，将实际飞行区域根据不同飞行密度聚类分成多个次区域，再利用ArcGis 10.1软件处理成输入模型中进行求解的基本数据，描述方式如图3所示。

图3 节点集聚式的低空飞行空间服务需求描述Fig.3 Description of low altitude flight airspace demand sevice with point congestion

图3利用ArcGis软件实现了低空飞行空间需求更为现实的集聚，不同于传统的简单以通航机场中心或飞行空域中心作为飞行空间需求集聚点，这种飞行空间需求量描述方式是基于飞行区域需求密度来选择的最优集聚模式。

2.3 低空飞行所需服务的不确定性

低空飞行活动是一项较复杂、烦琐的空间位置转移，飞行过程中需要众多部门的配合，同时受天气、飞行人员人为因素、与军民航协调等的影响。此外，低空飞行活动通常是在导航设备相对简陋的通航机场、起降点之间进行，飞行区域多是非管制地带，飞行人员的操作灵活性大，因此可将以上因素均纳入低空飞行所需服务的不确定性。

3 低空飞行服务站多目标优化模型

3.1 飞行服务站选址决策评价

低空飞行服务选址一项综合决策行为，需要全面分析飞行需求，制定即符合局方要求又高效规范的管理模式，明确飞行服务的响应时间要求，充分考虑设施设备建设的固定成本和后期的运营维护费用等各项因素。因此，在构架飞行服务站主要评价指标，需考虑飞行服务响应时效性、经济性和鲁棒性；将整个飞行过程所需服务的响应总时间为其时效性，服务站建设固定成本表示经济性，后期运营和维护成本及需求的变动表示目标鲁棒性(图4)。

图4 低空飞行服务站选址决策评价Fig.4 Decision evaluation of low altitude flight service site

传统的服务站选址模型通常没有充分考虑飞行服务响应时间和后期站点可持续性发展的鲁棒性[9],一定程度影响了选址决策的科学性。采用最大覆盖问题模型的覆盖半径概念,建立满足飞行安全服务响应时间要求下的服务最大覆盖区域和站点成本最低的多目标低空飞行服务站选址模型。

3.2 参数设定和决策变量

设置选址决策变量Xi、服务与需求匹配决策变量Yij和候选站点是否相交变量Wj，j+1，即

(1)

(2)

(3)

3.3 多目标优化模型

飞行服务站选址问题的目标首先必须设置的站点确保所属辖区内开展的低空飞行活动的安全，然后兼具建设和使用的经济性，同时具备一定的抗需求变动的波动性。因此，根据3.2节所设定的基本参数和决策变量，建立如下的目标函数。

3.3.1 飞行服务响应时间

飞行服务响应时间表示各低空飞行服务站为各需求点提供响应的总时间，目标函数Z1表示为

(4)

3.3.2 飞行服务站总成本

飞行服务站总成本包括选址建设成本、投入使用后的运营和维护成本的总和，目标函数Z2表示为

(5)

3.3.3 服务覆盖

服务覆盖目标是指飞行服务站所能服务的覆盖区域的总和最大化，但站点之间的重复覆盖需达到最小化，其目标函数分别用Z3和Z4表示，即

(6)

根据候选服务站点几何中心位置和服务半径判断两两相邻站点之间重复覆盖的区域定重复区域。设几何中心之间的距离为lj,j+1，即l<(rj+rj+1),重叠区域的半高度为h，相交区域对应的圆心角分别为θj、θj+1,具体描述如图5所示。

图5 相邻候选站点服务覆盖Fig.5 Service coverage of adjacent candidate sites

建立多目标低空飞行服务站选址数学模型为

(7)

(8)

(9)

(10)

约束条件为

DiYij≤Mj， ∀i∈M，j∈N

(11)

Yij≤Xj

(12)

(13)

Xj={0,1}

(14)

Yij={0,1}

(15)

(16)

约束条件(11)表示飞行服务站的服务需求不能大于自身的服务上限，约束条件(12)和(13)表示每一个需求点有且仅有一个服务站为其服务，约束条件(14)～(16)为决策变量的取值范围。

4 基于遗传算法的模型求解

由于上述模型是0-1整数非线性多目标规划问题，直接求解十分困难，因此求解该问题最重要的是多个目标函数的处理办法。本文借鉴当前学者们对多目标的研究成果[10]，预采用从理想点出发，将原模型转化成目标扰动最小化模型，并采用遗传算法进行站点与需要点之间服务匹配迭代搜索，找出低空服务需求覆盖程度最高、建设和运营成本最低和抗波动性最高的站点选址优化方案。

4.1 模型改进

(17)

式(17)中：Zk表示第k个目标函数的值，则原模型改进为基于理想点的新扰动模型为

(18)

原模型中包含若干个极小极大运算，采用遗传算法求解时会极大地提高求解难度[11-12]，而在改进原模型之后，遗传算法求解该模型的效率将提高。

4.2 遗传算法设计

算法设计的主要思路是首先确定服务站选址原模型的理想点Z0，再根据选择、交叉和变异运算进行迭代搜索，求解基于理想点的最小扰动模型，直至满足停止条件，停止搜索；将解的编码采用长度为|I|的二进制串Xj,在Xj确定后根据相应的函数找到站点服务方案Yij。

基于理想点的目标扰动最小化模型，引入满足飞行安全要求的响应时间、经济成本、覆盖区域和重复覆盖的最低标准为常数Fk分别构建四个目标函数的最大化适应函数fit(Xj)=Fk|a，具体的遗传算法步骤如下：

Step1初始化：确定原目标函数的初始理想点Z0，设置最大进化代数T和进化代数计数器t=0，生成初始场站选址方案种群Xt。

Step2个体评价：评价初始方案Xt对应的站点服务方案Yt1，计算个体适应度fit(X)t=Fk|a。

Step3选择运算：根据Step2中评估确定的初始个体群的适应度，选择动态需求变化Di作为算子作用于群体选择搜索，直到所有需求都被站点服务覆盖则算法停止，输出当前最好的个体Xbest=Xt;否则依据个体适应度fit(X)t，保留当代中最好个体Xbest进入下一代循环。

Step5变异操作：将对选址群体中的服务方案Yt作为个体串的基因变动。从0～1随机获取可接受的变异概率，对选址方案个体中任意选择两个站点服务对象进行逆序调换，则变异运算之后得到下一代的方案群体X(t+1)和目标函数群体Z(t+1)。

Step6判断终止条件：若迭代次数t=T，以最后搜索所得的选址方案Xt作为最优解输出，计算对应的目标函数值，算法终止；否则返回Step2，t++。

5 算例分析

为测试模型和算法的可行性和优化效果，运用MATLAB分别采用传统枚举算法和本文提出的多目标遗传算法进行仿真[12-13]。在300 km×300 km的平面上，均匀地随机产生飞行服务需求点和服务站备选点，如图1所示未标注的圆点代表低空飞行服务需求点；标注数字代号的圆点代表可供建设低空飞行服务站的设施备选位置。候选站“1”代表地区飞行服务中心，服务覆盖半径设为r1取值200 km；其他候选站表示地方飞行服务站，取服务覆盖半径r2=100 km。

图6 低空服务需求分布和可建站点的位置Fig.6 Request distribution and location avaiable of low altitude

假设最低服务响应时间Tact=15 s，根据本例候选站点与之覆盖需求点的相对位置，需求点的响应时间取值为15～10 s的随机数且服从λ为大于0.5的泊松分布、需求点的需求量为0～100的随机数，服务站的服务需求阈值为500，服务站的土地、设施、维护、预留成本分别为500万～100万、100万～50万、50万～20万、20万～10万的随机数。

表1 枚举法选址方案参数表Table 1 Parameters of site selection scheme

表1表明：方案S1选择了全部的备选站,满足响应时间最短的目标，但服务成本最高，且重复覆盖率最高。

算例的种群数量为23，设定研究区域的响应时间、经济成本、覆盖区域和重复覆盖的最低标准分别为F4=(345,90 000,600,15%)：停止迭代次数为5 000，交配概率为0.8，变异概率为0.1。根据目标扰动最小化模型，利用遗传算法选择各项目标函数都最低的“4”作为父代，在剩下的种群中利用适应度函数fit(X4)=F4|a对种群个体进行排序，选择出适应度好的个体进行下一个迭代，最终搜索迭代结果如表2所示。最优方案是更接近S3的S4即选址站点“1”和“5”。对比传统枚举法，无需搜索所有方案且各目标函数更加优化。

表2 多目标遗传算法选址方案参数表Table 2 parameters of multi-objective genetic algorithm location scheme

方案S4＊实现了除服务响应时间之外的其他目标函数最优，也能满足正常情况下的服务覆盖的要求，但若候选站点“1”故障则紧急情况时搜寻救援的效率低；因此可采用增设一座三级低空飞行服务站“3”或“4”的方案。

6 结论

低空飞行服务站选址是非线性组合优化问题，是在确保飞行安全的前提下，考虑运营的经济和高效。引入多目标规划理论求解低空飞行服务站选址问题，得出主要的结论如下：

(1)系统分析低空飞行服务流程，有利于确定服务需求对象和各阶段的服务内容，便于低空飞行服务需求的合理界定和定量表达。

(2)基于层次分析法的选址评价体系，有助于确定选址的基本原则和约束限制。

(3)建立多目标的低空飞行服务站选址模型兼顾了选址成本和服务品质，考虑了后期飞行服务的动态需求变化，增强服务站的抗扰动性。

(4)提出的改进遗传算法，有利于均衡各目标函数值，且在大规模的选址求解时较传统枚举算法求解时间复杂度更低。

增加服务覆盖面积和降低服务响应时间这两项目标往往需要增加服务成本为代价，属于帕雷托解。因此在实际选址决策时，可结合研究区域的具体需求，采用如权重系统法、排序和共享等求解方法。