空战场穿越走廊基本网络规划的混合禁忌搜索算法

刘影，周一叶，甘旭升，杨捷

(1.西京学院 信息工程学院，西安 710123) (2.中国人民解放军95746部队，成都 611531) (3.空军工程大学 空管领航学院，西安 710051)

0 引 言

基于枢纽轴辐式网络的穿越走廊基本网络规划，是指将穿越走廊按一定方式连接而形成的枢纽轴辐式网络结构系统，是空战场航空军事运输活动进行与发展的基础。穿越走廊质量或穿越走廊网络结构的质量是航空军事运输支援保障能力的主要指标之一，因此对穿越走廊网络进行科学、合理地布局规划是保障战场空运顺利进行的重要手段。

1996年，J.F.Campbell[1]针对枢纽轴辐式网络中的单分配多枢纽中位问题首先提出了线性整数规划模型；1998年，P.J.Lederer等[2]根据起讫点间飞行流量矩阵和距离矩阵对航线网络中的全连通网络(即点对点式网络)、环形网络、枢纽轴辐式网络和子环形网络四种类型进行了定量分析，提出了航向网络设计中需要注意的一些主要参考因素；2000年，E.Pels等[3]将点对点式航向网络与枢纽轴辐式航线网络进行了成本比较分析，指出枢纽轴辐式航线网络在降低成本方面的有效性；同年，耿淑香[4]对点对点式航线网络和枢纽轴辐式航线网络进行了详细分析，指出枢纽轴辐式网络能够更好地利用空域资源以及进行新航线的开辟，具有良好的鲁棒性；2006年，柏明国[5]提出了基于多属性决策法的枢纽集候选方法，对枢纽轴辐式航线网络中的枢纽机场进行选择；2007年，T.Kelly等[6]针对枢纽轴辐式航线网络模型特点，将遗传算法应用于模型求解；2010年，杨晗熠[7]以航空货运成本最小化为目标，建立了基于枢纽轴辐式航线网络的中国民航运输网络设计模型；2011年，杨年等[8]提出了基于混合集合规划的枢纽航线网络设计方法；2012年，葛伟等[9]针对枢纽轴辐式网络中的非必要中转问题，设计了蛛式航线网络模型及相关算法，是国内较早的针对蛛式航线网络的定量研究成果。综上研究表明，枢纽轴辐式航线网络凭借其良好的网络结构，国内外学者将大部分研究都聚焦于该类航线网络的规划设计，但更多关注于理想运行环境中航线网络的经济效益和服务质量，而对空战场条件下的穿越走廊基本网络规划设计问题研究甚少[10-11]。国内外大多数学者对枢纽轴辐式航线网络进行研究，所构建模型常为混合整数规划的SUMApHMP模型[12]，在问题规模较小时可利用精确算法求得最优解，但是对于解决战场空域内机场数目多，且飞行流量大的穿越走廊基本网络规划问题，还存在一定难度。

基于此，针对不考虑限制空域影响的穿越走廊基本网络规划问题特点，本文将禁忌搜索算法与Floyd算法有机结合，提出一种组合的SUMApHMP模型求解算法，并验证算法有效性。

1 基本网络规划模型描述

通过枢纽机场的中转集散，枢纽轴辐式航线网络内的运输机装载效率明显提高，从而达到减少飞行批次，节约运力成本的目的，提高了航空军事运输的战场保障能力。然而，枢纽轴辐式航线网络自身也存在一定的缺陷：所有非枢纽机场起飞的运输机，不论是否满载，不论起讫机场距离远近，都必须经过枢纽机场中转；大批装备物资装卸和分拣需要在枢纽机场进行，需要占用大量的人力物力来确保规定空运投送任务时间内的保障水平。因此，本文在基本枢纽轴辐式航线网络中采取多重分派的方式，即个别流量较大的非枢纽机场可以同时连接多个枢纽机场，对物资运输进行摊派，减少对单个枢纽机场保障水平的影响，构建多重分派航线网络 (非枢纽机场能与多个枢纽机场直接相连)如图1所示。

图1 多重分派航线网络Fig.1 Multi-assignment aviation network

无容量限制的严格型多重分派枢纽轴辐式航线网络实际运作情况较为复杂，为方便研究，符合实际情形，将假设条件和已知条件陈述如下：某战区中有n个机场，预置枢纽机场p个；枢纽机场之间的穿越走廊为点对点式全连通型，非枢纽机场之间的连接需要经过枢纽机场进行中转；枢纽机场和航线上不存在运输容量的限制，能够为大批量运输机的起降、物资装卸、飞行情报服务提供保障；运输机从起始机场起飞到达目的机场，只能沿路径最短的穿越走廊飞行；一个非枢纽机场可以和多个枢纽机场直接连接(多重分派)；枢纽机场之间的空运成本存在一个折扣系数ρ(0<ρ<1)；由于航空军事运输活动对时效性的要求，最多只允许两次经过枢纽机场进行中转。

根据ρ-HM-MA模型[8]，可针对不考虑限制空域(火力打击区、禁飞区、杀伤盒、危险区等)影响的穿越走廊基本网络规划建立SUMApHMP模型。

目标函数：

(1)

(2)

(3)

(4)

(5)

Hk∈{0,1} (∀k∈N)

(6)

xiklj≥0 (∀i,k,l,j∈N)

(7)

式中：wij为机场i到机场j的O-D流；xiklj为从机场i流经枢纽机场k到终点机场j的交通流量占wij的比例；cij为机场i到机场j的直达单位运输成本代价；Hk为枢纽机场选择变量，当机场k为枢纽机场时，Hk=1，当机场k不是枢纽机场时，Hk=0。

目标函数如式(1)所示，为了使网络运行总成本最小化，由cik+ρckl+cij可以看出，总成本分为三项：第一项非枢纽机场至枢纽机场运输成本，第二项为枢纽机场之间中转运输成本，第三项为枢纽机场至非枢纽机场运输成本。枢纽机场数目约束如式(2)所示，即枢纽机场个数预置为p；运输方式限制如式(3)所示，任意非枢纽机场之间的运输任务需要通过枢纽机场中转完成；非枢纽机场约束如式(4)～式(5)所示，即当某个机场不是枢纽机场时，运输机不能经该机场中转。

本文在研究中没有考虑限制空域(火力打击区、禁飞区、杀伤盒、危险区等)的影响，仅考虑了机场布局、交通流量、各机场对距离等的影响，对战场航空军事运输网络进行初步规划。

2 混合禁忌搜索算法设计

本文研究的不考虑限制空域的穿越走廊基本网络模型属于NP-hard问题，且求解规模较大，因此，在利用禁忌搜索算法[13]选取枢纽机场节点的同时，不能随机生成初始解，需要对初始解进行构造，这样可使算法具有较快的收敛速度，并且确保算法不会陷入局部最优。采用Floyd最短路径算法[14]对机场节点之间的穿越走廊路径进行安排，并以求得的所有机场节点间的穿越走廊最短路径作为禁忌搜索算法的初始解。

(1) 编码及初始解构造

模型采用自然数编码，集合N={1,2,3,…,n}表示n个机场节点形成的枢纽轴辐式网络，每个自然数对应一个机场接点。由于网络中的飞行流量和机场间距离矩阵等因素对枢纽机场的选取过程会产生直接的影响，因此在选取初始解的枢纽机场时需要选取合理的办法对待规划空域内的所有机场节点进行排序。本文采用的指标评价各机场节点[7]如式(8)所示：

(8)

式中：α、β为加权系数，且有α+β=1。

可以看出，某机场飞行流量越大，且到其它各机场距离之和越小，则该机场节点权值越大，即成为枢纽机场的概率越高。

选择权值最大的前p个机场节点作为枢纽，并利用Floyd最短路径算法对机场节点之间的穿越走廊路径进行安排，以求得的所有机场节点间的穿越走廊最短路径，作为禁忌搜索算法的初始解。由模型可知，共有p个枢纽机场节点在穿越走廊网络中起中转作用，因此，当实际应用于求解该模型时，Floyd最短路径算法运算过程只需要迭代p次。

(2) 适配值函数设计

(3) 邻域结构及其候选解

本文的邻域结构依靠单点交换方式，即移动当前解中的枢纽机场节点。假设S为初始解，S中有p个元素，即p个枢纽机场节点，则还有n-p个机场节点等待替换S内的枢纽机场节点。当初始解S以外的n-p个机场节点替换初始解S中的某个节点后就产生了S的一个邻域解S*，显然初始解S的邻域解集合N(S)中总共有p(n-p)个邻域解。例如S={1,2}，N={1,2,3,4}，则S*={1,3}，{1,4}，{2,3}，{2,4}。如此得到的四个邻域解将作为候选解以产生下一步解。

(4) 禁忌对象选择

当一个非枢纽机场Spoke和一个枢纽机场Hub进行单点交换后，便将机场Hub放入禁忌表中，此时禁忌对象就是机场Hub，处于被禁忌状态。当未达到预置迭代次数，即禁忌长度不为零，机场Hub不会被释放到搜索空间中(满足特赦准则的情况除外)，避免了迂回搜索的情况发生。本文以先进先出(First in First Out)作为禁忌表的状态更新原则。由此可知，禁忌解的邻域结构是通过机场节点的换入换出产生的，因此对解的变化进行禁忌可以通过对S中的换出节点进行禁忌来实现。仍以S={1,2}为例，表示机场1、2为模型中的枢纽机场，当变换S={1,4}时，表示机场4成为了枢纽机场，机场2变成了非枢纽机场，这时选择机场2作为禁忌对象，它作为曾经的枢纽机场节点，在未来的一定迭代次数内会避免其再次成为枢纽机场节点，从而可以使算法轻易跳出局部最优解。

(5) 禁忌长度确定

(6) 特赦准则

本文将特赦准则分三种情形进行分析：①在禁忌表中的候选解优于当前最优解时，则将该解从禁忌表中释放，作为当前最优解继续参与搜索；②在当前最优解优于禁忌表中的候选解以及搜索空间中的候选解时，则将搜索空间中的最优解作为当前解，以便跳出局部最优；③在所有候选解均被禁忌时，释放禁忌表中的最优解作为当前解，使得搜索能够继续。

(7) 停止准则

当达到算法预定的最大迭代次数或者目标函数的最优值在设定迭代次数内无法改进时，算法停止。

3 算例分析

为了验证模型和算法的有效性，本文选取10个机场节点作为研究对象，采用MATLAB 2014a作为程序开发平台，编写程序实现禁忌搜索算法和Floyd最短路径算法求解基于枢纽轴辐式理论的穿越走廊基本网络规划模型，输出最佳枢纽机场布局和穿越走廊路径分配。各机场节点的(x,y)坐标值以及机场对之间飞行流量如表1和表2所示(表中数据根据文献[17]整理获得)，为简化运算，机场之间的物资流量对称一致。机场节点空间分布如图2所示。下面利用所提出方法对10个机场节点的穿越走廊基本网络进行构建。

表1 机场节点坐标Table 1 Coordinate of each airport node

图2 机场节点空间分布Fig.2 Space distribution of airport nodes

表2 机场节点间的飞行流量Table 2 Flight flow between airport nodes

表3 机场节点间的距离矩阵Table 3 Distance matrix between airport nodes

根据10个机场节点的流量矩阵和距离矩阵，对混合禁忌搜索算法的求解效果进行验证分析，其中枢纽机场数目分别取p={2,3,4}，折扣系数分别取值ρ={0.4,0.6,0.8}。该验证基于MATLAB 2014a编程实现，且混合禁忌搜索算法的运算终止条件为最大迭代次数超过max_int=30或连续4次得到相同解。为验证算法准确性，本文利用Lingo 9.0对模型求解的最优解和混合禁忌搜索算法的计算结果进行比较分析，对比结果如表4所示，可以看出：利用混合禁忌搜索算法和Lingo 9.0软件都能得到模型的最优解；在求解速度上，利用混合禁忌搜索算法的求解时间远远少于利用Lingo 9.0的求解时间。另外，当折扣系数ρ确定后，随着枢纽机场数目p增大，穿越走廊网络的运行总代价会变小。然而，枢纽机场通常会被敌方列入高价值目标清单进行打击，实战时的穿越走廊网络设计并不是枢纽机场越多越好，较多的枢纽机场增加了机场的防御难度，而且在现实中枢纽机场的设置与维护需要大量财力、物力和人力的投入。

表4 混合禁忌搜索算法和Lingo 9.0求解模型结果的对比Table 4 Comparison of model solution results obtained by hybrid taboo search algorithm and Lingo 9.0

本文以p=3，ρ=0.4为例，不考虑限制空域的穿越走廊基本网络进行规划，由混合禁忌搜索算法求解得到最优枢纽机场为：机场1、3和4，对应的连接矩阵Rp如表5所示。

表5 连接矩阵Rp (p=3,ρ=0.4)Table 5 Connection matrix Rp (p=3,ρ=0.4)

表6 穿越走廊基本网络路径安排结果(p=3,ρ=0.4)Table 6 Results of TC basic network path arrangement(p=3,ρ=0.4)

根据路径安排结果，可设计出10个机场节点在不考虑限制空域情况下穿越走廊网络图，如图3所示。

图3 不考虑限制空域的穿越走廊基本网络规划结果Fig.3 Planning result of TC basic network without considering the restricted airspace

从图3可以看出：三个枢纽机场通过穿越走廊相互连接，构成穿越走廊干线网络；非枢纽机场中，机场9与三个枢纽机场直接连接，机场6和10与两个枢纽直接链接，而机场2、5、7和8只与一个枢纽机场直接连接，这些构成了穿越走廊网络支线网络。

至此，不考虑限制空域影响的穿越走廊基本网络初步规划已完成。下一步，需要对加入限制空域的穿越走廊基本网络进行重规划，模拟空战场实际，考虑穿越走廊网络与空中限制区、禁飞区和对空火力打击区等限制空域之间的结构关系，避免出现空域冲突，造成己方火力误击误伤的严重后果。在加入限制空域后，穿越走廊网络的空域运行情况如图4所示。

图4 加入限制空域后的穿越走廊基本网络运行情况Fig.4 Operation of TC basic network after the restricted airspace is added

从图4可以看出：加入限制空域后，各机场对之间共有7条穿越走廊与限制空域交汇，存在明显的冲突隐患。记path(i,j)表示连通机场i和机场j之间的穿越走廊，obstacle_paths表示战场空域环境中存在空域冲突的穿越走廊的集合，则根据图中信息可知，obstacle_paths={path(1,3),path(1,4),path(1,9),path(1,10),path(3,9),path(4,5),path(4,6)}。

4 结 论

(1) 对不考虑限制空域的穿越走廊基本网络规划的SUMApHMP数学模型，提出了一种混合禁忌搜索求解算法。算例分析表明，所提出算法和Lingo 9.0软件都能求得最优解，但前者在求解时间上要远远少于后者。

(2) 根据混合禁忌搜索算法优化结果，设计出不考虑限制空域情况下的穿越走廊网络图，验证了模型求解结果的正确性，也为考虑限制空域的穿越走廊可行网络规划搭建了基本框架。

(3) 出于说明模型和算法的需要，在研究空战场条件下的穿越走廊基本网络规划问题时没有考虑限制空域情况，仅仅初步规划了空战场航空军事运输网络，而加入限制空域后，穿越走廊基本网络规划问题将更为复杂，也是下一步需要深入研究的问题。