车间物流问题的布谷鸟算法

广东工业大学自动化学院 徐泽峰 蔡延光

1 引言

工厂车间普遍采用流水线生产模式。车间物流包括原料物流和工序间物流。

本文将车间物流问题建模为一类车辆路径问题（VRP，vehicle routing problem）问题。VRP问题可简单描述为，使用多辆车来为数个客户配送货物，要求规划各车辆的路线来使总配送路线最短。VRP是NP难问题，提出至今仍吸引着研究者的目光，不断为其提出求解效率更高的算法[1-2]。在原始VRP问题的基础上，一些研究者根据实际问题具有的特点提出了新的问题模型。蔡婉君[3]等人研究了周期车辆路径问题（PVRP，periodic vehicle routing problem），该问题将配送从CVRP中的一个周期扩展到多个周期。在每个周期中，由于客户需求不同，配送路线不同。Erdogan[4]等人提出了绿色车辆路径问题（GVRP，green vehicle routing problem），该问题研究如何用燃料有限的车辆实施配送。为了完成长距离的配送，车辆需要在途中补充燃料。

本文提出车间物流问题（WVRP，workshop vehicle routing problem），研究如何规划车辆向各工位输送原料和在各工位间搬运待加工产品的路线，以降低流水线生产周期。为WVRP设计一种布谷鸟算法来求解，并用实验来验证布谷鸟算法的有效性。

2 问题描述

车间内有一条流水线。流水线上有n个工位。用一辆车来完成输送原料和运输待加工产品的任务。为工位集合。用0表示仓库。每两工位或仓库i和j间的行驶时间为tij。工位i生产一单位产品所需的原料重为qi。一单位待加工产品重为q。车的最大载重为Q。

其中，（1）保证序列$S$中的每个元素对应仓库或工位。（2）表示运输从仓库开始。（3）表示序列$S$为循环序列，周期为$L$。（4）表示每个工位的每种访问在一个周期内只有一次。（5）（6）（7）（8）为载重变化的计算方式。（9）为载重的计算方式。（10）为最大载重的计算方式。（11）为装卸颠倒次数的计算方式。（12）表示在运输期间车不允许超载。

3 算法设计

为车间物流问题设计一种布谷鸟算法来求解。这是一种群体算法。群体中包含NumUnits个个体。算法起始阶段，为各个体生成初始解，然后进入循环。在每轮循环中执行如下操作：

（1）随机取一个个体a，生成满足levy分布的随机整数l，对a执行l次发散操作，得到个体a1。

（2）随机取一个个体b。若a1优于b，则用a1替代b。

（3）所有个体执行一次局部搜索操作。

（4）更新算法已获得的最优解。

（5）群体中比例为p的最劣个体用生成初始解的方法重新生成。

3.1 生成初始解

采用贪婪插入法来生成初始解。序列中两个0及它们之间不含0的一段称为一条线路。解初始时只有一条空线路，即只有首位两个0，中间没有其他点。每轮循环随机取一点插入最优位置，直到所有点插入完毕。

3.2 发散操作

引入超载惩罚。在评价解优劣时使用的是解的评价值，评价值越低则解越优。当解为可行时，解的评价值等于其行驶时间。当解不可行时，对解中的每一个超载点，将载重超出的量乘以超载惩罚系数f，加在解的行驶时间上，得到评价值。

发散操作随机取解中的一个点，将其移动到解中随机的新位置。发散操作可能极大地增加解的评价值，但是增强了算法跳出局部最优的能力。

3.3 局部搜索操作

采用如下两个邻域作为局部搜索邻域：

（1）移动一个非零点的位置；

（2）交换两非零点的位置。一次局部搜索操作为取上述两个邻域中评价值最低的解，并用它来替代当前解。若两个邻域中没有更优的解，则当前解不变。

4 计算实验

随机生成算例并用软件CPLEX来获得算例的全局最优解。CPLEX对较大算例的计算时间很长，故生成的算例规模较小，工位数从8到12。用布谷鸟算法对每个算例计算10次，取结果的平均值，并将其与全局最优解对比，结果如表1所示。

表1

可以看到，布谷鸟算法对所有算例均获得了全局最优解，且求解时间短，求解结果稳定，说明布谷鸟算法对WVRP是有效的。

5 结论

本文提出了车间物流问题，并设计了一种布谷鸟算法来求解该问题。实验结果表明，布谷鸟算法对该问题是有效的。

后续研究可以针对车间物流问题提出求解效率更高的算法。

[1]Teymourian E,Kayvanfar V,Komaki G,etl．Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem[J]．Information Sciences,2016,334-335∶354-378．

[2]Vidal T,Crainic T G,Gendreau M,Prins C．Implicit depot assignments and rotations in vehicle routing heuristics[J]．European Journal of Operational Research,2014,237∶15-28．

[3]蔡婉君,王晨宇,于滨,杨忠振,姚宝珍．改进蚁群算法优化周期性车辆路径问题[J]．运筹与管理,2014,23(5)∶70-77．

[4]Erdogan S,Miller-Hooks E．A green vehicle routing problem[J]．Transportation Research Part E,2012,48∶100-114．