基于改进遗传算法的汽车混流装配线物料配送路径优化

张新敏+李亮+刘设

摘 要：物料配送的及时和准确是汽车装配线高效运作的根本。针对汽车装配线物料配送路径优化的问题，运用无量纲化方法建立了以物料配送距离最短和惩罚成本最低为目标的多目标综合评价物料配送路径优化模型，引入新的轮盘赌选择算子和交叉算子，形成改进遗传算法，并采用该算法对模型进行了求解，最后用实例验证了该模型和改进遗传算法的有效性，并通过和遗传算法的计算结果对比，验证了改进遗传算法的优越性。

关键词：汽车装配线；VRPTW；改进遗传算法

中图分类号：F252.14 文献标识码：A

Abstract： Timely and accurately distribution of the material is the fundamental of the efficient operation of automobile assembly line. A multi objective comprehensive evaluation model of material distribution path based on the shortest material distribution distance and the lowest penalty cost is established by using the method of dimensionless method. Then， an improved genetic algorithm is presented to solve it. In this algorithm， the new roulette selection operator and crossover operator are proposed. Finally， the validity of the proposed model and improved genetic algorithm is verified by an example， and the superiority of the improved genetic algorithm is also verified by comparison with the standard genetic algorithm.

Key words： automobile assembly line； VRPTW； improved genetic algorithm

0 引 言

混流生产线是指在不做改变或者稍微调整后就能生产多种不同类型和数量的相似或相近产品的生产线。汽车装配线作为典型的混流生产线，其主要是完成零部件装配工作，由于同一装配线上产品种类和数量比较多，导致零部件的种类和数量更加繁多。物料的准时化配送成为了汽车装配线重点考虑的问题，也是提高装配效率的关键所在。准时化的物料配送，要求物料配送路径最优，成本最低，而且物料到达工位的时间有严格的区间要求。

目前针对混流生产线的物料配送路径研究较少，对路径优化问题，大多是设计新的算法，提高问题的求解速度，还有一部分是根据实际研究情况，改变数学模型或者增加约束。杨斯淇结合生产车间的实际情况，构建了有容量限制的物料配送优化模型[1]；任星球等提出带缓存区的准时化物料配送问题，建立总成本最低为目标的模型，并设计了混合量子进化算法，对模型进行求解[2]；高贵兵等建立了以车辆行驶距离最短、车辆利用率最大和配送次数最少为优化目标的多目标配送车辆路径优化模型，并根据问题实际情况，设计了双层递进进化多目标优化算法进行问题模型求解[3]；马尚兵等建立了以成本最低为目标的带时间窗的物料配送路径优化模型，并设计了改进的混合蚁群算法对模型进行求解[4]；侯玉梅等建立了带软时间窗的整车物流配送路径优化问题，并提出自适应遗传算法求解[5]。国外关于路径优化问题研究的相对较早也比较成熟，Mazzeo等建立了一种求解带容量限制的车辆路径优化的蚁群算法，并验证了算法的高效性[6]；CHOIW提出了一个动态的物料配送系统，根据实际生产进度动态预测生产线所需消耗的零部件种类和数量，然后完成配送[7]；Sulieman. D等根据不确定需求的车辆路径问题，提出了两个双目标模型，采用多目标进化算法求解[8]；William Ho等采用混合遗传算法求解VRP问题，首先用领域搜索算法构造初始解，然后用遗传算法进行求解[9]。

从上述文献中也可看出，针对物料配送路径优化问题，大多建立单目标的数学模型，即使建立多目标数学模型，运用无量纲化处理多目标函数进行运算的研究文献较少，同时考虑混合时间窗约束限制和运用改进遗传算法求解的文献也比较少。本文根据汽车装配线的实际需求，考虑了物料配送时间的限制，建立了以物料配送距离最短，物料在时间窗之外到达工位的惩罚成本最低为目标的多目标带时间窗物料配送路径优化问题模型，同时运用无量纲化手段对多目标函数进行相加运算，最后设计了一种新的选择算子和交叉算子的改进遗传算法对问题模型进行求解。

1 问题描述

本文提出的带有时间窗的物料配送路径优化问题（VRPTW）可以描述为：首先通过装配车间生产计划得到产品的种类和数量，再由BOM表得到所需物料种类和数量，最后按照各工位物料需求量和车间配送能力，完成物料从配送中心到需求点的配送，并且在完成配送后，小车返回配送中心。小车到达工位节点的时间也有严格的时间区间限制，在要求的时间区间之外到达工位节点，会造成成本增加，受到惩罚。

VRPTW就是在传统的VRP模型中加入了时间窗的限制，除了要满足物料配送严格的时间要求外，还要设计合理的配送路径，使得车辆行驶距离最短。时间窗分为软时间窗、硬时间窗和混合时间窗三种，本文根据汽车装配车间实际情况，采用混合时间窗，如图1所示。

要使本文提出的VRPTW模型成立，需满足以下假定条件：endprint

（1）所有车辆都是匀速行驶，且不同车辆的速度相同；

（2）配送车辆有容载量的限制，每辆车每次的装载量不得超过容载量；

（3）工位节点位置固定，每个工位只能由一辆车完成配送。

2 模型建立

本文的VRPTW模型建立如下：

式（6）为车辆未按工位满意时间完成物料配送的惩罚成本；式（7）为每辆车的最大载重量不得超过Q；式（8）为每个工位有且仅有一辆车提供配送服务；式（9）、式（10）分别表示每辆车都是从配送中心出发，且最终返回配送中心；式（11）为工位i接受服务的时间范围；式（12）为车辆k为工位i服务的起止时间；式（13）和式（14）表示工位i与工位j起止时间的关系。

3 改进遗传算法设计

遗传算法是一种借鉴自然界生物进化机制而形成的随机全局搜索和优化方法，由于其具有群体搜索、不需任何附加信息仅用适应度函数值就可评估基因个体、并行计算、可扩展性和发展成熟等特性，在解决VRPTW的问题上，遗传算法得到了广泛的应用。但同时，遗传算法也存在遗漏优秀个体、不能很好保留父代优秀基因和算法效率低下等不足，导致计算结果可能不是最理想的。因此本文通过引入新的选择算子和交叉算子，改善遗传算法的不足，形成改进遗传算法。

3.1 编码。本文中VRPTW要求，m辆车从配送中心（0）出发，完成n个工位的物料配送服务，并最终返回物料配送中心（0），且每辆车都仅要求完成一次配送和每个工位仅接受一次配送服务。根据VRPTW要求，提出了一种基于工位需求的基因分段自然数编码模式：n个基因代表n个工位，组成染色体并随机全排列，由m+1个基因代表m+1个物料配送中心（0），随机插入n个工位组成的染色体，形成完整的染色体，要求染色体的首末基因位置必须为物料配送中心（0）。

3.2 适应度函数。适应度函数是用来评价染色体的优劣，适应度值越大，染色体越优越。本文提出的VRPTW模型，目标函数值越大，即染色体越优越，因此本文采用目标函数作为适应度函数。

3.4 交叉。交叉的主要目的就是使子代能最大限度地保留父代的优秀基因，而传统的交叉算子不能很好地实现父代优秀基因的遗传，因此本文基于贪婪法的思想，提出了一种新的交叉算子，提高父代优秀基因遗传给子代的概率。具体方法说明如

下[10]：设现有工位需求点ii=1，2，…，n，待交双亲：

（3）重复步骤（2），直到生成完整的子代。

3.5 变异。变异是发生在少数基因位上的基因突变，是一种局部随机搜索过程。本文采用逆转变异模式，即在个体字符串中随机选择两个逆转点，使两个逆转点之间的基因值在变异概率为p的条件下逆向排序。

3.6 终止进化规则。本文采用种群中个体在连续10代中未获得改进作为终止进化规则。

4 算例验证

4.1 算例描述。某汽车装配车间有1个物料配送中心，3辆载重量为300个物料当量的小车给8个工位段提供物料配送服务，每辆小车的固定启动成本为1元，行驶成本为10元/km，早于最早满意接受时间到达工位的惩罚成本系数为C=12元/h，晚于最晚满意接受时间到达工位的惩罚成本系数为C=18元/h，M=30，现已知物料配送中心与各工位段之间的距离以及各工位段之间的距离（见表1）和各工位段的物料需求量d以及最佳服务时间段W，W（见表2），设计车辆物料配送路径，使得总距离最短和总成本最低，本文中距离权重取0.4，成本权重取0.6。

4.2 算法对比验证。将上述算例数据带入相关程序进行运行，得出结果见表3至表6和图2、图3。

由表4、表5可分别看出改进遗传算法和标准遗传算法的最优路径分别为0—1—3—4—0—2—5—7—0—6—8—0和0—2—1—6—0—5—4—7—0—3—8—0，车辆载重率改进遗传算法的结果比标准的更稳定。由表6可看出，改进遗传算法的计算结果，在距离、成本和综合评价值上，优越于标准遗传算法。由图2和图3可以看出，改进遗传算法的收敛性能明显优于标准遗传算法，改进遗传算法求解的行驶距离在进化到75代左右即收敛到最短行驶距离825，而标准遗传算法求解的行驶距离在进化到135代左右才收敛到最短距离895；改进遗传算法求解的成本在进化到75代左右达到最小成本20.07，而标准遗传算法在进化到135代左右才达到最小成本21.05。最终证明了本文提出的改进遗传算法的有效性和优越性。

5 结 论

本文通过对VRPTW问题分析研究，并联系生产实际，建立了以物料配送距离最短和物料在时间窗之外到达工位的惩罚成本最低为目标的多目标带时间窗的物料配送路径优化问题模型，运用无量纲化方法，建立可进行综合评价的目标函数，并提出改进遗传算法求解问题模型，该算法采用新的选择算子和交叉算子，从而提高优秀个体的选择概率和遗传给下代的概率。最终通过实际案例验证了模型和改进遗传算法的有效性，并通过改进遗传算法与标准遗传算法的结果对比，证明了该算法的优越性。同时也为实际生产中物料配送路径优化问题提供了理论依据。

参考文献：

[1] 杨斯淇. 基于遗传算法的制造企业生产物流牵引车配送路线优化研究[D]. 长春：吉林大学（硕士学位论文），2008.

[2] 任星球，张景玲，赵燕伟，等. 制造企业装配线物料准时配送路径优化问题研究[J]. 机械制造，2012，50（570）：1-4.

[3] 高贵兵，张红波，张道兵. 混流制造车间物料配送路径优化[J]. 计算机工程与应用，2014，50（15）：228-234.

[4] 马尚兵. 基于改进混合蚁群算法的物料配送路径优化研究[D]. 武汉：华中科技大学（硕士学位论文），2013.

[5] 侯玉梅，贾震环，田歆，等. 带软时间窗整车物流配送路径优化研究[J]. 系统工程学报，2015，30（5）：240-250.

[6] MAZZEO S， LOISEAU I. An Ant Colony Algori-thm for the Capacitated Vehicle Routing[J]. Electronic Notes in Discrete Mathematics， 2004，18：181-186.

[7] CHOIW， LEEY. A dynamic Part-feeding System for Auto-motion Assembly Line[J]. Computer & Industrial Engineering， 2002，43：123-124.

[8] Sulieman. D， Jourdan. L， Talbi. E. Using Multiobjective metaheuristics to solve VRP with uncertain demands[C] // IEEE World Congress on Computational Intelligence， 2010.

[9] William Ho， George TSH， Ping Jib， et al. A hybrid genetic algorithm for multi-depot vehicle routing problem[J]. Engineering Application of Artificial Intelligence， 2008，21（4）：548-557.

[10] 刘海，郝志峰，林智勇. 改进遗传交叉算子求解TSP问题[J]. 华南理工大学学报，2002，30（12）：71-73.endprint