面向数字化车间的工装配送方法研究*

（西北工业大学现代设计与集成制造技术教育部重点实验室，西安 710072）

德国提出的“工业4.0”在全球工业领域掀起一场风暴，它描绘了制造业的未来愿景，主旨在于将传统工业生产与现代信息技术相结合，即正在建设的未来工厂，其主要特征是智能和物联。数字化车间是建设未来工厂的重要基础，它不但要求单体设备智能，而且要求车间内的所有制造资源实现互联互通，这样才能满足智能生产和智能物流的要求。

数字化车间通过各种信息系统，实现了制造资源与生产过程信息的采集与管控，使精准的工装配送成为可能。而传统工装领用模式，常造成工装供应不及时或工装短缺的问题，影响生产进度甚至导致产品延期交付，是数字化车间中的必须解决的关键问题。工装配送作为数字化车间智能物流的关键环节，直接决定着生产运行的顺利与稳定。数字化车间的工装配送的研究主要集中在配送模型、配送路径优化等几方面展开。Prabaharan[1]、Udhayakumar[2]等分别研究了柔性制造单元和柔性制造系统在工装资源有限条件下的工装最优分配策略，并提出了相应的求解算法。数字化车间中的工装配送路径规划问题属于车辆路径问题（Vehicle Routing Problem，VRP）的扩展，为了实现精准的工装配送，其对时间的敏感性更强，对配送计划的依赖性更大。Wang等[3]将RFID技术运用于配送路线规划问题中，设计了一种实时车况配送系统，可实时规划运输路线并能够有效管理物料配送情况。Taillard等[4]针对软时间窗车辆路径规划问题建立模型，并采用禁忌搜索算法进行求解。Cheng等[5]针对时间窗信息模糊的VRP建立了多目标优化模型，并采用遗传算法对其求解。Baños等[6]提出基于平行多目标模拟退火遗传算法来求解带时间窗的车辆路径问题。Müller等[7]提出运用两阶段启发式算法与新型遗传模拟退火算法求解带时间窗的车辆调度问题，并取得一定效果。Ghoseiri等[8]对带时间窗的以最少车辆使用数和最短车辆行驶距离为优化目标的车辆路径问题进行了研究，运用数学规划的理论构建了研究问题的数学模型，并设计了遗传算法对模型进行求解。上述算法在求解多目标多约束优化问题时具有一定的局限性，模拟退火算法求解时收敛速度较慢，遗传算法易早熟且在进化后期搜索效率较低。

本文在考虑有限资源约束条件下的数字化车间的实际生产情况，提出了数字化车间的工装配送运行模式，包括车间现场工装互借和车间工装库配送两种工装配送模式；并且提出了一种改进的遗传算法，对带模糊预约时间窗的多工位混合配送的配送路径进行求解，提高了收敛速度，避免了早熟，实现了工装的精准配送，最后通过实例仿真验证了算法的有效性。

数字化车间的工装配送模式

数字化车间的工装配送系统与企业其他应用系统进行集成，各系统之间存在着大量的信息传递和数据交换。这些信息主要包含以下3类：（1）从企业级管理系统ERP、PDM（Product Data Management）、CAPP 中获取的生产计划、产品数据以及产品工艺等信息；（2）从车间级的MES（Manufacturing Execution System）系统中获取制造资源、生产过程的信息；（3）通过条码、RFID等信息采集方式获取工装的配送执行情况、工装使用状态等信息。

在工装配送过程中可采用零件直接标识（Direct Part Marking，DPM）以及RFID方式对工装进行标识追踪，使得工装配送情况、工装使用状态等信息的实时获取变成了可能，为工装的准时、准确配送提供了支持。在数字化车间的生产控制层，由车间底层采集到的实时生产状态数据流，经处理后反馈至各个信息系统，从而实现了工装配送管理与执行的闭环控制。数字化车间的工装配送运行模式如图1所示。

在有限资源约束下的数字化车间的生产运行过程，针对不同的工装需求场景，工装配送可以分为车间现场工装互借和车间工装库配送两种模式。

1 车间现场互借模式

车间现场工装互借模式是当某工序使用完某工装后正好有等待使用此工装的工序，则此工装不进行返库而是直接由车间现场配送人员配送给需要此工装的工位。

车间现场工装互借是指将工位使用完的某工装由车间现场配送人员直接配送到需要此工装的工位。这种配送模式主要针对在有限资源约束下存在工装使用冲突的工序经过工装调度调整后，冲突工序中部分工序的开工时间被推后，由于被冲突工序竞用的工装全部在车间现场，所以那些开工时间被推后的工序只有等先加工的工序加工完释放了占用的工装才能获得所需工装，对于这种情况只能通过车间现场工装互借模式配送，当先加工的工序使用完工装后现场配送人员立即将其配送到等待使用此工装的工位。

2 车间工装库配送模式

车间工装库配送是指在满足配送小车载量和时间窗约束的前提下配送人员将工装从车间工装库送达所需工位。车间工装库配送模式又可分为单工位直送配送模式和多工位混合配送模式。对于无法通过车间现场工装互借满足工装需求的情况则由车间工装库配送。

（1）单工位直送模式。

单工位直送模式是指配送中心指派一辆配送小车从车间工装库为某个工位配送所需工装，该车不得在配送任务中再为其他工位服务。这种配送模式只需要在满足配送小车载量和时间窗约束的前提下将工装送达所需工位即可。单工位直送模式主要针对关键工位和瓶颈工位的工装配送以及大体积工装的配送。

（2）多工位混合配送模式。

图1 工装配送的运行模式Fig.1 Mode of tooling distribution

多工位混合配送是指配送中心调派多辆配送小车服务多个工装需求工位，在满足配送小车载量和时间窗约束的条件下，通过合理调度，派遣最少的车辆数并且为配送车辆规划行驶距离最短的路径，以提高车辆满载率和配送准时性。多工位混合配送属于配送车辆调度问题，主要是针对常规计划配送件的组合配送。

工装配送时间窗的确定

在数字化车间工装精准配送中，对某一工位而言，如果工装早于需求时间送达，工装被提前占用，可能会导致其他工位等待此工装而无法进行生产；如果晚于需求时间送达将导致生产停工等待，影响生产计划的顺利执行，所以在工装配送的过程中要严格限制配送时间。

针对数字化车间的准时生产，工位对工装的送达时间要求更加精确，工位不但希望工装在某一时间窗口内被送达，而且更偏向于在时间窗内的某时间点被送达。而传统的时间窗无法真实反映工位对工装配送的时间偏好，所以本文选择模糊预约时间并将工位对于工装送达时间的满意度作为优化目标之一。传统时间窗与模糊预约时间对比见图2。

模糊预约时间包含可容忍时间区间[ETi，LTi]及期望服务时间DTi[9]。ETi和LTi分别表示工位i所能容忍的最早和最晚服务时间。工位对不同的工装送达时间满意度不同，当工位在期望时间DTi被服务时，工位满意度最大（μ=1），早于或晚于该时间工位满意度会逐渐降低。根据实际生产要求并结合车间管理人员的经验，用工装送达时间的模糊隶属度函数μi(ti)表示工位的满意度[10]：

图2 传统时间窗与模糊预约时间对比Fig.2 Comparison between traditional time window with fuzzy appointment

多工位混合配送的配送路径规划

1 问题描述

由配送中心调派配送小车为各个工装需求工位配送工装，配送车辆从车间工装库出发，依次供应各个工位，然后返回车间工装库为一次完整的配送任务。要求合理调派车辆及规划配送路线使得工位平均满意度最大、各车辆装载工装平均相似度最大并且配送车辆数最少。

本文研究的工装配送路径优化问题满足以下假设与约束条件：

（1）车辆从车间工装库出发，完成配送任务后返回车间工装库；

（2）每个工位所需的工装类型、数量及服务时间窗已知；

（3）一次任务中每个工位只能由一辆配送小车服务一次；

（4）各个工位对工装的需求都有时间窗限制；

（5）各个配送车辆仅考虑重量、容积约束；

（6）为方便计算将不同体积、重量的工装换算为标准包装量。

2 变量定义

At为工装类型为At的工装集合，at为At类型工装的总数，并且满足，L为工装类型总数；

Qt为配送工装类型为At的工装的配送小车载量；

为工位i所需工装Ap的重量；t

为工位i和工位j之间的距离；

Tij为配送小车从工位i行驶到工位j的时间；

Wi为配送小车在工位i处等待的时间；

ti为配送小车开始服务工位i的时间；

Ti为配送小车在工位i的服务时间；

sim(a，b)为工装a与工装b之间的相似度。工装相似度是根据工装之间的工装信息编码字段匹配程度设定的。

模型的决策变量为：

3 多目标优化数学模型

（1）优化目标。

工位平均满意度最大化：

车辆装载工装平均相似度最大化：

车辆使用数最小化：

（2）约束条件。

式（4）～（6）为模型的目标函数；式（7）表示配送车辆的载量约束；式（8）表示配送车辆对工位的开始服务时间必须在时间窗之内；式（9）表示在一次任务中每个工位只能由一个配送小车服务；式（10）～（11）表示对于任意一个由配送小车k服务的工位j，必定有且仅有一个由k服务的另一个工位（包括车间工装库），使得配送小车从该工位到达工位j；而对由k服务的工位i，同样存在一个且仅有一个由k服务的另一工位（包括车间工装库），配送小车是从工位i到达该工位的；式（12）～（13）表示配送小车从车间工装库出发，最后又回到车间工装库。

4 基于改进遗传算法的多工位混合配送路径求解

4.1 改进遗传算法步骤

改进遗传算法流程如图3所示。

4.2 染色体编码方式

本文染色体采用基于自然数编码方式，可以表示为R=(0,i1,i2,···,ij,0,···,0,ip,···,iq,0)的形式。其中，0表示车间工装库，ij表示子路径的第j个需求工位，相邻两个0之间表示一条子路径，子路径内部是有序的，而子路径之间是无序的。

4.3 生成初始可行种群

初始可行种群的生成步骤如下：

图3 改进遗传算法流程图Fig.3 Flow chart of improved genetic algorithm

Step1：随机排列N个工位，可得工位序列集，然后将其从左到右依次分派给配送小车，最后初始化配送路径编号Car_N=0。

Step2：置 Car_N=Car_N+1，新派一辆配送小车并置其路径编号为Car_N，将当前工位序列集X中最左边的工位加入到该配送小车路径中，然后将该工位从X中删除。

Step3：判断工位序列集X是否为空。若为空，转Step5；否则转Step4。

Step4：取当前工位序列集X中最左边的工位，判断其在当前的配送小车路径是否存在可行插入位置。如果不存在，则转Step2；如果存在，将其插入到当前配送小车路径的最佳插入位置，将该工位从X中删除，然后转Step3。

Step5：确定可行染色体的最佳开始服务时间，使该染色体的工位平均满意度最大。

Step6：判断生成的可行染色体数是否达到规定数量。若达到，则停止；否则重复 Step1～Step5。

对于上面初始可行种群生成步骤中的可行插入位置的确定方法如下。

定义：在当前配送路径的可行插入位置的集合中，使得工位综合满意度最大的位置为最佳插入位置。

假设已生成的某配送小车的可行配送路径为则配送小车到达工位xi的最大推迟时间[11]为：

若在其可行配送路径中工位xi和xi+1之间插入一个工位S后该路径仍为可行的配送路径，则需要满足如下条件。

条件1：时间约束。

（1）配送小车到达工位S的时间最晚不能超过该工位时间窗的最晚容忍时间，即：

（2）当i≤h−1时，配送小车到达工位xi+1必须满足：

条件2：运载能力约束。

4.4 适应度函数

个体的适应度计算公式如下：

式中，hk为第k个染色体；uk为hk的工位平均满意度；sk为hk的车辆装载工装平均相似度；vk为hk的配送小车使用数；umax为当前种群中染色体的最大工位平均满意度；smax为当前种群中染色体的最大车辆装载工装平均相似度；vmax为当前种群中染色体的最大配送小车使用数；为权重系数。

4.5 遗传算子设计

（1）选择。

选择是从当前种群中根据个体的适应度值，按照某种准则选出好的个体进入下一代种群，本文采用轮盘赌选择方法。

（2）交叉。

对选择操作得到的种群进行交叉操作，本文采用顺序交叉（Ordered Crossover，OX）法进行交叉。交叉过程中要满足最大保留交叉算子的规则[12]：随机选取染色体的两个交叉点，如果交叉点处两个基因都为0，则直接进行OX交叉；否则左移（右移）两个交叉点，直到使得两个交叉点处的基因都为0，然后进行OX交叉。为了防止出现大量相似个体交叉，在交叉操作中引入广义海明相似度区分染色体的相似性[13]。为了避免近亲繁殖，抑制早熟，对局部变异产生的种群，先通过选择操作淘汰一批不良染色体，然后计算两个体间的广义海明相似度，对小于广义海明相似度阈值的个体进行交叉操作。

（3）变异。

为了改善遗传算法的搜索能力，维持种群的多样性，防止出现早熟，随机选择多个基因段内的基因采用逆转变异的方法进行变异，在变异操作中引入局部小变异率和全局大变异率的双变异率机制[14]。当交叉产生的个体数TempPop_size小于种群个体数Pop_size时，选择操作产生的群体相似度较高，为提高染色体的多样性，避免早熟，对交叉后的种群以小变异率Local_Pm进行局部变异，通常取0.05～0.15，这样可以保持解种群的优良性。在每一代交叉操作后采用轮盘赌法选择较优个体，对该群体以大变异率Global_Pm进行全局变异，以保证进化过程的全局性。

仿真验证

根据某企业在有限资源约束下，经过工装调度的生产作业排程，如图4所示，共有16台加工设备，18个待加工工件，每个工件包含3或4道加工工序。

在生产作业排程甘特图中，纵坐标表示加工设备，Mi表示编号为i的加工设备，横坐标表示时间，Oi,j表示编号为i的工件的第j道加工工序，假设生产作业排程开始时间从8∶00开始。

由生产作业排程可以得到工装需求计划，然后以工装需求计划清单制定工装配送计划。完成一道工序的加工可能需要多种工装，本文以夹具为例验证工装配送计划求解方法，其他工装的配送方案制定类似。根据配送工装的重量、体积不同配送小车的大小也不同，设夹具的配送小车载量为60个单位。夹具配送任务如表1所示。

图4 生产作业排程甘特图Fig.4 Gantt chart of production scheduling

对工装需求计划进行分析可知，工位M6及M8加工的工序是由于夹具使用冲突经过调整的工序，所以工位M6及M8所需的夹具需要通过车间现场工装互借模式进行配送，工位M13及M16加工的工件J12为关键件，其加工优先级为A，所以M13及M16所需夹具需要通过单工位直送模式进行配送。其他夹具通过多工位混合配送模式进行配送。

多工位混合配送模型求解时其改进遗传算法基本参数的选取如下：初始种群大小Pop_size=100，选择概率Px=0.8，交叉概率Pc=0.8，局部变异率Local_Pm=0.1，全局变异率Global_Pm=0.2，海明相似度阈值取0.5，迭代次数 Max_grn=200。

本文采用序关系分析法确定多目标问题的权重系数，记平均工位满意度为x1，车辆装载工装平均相似度为x2，车辆使用数为x3。设优化目标xk-1与xk的重要性程度之比为rk=αk-1/αk，rk的取值分别为 1、1.2、1.4、1.6、1.8，分别代表优化目标xk-1与xk同样重要、稍微重要、明显重要、强烈重要、极端重要。根据车间的实际生产情况，配送人员在决策工装配送路径时，考虑多个优化指标重要性排序为：平均工位满意度＞车辆装载工装平均相似度＞车辆使用数，取r2=α1/α2=1.6，r3=α2/，经计算得α1=0.48、α2=0.29、α3=0.24，故取优化目标决策权重为：α1=0.5、α2=0.3、α3=0.2。

根据改进遗传算法步骤及以上基本参数和权重，采用Matlab进行仿真计算，得出的最优染色体，解码后得到夹具的配送计划如表2所示。

本文以夹具配送计划的多工位混合配送为例验证本文提出的改进遗传算法的有效性，分别取权重系数α1=1、α2=0、α3=0 和α1=0.5、α2=0.3、α3=0.2，以改进遗传算法与标准遗传算法求解本实例的工位平均满意单目标优化结果进行比较，标准遗传算法的基本参数设置为：初始种群大小取100，选择概率取0.8，交叉概率取0.8，变异率取0.1，迭代次数取200。

取α1=1、α2=0、α3=0，以工位平均满意度为优化目标，分别用改进遗传算法与标准遗传算法运行10次。改进遗传算法在120代左右开始收敛，而传统遗传算法在170代以后才开始收敛。

取α1=0.5、α2=0.3、α3=0.2，以工位满意度，工装平均相似度，车辆使用数为优化目标，分别用改进遗传算法与标准遗传算法运行10次，改进遗传算法在80代以后呈稳定变化趋势，至100代左右收敛；而传统遗传算法在中后期收敛速度很慢，直到160代才开始收敛。改进遗传算法的收敛速度优于标准遗传算法。

表1 工装配送任务信息

表2 夹具配送计划

结束语

本文提出了制造资源有限约束条件下的数字化车间的工装配送模式。采用改进遗传算法解决带模糊时间窗的多工位混合配送路径规划问题，在算法设计上，改进初始种群的生成方式，在交叉操作中引入广义海明相似度区分染色体的相似性，增加了种群的多样性；在变异操作中引入局部小变异率和全局大变异率的双变变异机制，改善了遗传算法的搜索能力，维持种群的多样性，防止出现早熟，最好通过实例验证了算法的有效性。本文为数字化车间中工装的精准配送提供了有效的方法，提高了数字化车间的运行效率。

参 考 文 献

[1] PRABAHARAN T, NAKKEERAN P R, JAWAHAR N. Sequencing and scheduling of job and tool in a flexible manufacturing cell[J]. The International Journal of Advanced Manufacturing Technology, 2006,29(7/8):729-745.

[2] UDHAYAKUMAR P, KUMANAN S.Sequencing and scheduling of job and tool in a flexible manufacturing system using ant colony optimization algorithm[J]. The International Journal of Advanced Manufacturing Technology,2010,50(9-12):1075-1084.

[3] WANG Y Z, HO O K W, HUANG G Q,et al. Study on RFID-enabled real-time vehicle management system in logistics[C]// Proceedings of IEEE International Conference on, 2008:2234-2238.

[4] TAILLARD É, BADEAU P,GENDREAU M, et al. A tabu search heuristic for the vehicle routing problem with soft time windows[J]. Transportation Science,1997,31(2):170-186.

[5] CHENG R, GEN M, TOZAWA T.Vehicle routing problem with fuzzy due-time using genetic algorithms[J]. Journal of Japan Society for Fuzzy Theory & Systems, 1995,7:1050-1061.

[6] BAÑOS R, ORTEGA J, GIL C, et al.A simulated annealing-based parallel multiobjective approach to vehicle routing problems with time windows[J]. Expert Systems With Applications, 2013,40(5):1696-1707.

[7] MÜLLER J. Approximative solutions to the bicriterion vehicle routing problem with time windows[J]. European Journal of Operational Research, 2010,202(1):223-231.

[8] GHOSEIRI K, GHANNADPOUR S F. Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm[J]. Applied Soft Computing,2010,10(4):1096-1107.

[9] 张建勇,李军,郭耀煌. 具有模糊预约时间的VRP混合遗传算法[J]. 管理科学学报, 2005,8(3):64-71.ZHANG Jianyong, LI Jun, GUO Yaohuang.Hybrid genetic algorithm to vehicle routing problem with fuzzy due-time[J]. Journal of Management Sciences in China, 2005,8(3):64-71.

[10] 严正峰, 梅发东, 葛茂根, 等. 基于模糊软时间窗的车间物料流路径优化方法[J].计算机集成制造系统, 2015,21(10):2760-2767.YAN Zhengfeng, MEI Fadong, GE Maogen. Path optimization method of workshop logistics based on fuzzy soft time windows[J].Computer Integrated Manufacturing System,2015,21(10):2760-2767.

[11] 王君, 李波. 带模糊预约时间的车辆路径问题的多目标禁忌搜索算法[J]. 计算机集成制造系统, 2011,17(4): 858-866.WANG Jun, LI Bo. Multi-objective tabu search algorithm for vehicle routing problem with fuzzy due-time[J]. Computer Integrated Manufacturing System， 2011,17(4): 858-866.

[12] 王晓博,任春玉,元野.一类最小-最大车辆路线问题的启发式算法研究[J].运筹与管理,2013,22(6):26-33.WANG Xiaobo, REN Chunyu, YUAN Ye.Heuristic algorithm for min-max vehicle routing problem[J]. Operations Research and Management Science, 2013,22(6):26-33.

[13] 李晋航, 黄刚, 贾艳. 多模糊信息条件下的物料配送路径规划问题研究[J]. 机械工程学报, 2011,47(1):124-131.LI Jinhang, HUANG Gang, JIA Yan. Vehicle routing problem in material distribution under condition of much fuzzy information[J]. Journal of Mechanical Engineering, 2011,47(1):124-131.

[14] 王杰, 马雁, 王非. 一种双变异率的改进遗传算法及其仿真研究[J]. 计算机工程与应用, 2009, 44(3): 57-59.WANG Jie, MA Yan, WANG Fei. Study of improved genetic algorithm based on dual mutation and its simulation[J]. Computer Engineering and Applications, 2009, 44(3): 57-59.