基于混合算法的导弹部队铁路机动路径选择

詹仁超，李应岐

(第二炮兵工程大学，西安 710025)

我国铁路网纵横交错，十分复杂，平时导弹列车可以像普通列车一样在铁路上运行，但战时，我们的一举一动都处于敌人的严密监视之下。如何选择合适的机动策略，是完成机动作战任务面临的首要问题。本文主要对战略导弹列车机动中的路线选择进行了研究，其意义主要表现在2 个方面。第一，具有很好的实用价值。在未来作战中，武器的运输都将面临路线选择问题且必须快速做出决策。对于战略导弹而言，做出的决策是否可行，将直接关系到战争的进程甚至战争的胜负。对这些问题进行深入细致的研究，无疑可以为指挥员做出科学的决策提供可靠的依据和支持。同时，对提高战略导弹武器的机动能力和生存能力都有重要意义。第二，机动路线的选择问题，与生活、商业活动中的对策问题、车辆路径问题、最短路径问题有着诸多不同，但是对这些问题的研究实质上都是对算法的研究和改进，具有一定的理论意义。

1 战略导弹铁路机动路线问题建模

1.1 问题的基本描述

在战略导弹实施铁路机动作战的过程中，所面临的一个重要问题就是根据各种情报，选择合适的机动路线［1-2］，以保证我战略导弹的生存，并最终完成上级赋予的任务。

对这一问题，进行如下抽象描述，以便于建立模型:预警条件下战略导弹铁路机动中的路线选择，就是在根据敌对我的侦查监视情况(即导弹列车在不同区域内机动被敌发现的概率p1)，敌方可能采取的打击手段和在遭受打击时我方的生存概率p2，作战区的路网情况(即网络图和边的权值)、道路周边的基础设施建设情况(如桥梁和隧道的数量、可供导弹隐蔽的场所及其分布)等情报和数据，并根据一定的判断准则，确定出1 条或是几条合理的路线。其实质是一个在作战环境下的车辆路径问题。由此，我们可以将战略导弹铁路机动中的路线选择问题做出如下数学意义上的描述:给定一个完全图(铁路网)G=(V，A)，其中V ={v0，v1，…，vn}为图的顶点集(站点的集合)，A ={(vi，vj)|i≠j，vi，vj∈V)为边集。矩阵C= ( cij)n×n中的元素cij表示从vi到vj的距离。列车从v0出发，经过某些站点到达发射阵地vk(1≤k≤n)。在满足某些约束条件下，如何安排列车行程，使到达列车顺利到达vk并完成作战任务。

下面给出问题的约束条件:

1)总里程S 约束，列车一次机动里程不大于技术条件所允许的最远机动距离，以保证导弹到达发射阵地后具有最佳的技术状态。

2)时间T 约束，即导弹列车必须在指定的时间内到达某阵地，否则将会贻误战机。

3)生存概率p 约束，所选择路线必须保证导弹的生存，这是完成任务的先决条件。

1.2 建立模型与算法步骤

1.2.1 建立模型

在上节中，给出了问题的基本描述，确定了完全图(铁路网)G=(V，A)，顶点集(站点的集合)V ={v0，v1，…，vn}，边集A={(vi，vj)|i≠j，vi，vj∈V)和邻接矩阵C = ( cij)n×n几个主要元素，并给定了总里程S、时间限制T、生存概率p 几个约束条件。

除此之外，还必须确定以下因素:列车在不同路段的实际机动速度vij和最大机动速度vij0;敌方对我作战区域的监视情况，即导弹在不同路段机动时被发现的概率pij1;在得到预警信息后避开敌人打击的概率，或者说是在预警条件下敌方采取一定手段对我实施打击后的被击毁概率pij2。

由于军事活动的特殊性，本文研究的铁路机动路线的选择问题，与传统的VRP 和TSP 问题有许多不同，主要表现在以下几个方面:

1)军事活动中，不需要通过图中所有点，只需要到达目标点。

2)军事活动中，对同一个点，在一条路线中可以几次选择，也就是说在路线中可以出现回路。

3)军事活动中，机动路线不一定形成回路，也就是说起点与终点很可能不是一个点。

因此，针对该问题建模时，传统的许多约束条件都可以除去，只考虑与完成作战任务相关的几个条件即可。在确定以上所有数据之后，便可以得到其数学模型:

目标函数: maxp

目标函数表示最终确定的机动路线是使得导弹的生存概率最大。这一具体数值与pij1、pij2、vij、vij0、所选路线的设施建设和周围环境等因素密切相关。

1.2.2 算法步骤

GA 具有良好的并行性，TS 则具有很强的“爬山”能力，将两者结合，优劣互补，将会有效地提高优化算法的效率。本文将遗传算法和禁忌搜索算法相结合组成GATS 混合算法［3-5］，即以GA 算法为整个算法的框架，对GA 经过遗传操作运算后产生的新种群的个体，用TS 算法进行局部搜索［6-7］，改善群体的质量，具体步骤如图1 所示。

需要强调的是在产生初始群体中，没有要求列车必须通过每个站点，也没有每个站点只能通过一次的限制，也就是说，染色体的长度是可变的，而且一条路线中还可能有迂回回路。要产生初始群体，必须确定染色体的长度，即站点的数量。

可以通过以下方法确定

对于具有不同长度的染色体，本文中将其称为具有不同的染色体结构。起点和终点是确定的，也就是说染色体最多有m -1 种结构，在起点与终点之间最多有m -1 个站点。若用M 表示起点与终点之间站点个数，则0≤M≤m-1。每一种染色体结构，对应一个M 值，都可用插入法生成初始群体。用这种方法产生的初始群体也有利于提高算法的性能。

图1 GATS 混合算法流程

2 算例

假设我战略导弹部队接到命令，要从当前位置机动到某一阵地。首先对铁路网中的各站点进行编号。假设一个有30 个站点的铁路网，将出发点编号为1，终点编号为30，其余各点可随机编号。为了计算简便，假设各路段的建设标准相同，也就是说列车在各路段行驶的最大速度相同，记为v。同样，在一次最大机动里程范围内，列车在行驶中对导弹仪器设备的影响相同。

因此，路线选择主要受到时间和安全性的限制。时间主要与路线长度有关，要在规定的时间内到达指定地点;安全性主要与沿线设施建设、自然环境、伪装防护和敌方侦察监视有关。对于不同区域，敌人侦察监视的强度可能不同，算例中为了简化计算过程，设敌方对整个作战区域内的侦查监视强度取为p=0.8，即在未采取任何措施情况下敌方的发现概率。

相邻两站点间的路线长度矩阵(km)，即邻接矩阵，记为D

假设列车最快机动速度是v =100 km/h，完成任务的时限是T=3 h，初始种群中个体的数目是5。将以上数据代入到仿真程序中，得到结果如表1 所示。

通过仿真结果可以找到3 条可行路线，分别是M =2 情况下有2 条、M =4 情况下有1 条。按照上表中的顺序，第1条路线的生存概率最小、路线最长(接近了机动时限内的最远机动距离300)、有一个可能影响通行性的点。第二、三条路线的生存概率都为0.7，路线长度相差不大，第2 条中有一个可能影响通行性的点，而第3 条中没有。所以，应该选择第3 条路线作为机动路线。

除M=2、4 以外，其他情况下均为得出可行解。表中仍给出了在M =5、7 情况下各一个解。从解中可以看到，这2条路线中存在子路径，分别是17—21—17、17—20—17，而且这2 条路线的生存概率均高于可行路线的生存概率。在实际作战中，机动经常采用迂回、穿插等战术，也就是说，机动路线中会包含有子路径。以上2 条路线虽不是可行路线，却说明了该算法符合军事作战中的实际情况，而且其仿真结果也表明，机动中采取迂回等战术可以有效提高生存概率，符合作战实际。这些都说明了该算法是可行有效的。

表1 GATS 程序仿真结果

3 结束语

运筹学的目的是为指挥员做出决策提供可靠依据，而不是直接做出决策，所以最后提供给指挥员的应该是尽可能多的可靠信息，而不是某一条单独的路线。本算法在结果中并未直接给出应选择的哪一条路线，而是给出在不同M 值下的k 条(本例中为5，即染色体数目)路线，由指挥员根据战场的实际情况、作战经验和其他标准选择最终的机动路线。

［1］郭强，谢秉磊.随机旅行时间车辆路径问题的模型及算法［J］.系统工程学报，2003(18):244-247.

［2］Martins.On a multicriteria shortest path problem［J］.European Journal of Operational Research，1984 (16):236-245.

［3］韩万林，张幼蒂.遗传算法的改进［J］.中国矿业大学学报，2000，29(1):102-105.

［4］Millar J A，Potter W D. An Evaluation of Local Improvements Operators for Genetic Algorithms［J］.IEEE Trans.on SMC，1993，23(5):1340-1351.

［5］张淑荣，苏兵.谈谈禁忌搜索算法［J］.信息技术教学与研究，2008(48):228-229.

［6］王正志，薄涛.进化计算［M］.长沙:国防科技大学出版社，2000:70-75.

［7］吴斌，吴坚，涂序彦.快速遗传算法［J］.电子科技大学学报，1999，28(1):49-53.