基于回溯算法的海上兵力投送船舶选择优化研究

王建鹏

摘 要：随着我国经济水平的提高以及国家军事战略体系的逐渐构成，部队海上投送船舶选择优化问题已经成为新时期我国军事准备所面临的一项重大现实问题。本文建立了部队海上投送船舶选择模型，并利用回溯算法对模型进行求解、验证，在保证所用船舶完成任务的总时间最小的同时，力求使用船舶运力最少。

关键词：海上投送;船舶选择;回溯算法

1大规模作战部队海上投送船舶选择问题描述

大规模作战部队海上投送船舶选择问题可以描述为：作战需将大量的人员和装备进行海上投送，现有可用船舶（如海军登陆舰、登陆艇、陆空军船艇登陆艇、民用杂货船、散货船、滚装船、多用途船、集装箱船）等各类型船各若干艘，从这些可用船中进行选择，合理搭配一组船舶组合，目标函数是使投送时间都尽可能短，同时使占用船舶运力（船舶运输装备的能力和运输人员的能力）尽可能小，所选船舶组合需要同时满足待运部队所需总配载面积、装备配载面积、人员乘载面积等要求。

2大规模作战部队海上投送船舶选择模型

2.1船舶运力约束处理

船舶运力包括船舶运输物资装备的能力和运输人员的能力，本文将船舶运输装备的能力和运输人员的能力统一用面积y表示，即

式中：Kz为该型船的客位数;为单人所需的配载面积;有效为该型船的有效配载面积，船舶有效面积既可配载装备，也可配载人员。

2.2目标函数处理

选船问题实际考虑的优化目标主要有2个：一个是船舶的运力最小;另一个是所有船舶完成任务的时间之和最小。这2个目标间是存在矛盾的，很难找到共同的最优解，需要采用多目标规划的方法求解折中非劣解。

目标函数一：船舶的运力总和y最小，数学表达式为

式中：为船型i的运力;为问题的决策变量，表示船型i被选择的船的数量。

目标函数二：所有被选船舶完成任务的总时间z最短，数学表达式为

式中：为该船型的平均装卸载时间，指在理想码头条件下和工人平均操作熟练程度下，装载部队各型装备所需的平均时间。

由于上述2个优化目标的单位不统一，不能直接转化为单一的目标函数，因此，本文采取功效系数方法解决多目标规划问题。将2个目标函数通过线性加权法进行归一化处理，得到新的目标函数YZ，其结果为

式中：a为目标函数Y的权重系数;b为目标函数Z的权重系数，且a+b=1。可以针对不同类型的任务通过咨询专家赋予a，b不同的比值，从而达到根据任務的轻重缓急合理搭配船型比例，统筹安排运力资源的目的。

2.3模型的建立

根据以上分析，本文对大规模作战部队海上投送船舶选择问题建立如下模型：

式中：X=（X1，X2，...，Xn）为决策向量集合;为船舶运力集合;为船舶载质量集合;为可选船舶可装载质量装备面积的集合;为决策向量，≥0，∈Z，i=0，1，…，n，为非负整数，例如： =3为i型船舶有3艘被选中;n为船型的型号数量;m为装备的型号数量;z为重装备的型号数量;为j型装备数量;为j型重装备数量;为j型装备的限制面积;为j型装备的配载系数。

3 基于回溯算法的模型求解

3.1算法思想

有一类叫做“组合总和”的问题可以用回溯算法就行求解，问题描述为：给定一个无重复元素的数组“candidates”和一个目标数 “target”，找出“candidates” 中所有可以使数字和为 “target” 的组合。“candidates”中的数字可以无限制重复被选取。此处以candidates = [2，3，6，7]，target = 7为例进行说明。候选数组里有 2，如果找到了 7 - 2 = 5 的所有组合，再在之前加上 2，就是 7 的所有组合;同理考虑 3，如果找到了 7 - 3 = 4 的所有组合，再在之前加上 3，就是 7 的所有组合，依次这样找下去。以 target = 7 为根结点，每一个分支做减法，减到 0 或者负数的时候，就到了叶子结点;在结果为 0 的子叶节点进行“结算”，即从结果为0的子叶节点到根节点的路径作为一个组合添加到结果集，此结果集就是题目所求组合。对结果进行观察不难发现，其中有[2，2，3]，[3，2，2]，[2，32]之类的结果，可以求解完毕以后用去重复的方法予以剔除，或在计算过程中以“减枝”的方法去除，节约计算时间。

3.2求解步骤

结合前文所建立的模型，对3.1中的算法做进行修改，修改后计算步骤如下：

①将模型中的的总运力需求设为target;

②进行递归计算;

③当target小于或等于0时停止计算;

④将子叶节点到根节点的路径作为一个组合添加到结果集;

⑤计算全部结果集中各组合的目标函数值;

⑥目标函数值最大组合的即为最优方案组合。

4算例分析

某演习中，第1梯队在舰队和作战机群强大火力掩护下，向敌海岸防御前沿发起了猛烈的攻击。根据作战计划，担负任务的某部作为第2梯队，必须在第1梯队占领敌阵地，夺取敌沿岸港口后，实施后续登陆，现该部队已整装待命。现命令某军区联合作战指挥部迅速、合理选调船舶，在最短时间内完成该集团军的装载任务。模型中走道系数（0≤≤1）取0.2，统一取0.875 ，当运输任务为“紧急”时，令模型中目标函数控制参数a=0.1，b=0.9，将实验结果代人模型中可验证该结果满足模型约束，说明实验结果的正确性。

参考文献

[1] 苑德春，潘藩，葛同民，罗雷.大规模作战部队海上投送船舶选择优化研究[J].军事交通学院学报，2013，15（1）.

[2] 姚恩瑜，何勇，陈仕平.数学规划与组合优化[M].杭州：浙江大学出版社，2001：22-25.