无人钢材仓库智能起重机路径规划

无人仓库，由于整个仓库不需要人力劳动，照明系统可以长时间保持关闭为黑灯状态，亦称黑灯仓库。无人仓库主要依靠智能化物流系统的应用集成，物流系统可自动运转，卸货—存货—提货—分拣—贴标—装货等整套物流流程实现智能化、自动化、网络化，同时，由于智能物流系统整个系统不需要人力劳动，可以避免货物的破损、错发等一系列人为错误。

起重机是无人仓库应用最多的一种满足搬运工艺使用的智能化物流装备，应用在造纸、钢铁等众多工业领域。钢铁工业中的工艺起重机通常用于谨慎且可靠地搬运钢材等货物。利用起重机实现的空中物流可以充分利用空间，无需在地面上规划路径。此外，起重机的工作效率高，可以直接集成到生产设施的整体物流中。

智能起重机系统是具有自动控制的操作和移动功能、可编程功能、人机交互功能和自诊断功能，能完成起重机各种任务的、具有高度灵活性的自动化机器系统。它具备一些与人或生物相似的智能能力，如感知能力、规划能力、动作能力和协同能力。它是一个由机械、电力电子、液压、信息、网络等多个学科高度集成的系统。涉及到多刚体动力学、多变量多耦合非线性控制、大型钢结构动态分析、GPS、检测、监测和控制等多个学科。无人仓库的工艺起重机就是一种智能起重机。

1. 起重机搬运货物的路径

为了提供完善的服务，开发合适的仓库管理系统WMS (Warehouse Management System) 十分必要。文中介绍了一种采用基于云的仓库管理解决方案，可以方便地对仓库操作，包括对货物或材料进、出库的全过程进行控制和管理。仓库操作包括库存管理、分拣、质量控制和审计，可随时了解和掌握仓库的实时状态，有利于满足不同情况下的不同需求，保持对库存和营运资金的控制。该系统囊括整个物流过程，从收货、中间商和运输服务商，以及堆场管理的生产过程等。基于云数据的科学管理，便于对每一次生产、每一次发货和交货，以及任何其他操作进行追踪，登录简单容易而且可形成日志。实时而准确的库存水平报告，有利于优化钢材的库存，避免缺货的情况发生。中央云管理系统可管理多个跨地区的仓库，包括供应商管理的库存、第三方仓库和寄售库存，与销售、制造和采购订单、运输和收货形成信息集成，实时更新库存和预期库存。仓库里至少会配置一台用于搬运装卸钢材起重机。假设仓库有 p 个不同的区域或堆场用于存放钢材，每个堆场可以是空的，或存放着一些某一种类型的钢材，设计和规划一个起重机搬运装卸系统。

假设每个堆场存放钢材的容量无限；起重机的搬运没有延迟；起重机一次只能搬运一种钢材，且只能搬运装卸位于各堆场钢材堆顶部的钢材；每次必须对每个堆场钢材堆顶部的钢材进行重新定位（即重新排序）。最终目的是尽量减少起重机的搬运次数。

约束条件为起重机只能搬运各堆场钢材堆顶部的钢材；必须满足发货日期 R 和交货日期 D；根据发货日期R 和交货日期 D 确定是否进行搬运装卸，何时进行。从搬运起始堆场 o 到目的堆场 d 的搬运列表 M 可表示为

M = [(o1, d1),…,(ok, dk)]

0 ≤ oi ≤ p, 1 ≤ di ≤ p+1 （1）

式中，oi 为第 i 个搬运起始堆场；di 为第 i 个搬运目的堆场；p ∈ N，为仓库的堆场数量；n ∈ N，为订单的数量；Ri ∈ N, i=1,…,n，为发货日期；Di ∈ N,i=1,…,n，为交货日期。堆场 0 为钢铁厂，堆场 p+1 为用户或运输船。

最终目的是使起重机搬运的次数最小（即确定 M的最小值）。

图 1 显示了四种（件）钢材 A、B、C、D 从钢厂到仓库，再从仓库到用户的过程和路径，以及它们的搬运列表 M。（图 1 a 为表示在钢厂生产的顺序；图 1 e到图 1 m 为仓库堆场只能堆放 2 层货物；图 1 j 到图 1m 为根据用户要求将 B 和 C 取出并搬运、同时发货给用户的过程。）

图 1 起重机搬运货物路径示例

2 基于 MIP 的起重机路径规划

MIP 问题即混合整数规划问题。线性规划问题指满足目标函数是线性函数、约束条件是线性等式或不等式两项的优化问题。求最小化目标函数或最大化目标函数。若无特殊说明，文中涉及的线性规划问题为最小化目标函数。最小化目标函数与最大化目标函数可以相互转换，没有实质上的区别。

线性规划问题包括整数规划问题、0-1 问题和混合整数规划问题。根据对变量的限制，线性规划问题可以更细地区分出：

1）整数规划问题 指变量为整数的线性规划问题。该问题将连续的线性规划跳转到离散的整数规划。求解整数规划的难度比求解线性规划的难度更大，当问题的规模较大时更为明显。

2）0-1 规划问题 指变量只能取值 0 或 1 的线性规划问题，是整数规划中特殊的一种。

3）混合整数规划问题 指所有变量中有些变量可以取值连续，部分变量只能取整数值的线性规划问题。根据定义，混合整数规划问题可以概括出其一般形式

(P) min c T x

s.t. Ax ≥ b （2）

xj , integer j ∈ I

除少数整数规划可以用线性规划的单纯形法直接求解外，一般整数规划必需寻找新的求解方法。全整数规划的分枝定界方法可以用于求解混合整数规划问题和0-1 规划问题。分支定界法（Branch and bound）是一种求解整数规划问题的最常用算法，这是一种在问题的解空间树上搜索与迭代进行求解的方法，选择不同的分支变量和子问题进行分支。与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，每一个活结点只有一次机会成为扩展结点。它不但可以求解纯整数规划，还可以求解混合整数规划问题。

分支定界法步骤：1) 创建队列 Q；2) 将根节点推入Q；3) 当 Q 不为 0 时，h ←从 Q 中取出一个节点，即某个堆场中空的位置；4) i 将货物放置到下一个节点 h；5)i 都可以被堆放到每一个堆场 s；6) h‘ ←节点 μ 的副本；7) 将货物 i 堆垛在堆场 s 的节点 h‘；8) 从堆有 h‘ 的堆场的顶部开始搬运进行交货；9) 如果 h‘ 是一个叶节点，即没有子节点的节点；10) 检查是否 h‘ 有一个更好的解决方案；11) 把节点 h‘ 推入 Q。

通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），称为定界。分枝定界法的主要思路为在每次分枝后，界限超出已知可行解集目标值的子集不再进一步分枝（许多子集可不予考虑，称为剪枝）。将仓库中的堆场区域等价于子集或分枝，将各堆场中的区域等价于分枝中的解集，就可以采用分支定界法对仓库规划问题进行求解优化。这也是一个混合整数规划 MIP 问题。采用分支定界算法确定解决方案。当某个订单的货物要发货或更换堆场存放时，要先检查所有堆场区域，选择哪个堆场可以放置，并为它们分别确定一个备用堆场（创建一个分枝），以防当该订单的货物从堆场货物顶部取出交付时，没有备用堆场（分枝）暂存货物。

离散事件仿真是用计算机对离散事件系统进行仿真实验的方法，是一种在状态变化的系统中使用的仿真方法，其运行成本低。每次仿真都与随机性有关，每件货物堆放的堆场均是从候选堆场列表中随机选择的。不同的运行产生不同的解决方案，需要大量搬运仿真才能获得良好的结果，可以使用试探法对几种堆垛策略进行测试，最后才能选择出最优的运行方案。

仿真过程为使用公式描述问题，创建模型，再读取一个案例实例对模型进行修正，然后将它发送到解算器。仿真策略为采用启发法为一种货物选择一个堆场，货物到达时或把一件货物从堆场顶部搬运到另一个货位的下部时，要重新排序。交货优先于堆场发货，同步发货是通过反推交货日期来实现的。同步交货从堆场顶部到底部逐步进行。

定位启发式过程为放置货物时，根据某些规则为每个位置即堆场分配一个值；再根据最优分类构建一个候选货位列表，仿真过程为使用公式描述问题，创建模型，再读取一个案例实例对模型进行修正，然后将它发送到解算器。仿真策略是采用启发法为一种货物选择一个堆场，货物到达时或将一件货物从堆场顶部搬运到另一个货位的下部时，要重新排序。交货优先于堆场发货，同步发货是通过反推交货日期来实现的。同步交货从堆场顶部到底部逐步进行。

定位启发式过程为放置货物时，根据某些规则为每个位置即堆场分配一个值；再根据最优分类构建一个候选货位列表，但这取决于采用哪一种的启发法；从这个列表中，随机选择一个来堆放货物。如图 2 所示，要将堆场 1 和堆场 2 中的 B 和 E 取出交货，采用以下表 1 中表示的两种搬运规划，可比较它们的搬运次数。

图 2 搬运规划对比示例图

表 1 搬运规划对比

3. 路径优化

不同的货物在出入库时，可遵循不同的出入库原则，图 3 显示了“后入先出”、“先入先出”和“双端队列”的三种出入库原则。可以采用“灵活性优化”启发法来对搬运活动进行规划定位。定义货位的灵活性为可以堆放的具有不同交货日期的货物的最大数量，且不能出现反向重复搬运。故为一个货物选择候选堆场应满足以下条件：①最大限度地提高灵活性，不能出现反向重复搬运；②如果反向重复搬运是不可避免的，应尽量减少灵活性。采用基于仿真优化的启发法，运行N 次独立的仿真模拟，选择起重机搬运次数最少的那个方案。进行每一个N 次仿真时，对于每个货物，根据所选的启发法来选择堆场，并继续进行货物的发货和交货，直到完成所有货物的交货，就确定了需要搬运的次数以及相应的搬运列表。

由于许多实际情况与仿真条件有差异，影响了仿真的结果，相关影响因素包括：

1）实际的堆场与建模的条件不同，如双端队列（见图 4），即一个端点允许堆入和搬出，另一个端点只允许堆入。

2）起重机的搬运活动有限的（见图 5），因此，从给定位置可以到达的堆场数量是有限的。即一个端点允许堆入和搬出，另一个端点只允许搬出。

3）货物在某些堆场位置限制了起重机的搬运活动，即：当货物堆放在某一位置后，搬运活动的路径为动态变化的，此时就要对各种动态状态进行对比优化，以期获得最优的搬运方案。

4）如果起重机的搬运效率低，会导致搬运严重延迟，立即交货的设想无法实现；

5）其他影响因素包括：装车 / 船耗费的最少时间要求；货物在车 / 船到达前可能需要在货场重新定位；目标为装车 / 船的搬运次数最少；由于某些因素影响，可能同时要搬运多件货物等。

图 3 出入库原则图示

图 4 双端队列

图 5 受限的搬运

4. 结论

1）决定或改变搬运路径中的某一步，可能对后续的搬运过程造成不同影响；

2）应基于仿真进行路径优化；

3）可以采用不同的方法解决路径规划问题；

4）做出决定时，动态路径的配置可能发生变化；

5）尽量采用形式化问题描述的语言建模。通过改进和应用仓库智能起重机路径规划，能有效地提高仓库的运营效率，可更好地满足不同情况的需求。