基于空箱拉动的总装线物料配送研究

李　伟，董宝力

(浙江理工大学 机械与自动控制学院，浙江 杭州 310018)



基于空箱拉动的总装线物料配送研究

李伟，董宝力

(浙江理工大学 机械与自动控制学院，浙江 杭州 310018)

摘要：针对汽车总装线边空箱拉动供料模式下的物料配送问题，分析了空箱拉动模式下物料配送、空箱回收、需求点物料消耗速度对配送路线规划的影响.以配送路线最短和配送路线需求点配送频次均衡化为优化目标，建立了基于空箱拉动模式的总装线边物料配送路径优化模型.利用改进自适应遗传算法求解模型，根据种群适应度分布变化趋势调整交叉和变异概率，提高了遗传算法搜索能力.实例仿真结果显示，与总装线原配送方案相比，该模型减少了约32%的配送路程.

关键词：空箱拉动；汽车总装线；路径优化；物料消耗速度

随着市场对个性化产品的需求增加，混流装配线因能够满足多品种小批量的柔性生产要求而受到广泛关注，越来越多的产品总装线采用混合装配的方式进行生产[1].在混流生产过程中，理想有效的物流应该是物料配送与装配生产紧密配合.在实际工作中，总装线上的物料配送往往是厂内物流的最大瓶颈，物料配送直接影响产品的装配质量、装配效率、线边库存水平等.今天，合理规划总装线边物料配送路径已成为混流生产的研究热点之一.

装配线物料配送问题是经典车辆路径规划问题的扩展，但混流生产时作业的复杂性使得总装线边的物流配送路径问题更加复杂.目前对总装线边物料配送路径问题的研究较少.倪健毓等以总装牵引车配送路线和载重为优化目标建立整数规划模型，并通过改进遗传算法进行了求解[2].Yannis M等针对牵引车物流配送路径问题，提出一种利用粒子群优化器对群体中个体移动距离进行改进的混合粒子群算法[3].黄志刚等将车间物料配送路径优化归结为旅行商(TSP)问题，利用蚁群算法和最近插入法进行求解[4].刘进等利用eM-Plant软件对混流装配线的物料配送进行仿真分析，优化了配送车辆的数量、速度及装载量等参数[5].蒋丽等提出以工位为中心的总装物料配送模式，建立了以配送时间最小为目标的配送优化模型[6].李思淼等建立了基于工位缓存区有容量约束限制的配送模型，并采用基于预选机制的遗传算法进行求解[7].王楠等建立了总装线物料配送路径规划的混合时间窗模型，利用改进遗传算法进行求解[8].Bharath S Vaidyanathan等建立了总装线边准时制(JIT)模式下带容量约束的物料配送路径模型，并利用两阶段法对模型进行求解[9].葛茂根等针对JIT模式下总装物料配送问题，以运输成本、运输时间及线边库存为目标，建立优化模型，并利用混合粒子群优化算法进行了求解[10].Emdes等提出了JIT模式下混流装配线物料配送路径和配送车辆调度问题的混合模型，并分析了配送车数量和线边在制品库存之间的关系[11].看板拉动模式下物料配送的研究多集中在配送循环周期和收容数量最优等方面，并没有考虑配送路径优化问题[12-13].

以上对总装线物流配送路径问题的研究大都集中在准时化和时间窗模式上，通过改进算法，加快求解速度；还有一些研究者结合总装线实际情况建立了相应约束条件的问题模型，但并未考虑物料消耗速度对配送路线的影响，同时对于配送过程中装载能力的约束只规定了总体约束，并没有具体到需求工位之间的装载能力约束.本研究针对汽车总装车间空箱拉动模式的物料配送问题，分析该模式下空箱回收和零部件消耗速度对配送路径和配送次数的影响，提出以配送路径最短和需求点零部件配送频次均衡化为目标建立优化模型，并通过改进自适应遗传算法求解，得出最优的配送路线.

1基于空箱拉动的总装线物料配送问题描述

总装线边的零部件供应模式分为JIT、电子看板、空箱拉动等.JIT供料模式只是针对相当少的一部分零部件，大部分零部件的供料模式为看板和空箱拉动.空箱拉动即配送人员按照一定的配送周期将工位需求的零部件配送到相应的位置，并将配送路线上的空箱运回零部件存储区，通过扫描空箱上的条码信息来产生物料拉动需求.基于空箱拉动的物料配送模式如图1所示.

在空箱拉动的物料配送模式下，牵引车不仅要配送工位上所需要的零部件，同时还要回收工位上的空箱.在配送过程中，牵引车的运载能力是有限制的，离开每个工位时的装载量不能超过其运载能力.因此，各工位的配送顺序必须严格控制，否则就会导致部分空箱无法回收.

图1　基于空箱拉动的物料配送模式

利用空箱拉动模式进行物料配送时，同一条配送路线上不同工位零部件的包装容数和单车用量不同，导致生产过程中不同工位零部件消耗速度不一致，进而会影响零部件的工位配送频次.零部件包装容数大、单车用量小的工位，单位时间内配送频次低；零部件包装容数小、单车用量大的工位配送频次高.同一条配送路线上零部件的工位配送频次差异较大时，空箱拉动的物料配送模式会导致配送次数增加，单次配送装载率降低，影响配送效率.因此，在利用空箱拉动模式进行配送路线规划时，缩小工位间的零部件消耗速度差异将有利于配送效率的提高.综上可知，空箱拉动的物料配送模式应当满足如下假设和约束条件：①每辆牵引车从物料仓库出发，配送完成后回到物料仓库；②每一个工位有且只有一辆牵引车负责配送；③每辆牵引车从物料仓库发出，将各工位所需的物料配送到位，同时将各工位上的空箱收回；④牵引车离开每个工位时装载量不能超过其运载能力；⑤牵引车的数量和运载能力已知.

2基于空箱拉动的总装线物料配送模型建立

空箱拉动模式下总装线边物料配送路线的数学模型包括目标函数和约束条件.

2.1目标函数

(1)总目标函数为：

(1)

式中：k为牵引车的辆次；k=1,2,…，m.

(2)牵引车配送总路程为：

(2)

式中：i和j为工位，i=0,1,…,n；j=1,2,…,n;i=0时，零部件存储于物料仓库；xi j k表示第k辆牵引车是否从工位i到达工位j；xi j k=0时，第k辆牵引车未从工位i到达工位j；xi j k=1时，第k辆牵引车从工位i到达工位j；di j k为第k辆牵引车从工位i到达工位j的位移.

(3)同一条配送路线上第k辆牵引车的各工位零部件消耗速度的均方差为：

(3)

式中：vi k为第k辆牵引车所配送工位i的零部件消耗速度.

2.2约束条件

(1)在牵引车配送过程中，各工位的零部件需求量与容盛具返空量之和不能超过第k辆牵引车的运载能力，即：

i=1,2,…，n；k=1,2,…,m(4)

式中：yi k表示第k辆牵引车是否配送工位i;yi k=0时，第k辆牵引车不配送工位i；yi k=1时，第k辆牵引车配送工位i；Ri k为工位i对牵引车配送零部件的需求量；Qi k为工位i由第k辆牵引车带走的空盛具数量；C为第k辆牵引车的最大运载能力.

(2)第k辆牵引车离开工位i之后的剩余运载能力与上工位(i+1)的需求量之和不小于工位(i+1)的空盛具返回量，即：

(5)

(3)第k辆牵引车离开需求工位后的空盛具数量与零部件需求量之和不超过牵引车的运载能力，即：

(6)

(4)每个工位i仅有一台牵引车配送一次,即：

(7)

(8)

式中：xj i k表示第k辆牵引车是否从工位j到达工位i；xj i k=0时，第k辆牵引车未从工位j到达工位i，xj i k=1时，第k辆牵引车从工位j到达工位i.

(5)第k辆牵引车到达工位i后又从工位i离开，即：

(9)

(6)每个工位i都由一台牵引车负责配送，即：

(10)

3基于空箱拉动的总装线物料配送模型求解

物料配送路径优化问题属于N-Hard问题.求解这类问题一般都采用启发式算法，如遗传算法、模拟退火算法、蚁群算法、禁忌搜索算法等.与其他算法相比，遗传算法不仅能够全局并行搜索，而且应用非常成熟，针对不同问题都有其解决的理论和方法，能为研究带来方便.但是，在传统遗传算法的种群中，个体交叉率和变异率固定不变，不仅求解时间长，而且容易陷入局部收敛.为避免出现早熟和局部优化现象，本研究采用改进自适应遗传算法，根据个体适应度变化趋势对交叉率和变异率进行调整.

3.1编码设计

对于染色体，采用基于工位需求点的自然数编码方式，一方面便于计算机运算，另一方面使求解过程大大简化，可提高运行效率.i表示第i个工位需求点，i=1，2，…，n；0表示物料仓库；配送中心有m辆牵引车；存在m条配送路径且每条配送线路都起始于配送中心.这样，n个需求点和m-1个0可随机排列成一条具有n+m-1个基因位的染色体，每条染色体代表一种配送方案.例如:1-5-0-3-6-0-2-4-7，表示3条路线.

3.2初始种群生成

根据工位需求点随机产生一个1～n的全排列，再将m-1个0随机插入该排列中，形成一条染色体，则染色体被分成m个基因段，每个基因段分别表示一个子路径.

3.3适应度函数

适应度函数是评价种群个体进化优劣的依据.个体经过反复迭代后，适应度函数值大的个体被不断筛选保留下来.因此，种群的个体适应度函数对算法结果具有直接影响.本研究采用如下适应度函数：

(11)

式中：fg为第g条染色体的适应度；μ为常数；ZO为当前种群中个体的目标函数平均值；Zg为第g条染色体对应的目标函数值.

3.4选择操作

(12)

每次轮盘转动将产生一个介于0、1之间的随机数.当该随机数小于Pg h时选择第g条染色体；否则选择累积概率在P(g-1)h和Pg h之间的染色体.

3.5交叉操作

交叉操作是最主要的遗传操作，从经过选择操作的个体中随机选择两个个体，按照交叉概率Pc交叉操作，产生新一代个体.染色体中含有多条可行配送路径，为避免这些路径被破坏，本研究采用保留交叉算子的策略，即如果染色体两交叉点对应的基因值均为0，则直接进行交叉；如果不全为0，则交叉点向左或向右移至基因值为0的位置，再进行交叉.

3.6变异操作

变异是发生在某基因位上的基因突变.在局部随机搜索过程中，它与复制、交叉运算结合在一起，使算法具有局部的随机搜索能力，也使得种群保持多样性，有利于防止求解过程出现的早熟现象，使搜索过程从局部最优解中逃出.

本研究采用2-交换变异算子，在种群中随机选取一条染色体上的两个基因位，交换两个基因位的基因值，从而产生一个新的染色体，用新的染色体代替之前的染色体，并设染色体变异概率为Pm.

变异操作如下：染色体为：1-5-0-3-6-0-2-4-7；变异点为：2，6；变异后染色体基因为：1-5-0-3-2-0-6-4-7.

3.7交叉和变异率自适应调节

遗传算法控制参数的自适应调节问题受到了很多学者的重视.Srinivas等最早提出了一种自适应遗传算法，其特点主要体现在变化的交叉变异概率设计上，但当优化的中后期进化趋于停滞时，对交叉变异概率的处理容易使算法陷入局部优化的困境[14].在Srinivas自适应遗传算法的基础上，G、F、S、C典型的自适应遗传算法也被相继提出.这4种自适应遗传算法能够有效地避免Srinivas自适应遗传算法的缺陷[15].其中，F自适应遗传算法的自适应性能表现较好.其表达式如下：

(13)

(14)

从式( 13)和式( 14) 可以看出，当个体的适应度非常接近时，个体被选择的概率相当，使得个体在进化过程的交叉变异效果不明显，搜索时间延长.该算法只考虑种群中个体适应度与种群平均适应度之间的关系，在搜索过程中，很容易陷入局部最优而不能逃出.

为了改进F自适应遗传算法，本研究在基因进化过程中，根据上下两代个体适应度的分布趋势，对交叉变异概率进行了相应调整.其表达式如下：

(15)

(16)

当前种群的适应度分布直径为N(t)= f(t)max-f(t)min，t为当前种群进化的代数，(t-1)为种群进化的上一代.当种群适应度分布趋于分散时，减小交叉变异概率；当种群适应度分布趋于集中时，增大交叉变异概率，使算法避免陷入局部优化.同时，对适应度值低于平均值的个体，增大交叉变异概率来淘汰不良基因，增加种群的多样性.

4实例分析

本研究以某汽车装配车间的底盘装配线、发动机变速箱合装线、发动机分装线、水箱分装线、前后桥分装线上的18个工位需求点的零部件配送为例，以物料仓库为坐标原点建立坐标系.装配线工位需求点的分布如图2所示.各工位需求点的坐标、需求零部件名称、零部件需求量、空盛具数量、零部件消耗速度如表1所示.物料仓库到各工位需求点及各工位需求点之间的位移均为直线.

工位i到工位j的直线距离为：

图2　总装线各工位需求点的分布

配送点零部件名称横坐标a/m纵坐标b/m需求量/箱返空盛具量/箱零部件消耗速度/箱·h-11分动器34010.202通风管45010.363右后制动油管912110.364水箱128100.325风扇总成1210110.306发电机136210.377空调压缩机145010.228三元催化176110.289左前半轴167210.2710前转向节总成199110.2711后弹簧235120.7512方向机总成228100.5013后稳定杆胶套263110.5814后制动盘295120.3615后半轴267110.2016RDU通风管298100.3817RDU前支架2810110.7118燃油滤清器3211100.75

用Matlab2013进行遗传算法编程，改进自适应遗传算法的参数为：初始种群数量为50，最大进化代数为100，Pc1=0.8，Pc2=0.5，Pm1=0.1，Pm2=0.01.图3为一般自适应遗传算法和改进自适应遗传算法求解过程的收敛曲线.从图3可以看出，改进自适应遗传算法的解优于一般自适应遗传算法，计算时间更短，计算精度更高.各工位的零部件配送路径最优方案如表2所示.优化后的总配送位移为299.28 m，与总装线原配送方案总配送位移398 m相比节约了32%左右.

图3　改进自适应遗传算法与一般自身适应遗传算法收敛过程对比

车辆序号配送工位顺序路径长度/m各配送路径零部件消耗速度均方差10-1-2-3-4-034.440.0820-5-9-038.080.0230-6-7-8-036.920.0840-10-17-18-068.040.0250-13-12-11-059.280.0560-15-16-14-062.520.10

5结束语

在分析汽车总装线边空箱拉动模式下物料配送和空箱回收特点的基础上，提出以配送路线最短和配送路线需求点配送频次均衡化为优化目标，建立了基于空箱拉动模式的总装线边配送路径模型.针对传统自适应遗传算法在进化过程中容易陷入局部优化的问题，提出在进化过程中根据个体适应度的分布趋势，相应调整交叉变异概率，提高遗传算法的收敛速度，避免算法陷入局部最优.通过实例仿真，验证了所建立的总装线边配送路径模型的可行性和有效性.

参考文献:

[1]曹振新,朱云龙.混流轿车总装配线上物料配送的研究与实践[J].计算机集成制造系统，2006，12(2)：285-291.

[2]倪健毓，肖华峰，龙少良，等.汽车零部件厂内线边物料配送路线优化方法研究[J].汽车零部件，2013(10)：70-76.

[3]Yannis M, Magdalene M.A hybrid genetic-particle swarm optimization algorithm for Tehran vehicle routing problem [J].Expert Systems with Application.2010,37:1446-1455.

[4]黄志刚，林凤涛.车间配送路径优化的研究[J].华东交通大学学报，2007,24(4):111-114.

[5]刘进,窦照亮.基于eM-Plant软件的液压支架装配线物流仿真与优化[J].成组技术与生产现代化,2015,32(2):37-42.

[6]蒋丽,丁斌,臧晓宁.以工位为中心的生产物流配送优化[J].计算机集成制造系统2009,15(11)：2153-2159.

[7]李思淼，葛茂根.面向装配过程的物料配送路径优化研究[J].机械工程师，2014(7)：55-58.

[8]王楠，李世其，王峻峰.带时间窗的汽车总装线物料配送路径规划[J].工业工程，2012，15(2)：94-99，120.

[9]Bharath S Vaidyanathan,Jessica O Matson,David M Miller,et al.Acapacitated vehicle routing problem for just-in-time delivery[J].Institute of Industrial Engineers,1999,31(11):1083-1092.

[10]葛茂根，刘明周，钱芳，等.基于JIT的多目标总装准时物料配送方法研究[J].中国机械工程，2011，22(23)：2834-2838.

[11]Emdes,Boysen N.Optimally routing and scheduling tow trains for JIT-supply of mixed-model assembly lines[J].European Journal of Operational Research,2012,217(2):287-299.

[12]蔺宇，秘志利.基于均衡消耗的器具收容数设定方法研究[J].物流技术，2014，33(4)：101-103.

[13]洪旭东，徐克林，夏天.基于看板的生产线物料循环配送方式[J].工业工程，2009，12(4)：116-120.

[14]Srinivas M, Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms [J].IEEE Trans on Systems, Man and Cybernetics, 1994,24(4): 656-667.

[15]王万良，吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007.

Research on Material Distribution of General Assembly Line Based on Empty Pull

LI Wei, DONG Bao-li

(School of Mechanical Engineering and Automation,Zhejiang Sci-Tech University,Hangzhou 310018, China)

Abstract：Aiming at the empty pull material distribution problems of automobile general assembly line, the influence of the material delivery, empty pick-up and the rate of material of different stations are analyzed, an empty pull material distribution model is built by taking the shortest travel distance of vehicles and balancing the distribute frequency of the same route as the optimization objective. The empty pull material distribution model is solved by the improved adaptive genetic algorithm according to the concentrating degree of fitness of the populations, a kind of adaptive crossover probability and mutation probability are designed; the search efficiency of the genetic algorithm is improved significantly. Simulation results show that compared with the original scheme of material delivery in automobile general assembly line, this model reduces the path distance by 32% which demonstrated the feasibility and validity of this model.

Key words:empty pull; automobile general assembly line; route optimization; material consumption rate

doi:10.3969/j.issn.1006-3269.2016.01.004

中图分类号：TP30

文献标识码：A

作者简介：李伟(1988-)，男，河南永城人，硕士研究生，研究方向为精益生产、供应链与物流管理.

基金项目：浙江省自然科学基金资助项目(LY12G02015)

收稿日期：2015-07-28

文章编号：1006-3269(2016)01-0021-06