柔性制造车间AGV 小车物料配送路径优化研究

葛能鹏，陈金兰，吴利清

（湖南工业职业技术学院机械工程学院，湖南 长沙 410082）

0 引言

随着柔性制造企业的不断发展，生产模式也朝着多品种和小批量生产模式演变，这势必会增加生产组织的难度，生产物料配送环节是车间制造过程的重要组成部分，如何快速地把生产物料通过AGV 小车配送至生产线边对生产效率的提升有着重要的意义[1]。对于解决这类带时间窗约束的车间物流路径优化问题，本文建立以配送成本为优化目标的数学模型，提出一种改进的蚁群算法求解该问题，并与基本蚁群算法、遗传算法等进行实验对比，最终实验结果表明本文提出的改进后的蚁群算法可以更好地解决带时间窗的车间AGV 小车物流路径优化问题，以达到降低车间运输的物流成本、提高物流效率等目的[2]。

1 带时间窗车间物流路径优化的数学模型

1.1 问题描述

带时间窗车间AGV 小车物流路径优化问题可以描述为：存在M个货物供应点，负责给N个生产岗位需求点配送货物，每辆AGV 小车最大的运量为Q，每个货物供应点最多可派遣的AGV 小车数量为Km（m= 1，2，…，M），每个客户对货物的需求都有时间窗要求[ETi，LTi]（i= 1，2，…，N），货物必须要在生产岗位要求的时间内送达，每个生产岗位的货物需求量为Gi（i= 1，2，…，N），且每个生产岗位的需求量应小于单辆AGV 小车的运量，每个生产岗位都可以由任何一个货物供应点供货，要求设计一套合理的车间AGV 小车配送方案，在满足各个客户的前提下，使车间AGV 小车物流运输成本最低或者运输距离最短[3]。并且，存在以下多项约束条件：

（1）单个生产岗位的货物需求量必须由同一辆AGV 小车完成配送，即不可多辆AGV 小车同时经过一个需求点。

（2）车间由货物供应点作为配送开始位置，经过各个生产岗位后最后返回原来的货物供应点。

（3）单个生产岗位的需求量不能超过AGV 小车的最大运量。

1.2 数学模型的建立

为了简化模型的复杂度，设生产岗位的需求点的编码为（1，2，…，N），货物供应点的编码为（N+ 1，N+2，…，N + M），定义变量表示供应点m的AGV 小车k是否从货物需求点i行驶至货物需求点j，若不行驶的值为0，否则的值为1[4]。

总行驶距离：

式中，Z为AGV 小车行驶的总路程。

目标函数：

式中，目标函数C是最小化成本，P为AGV 小车路径单价成本。

约束条件为：

约束条件（4）～（9）中，式（4）表示车间AGV 小车行驶的开始位置和终点位置必须为所属货物供应点；式（5）和式（6）表示每个生产岗位需求点有且只能通过一个AGV 小车进行货物配送；式（7）表示车间途径各客户的总需求量必须小于等于AGV 小车的最大运量；式（8）表示车间不能从货物供应点直接行驶到供应点；式（9）表示车间到达生产岗位需求点时需在时间窗内。

2 基于蚁群算法优化配送路径

2.1 传统蚁群算法的求解模型

蚁群算法是由Marco Dorigo 提出，是一种模拟蚂蚁觅食寻找最优路径的仿生算法，蚂蚁在觅食的过程中会根据概率选择一条路径留下信息素，当某一路径或者节点留下的信息素浓度越大，被选择的概率就越大，因此蚂蚁会根据信息素浓度最大的地方找到一条最佳的觅食路径[5]。

2.2 蚁群算法的改进

2.2.1 种群个体编码和解码方案设计

（1）个体编码方案：编码是应用群体智能算法时要解决的首要问题，也是设计群体智能算法时的一个关键步骤。多中心物流配送路径优化问题是将已知的点通过不同的顺序进行连接，以保证AGV 小车行驶路径距离最短。以一个具有N个生产岗位需求点，M个货物供应点，每个货物供应点最多可派遣K辆AGV 小车的问题为例。将N个需求点分别标记为1，2，3，…，N-1，N；对于任意供应点的K辆AGV 小车标记为相同的编号，M个供应点的车间编号分别为N+1，N+2，N+3，…，N+M；故一个个体所具有的基因个数为N+M*K，其中编号小于等于N的基因代表需求点，大于N的基因代表不同供应点派遣的车间，如图1 所示。将这些基因置乱即可得到不同的个体。

图1 个体编码方案

（2）个体解码方案：如果需求点数N= 30，供应点数M= 2，每个供应点最多可派遣AGV 小车数K=5，每个个体的基因数为30 + 2 × 5 = 40，将该40 个基因位随机置乱得到一个个体，如图2 所示。1～30 的基因代表30 个“需求点基因”，31～32 的基因分别有5 个代表不同供应点派遣的“AGV 小车基因”。

图2 随机个体

以一个“AGV 小车基因”为起点，下一个“AGV 小车基因”的前一个基因为终点，即代表了一辆AGV 小车派遣路径。以图2 个体为例，从左往右，从上至下扫描各个基因位。一个“AGV 小车基因”为31，下一个“AGV 小车基因”为32，故第一辆AGV 小车的派遣路径为{31}，因为没有经过需求点故舍弃；同理第二辆AGV 小车和第三辆AGV 小车的派遣路径为{32}，舍弃；第四条{31}，舍弃；第五条{31-1-30-6-27-9-20-23-22-19}，保留，由于AGV 小车的派遣必须从起点出发最终回到原供应点，故完整的AGV 小车路线应为{31-1-30-6-27-9-20-23-22-19-31}，其中31 代表了1 号供应点。以此类推，最终可保留3 辆AGV 小车，其中供应点31 派遣1 辆AGV 小车，供应点22 派遣2 辆AGV 小车。

2.2.2 变异算子改进

本文在传统蚁群算法的基础上，对变异算子进行改进，加入扰动算法，该扰动算法输入当前个体individual，输出新个体newIndividual。此种扰动策略主要针对TSP 类的路径优化问题，TSP 问题的个体是Hamilton 回路，是一个需求点序列，而个体中的每一个基因表现为序列中相邻的两个需求点，通过两个需求点组成的序列，就可以求得目标值。传统邻域扰动算子是随机选择两个基因位r0，r1，然后进行调换位置，这会改变4 处的距离，分别是r0 位左右距离和r1位左右距离。而新策略的扰动只会改变2 处的距离，分别是r0 位左距离和r1 位右距离。采用此种策略的好处是，可以尽量降低一次的扰动程度，有利于局部搜索。如图3 所示。

图3 改进变异操作

2.2.3 交叉算子改进

本文在传统蚁群算法的基础上，对交叉算子进行改进，该算法与传统的交叉操作不同，这里提出一种改进交叉操作。具体步骤是设定一个变异概率p，如图4 所示，先在染色体中随机选择一个点G1，如G1=34。产生一个随机小数，若小于p，则第二个点G2 来自同一个个体的另外一个任意点，如G2=54，然后点G1 和G2 之间的部分被倒置；若随机小数大于p，则从种群中任意再选择一个个体，找出G1=34 在该个体中，上一个位置的点，如下一个点G3=3，则回到原来的个体，点34 到3 之间被倒置。这种遗传的思路在于，它能尽量利用种群中获得的信息，来指引个体的变异或者导致操作，最后使得交叉算子比较高效。

图4 改进遗传操作

3 实例计算与仿真

将某柔性制造车间的AGV 小车物流配送作为测试背景条件，经调查，该车间AGV 小车物料配送中心有2 个配送中心，20 个生产岗位需求点，每辆AGV小车的最大载荷量为800 kg，每个需求点的具体坐标、需求量及时间要求见表3。

表3 客户点信息

使用遗传算法、传统蚁群算法和本文改进后的遗传算法对该实例进行计算得到的最佳路径及种群进化曲线如图5、图6、图7 所示。

图5 遗传算法最佳路径

图6 传统蚁群算法最佳路径

图7 改进蚁群算法最佳路径

具体路径情况见表4。

表4 最优路径对比表

三种算法的种群进化曲线对比如图8 所示。从上述实验的结果来看，相比于传统的遗传算法和蚁群算法，得到的AGV 小车最优路径总路程为373.47 km，优于遗传算法的392.91 km 和传统蚁群算法的446.66 km，所以本文提出的改进后蚁群算法应用在带有时间窗约束的AGV 小车物流路径优化问题上，可以得到不错的使用效果。

图8 三种算法的种群进化曲线对比

4 结语

针对带时间窗约束的AGV 小车物流路径优化问题，本文建立以配送成本为优化目标的数学模型，通过对传统蚁群算法进行变异算子改进和交叉算子改进，提出一种改进的蚁群算法求解该问题。通过实例进行验证，改进后的蚁群算法相比于传统的遗传算法和蚁群算法，可以更好地解决带时间窗的柔性制造车间AGV 小车物流路径优化的问题，以达到降低物流成本、提高物流效率等目的。