胡小建, 陈茹梦

(合肥工业大学 管理学院,安徽 合肥 230009)

0 引 言

物料配送是数字化车间实现物流智能化的关键,直接决定生产线的稳定运行。数字化车间的物料配送研究主要集中在配送模型、配送路径优化等方面，数字化车间中的物料配送路径优化属于车辆路径问题(vehicle routing problem, VRP)的拓展。

文献[1]通过综合考虑距离、成本和时间等,提出选择合适的车辆行驶路径,完成货物配送等车辆路径问题；文献[2]研究了有容量和时间窗约束的车辆路径问题,建立了VRP的三目标模型,并通过交替求解一般指派问题和有时间窗约束的旅行商问题求解该问题；文献[3]针对非满载车辆路径规划问题建立了带时间窗的路径规划模型,并采用遗传算法进行求解；文献[4]针对制造资源约束的数字化车间,提出了包括车间现场互借以及车间工装库配送的多种工装配送模式,并研究多目标下带模糊预约时间窗的配送方案；文献[5]针对有时间窗的车辆路线安排提出一种利用旅行商问题的C-W算法选择路线的启发式算法；文献[6]针对门店配送及种类配送2种配送方式,运用遗传算法求解配送成本最小化配送策略及车辆行驶路线；文献[7]针对不确定环境下再制造加工车间的调度问题,提出在满足模糊交货期约束条件下运用混合智能算法求解最小加工时间的调度方案；文献[8-9]采用遗传算法来解决带有时间窗的车辆路径规划问题。

综上可见,学者们对综合考虑车间仓储区与工位之间关系的研究相对较少。本文以安徽省某高端液压元件制造企业数字化车间为例,以寻求车辆配送时间最短为目标建立基于工位的物流配送调度模型[10],并运用遗传算法对带时间窗的多工位混合的配送路径进行求解,得到工位与智能仓储各仓储区域的对应关系,同时得到各配送工具的最优配送路径,从而实现了物料的准时制配送。

1 以工位为中心的模型构建

1.1 问题描述

实际生产中,流水线上的物料是按套配送的,即每台运输工具每次只配送1个加工工位、1个生产节拍内所需的物料。由于智能化流水线生产,各工位对物料的需求几乎是同时的。若每个工位发出物料需求,则立即调度配送车辆进行配送,便会导致配送小车数量过多、利用效率低以及生产成本的增加。因此,配送小车应在工位发出物料需求至工位缓存消耗完毕的时间窗之内,完成工位的配送任务。

物料存储区常常集中布置在数字化车间的某一区域,仓储区域划分的不同,配送车辆配送任务的调度也会发生改变,因此从数字化车间总体出发探讨配送车辆调度可以为仓储区的布局提供一定的参考。数字化车间内生产物流调度的目标就是在给定约束条件下，寻求配送时间最短情况下的车辆配送路径以及各仓储区与工位之间的对应关系。

1.2 数学描述

泵体智能生产线内有k辆配送工具(一次配送容量为一套工装板),n种工装板存储区(M1,M2,M3,…,Mn)和m个加工工位(s1,s2,s3,…,sm),配送工具负责将工装板从不同划分区域的仓储区配送到各工位,已知每个加工工位的配送时间窗为(ETi,LTi)和工装板各存储区到各工位的配送时间矩阵T,设工装板到达各工位的时间为ti,满足ti∈(ETi,LTi),tiLTi时工位停工等待工装板,求解总配送时间最小情况下k辆配送工具的配送路线以及仓储区与工位之间的对应关系。ETi、LTi分别为第i个工位配送时间的上限、下限。

1.3 配送规则

本文研究的配送优化问题满足以下规则。

规则1 配送工具从相同的初始位置出发(其初始位置编号为s0),完成配送任务后再回到初始位置,下一个配送循环开始。

规则2 1次任务中每个工位只能由1辆配送小车服务1次。

规则3 1个工位与1个工装板存储区对应,形成m个“工位-存储区对”,设第i个“工位-存储区对”到第p个“工位-存储区对”的配送时间为Tip′。

1.4 决策变量及约束条件

首先,引入一个决策变量xij，表示工位i所需的工装板是否由工装板存储区j存储,当xij=1时表示工位i所需工装板是由工装板存储区j存储,否则xij=0,其中,i∈{1,2,…,m},j∈{1,2,…,n}。于是,对于每个工位由一个存储区进行存储则可表示为:

(1)

其次,引入一个决策变量yik,表示工位i的配送任务是否由车辆k完成,当yik=1时表示工位i的配送任务是由车辆k完成,否则yik=0,其中,i∈{1,2,…,m},k∈{1,2,…,k}。于是,对于每个工位由一个小车进行配送则可表示为:

(2)

同样,如果车辆k负责工位i的配送任务,那么这辆车在自己的配送路径中至少要访问1个工位。因此,再引入决策变量xipk表示车辆k是否由第i个“工位-存储区对”运行到第p个“工位-存储区对”。当车辆k由第i个“工位-存储区对”运行到第p个“工位-存储区对”时,xipk=1,否则xipk=0。对于车辆k负责的工位点p,要访问1次则可表示为:

(3)

如果车辆k不负责工位i的配送任务,那么车辆k从第i个“工位-存储区对”运行到第p个“工位-存储区对”的条件也不成立,因此,要满足以下约束:

若yik=0,则有：

xipk=0

(4)

为了满足每个工位都被服务到,且保证1个工位只能由1个工装板存储区为其服务,即有:

(5)

(6)

为了保证车辆到达每个工位的时间ti都是在工位发出物料需求至工位缓存消耗完毕的时间窗之内,则有:

ETi≤ti≤LTi

(7)

1.5 模型构建

根据规则3,第i个“工位-存储区对”到第p个“工位-存储区对”的配送时间为:

Tip′=Tir,r={j|xpj=1}

(8)

根据规则2,工装板配送到第p个工位的时间点为:

(9)

其中,k′={k|ypk=1}。

m个工位的总配送时间为:

(10)

综上所述,以总配送时间最小为目标函数，采用(1)～(7)式建立以工位为中心的配送调度模型为:

Tip′=Tir，r={j|xpj=1};

s.t.ETi≤ti≤LTi,

若yik=0,则xipk=0。

2 遗传算法的设计

本文建立了一个带时间窗的物流调度优化模型,属于VRP,根据实际的车辆调度情况会产生几种VRP问题的拓展形式,其中最重要的是带能力约束的VRP和带时间窗的车辆路径优化问题。这些问题已被证明是一个NP完全问题,只有在求解规模较小时才能求其精确解。因此,本文采用遗传算法对模型进行求解。

2.1 染色体编码方式

在本问题中,由于每个加工工位的时间窗约束,排在前面的工序先加工,工装板要优先配送。在确定车辆分配和工位与仓储区的对应关系后,“工位-存储区对”的调度按照工位顺序配送,说明对该模型的求解关键在于确定车辆分配及工位与仓储区的对应关系。因此,本文染色体采用实数编码方式,可以表示为(r1,r2,…,ri,…,rm,r1+m,…,ri+m,…,r2*m…r1+2*m,…,ri+2*m,…,rk*m)的形式，其中,(r1+k*m,…,r2+k*m，…,ri+k*m,…,rk*m)表示由小车k完成的配送路径,ri+k*m表示第i个工位对应的仓储区,ri+k*m为0代表小车k不进行第i个工位的物料配送。各小车内部配送路径是有序的,而小车之间的配送是无序的。

在有5个工位、2辆配送小车和3个工装板存储区的分配方案中,其中一条染色体编码如图1所示,即[2,0,0,3,0,0,1,2,0,3],则[2,0,0,3,0]表示车辆1负责工位1、工位4的配送,仓储区2和仓储区3分别负责工位1、工位4工装板的存储;[0,1,2,0,3]表示车辆2负责工位2、工位3、工位5的配送,仓储区1、仓储2、仓储区3分别负责工位2、工位3、工位5工装板的存储。

图1 染色体编码示意图

2.2 初始种群生成

每个配送小车由工位数目m个基因位组成,每个基因位的数值取值范围不同,但存在一定的联系,且整条染色体必须满足约束条件,因此本文对初始种群的生成方法做了一些改进,以由2辆配送工具为例生成初始种群,具体步骤如下:

(1) 为第1辆配送小车安排配送任务,各基因随机生成0和1,0表示不由小车1配送,1表示由小车1配送,然后在基因值为1的工位随机生成1-n的数字,指定与工位对应的仓储区。

(2) 生成第2辆小车的配送任务,若第1段基因对应工位为0,则表示该工位还未配送,此时安排小车2配送,即随机生成1-n的数字;若第1段基因对应工位不为0,则表示该工位已由小车1配送,此时该基因值应为0;此时1条完整的染色体生成。

(3) 由(9)式计算出每辆配送小车到达配送工位的时间,并根据(7)式判断到达工位时间,以确定染色体是否非法;若非法,则舍弃此条染色体,重复前面的步骤,直至生成有效的染色体。

(4) 重复以上步骤N次,得到染色体数量为N的初始种群。

2.3 适应度函数

适应度函数是遗传算法中评价染色体好坏的依据,适应度值越大,染色体解的质量越好。通过适应度函数计算每个个体的适应度,淘汰适应度低的个体,保留高适应度个体进行遗传操作,从而实现优胜劣汰的自然选择过程。虽然初始种群加入了有效性检验,保证了群体中的个体均为有效个体,但是在交叉变异过程中会出现新的不符合要求的个体,因此本文在适应度函数里引入了惩罚函数来避免无效个体的存在,并根据本问题的约束限制,将模型的适应度函数设计为:

(11)

如果配送小车到达各工位的时间ti满足(ti-ETi)<0或(ti-DTi)>0,那么α为0;否则,α为1,D是一个很大的正数。

2.4 种群的选择

采用轮盘赌法对个体进行选择,个体的适应度值越大,被选中的概率越大。

2.5 交叉与变异

通过交叉与变异可以生成新的配送方案。以交叉概率pc对染色体种群随机交换2个个体之间的片段产生新的个体,以变异概率pm对染色体种群中的某些染色体的随机2个位置进行变异产生新个体。

3 算例分析

根据以上分析,为了验证模型的有效性,本文以安徽省某高端液压元件制造企业数字化车间作为研究对象进行仿真验证。安徽省某高端液压元件制造企业是一家专业从事液压系统元件的研发制造为一体的高新技术产业,积极开展智能制造数字化车间项目建设,努力实现企业生产效率的提升以及高端液压元件装配制造的国际化。

3.1 数字化车间的整体布局

数字化车间共由1套智能仓储、1条清洗线、2条部装线及1条总装线组成。智能仓储为1套自动化立体仓库,存放加工工位需要的物料,2条部装线包括1个预加工工位,1条总装线包括4个人工工位,手动装配以上各部装区域未安装的零部件,具体整体布局如图2所示。

智能仓储区负责为生产线上的工位进行物料配送,存储区的物料存储方式直接影响车间的工装配送效率。制造类企业的生产物流活动都是为工位服务的,因此本文提出以工位为中心的存储策略,首先分析不同工位所需的物料,将每个工位所需物料存放至1个工装板上,以工装板为单位进行配送。其次，在仓储区内对工装板进行分区存放,将车间存储区划分为1个个为特定工位服务的仓储区,部装线上的1个工位只能由1个仓储区服务,而1个仓储区可以为多个工位提供配送服务。

由于各个工位所需要的物料分别存放在唯一且固定的仓储区内,且各工位与各仓储区建立一一对应关系,说明通过物料—工装板库位—工位的精准对应可以实现零部件的精确快速拣取。

本文以该企业某一型号泵生产为例,该型号泵共含117个零部件,根据各工位的物料需求,将部装零件按照类别存放至7种工装板上,分别为壳体工装板、安装座工装板、摇摆座工装板、花键轴工装板、端盖工装板、柱塞缸体工装板和控制阀体工装板。

工装板种类确定后,对自动化立体仓库区域进行划分并编号,分别为仓储区1、仓储区2……仓储区7。

数字化车间生产线由2条部装线(包含1个部装工位)和1条总装线(4个人工工位)组成。2条部装线与1条总装线为串行加工,部装线内的各工位为并行加工,总装线内的人工工位为串行加工。在进行计算时,将总装线内4个人工工位考虑为1个整体加工工位。为保证生产节拍的一致,各工位对工装板的来料时间要求不同。

在数字化车间的精准配送中,对某一工位而言,若工装板早于需求时间送达,则工位无存放位置,导致工装板堆积,物料呆滞;若工装板晚于需求到达，则生产停工等待,在工装板配送中要严格限制配送时间。

图2 数字化车间的整体布局

3.2 数据采集

针对数字化车间的准时生产,在一套泵产品完整的加工过程中,考虑生产节拍、工位缓存区存储量等约束条件,以一整套产品加工时间最短为目标,计算各工位工装板的到达时间要求。经过与车间工作人员的讨论与修订,本文计算得出各工位的配送时间窗(ETi,LTi)。其中，智能生产线内各工位的时间窗、各仓储区至工位的配送时间等调查数据见表1所列。表1中，工位s1～s11对应的时间窗分别为[0,3]、[2,6]、[4,10]、[5,13]、[7,15]、[8,18]、[9,20]、[10,22]、[15,25]、[18,32]、[20,35] ,时间窗中时间单位为min。

表1 数字化车间仓储区至加工线配送时间 s

3.3 求解过程

将表2中的数据代入本文构建的基于工位的带时间窗的生产物流调度优化模型,并采用遗传算法对模型进行求解。设车辆从初始位置s0出发,初始位置s0到工位s1的时间设为0,在求解过程中,取遗传算法种群数N=300,最大遗传代数G=300,交叉概率为0.9,变异概率为0.1。利用Matlab编程求解,经迭代后得到目标值与种群均值的变化如图3所示。从图3可以看出,种群在第14代收敛至最优解,小车的最小配送时间为2 722 s,对应染色体为[1,0,4,6,3,0,0,6,0,0,3,0,2,0,0,0,4,4,0,6,7,0],经过解码得到各仓储区对应的工位以及2辆小车的配送顺序见表2所列。根据编码规则,本文得到2辆配送小车的最优配送路径如下：车辆k1的为s0→M1→s1→M4→s3→M6→s4→M3→s5→M6→s8→M3→s11→s0；车辆k2的为s0→M2→s2→M4→s6→M4→s7→M6→s9→M7→s10→s0。

图3 种群迭代

表2 计算结果

3.4 结果分析

通过优化,本文提出的配送方案有如下3个方面改进:① 在仓储区存取方面。7个工装板存储区分别于11个工位存在对应关系,且占用合理，该分区存储策略既方便了工装板出库时的拣货操作,又使得智能仓储区的利用更加集中合理。② 在配送时间方面。以上生产物流配送方案的实际应用,优化后的2辆小车对11个工位在23 min内完成1次配送循环,且工装板到达各工位的时间点均在工位预约时间窗之内,2辆配送小车分工合理。③ 本文提出的“以工位为中心”的数字化车间配送模式,实现了智能仓储区主动为生产线工位提供物料,提高了配送时间的预测精度,企业可更合理地安排工装板存储数量与配送时间,在多批次、小批量的快速流通生产车间配送背景下提升配送效率,降低存储于配送费用,提升企业竞争力。

4 结 论

对于数字化车间,低效、繁杂的车间配送方案往往是车间实现准时制生产的瓶颈。为提升配送效率,实现准时制生产,本文基于数字化车间物流整体优化的思想,在企业加工车间工位物料需求时间不确定的基础上,借鉴物流车辆配送路径问题研究,将其应用到车间内部物料配送中,提出带有智能仓储区的数字化车间的生产物流配送优化调度模型；在数学模型中增加了时间窗,能有效保证工位的生产节拍稳定与准时制生产；采用遗传算法求解生产物流调度模型,得出仓储区与工位之间的对应关系,并为各配送工具分配了最优行驶路线。通过安徽省某高端液压元件制造企业数字化车间的实例分析,验证了该模型与求解算法的可行性。将数字化车间作为整体考虑生产物流配送,优化作业效率,是未来研究的重点。