钢板倒垛问题的一种顶层搜索算法

2013-08-16郑武全冯定忠

机械设计与制造工程 2013年2期

郑武全，冯定忠，姜懿

(1．浙江工业大学机械工程学院，浙江杭州 310032)

(2．九江职业大学文化旅游学院，江西九江 330013)

在堆场管理中，倒垛问题是其管理的关键性问题，国内外对布局研究得比较多，但对倒垛问题的研究则相对较少。根据订单从堆场中选取合适的钢板，同时保证倒垛次数较少。关于倒垛问题的研究主要涉及3个领域：港口集装箱的倒垛问题;钢厂热轧板坯的倒垛问题;船用钢板堆场的倒垛问题。针对倒垛问题的研究主要分成两类：一类是仓储策略的研究;一类是数学方法的研究。针对港口码头集装箱的倒垛问题［1-2］，陶经辉、计三有等对此进行了研究。王敏等通过邻域搜索方法［3］研究了钢厂板坯倒垛问题。施敏等提出了一种垛位自动预约［4］的仓储策略，即将同一客户同一订单的钢板通过管理系统选取垛位集中堆放的策略来实现倒垛的零化。李耀华等提出采用离散粒子群算法［5］来求解倒垛问题，通过计算不同粒子的适应度函数即倒垛次数来选取最优粒子，从而转换为板坯选取目标。李铁克等采用单亲遗传算法［6］对倒垛问题也进行了求解。以上两者属于数学方法的研究。

本文在已有研究的基础上，提出了订单拆分重组的方法，对钢板倒垛问题进行了研究。研究目标是在保证钢板出库要求的前提下，对钢板订单进行拆分重组，再通过顶层搜索法，对所需钢板进行选取，以减少倒垛次数，提高堆场的作业效率。

1 问题描述和模型建立

1.1 问题的提出

钢板的出库是由客户订单决定的，尤其对于船板配送中心来讲，每个出库计划都是严格按照订单的要求，并根据订单中钢板的规格及数量，从堆场中选取合适的钢板，然后出库运输，以保证造船企业的生产。由于堆场面积通常都很大，垛位数量庞大，而且所需钢板通常不会位于垛位的上方，因此需要首先把位于所需钢板上方的钢板移开，放置在临近垛位上，才能获取所需钢板，在此过程中不可避免地会产生倒垛。同一规格尺寸钢板可能位于不同的垛位，不同垛位所产生的倒垛次数多数情况下是不同的，而且同一垛位中所需钢板可能不会只有一种。在上述约束条件下，如何根据订单从堆场中选取钢板，同时保证倒垛次数最少，就成为出库作业中急需解决的问题。

一般倒垛问题可以这样描述：设有n种规格的钢板若干，可以按一定规则对其进行编号为1，2，…，n，这n种钢板分布在堆场中m个垛位中，垛位编号是按照距离出货区域的距离远近进行编号。由于同种规格的钢板在不同垛位中所处的位置不同，可将钢板i取自垛位j的倒垛次数记作Cij，且规定移走一张钢板，然后再移回原垛位记作一次倒垛。现在需要按照编号顺序各选一件货物出库，假设一般性情况，同一垛位中相同编号的钢板不超过一个单位，目标是怎样使得倒垛的次数最少。图1是垛位m=6，钢板数n=8的情况。

图1 垛位m=6，钢板数n=8时的倒垛

1.2 模型的建立

倒垛问题可以看作带约束条件的任务指派问题，对于一个出库计划，我们可以建立数学模型［P］：

式(1)作为目标函数，表示在满足出库计划的条件下，使得倒垛次数最少。式(2)表示要求每个编号的钢板取且仅取出一件。式(3)～(5)表示每个垛位可取钢板的上下限。Hj表示垛位的高度。这里可以用垛位的钢板数来表示。式(6)中Xij为决策变量，表示货物i取自j号垛位，其中i是确定的。此模型又与广义指派问题存在差别，目标函数中的系数Cij不是一个常数，它是随着前(i-1)张钢板的选取情况而变化的。假设bi为出库前第i张钢板上的最初钢板数，φ(i)表示钢板所在的垛位，则有二次模型：

2 模型的求解

在以往的研究中，大多着眼于单个个体的求解，搜索范围着眼于整个的堆场。这种情况下会出现两个问题：(1)堆场中，钢板的堆垛都是按照一定的尺寸规格进行堆垛，这样就会形成很多独立的区域，如图2所示，假设有1，2，…，g个区域，在每个订单中，有些钢板属于同一个区域，有些钢板则属于另外的区域，如果属于不同的区域，那么这不同区域的钢板在倒垛方面就不存在关联。在这种情况下，对整个堆场进行搜索，就会增加不必要的搜索空间，增加搜索时间，降低出库效率。(2)通常情况下，在单位时间内堆场处理的订单不只一个，假设有1，2，…，k个订单。在这种情况下，不同订单中某些钢板可能属于堆场中的同一区域，如按顺序对订单进行逐个处理，不单单会增加行车的行程，降低出库效率，且逐个订单处理也会增加倒垛次数。例如：假设钢板编号为A，B的钢板分别属于订单e，f，且订单f出库时间在订单e之前，如图3所示。如果逐个处理订单f，e，则需要先倒垛3次，取钢板B，然后再倒垛2次，取钢板A，需倒垛5次。若订单e，f一同处理，则只需倒垛2次，即可获取所需钢板A，B。基于上述描述，本文提出了订单拆分、区域内重组的出库方法，以降低行车行程，减少倒垛次数，提高出库效率。按本文所提出的方法，需两步实现出库操作：(1)订单拆分，区域内重组;(2)区域内钢板的选取求解。

图2 堆场区域图

图3 钢板A B倒垛图

2.1 订单拆分，区域内重组

订单拆分：由于堆场是按照钢板的规格尺寸在一定的区域堆放，因此可以将订单内所有的钢板，按照其所在的区域进行拆分。拆分操作：假设堆场单位时间内需要出库的订单共有k个，从订单K(K∈(1，2，…，k))的第一张钢板开始，按照其所在堆场区域，自动拆分到区域 G(G∈ (1，2，…，g))，依次进行拆分，直到订单K的最后一张钢板。按照上述的操作原则，对单位作业时间内所有的订单进行拆分，直到所有订单内的所有钢板都拆分到其所在区域，如图4所示。订单拆分完毕之后，各个区域便获得了来自多个订单的钢板出库作业计划，将所有钢板按照规格尺寸进行数字编号，生成出库作业计划单，即区域内的重组。编号只对钢板的规格尺寸信息进行识别，数字信息不作为出库顺序的识别信息。

图4 订单拆分图

2.2 区域内钢板的选取求解

针对倒垛问题，已有文献给出了几类算法。例如原系统启发式算法和多回路启发式算法。原系统启发式算法是针对每张所需钢板，从可选的垛位组中选取倒垛次数最少的垛位，如有多个垛位满足此条件，就选取条件值最大的(例如使得行车最短的垛位)，依此规则选取，直至完成一个出库计划。多回路启发式算法则是在原系统启发式算法的基础上进行改进，按照原有的策略，产生一个初始解，然后再将每张所需钢板对应的垛位组设为替换邻域，依次从各个邻域中进行寻优替换，以改善初始解。

现有算法中，往往是针对整个出库计划去搜索，而忽略了在所有区域垛位中位于垛位顶部的钢板与出库计划所需钢板重合度，基于此，本文提出了一种针对垛位顶部与出库计划重合搜索的算法。如图 1 所示：位于6 个垛位顶端的 5，7，2，7，5，2 号钢板，有3张符合出库计划。由于5，7，2钢板有重复，可以按垛位号(垛位号按照离出货区域远近进行编号)小的进行选取，由此可以选出5，7，2号钢板，选取结果如图5所示。出库计划中剩下1，3，4，6，8号钢板未选取，继续从6个垛位顶部钢板进行搜索，选取位于2，3号垛位上的4，3号钢板，选取结果如图6所示。再次对垛位顶部钢板进行搜索，选取6，8号钢板，选取结果如图7所示。继续对垛位顶部的钢板进行搜索，未发现所需1号钢板。再对所有垛位中次于顶部钢板的位置进行搜索，从垛位1中选取1号钢板，至此选取结束。选取过程中只需倒垛1次，选取结果如图8所示。按照传统启发式算法，需要倒垛3次，选取结果如图9所示。

图5 5，7，2号钢板选取结果

图6 4，3号钢板选取结果

图7 6，8号钢板选取结果

图8 顶层搜索法选取结果

图9 传统启发式选取结果

3 算例分析

3.1 算法设计

由2．1节描述可以看出，将订单合并处理的优势显而易见，对此不进行仿真，仅对区域内钢板的选取进行仿真，顶层搜索算法实现流程如图10所示。

算例可以描述为：区域 G(G∈ (1，2，…，g))内按规则编号的一个出库计划，钢板数目若干，随机分布在区域G的各个垛位中，每个编号的钢板不超过1张，从各个垛位中选取，以满足出库计划，使得倒垛次数最少。为使得算法具有通用性，本文根据出库计划与垛高的不同，在垛位数目为30的情况下，设计了3种出库计划数(40，60，80)、2种垛高(8，10)的3×2共6种组合。