求解三维装箱问题的启发式搜索算法

2023-04-13梅志虎唐志波

中国水运 2023年3期

梅志虎，唐志波

（浙江海洋大学，浙江舟山 316022）

1 引言

据中国海关统计，2021年度我国外贸进出口总值到达27.8 万亿元人民币，同比增长14.2%，出口值15.3万亿元人民币，同比增长10.8%，进口值12.5 万亿元人民币，同比增长18.7%，如图1所示。在我国，九成以上的外贸货物均通过港口进出[1]。随着港口货物运输量呈现螺旋式上升的趋势，越来越多的外贸公司加速发展信息化管理，提高公司的效率，增加企业及行业的经济效益。研究三维集装箱装箱问题对于提高运输效率、降低运输成本、提高企业盈利能力、减少污染物排放等方面具有十分积极的现实意义。

图1 近五年进出口总额统计

2 三维装箱问题的数学模型

2.1 装箱问题描述

装箱问题是一个经典的组合优化问题，属于经典的NP-hard 问题，有着广泛的应用，在日常生活中也屡见不鲜。通常定义为：给定i 种长宽高为Li、Wi、Hi 的集装箱和j 种长宽高为lj、wj、hj，重量为mj 的货物[2]，然后将所有物品都装入箱子中，要求装入箱子中所有物品的总体积不能超过箱子的容积，并且使集装箱的利用率达到最高。装箱问题的示意图如图2所示。

图2 装箱示意图

2.2 模型假设

本文主要研究单个集装箱装载问题，考虑以下约束条件：

（1）体积约束：货物的总体积不超过集装箱的最大容积；

（2）载重量约束：货物的总重量不超过集装箱的最大承载能力；

（3）不重叠约束：货物之间不允许重叠放置；

（4）正交放置约束：摆放过程中货物边缘与集装箱边缘平行或者垂直。

（5）稳定性约束：在实际应用中，装载必须保证每个装载的货物必须有集装箱底部或其他货物的支撑，以防止货物被悬挂。

（6）方向约束：一些特定类型的货物在确定装载顺序时，还需考虑摆放方向。

2.3 模型建立

在实际装箱中，由于订单货物和货运车辆的多种多样，对于公司来说，集装箱的空间利用率是他们最关心的问题，因此，基于以上分析的内容，建立目标函数和装箱约束的数学模型如下。

2.3.1 目标函数为集装箱体积利用率最优

其中，i 为货物的序号，i=1,2,…,N，ai为第i 种货物在集装箱里面的装载数量，vi为第i 种货物的体积，Z 为集装箱的体积利用率，V 为集装箱的容积。

2.3.2 货物重量约束

其中，mi为第i 种货物的重量，M 为集装箱的最大载重量。

2.3.3 货物体积约束

其中，vi为第i 种货物的体积，V 为集装箱的容积。

2.3.4 货物装载三维尺寸约束

其中，xi,yi,zi为第i种货物在集装箱内部的位置坐标，li,wi,hi为第i 种货物的长宽高，L,W,H 为集装箱的长宽高。

2.3.5 方向约束

其中，bli,bwi,bhi为第i 种货物对应的边竖直放置作为高度，0 表示不可以，1 表示可以。

3 启发式搜索算法

本文所研究的启发式搜索算法具体流程如图3所示。通过两个启发式算法来获取当前剩余空间的可行性块，为后续寻优过程提供较为良好的初始解；随后采用带有深度限制的深度优先搜索算法和贪心算法对装载方案进行寻优。

图3 启发式搜索算法

3.1 启发式算法

3.1.1 简单块

简单块是由同一朝向的同种类型的箱子堆叠而成的，箱子和箱子之间没有空隙，堆叠的结果形成一个长方体[3]。将所有排列组合生成并满足约束条件的简单块，按照体积降序排序存储到块表中，用于迅速生成指定剩余空间的可行块列表。如图4所示，nx,ny,nz 分别表示在对应坐标轴上的箱子数。

图4 简单块

3.1.2 空间分割

如图5所示，将一个长为l，宽为w，高为h 的可行块装入到这个剩余空间中[4]，此时该剩余空间除去该可行块所占有的体积外，将该空间划分成前(Front)、右(Right)、上(Up)三个空间，但是在分割前(Front)、右(Right)两个空间时，可以有如图5（a）和图5（b）两种分割方式，图5（c）箭头所示的空间便是图5（a）和图5（b）的可转移空间，随着装箱的需要，可转移空间可以被转移给另一个剩余空间重新利用。