基于0-1整数规划的舰船内集装物资存放方法

于辉，王治国，李晶晶，叶又东，韩海荣

1 海军驻大连船舶重工集团有限公司军事代表室，辽宁大连116005

2 中国舰船研究设计中心，湖北武汉430064

0 引 言

大中型水面舰船在执行作战任务及海上补给的时候，需要运输大量的武器弹药、零部件和生活物品等物资。为了满足作战需求，避免较高危险性的物资长时间暴露于甲板，需安全高效地进行物资运输［1-2］。采用军用物资集装化储运对提高物资保障速度至关重要［3］，美国海军将船内物资的快速运输作为一项重要内容写入海上补给发展规划［4］。要想在未来信息化战争中实施高速度、大运量、远距离和全方位的物资保障，必须大力推进军用物资集装化运输工作的开展［5］。但由于集装物资一般体积较大，受船型和船体结构的影响，物资集装化后不利于在舱内储存和运输。

舰船内部集装物资的存放实质是一种三维箱装问题（3D packing problem）［6-7］，即在满足舰船约束和货物要求的条件下，以存放效益最大化为目标，找到一种将集装物资装满船舱的方案。目前有大量关于船舶集装化物资存放的研究。例如：孙俊清等［8］对船舶稳定性的多港口集装箱配载问题进行了研究，基于0-1 整数规划，通过改进遗传算法对问题进行求解，使得集装箱配载效益得到明显提升；汪达钦等［9］通过对散货摆放规则的分析，将三维问题简化为一维问题，提出了出厂物流整体优化的散货船舶配载模型与算法；Todd 等［10］以针对单港口的配载为题，根据多个标准，采用遗传算法进行配载计算。但这些研究大多是针对集装箱船舶，目标函数为单一经济指标，只考虑在船舶甲板上的装卸，并未涉及到船舶内部的存放问题，并且对船舶内部物资存放效益指标也缺乏指导。因此，针对舰船内部集装物资存放的特点，研究集装物资存放方法以提高存放效益，具有较大的研究和实用价值。

本文首先根据舰船内部集装物资存放的特点，对问题进行形式化描述，接下来根据形式化描述，定义舰船内部集装物资存放的一般目标函数和约束条件，提出基于层次分析法（AHP）［11］的集装物资价值量评估方法，从而构建基于0-1 整数规划的舰船内部集装物资存放数学模型，并给出加速该模型计算的思路。最后，利用Excel 对实例进行规划求解，并通过运用CAD 布置来证明方法的有效性。

1 问题描述

集装物资一般采用标准化接口，分为若干种规格，可以描述成规整的长方体。集装物资相对散货物资而言，最大的特点就是采用了标准化的接口，减少因接口转换而带来的时间浪费，且简化了操作，便于物资流转，因此应用广泛。集装物资在舰船内的存放不同于集装箱运输船舶在船体外的存放，其存放有以下特点：

1）集装物资存放需要一定的操作空间。集装物资是采用集装储具（托盘、包装箱等）存放的。由于舰船出海时间较长，需要对存放的物资进行定期检查、维护、管理和消防等工作，因此合理的存放间距是必要的。不同集装物资之间的安全间距因物资种类的不同而不同。

2）某些集装物资因某些原因不能存放在同一个舱室。譬如出于安全性考虑，强还原性物资和强氧化性物资不能存放在同一个舱室；油气不能与精密电子产品放在同一个舱室；有毒有害物资不能与食物水源放置在同一个舱室等。

3）物资存放受船型、船体结构等影响。一般物资储存舱室位于船体底部，受船型影响较大，特别是对V 型等高速船舶而言，越往底部，船型收缩越严重。在存放集装物资时，需考虑到船型的影响，充分利用船上宝贵的空间资源。

4）物资存放受运输设备和运输通道的影响。由于物资一般存放在船体底部，因此需要较长的运输通道。另外，对于大型集装储具，需要借助运输设备才能运输，因此，在布置物资时需要考虑运输设备的行程。

5）相比运输船舶而言，舰船装载的集装物资排水量占比不大，因此对舰船稳定性影响不大。

6）对于既定的基本任务，需要一定量的必备保障物资。对用户来说，基本的生活保障物资和保障任务基本完成的物资是必须满足的，即保障基本所需的物资数量具备一定的门限值，且所有存放方案必须满足该值。

舰船出海一般伴随着多项任务，不同的任务对物资有着不同的需求，因此各类物资具备不同的价值量，即物资在舰上存放的效益。从上述分析中，可以发现，舰船内部集装物资存放方法是一类典型的多约束多目标决策问题。对于该决策问题，进行如下描述：

1）存放问题P=(A，F)，其中，A 是集装物资单体价值量，F 为集装物资存放方案。

2）存放方案F=(M，T，V，N)，其中，M 是规划的某类物资储存量的门限值，T 是集装物资单体尺寸，V 是船舱容量，N 是集装储备物资混放的约束。

2 基于0-1整数规划的存放方法

2.1 总体思路

对问题的描述进行分析。若是采用传统的三维箱装问题求解方法，则需考虑集装物资的长、宽、高三维空间因素，其算法计算量会因变量的增加呈指数上升，不仅计算速度慢，而且可能导致内存溢出致使无法得到计算结果。

针对该问题，最有效的方法是降低问题维度，将复杂的三维问题转化为二维甚至是一维问题，以快速求解，得到满意答案。基本思路如下：

1）根据运输通道能力，考虑舱室内同一垛布置同一类集装物资，将三维问题转化成二维问题，每个储存位置作为1个0-1变量。

2）将通过单一集装物资布置填充整个可布置的二维空间。

3）将填充完成的二维空间重合，枚举其中的干涉情况。

4）剔除同一舱室内不可混放的集装物资布置。

5）考虑门限值，作为集装物资存放的最小值约束。

6）以价值量为目标函数系数，求取定义模型的最大值。

2.2 目标函数

某集装物资是否存放于舱内某处空间，会有2 种状态，可以用0 或1 来表示，与0-1 整数规划思想吻合。

将整个舱室存放空间用某一类集装物资全部填充，则任意一处集装物资存放空间可以视为1个存放单元xi，j，其中i 为集装物资的种类编号，j为该类集装物资的布置单元编号，xi，j=1 表示该存放单元存放集装物资，xi，j=0 表示该存放单元不存放集装物资。其他集装物资也采用xi，j来表示，并检查空间干涉情况。

令λi为集装物资i 单体的价值量，z 为总价值量。则整个存放问题P 的目标函数为：

2.3 价值量

价值量的确定采用层次分析法（Analytic Hierarchy Process，AHP）。该方法是一种定性与定量分析结合的多目标决策分析方法，其将决策者的经验判定给予量化，适用于目标（因素）结构复杂且缺乏必要数据的情况，在国内外应用广泛。使用AHP 对舰船内物资存放价值量进行分析的示意图如图1 所示。

图1 贮存价值量层次结构图Fig.1 Hierarchy of stored value

其中，目标层反映了提高物资存放效益是本次出海总存放目标；准则层反映了一大类物资，按照具体的任务分类，增加该类物资效益即增加了任务完成的能力，例如生活保障物资、救援医疗物资、作战物资等；措施层反映了存放的具体物资，其中某项具体物资可能对应多个准则层的大类物资；比如桶装饮用水既是生活保障类物资，也是救援医疗物资。

依据图1 进行矩阵运算可以得到A～K 等集装物资的价值量。具体步骤如下：

1）先对目标层和准则层以“增加一类物资效益”为权重1，然后以其为基础，以专家经验和认知标准，让多个专家打分，得到“增加二类物资效益”和“增加三类物资效益”的价值量。

2）对各个专家打分求平均值，然后对这3 个数值进行归一化处理，得到准则层物资大类相对目标层的价值量，整理为矩阵Ⅰ。

3）然后对准则层和措施层采用步骤1）和2），得到措施层物资相对准则层物资大类的价值量，整理为矩阵Ⅱ。

4）最后，通过矩阵Ⅰ和矩阵Ⅱ的矩阵相乘得到措施层物资相对目标层的价值量λi，整理为矩阵Ⅲ。矩阵Ⅲ即为目标函数式（1）中的输入λi。

2.4 约束条件

存放方案F 必须满足约束条件。令布置单元长度为Li，宽度为Wi，高度为Hi，则集装物资单体尺寸T={Li，Wi，Hi} ；令集装物资i 储存量门限值为mi，则mi∈M ；令舱室可存放空间横向尺寸为p，纵向尺寸为q，垂向尺寸为g，则船舱容量尺寸V={p，q，g }。根据尺寸参数，用集装物资对每一个舱室进行全部填充，而后将填充后的图样叠放在一起，明确集装物资之间的干涉关系，以及根据混放约束N 得到存放方案F 的一般约束条件，具体叙述如下。

干涉约束：

对于任意集装物资i 的布置单元j 和与它干涉的其他集装物资a 的布置单元b 有如下关系：

不可混放约束：对于任意舱室内的集装物资i和a，不可混放下的约束如下：

式中，j 和b 为同一舱室所有的布置单元。

门限值约束：

式中，j 为舱内所有布置单元。

0-1整数约束：

2.5 加速计算建议

基于0-1 整数规划会随着问题规模的不断扩大呈现指数上涨，所以在0-1 规划的基础上，还需进一步改进，以缩小算法搜索空间来加速计算。针对上述方法特点，给出加速计算的建议：

1）分支界定法。该方法是一类常用的加速计算方法，为通过已经求解的一个可行解，将解的目标值作为约束插入数学描述中，其理由是希望找到一个比这更优的解。该约束将最优解和其他解分离开来，使其能够在更小的空间进行搜索。当执行一段时间后，再从中找到一个更优解，以该解作为约束替换之前的。如此，则将原本指数性增长的搜索方法替换成多项式类型，极大减少了搜索空间和时间。

2）根据舱室要求，减少舱室内不同集装物资的组合种类。比如有些舱室门开口太小，大型集装物资无法进出；有些舱室有严格的卫生要求，那么该类舱室只能存放符合卫生标准的集装物资。

3）某几类集装物资可以等同考虑，减少输入参数数量。由于集装物资采用了统一的规格，因此会出现几种集装物资采用同一种储具的情况。这时可以将这些采用同一种储具的物资等同考虑。

4）根据物资的特殊存放要求，减少不同物资的存放组合。比如食品类物资宜分块集中存放，以方便使用；质量大的物资宜在舱底存放，以减小对船舶稳性的影响。

3 实例分析

本文选择Excel 为规划软件。“规划求解”是Excel 中的一个加载宏，其线形和整数规划问题取自Frontline Systems 公司的John Watson 和Dan Fylstra 提供的有界变量单纯形法和分支定界法。由于Excel 的应用广泛，且易于操作，对低复杂度的规划模型具备一定的规划能力，因此，采用Excel规划案例能够证明方法的有效性。

例子说明：有A～F 6 种集装物资需放入2 个船舱内，其中A，B 为甲类物资，C，D 为乙类物资，E，F 为丙类物资，甲类物资和丙类物资不可混放。6种集装物资门限值分别为2，2，1，1，1，1，集装物资尺寸如表1 所示，舱室尺寸如表2 所示，求各种集装物资的布置方案。

表1 集装物资尺寸Tab.1 Size of integrated materials

表2 舱室尺寸Tab.2 Size of the cabin

根据实例说明，进行求解，流程如图2 所示。

图2 求解流程图Fig.2 Resolving flow chart

求解步骤如下：

1）根据AHP 方法，由专家打分，分解得到6种集装物资准则层与指施层的价值量比值分别为1，1，3，3，5，5，如图3 所示。

2）考虑加速计算。根据例子可以看到，集装物资A 和B 的尺寸相当，B 可以等同集装物资A 处理；同样，C 和D 的尺寸相当，E 和F 的尺寸相当，D可以等同集装物资C 处理，F 可以等同集装物资E处理。

图3 AHP 分解图Fig.3 Decomposition chart by AHP

3）建立目标函数：

式中，x1，j表示集装物资A（B）的存放，x2，j表示集装物资C（D）的存放，x3，j表示集装物资E（F）的存放。x1，j，x2，j，x3，j的价值量与所表示的集装物资相同，分别为1，3，5，门限值为所表示的集装物资门限值之和，分别为4，2，1。

4）根据上述数据，画出填充图（数字表示布置单元编号）如图4 所示。

图4 物资填充图Fig.4 Materials fill diagram

5）根据填充图和例子数据，列出如下约束条件。

干涉约束条件为

式中i，j，a，b 表示任意集装物资i 的布置单元j 和与它干涉的其他集装物资a 的布置单元b。

不可混放约束：

门限值约束条件为：

0-1整数约束：

6）使用Excel进行规划，求解值见表3。

表3 Excel规划结果Tab3 Programmed results by Excel

7）根据规划结果进行CAD 布置，以验证规划结果的合理性，如图5所示。

图5 CAD 布置结果Fig.5 Placement result by CAD

由表3 和图5 可以看出，规划结果合理，验证了本文提出的规划方法的有效性。能够通过Excel 进行快速求解，说明该方法有效控制了算法规模，成功降低了运算维度，具有较大的学术研究和工程实用价值。

4 结 语

集装物资存放是舰船内部物流中常见的问题，本文根据舰船内部集装物资的存放特点，进行问题的形式化描述，提出了基于0-1 整数规划的存放方法。该方法首先定义了舰船内部集装物资存放的一般目标函数和约束条件，提出了基于AHP 的集装物资价值量评估方法和基于0-1 规划的数学模型，然后给出了加速该问题0-1 整数规划的计算思路，最后，利用Excel 对实例进行规划求解，并通过CAD 布置来证明该方法的有效性。结果证实，该方法能够较快速地进行求解，结果正确合理，具有较大的研究和实用价值。

但是，本方法是依据已有的填充方案，因而只是在已有方案的基础上进行的优化，最优解也是局部最优解，不能代表整个问题的最优解，这也是加速运算，缩减搜索空间的代价。所以，下一步考虑通过合理增加已有填充方案，扩大搜索空间，采用递进求解的方式，在保证运算时间的基础上，尽量扩大搜索空间，以最大限度地逼近最优解。

［1］王凯，赵彦森.基于改进遗传算法的舰船物资转运方案研究［J］.舰船电子工程，2013，33（6）：114-115，162.WANG Kai，ZHAO Yansen. Material transport scheme on ships based on improved genetic arithmetic［J］.Ship Electronic Engineering，2013，33（6）：114-115，162.

［2］张晓东，童剑，郭敏，等.舰船物资转运方案计算机辅助决策算法研究［J］.中国舰船研究，2011，6（4）：104-110.ZHANG Xiaodong，TONG Jian，GUO Min，et al. Com⁃puter aided decision-making method for material trans⁃fer planning on ship deck［J］. Chinese Journal of Ship Research，2011，6（4）：104-110.

［3］陈兴刚，刘振华，郭宝华.实施军用物资集装包装之我见［J］.包装工程，2006，27（3）：229-233.CHEN Xinggang，LIU Zhenhua，GUO Baohua.Discus⁃sion on implementing integrated packaging of military supplies［J］. Packaging Engineering，2006，27（3）：229-233.

［4］王晓林.美国海军海上补给装备发展趋势研究［J］.物流技术，2007，26（6）：127-128.WANG Xiaolin. Research on the trend of replenishing equipment of US Navy［J］. Logistics Technology，2007，26（6）：127-128.

［5］侯仁海，王金松，殷鹏.集装箱滚装托盘系统在军用物资运输中的应用研究［J］. 国防交通工程与技术，2010（6）：60-63.HOU Renhai，WANG Jinsong，YIN Peng. A study of the application of the container roll-in-and-roll-out platform to the transport of military materials［J］. Traf⁃fic Engineering and Technology for National Defence，2010（6）：60-63.

［6］DYCKHOFF H.A typology of cutting and packing prob⁃lems［J］. European Journal of Operational Research，1990，44（2）：145-159.

［7］DYCKHOFF H. A new linear programming approach to the cutting stock problem［J］. Operations Research，1981，29（6）：1092-1104.

［8］孙俊清，陈忱，刘凤连.考虑船舶稳定性的多港口集装箱配载问题［J］.计算机工程与应用，2012，48（32）：236-243.SUN Junqing，CHEN Chen，LIU Fenglian. On stow⁃age planning for mult-port container transportation based on stability constraint［J］. Computer Engineering and Applications，2012，48（32）：236-243.

［9］汪达钦，霍佳震，张丽华.出厂物流整体优化的散货船舶配载模型与算法［J］.工业工程与管理，2010，15（5）：11-16.WANG Daqin， HUO Jiazhen， ZHANG Lihua.Bulk-cargo ship stowage model and algorithm for the optimization of external logistics［J］. Industrial Engi⁃neering and Management，2010，15（5）：11-16.

［10］TODD D S，SEN P. A multiple criteria genetic algo⁃rithm for containership loading［C］//IEEE Proceedings of the 7th International Conference on Genetic Algo⁃rithms，1977：674-680.

［11］汪应洛.系统工程［M］.2 版.北京：机械工业出版社，2002.