基于 递归 算法 的 舰船装载泊位分配方案优化

王建鹏

国防大学联合勤务学院 北京海淀

摘 要：海上兵力投送装载过程中，如何合理分配装载泊位，使整个装载任务在最短时间内完成是部队制定装载方案时需要解决的一项重要难题。根据泊位装载配置特点和要求，运用运筹学理论构建装载泊位分配模型，并运用递归算法和计算机编程软件工具对模型进行求解，能够有效提高海上兵力投送泊位装载方案制定的时效性和科学性。

关键词：递归算法，装载，泊位分配，方案优化

0 引言

装载是海上兵力投送的关键环节，是完成兵力投送的首要任务。依靠健全的港口装载设施进行 装载是装载的首选方式，因此在装载过程中，如何科学配置装载泊位，使整个装载任务在最短时间内完成是部队制定装载方案时需要解决的一项重要难题。在进行较大规模海上兵力投送装载任务时，通常涉及的船只类型、数量较多，选可供选择的装载类型、数量较多，需装载装备的类型、数量较多，这些涉及因素都将直接影响装载任务完成的效率。通过构建泊位分配方案优化模型，使得在最短时间内完成整个装载任务，是提高海上兵力投送装载任务效率的有力方法。

1舰船装载泊位分配方案优化问题描述

1.1分配方案优化问题简述

舰船装载泊位方案优化问题可以描述为：大兵团作战需将大量的人员和装备实施海上投送，现有可用的典型船舶(如海军登陆舰、登陆艇、陆空军船艇登陆艇、民用杂货船、散货船、滚装船、多用途船、集装箱船等)各若干艘，要求将这些船合理分配在已有的泊位上进行装载，目标函数是使装载部队所用时间尽可能短，同时要使装载泊位满足所选船只的需求。可以抽象概括为将m艘舰船分配给n个泊位进行装载，求解出装载时间最短的方案。

1.2舰船装载泊位分配方案优化问题是不平衡最短时限指派问题

根据舰船装载泊位方案优化问题的描述，可以认为该问题属于指派问题。指派问题又称为分配问题，是运筹学中一类典型的组合优化问题，它在运输调度、工作安排及柔性制造系统中有着广泛的应用。传统的指派问题可以描述为：ｎ个人要完成ｎ项任务，由于每个人的专长不同，因此各人完成各项任务所需时间也不尽相同。已知指派第ｉ人完成第ｊ项任务所需时间为 ，试确定１个指派方案，使完成这ｎ项任务的总时间最少。但是在本问题中，泊位数n和待装载舰船数m不一定相等，因此该问题属于指派问题中的不平衡指派问题。同时，ｎ个泊位同时装载，任务完成时间由最后完成装载的时间所决定，即用时最多者达到最小，是最短时限指派问题，因此舰船装载泊位分配方案优化问题是不平衡最短时限指派问题。

2装载泊位配置方案模型构建

2.1 投送舰船及装载泊位分类

为了提高模型构建的通用性，现将投送舰船和装载泊位进行分类。投送舰船按照排水量和功能特点可划分为大型、中型、小型3种装载泊位类型。

2.2 投送舰船装载泊位配置条件

投送舰船配置装载泊位时应遵循以下条件：大型舰艇只能配置在大型泊位装载，不适合在中、小型泊位装载；中型舰艇只能配置在大型泊位或中型泊位装载，不适合在小型泊位装载；小型舰艇可以配置在大、中、小型泊位装载。另外，规定一座泊位同一时间内只能容纳 1 艘舰船进行装载。

2.3 装载泊位配置方案模型构建

已知在第ｉ号泊位装载ｊ型舰船所需时间为 ，当ｎ个泊位同时开始装载时，确定一个指派方案，在最短时间内完成所有装载任务。则此不平衡最短时限指派问题的数学模型如下：

i=1,2，…，n （1）

j=1,2，…，m （2）

目标函数为（1），旨在使完成任务时间最长的泊位所用时间最短，其中 为j型舰船在i号泊位的数量，当j型舰船不满足在i号泊位的装载条件时， =0。约束条件为（2）， 为j型舰船的总数量。

3运用递归算法求解不平衡最短时限指派问题

3.1算法思想

非平衡最短时限指派问题属于ＮＰ难题，随着规模ｎ的增大，其可行解数目以ｎ！的速度增大。当规模ｎ较小时，可以用穷举法精确求出问题的最优解；但是当规模ｎ较大时，穷举法耗时太长，不是一种好的算法。求解此类问题常用的方法有匈牙利法和启发式智能算法、最小调整法、大Ｍ法、生长树法、标号法等。本文结合问题实际，使用递归算法进行求解。用递归算法求解该问题时，求解思路是采取增加虚拟舰船的方法，根据泊位配置条件，将各个泊位上可装载的舰船数量加到最大，之后选出当前可优化的泊位中装载时长最长的，并对该泊位中可优化的、等待装载的船只中装载用时最长的船只数量进行优化，最后对各泊位和各类型船只的可优化状态进行检查后继续进行优化，递归的结束条件为所有泊位和船只优化都已完成。

3.2求解步骤

Step1 令 = ,i=1,2…n,j=1,2,…m；

Step2 令 =1 i=1,2,…n 为i号泊位对应的可优化状态，1为可优化，0为不可优化；

Step3 令 =1 j=1,2,…m 为j型舰船对应的可优化状态，1为可优化，0为不可优化；

Step4 计算 ，若 ，说明j型船已完成优化，则令 =0，j=1,2，…m；

Step5 计算当 >0时的 ，若 =0说明i号泊位已完成优化，则令 =0，i=1,2,…n；

Step6 求出满足 =1和令 取得最大值的i，（从可优化泊位中找出用时最长的泊位）；

Step7 将Step6中的i带入 ，求出使 取得最大值且 =1的j，（从泊位中选出可优化且用时最长的j型舰船）；

Step8 将Step6中的i、Step7中j带入 ，令 = -1；

Step9 将Step7中的j带入 ，若 ，说明j型船已完成优化，令 =0；

Step10 将Step6中的i带入 >0，并计算此时的 ，若 =0说明i号泊位已完成优化，则令 =0，i=1,2,…n；

Step11 计算 ，若 =0说明全部泊位已完成优化，优化结束，此时的 即为在i号泊位装载j型舰船的数量，矩阵X即为装载方案，且装载任务总用时为max 。若 >0,返回Step6。

4算例分析

某演习中，第1梯队在舰队和作战机群强大火力掩护下，向敌海岸防御前沿发起了猛烈的攻击。根据作战计划，担负任务的某集团军作为第2梯队，必须在第1梯队占领敌阵地，夺取敌沿岸港口后，实施后续登陆，现该部队已整装待命。现命令某军区联合作战指挥部迅速、合理安排装载方案，在最短时间内在某港口完成该集团军的装载任务。已知某港口现有泊位类型和数量见表1，某集团军需装载的船舶数量和类型见表2。

表1 某港泊位类型数量表

泊位类型	大	中	小
泊位数量	2	4	9

表2 需装载船舶数量类型表

舰船名称	滚装船	集装箱船	杂货船	散货船	多用途船	A型 登陆舰	B型 登陆舰	C型 登陆舰	D型 登陆舰	E型 登陆舰	F型 登陆舰	G型 登陆舰
类型	中型	中型	中型	大型	中型	小型	小型	小型	小型	小型	小型	小型
数量	1	2	3	4	5	6	7	6	2	3	1	2
装载 时间 （小时）	2.6	5.2	3.5	6.2	5.8	2.5	2.1	0.8	0.85	1	1.3	1.7

利用计算机编程将以上参数带入模型进行解算可得优化方案为表3,舰船全部装载完毕所需最短时为:max{12.4,

12.4,11.9,14.5,14.5,11.6,6.2,3.75,6.25,5.6,4.3,4.3,5.9,3.8,3.8}=12.4h

表3 泊位配置优化方案表

舰船名称 泊位编号	滚装船	集装箱船	杂货船	散货船	多用途船	A型 登陆舰	B型 登陆舰	C型 登陆舰	D型 登陆舰	E型 登陆舰	F型 登陆舰	G型 登陆舰	装载 时间
1（大型）	0	0	0	2	0	0	0	0	0	0	0	0	12.4
2（大型）	0	0	0	2	0	0	0	0	0	0	0	0	12.4
3（中型）	1	0	1	0	1	0	0	0	0	0	0	0	11.9
4（中型）	0	1	1	0	1	0	0	0	0	0	0	0	14.5
5（中型）	0	1	1	0	1	0	0	0	0	0	0	0	14.5
6（中型）	0	0	0	0	2	0	0	0	0	0	0	0	11.6
7（小型）	0	0	0	0	0	1	1	2	0	0	0	0	6.2
8（小型）	0	0	0	0	0	0	1	1	1	0	0	0	3.75
9（小型）	0	0	0	0	0	1	1	1	1	0	0	0	6.25
10（小型）	0	0	0	0	0	1	1	0	0	1	0	0	5.6
11（小型）	0	0	0	0	0	1	0	1	0	1	0	0	4.3
12（小型）	0	0	0	0	0	1	0	1	0	1	0	0	4.3
13（小型）	0	0	0	0	0	1	1	0	0	0	1	0	5.9
14（小型）	0	0	0	0	0	0	1	0	0	0	0	1	3.8
15（小型）	0	0	0	0	0	0	1	0	0	0	0	1	3.8
合计	1	2	3	4	5	6	7	6	2	3	1	2

5结论

装载泊位配置是部队制定装载方案的一项重要工作，本文运用军事运筹学理论和递归算法论构建装载泊位配置方案优化模型，有效解决了泊位配置优化问题，提高了部队装载方案制定的科学性和时效性。该模型算法可以扩展运用到大规模登陆作战中两栖输送舰船同时采用码头装载、抵滩装载、泛水装载时，多种上船点的优化配置问题。但装载配置问题是典型的NP问题，随着装载舰船、上船点种类及数量的增加，计算量迅速增长，算法效率必然会下降。因此，必须进一步改进算法，提高算法的效率。

参考文献：

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

[2]徐清华，季大琴，英 戈.基于遗传算法舰船装载码头配置方案优化[J].火 力 与 指 挥 控 制,2017,42(4).

[3]冷画屏，徐清华.大型两栖舰艇编队陆战兵力装卸载方案及流程研究［M］.广州：海军陆战学院，2015：20-21.

[4]任德华，卢桂章．最短时限最少耗费指派问题的一种解法［Ｊ］．自动化与仪表，２００５，２０（３）：１－４．

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

[6]陈晓娟，李学军，于胜，等．浅谈NP问题[J]．中国科技信息，2005(22)：53-54．