部队陆空联合投送路径优化

侯小平，胡坚明，陈兴德

(1.驻成都铁路局军代处，成都 610082； 2.清华大学，北京 100084)



部队陆空联合投送路径优化

侯小平1，胡坚明2，陈兴德1

(1.驻成都铁路局军代处，成都 610082； 2.清华大学，北京 100084)

在成建制部队陆空联合投送中，为选取最优投送路径，采用图论的方式构建虚拟联合投送网络图，分析网络边(弧)权值，对“人装一体”投送条件下航空装运卸时间以及各种投送方式之间换装时间，建立以时间最短为目标的陆空联合投送路径优化数学模型，并使用遗传算法求解模型。模拟验证表明，该模型能够求得时间最短的优化路径。

陆空联合投送；路径优化；遗传算法

随着军队职能使命的不断拓展和交通运输的快速发展，部队投送只采用单一投送方式已不能满足部队快速机动的要求，联合投送是大势所趋，特别是充分利用航空这种快速投送方式[1]，采取陆空联合投送迅速将成建制轻装部队“人装一体”地投送到指定地域。但从当前研究现状看[2-4]，公铁联运研究多、陆空联合投送研究少，联合投送路径定性分析多、定量研究少，“人装分离”的立体投送研究多、成建制部队“人装一体”联合投送研究少。因此，研究“人装一体”条件下成建制部队陆空联合投送路径优化问题，具有十分重要的意义。

1 模型建立

1.1 问题描述

西部战区某轻装部队接到上级命令，要求其在最短的时间内从驻地O投送至目的地域D，途经若干节点且相邻两点间有多种投送方式可以选择。根据西部交通实际，只考虑铁路、公路、航空3种投送方式组合，暂不考虑水路投送方式。在这种情况下，需要选择一条合理的投送线路和最佳投送方式组合，使部队联合投送时间最短。

1.2 构建虚拟网络图

联合投送网络不仅空间跨度大，而且十分庞杂，包含众多交通信息，如果不对其进行适当的抽象简化，最优路径的搜索将会比较繁琐。因此，本文将每一个实际节点按照所需运输方式数量的不同，扩展出与之相对应的虚拟节点，每个虚拟节点表示从实际节点出发的一种运输方式[5-6]。

图1 虚拟联合投送网络

结合联合投送的实际情况，该虚拟网络图的特点如下：

(1)该虚拟网络图用平面图的方式表达了一个4个水平面和n个垂直面的立体空间图，其中每一个水平面对应一种投送方式，每一个垂直面表示不同投送方式之间转换；

(2)N1和Nn分别为投送的起始点和终到点，O、D为虚拟源点和终点，为了方面最短路求解，O到N1、Nn到D的权值均为0；

(3)对于同一水平面的不相邻节点，如果存在弧线连接，说明这两点之间存在不经过第三方的直达投送线路，这与联合投送的复杂网络特性是相一致的；

(4)联合投送的实际网络中，不可能每个节点都能提供4种不同的投送方式，对此，在同一层面，如果两个相邻节点之间不提供某种投送方式，则该相邻节点无连接弧或为无穷大。

1.3 建立陆空联合投送路径优化模型

1.3.1 情况假设

(1)各种投送方式的转换只能在节点处发生，且每一节点只能实施一次换装；

(2)两相邻节点之间只能选择一种投送方式，若不存在投送方式，则两者不相连或为无穷大；

(3)相同投送方式之间或途中不发生中转和倒装；

(4)不考虑拥堵、晚点等因素对投送时间的影响；

(5)部队在装载或换乘时，铁路车辆和飞机均已集结完毕，则不需考虑等待时间。

1.3.2 目标决策分析

从联合投送的过程看，投送的总时间T=tz+ty+th+tx,其中：tz为部队在集结地域出发装载的时间；ty为部队在各节点之间的运行时间；th为部队投送中所有的换装时间；tx为部队在目的地的卸载时间。

实际中，各种投送方式的装运卸时间都可以根据投送任务实际和交通设施设备保障能力加以求解。但在“人装一体”条件下，进行陆空联合投送需要考虑公路或铁路投送与航空投送之间的衔接、换乘问题，对于运力比较大的铁路和公路投送来说，可以一次性投送大批量的人员和装备，但航空投送受运输机的单机装载能力和保有数量的制约，对成建制部队航空投送时，需采取飞机“循环套用”的运输组织形式，即按照空运顺序，循环使用飞机分批次运送部队，直至空运完毕。针对这一特殊情况，着重对航空投送时间进行分析研究。

(1)根据部队人员数量和装备物资尺寸、重量，预测所需客、货机架次数。部队成建制进行航空投送时，通常使用客机运送人员、货机运输装备物资，客机通常按部队总人数除以客机航次载客量的90%来估算，货机通常用装备物资总重量和总长度两个指标来估算，并需综合考虑装卸载机场保障能力。

(2)根据可供选择的货机机型、架数以及架次数，计算单机往返次数。这是由于我国货机短缺，适合轮式装备装载的大中型运输机更是极其有限，通常需采取飞机“循环套用”的运输组织形式，即按照空运顺序，循环使用飞机分批次运送部队，直至空运完毕。比如，选择了5架飞机，需飞行15个架次，则需飞行3个梯队，每个梯队包含5个架次。

(3)战时特殊情况下，部队实施空中投送可采取在机场半关闭或全关闭的状态下装卸载，并尽可能开展多架次、多机种平行装卸载作业。

因此，可以求出航空投送实际装载时间为

实际运行时间为

实际卸载时间为

1.3.3 建立模型

根据上述分析，建立以时间为最短的陆空联合投送路径优化数学模型：

minT=tz+ty+tx+th=

(1)

约束条件：

(2)

(3)

(4)

(5)

(6)

目标函数式(1)表示求陆空联合投送时间最短。约束条件式(2)保证从任一节点出发只能选择一种投送方式，式(3)保证任一节点至多发生一次换装，式(4)保证投送方式的连续性，式(5)和式(6)表明决策变量只能取整数0或1。

2 算法设计

部队陆空联合投送路径优化问题不是一个线性规划问题，而是一个典型的NP问题，用精确算法有一定的困难，而遗传算法[7-9]的染色体编码序列与路径节点序列存在关联性，即一条染色体的编码可以表示为一条路径，以及遗传算法所具有的并行性特点，可以较快地在全局寻找到最优解，因此本文运用遗传算法对部队陆空联合投送路径优化问题进行求解。

2.1 染色体编码

采用比较简单易懂的自然数编码方式，这样能与投送节点编号和投送方式代码相对应。染色体的基因就是投送节点编号与投送方式代码间隔编码，其排列顺序代表着从起点到终点的路径。基因构成为：第一个和最后一个分别为起点编号“1”、终点编号“n”,偶数位置为投送方式代码，奇数位置为投送节点编号。一般来说，投送节点编号一般用1,2,…,n表示，为了相互区别，投送方式代码用0、-1、-2、-3表示，其中：0表示两个节点间不连通；-1表示铁路；-2表示公路；-3表示航空。

2.2 建立适应度函数

考虑到遗传算法中一般是适应值越大越好，以时间最短为目标的路径优化模型适应度函数可以取F=1/T。

2.3 染色体选择

本文采用轮盘赌选择法。假设初始群体的个体数量为M，各染色体的适应值为F1,F2,…,Fn，则染色体被选择的概率为

2.4 染色体交叉

采取单点交叉，且交叉的点为除1、n外所有投送节点编号。由于投送节点位于染色体中的奇数位置，设染色体基因串长度为m，那么交叉点就是从3,5,…，m-2中随机选取。

(1)从上一代选择染色体A和B的基因中随机确定各自交叉点，交叉点必须位于1和n之间。

(2)进行交叉操作。主要分两种情况：如果两个交叉点对应的节点编号相同，则将个体A交叉点的左半部分与个体B的右半部分通过相同的交叉点连接在一起，得到新的个体A1；同理，将个体A交叉点的右半部分与个体B的左半部分通过相同的交叉点连接在一起，得到新的个体B1。如果两个交叉点对应的节点编号不同，则将个体A交叉点的左半部分与个体B的右半部分进行组合，并随机生成一条路径衔接两个交叉点，最终得到新的个体A1，同理可以得到新的个体B1。

(3)消除染色体中重复节点。对交叉后的染色体进行检查，若有完全相同的基因，则将相同基因间的路段删除，最终得到新个体。

2.5 染色体变异

根据编码方式，主要采取两种变异方法。

(1)变异位为染色体中奇数位的投送节点，则将该节点变更为其他节点，并重新确定变异节点与相邻节点的投送方式，以确保变异后的染色体有效。同时检查变异后的染色体是否存在重复地点，若有则删除。

(2)变异位为染色体中偶数位的投送方式，然后查看该投送方式连接的左右两个节点，并将该投送方式变更为这两个节点之间其他可连通的投送方式。如果这两节点之间只有这种投送方式，则不做更改。

3 算例验证

假设，某部队奉命从驻地出发，采取“人装一体”方式，运用铁路、公路、航空3种投送方式，机动至指定地域。其投送网络如图2所示。

图2 联合投送网络

该输送梯队包含200名官兵和30辆装备，其中装备为某式轮式装甲突击车，可摩托化机动并装运少数兵力(9人)。

鉴于当前我国航空投送装备数量严重不足的实际[10]，应急情况下能用于部队成建制航空投送的大中型运输机非常有限。本文假设一次性能调动参与部队航空投送的运输机为5架、客机1架，其技术参数见表1。

表1 运输机、客机技术参数

从部队装备实力和飞机装运能力、实际数量情况看，要完成该部航空投送，需要12架次飞机，即单机需往返1次，则可以根据航空运输装运卸时间的计算式进行求解实际装载、运行、卸载时间。假设该输送梯队以铁路、公路、航空投送方式在各线路的投送时间见表2，各节点铁路、航空投送装卸载时间见表3(航空投送时间已综合考虑了航空运力和单机往返次数等因素)。

表2 各节点之间的运输投送时间 h

表3 各节点装卸载、换乘时间 h

根据网络节点数可知，有效染色体的基因个数小于48个。设遗传算法的群体大小规模为300,交叉概率0.85,变异概率0.05,最大迭代次数为300次。

对于以时间最小为目标的路径优化问题，经遗传算法求解后得到染色体为1-3、10-1、13-1、15-2、16，其运输路径为1→航空→10→铁路→13→铁路→15→公路→16,时间为42.300 0 h。

算例表明，利用本文给出的模型研究部队陆空联合投送路径优化问题，符合铁路、公路、航空投送的特点和实际需要，而采用遗传算法是求解该问题的一种有效方法，能够求解得到时间最短的优化路径。

4 结 语

陆空联合投送是部队快速投送发展的重要方向，通过本文提供的模型和算法，能够较好地解决“人装一体”条件下成建制部队陆空联合投送路径优化问题，可为指挥决策者确定部队陆空联合投送路径优化提供有效的决策支撑。但是由于陆空联合投送路径优化问题涉及的内容以及各种不确定性因素较多，还需要进一步考虑铁路车辆和运输机的集结准备时间问题以及运输网络的动态性，并且必经点和禁行点问题也是联合投送中的一个重要问题，这些都需要下一步研究解决。

[1] 吴晓东,杨永伟.战略投送兵棋推演初探[J].军事运筹与系统工程,2011,25(3):15-19.

[2] 寇世强.兵力运输投送及其相关概念[J].国防交通,2005(3):29-30.

[3] 管井标,周赤非,许瑞明,等.战略运输投送能力评估方法研究[J].军事运筹与系统工程, 2011(2):76-80.

[4] 海军.部队战略运输投送模式问题探析[J].国防交通工程与技术,2013(5):8-10.

[5] 王清斌,韩增霞,计明军,等.基于节点作业随机特征的集装箱多式联运路径优化[J]．交通运输系统工程与信息,2010(6):137-144.

[6] 董洁霜.港口集疏运系统优化模型[J].上海理工大学学报,2007,29(5):453-456.

[7] RYAN J L, BAILEY T G,MOORE J T, et al. Reactive Tabu search in unmanned aerial reconnaissance simulations[C]//Proceedings of the 30th Conference on Winter Simulation，Washington DC,USA:IEEE Computer Society Press,1998:873-879.

[8] KOH S P, ARIS I B, HO C K, et al. Design and performance optimization of a multi-TSP (traveling salesman problem) algorithm[J]. AIML Journal, 2006, 6(3):29-33.

[9] 崔珊珊.遗传算法的一些改进及其应用[D].合肥：中国科学技术大学,2010.

[10] 程文明,何孟良,唐准,等.关于我军航空战略投送装备建设的思考[J].军事交通学院学报,2014,16(7):5-8.

(编辑：张峰)

Route Optimization of Military Air-ground Joint Projection

HOU Xiaoping1, HU Jianming2, CHEN Xingde1

(1.Military Representative Office in Chengdu Railway Bureau, Chengdu 610082, China; 2.Tsinghua University, Beijing 100084, China)

To select optimized projection route in military air-ground joint projection, the paper firstly establishes virtual joint projection network diagram with graph theory. Then, it analyzes weights of network sides (arcs) and studies aviation load-haul-dump time under the projection condition of personnel-equipment integration and converting time among different projection modes, and establishes a route optimization mathematical model of air-ground joint projection which taking shortest time as the objective. Finally, it solves the problem with genetic algorithm. The simulation verifies it can obtain optimized route with shortest time by this model.

air-ground joint projection; route optimization; genetic algorithm

2016-12-22；

2016-12-29．

国家重点研发项目(2016YFB0100906)；国家自然科学基金项目(61673232)．

侯小平(1983—)，男，硕士．

10．16807/j.cnki.12-1372/e.2017.05.002

E234

A

1674-2192(2017)05- 0005- 05

● 战略投送 Strategic Projection