基于改进混合粒子群算法求解混流车间物料配送路径问题

施贝，张玺，黄雪思，江东，杜闯**

（合肥工业大学机械工程学院，合肥 230009）

2.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.0Hefei University of Technology,school of Mechanical Engineering,Hefei 230009；Hefei University of Technology,school of Mechanical Engineering,Hefei 230009；Hefei University of Technology,school of Mechanical Engineering,Hefei 230009；Hefei University of Technology,school of Mechanical Engineering,Hefei 230009；Hefei University of Technology,school of Mechanical Engineering,Hefei 230009合肥工业大学机械工程学院，合肥 230009;合肥工业大学机械工程学院，合肥 230009;合肥工业大学机械工程学院，合肥 230009;合肥工业大学机械工程学院，合肥 230009;合肥工业大学机械工程学院，合肥 230009230009;230009;230009;230009;23000918298000135;18505512009;;;18298000135;18505512009;;;安徽省合肥市合肥工业大学屯溪路193号;安徽省合肥市合肥工业大学屯溪路193号;安徽省合肥市合肥工业大学屯溪路193号;安徽省合肥市合肥工业大学屯溪路193号;安徽省合肥市合肥工业大学屯溪路193号bz151hfut@163.com;zhang_xi@hfut.edu.cn;834406634@qq.com;1254215370@qq.com;1468845271@qq.com施贝（1993-），女，合肥工业大学硕士研究生，主要研究方向：制造系统监测、控制与管理;张玺（1985-），男，讲师，硕导，生产计划控制与调度、智能制造;黄雪思（1993-），女，合肥工业大学硕士研究生，制造系统监测、控制与管理;江东（1992-），男，合肥工业大学硕士研究生，制造系统监测、控制与管理;杜闯（1994-），男，合肥工业大学硕士研究生，制造系统监测、控制与管理施贝;张玺;黄雪思;江东;杜闯SHI Bei;ZHANG Xi;HUANG Xuesi;JIANG Dong;DU Chuang张玺2.02.0 2.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.01*|*期刊*|*蒋增强, 金阳, 梁军义,等. 不确定环境下混流装配生产车间的动态物料配送策略[J]. 计算机集成制造系统, 2017, 23(10):2108-2118.<CR>2*|*期刊*|*周炳海, 徐佳惠, 彭涛. 基于新型线边集成超市的周期性物料配送优化[J]. 吉林大学学报(工学版), 2018, 48(2):588-595.<CR>3*|*期刊*|*Zhou B H, Shen C Y. Multi-objective optimization of material delivery for mixed model assembly lines with energy consideration[J]. Journal of Cleaner Production, 2018, 192:S0959652618312939.<CR>4*|*期刊*|*刘旭, 楼佩煌, 钱晓明,等. 基于改进遗传算法的物料配送多AGV调度优化[J]. 机械设计与制造工程, 2015(3):16-21.<CR>5*|*期刊*|*涂海宁, 徐星. 改进蚁群算法下的物料配送路径优化研究[J]. 机械设计与制造, 2017(8):265-268.<CR>6*|*期刊*|*庄存波, 刘检华, 唐承统, 邢香园.复杂产品离散装配过程中的物料动态跟踪与管理技术[J].计算机集成制造系统，2015, 21(1): 108-122.<CR>7*|*期刊*|*徐晓芳, 刘鑫. Job Shop作业车间物料配送小车定位方法研究[J]. 机械工程师, 2018(1):55-56.<CR>8*|*期刊*|*韩曙光, 蒋欢欢, 胡觉亮. 基于电子看板的装配线物料配送优化研究[J]. 浙江理工大学学报:社会科学版, 2017, 38(2):120-126.<CR>9*|*期刊*|*吴京秋, 王梓懿, 吕立,等. 基于ERP信息管理的焊接生产线物料配送控制系统的设计[J]. 自动化博览, 2018(z1):117-119.基于改进混合粒子群算法求解混流车间物料配送路径问题|Solving the problem of material distribution routing in mixed-flow workshop based on Improved Hybrid PSO||1|施贝|SHI Bei|合肥工业大学机械工程学院，合肥 230009|Hefei University of Technology,school of Mechanical Engineering,Hefei 230009|施贝（1993-），女，合肥工业大学硕士研究生，主要研究方向：制造系统监测、控制与管理|安徽省合肥市合肥工业大学屯溪路193号|230009|bz151hfut@163.com|18298000135|18298000135<CR>*|2|张玺|ZHANG Xi|合肥工业大学机械工程学院，合肥 230009|Hefei University of Technology,school of Mechanical Engineering,Hefei 230009|张玺（1985-），男，讲师，硕导，生产计划控制与调度、智能制造|安徽省合肥市合肥工业大学屯溪路193号|230009|zhang_xi@hfut.edu.cn|18505512009|18505512009<CR>|3|黄雪思|HUANG Xuesi|合肥工业大学机械工程学院，合肥 230009|Hefei University of Technology,school of Mechanical Engineering,Hefei 230009|黄雪思（1993-），女，合肥工业大学硕士研究生，制造系统监测、控制与管理|安徽省合肥市合肥工业大学屯溪路193号|230009|834406634@qq.com||<CR>|4|江东|JIANG Dong|合肥工业大学机械工程学院，合肥 230009|Hefei University of Technology,school of Mechanical Engineering,Hefei 230009|江东（1992-），男，合肥工业大学硕士研究生，制造系统监测、控制与管理|安徽省合肥市合肥工业大学屯溪路193号|230009|1254215370@qq.com||<CR>|5|杜闯|DU Chuang|合肥工业大学机械工程学院，合肥 230009|Hefei University of Technology,school of Mechanical Engineering,Hefei 230009|杜闯（1994-），男，合肥工业大学硕士研究生，制造系统监测、控制与管理|安徽省合肥市合肥工业大学屯溪路193号|230009|1468845271@qq.com||

摘要：针对混流制造车间物料配送问题，建立了基于平衡优化指标的思想的多目标配送路径优化模型。提出了改进混合粒子群算法，将遗传算法的交叉变异操作以及模拟退火思想与粒子群算法相结合，并提出一种基于顺序列的分组组合优化编码方式，在该编码方式的基础上规划了带硬约束的编码步骤，通过降低粒子重复性和提高粒子有效性两方面提高粒子初始群体的质量，改善了粒子寻优能力。通过算例验证分析，结果表明改进的算法具有较强的寻优能力。也验证了改进的模型与算法可以更有效地解决混流制造车间的物料配送路径问题。

关键词：改进混合粒子群算法；路径优化；物料配送；混流制造;分组组合优化编码

中图分类号：TH165

Solving the problem of material distribution routing in mixed-flow workshop based on Improved Hybrid PSO

SHI Bei, ZHANG Xi, HUANG Xuesi, JIANG Dong, DU Chuang

(Hefei University of Technology,school of Mechanical Engineering,Hefei 230009)

Abstract: Aiming at the material distribution problem of mixed-flow manufacturing workshop, a multi-objective distribution path optimization model is established based on the idea of balance optimization index. An improved hybrid particle swarm optimization (IHPSO) algorithm is proposed. The crossover and mutation of genetic algorithm and simulated annealing are introduced into the particle swarm optimization algorithm. A sequence-based grouping combination optimization coding is designed, and the encoding steps with hard constraints are designed to improve the particle optimization ability and the effectiveness of particles by reducing particle repeatability and improving particle effectiveness. The example verification analysis shows that the improved algorithm has better optimization ability. Also it proved that the improved model and algorithm can solve the material distribution route problem of the mixed-flow manufacturing workshop more effectively.

Key words: Improved Hybrid PSO; Path Optimization; Material Distribution;Mixed-flow Manufacturing;Sequence-based Grouping Combination Optimization Coding

引言

混流制造车间物料的多样、复杂性给物料配送带来了一定的挑战。越来越多的学者对混流制造物料配送展开研究。蒋增强等[1]设计了动态周期的物料配送策略，周炳海[2]设计了线边集成超市周期性配送策略;Zhou B H、刘旭、涂海宁等[3-5]分别采用TEPSO算法、改进遗传算法、改进蚁群算法等求解不同约束条件和优化目标的配送模型；庄存波、徐晓芳、韩曙光、吴京秋等[6-9]采用RFID技术、电子看板、ERP以及MES等信息系统等手段进行物料配送优化管理。

目前有对混流制造物料分类问题进行研究，也有对配送路径优化问题进行研究，但都存在默认配送任务在优化指标上是一致的缺陷。但实际中由于不同类别物料的配送任务在优化

时侧重点不同。对于库存容量小的配送任务，物料早达线边的影响比容量大、物料价值低的库位恶劣，因此急需进行指标平衡。目前针对不同类别配送任务在同一个系统中进行优化研究的比较少。本文在建模型时将平衡优化指标思想带入传统多目标模型中，使模型更贴合实际需求。同时采用改进混合粒子群算法对模型求解，设计一种基于顺序列的优化组合编码方式，提高算法粒子初始群体的质量，提高寻优能力。

问题描述与指标平衡设计

问题描述与约束条件

物流部门收到配送任务，要从配送中心（编号为0）将一批物料配送到N个工位(编号为1，2,…,n)，每个工位物料需求为（i为工位），各物料需在配送服务时间窗之间到达，有K个载重为Q的车辆可供调用，各工位时间窗惩罚早达系数和晚达平衡系数为。物料配送路径优化目标为：调用尽可能少的车辆，路径尽可能短，各工位物料需求尽量在服务时间窗内到达。

针对混流制造车间物料配送的特点，做出以下假设与约束。

(1)所有物料都由同一个配送中心发出去；(2)工位物料需求和服务时间窗都已知；(3)各点之间的位置距离已知，车辆行驶速度已知；(4)物料过早到达或过迟到达都将要付出时间惩罚代价；(5)车载量不能超过其额定载重；(6)每个工位都只能由一辆车完成配送。

基于指标平衡的多目标优化设计(新增小节，解释平衡系数设计)

物流部门收到的配送任务是多类型的，目前企业配送任务一般分为JIT件、缓存件和经验批量件三种。这三者在上述优化目标中，最大的区别在于物料配送时间精度要求。在这方面，目前研究比较少，没有可参考的数据，所以本文从实际问题出发，以定性思想进行对比分析，确定平衡系数的参考值。

针对早达时间而言，主要是由从线边或缓存区的库存容量来决定的。JIT件配送任务，线边库存容量最小，要求最为严格；经验批量配送任务，体积小、线边库存容量最大，要求最低；中转配送任务，缓存区库存容量居中，要求居中。

针对晚达时间而言，主要由缺料所影响的生产范围来决定的。零库存件配送任务和经验批量配送任务，缺料时都是影响单条产线，要求较为严格。中转配送任务，缺料时影响范围较广，至少是一条生产线，要求严格。以研究较多的JIT件为基准，设计三种任务的指标平衡系数如表1所示。

表1 优化指标平衡系数设计

Tab 1 The balanced design of delivery time index

JIT件	缓存件	批量件
早达惩罚平衡值	1	0.3	0.5
晚达惩罚平衡值	1	2	1

配送模型

参数符号

如下是本论文对每一个参数的解释说明：

(1)N: N={0,1,2,3,…,n}，其中0代表配送中心，1，2，…,n等代表各个工位点。(2)K:配送车辆的车辆编号:1，2，3，4，…,K;(3):过早配送时间惩罚平衡系数；(4):过晚配送时间惩罚平衡系数；(5):物料由车辆k配送到达工位n的时刻，n=1，2，…,N;(6):工位或配送中心m到工位或配送中心n之间的距离；(7):工位n的物料需求量,n取工位编码1，2，3，…,n;(8)A、B：过早、过晚到达的全局时间惩罚系数。

模型建立

决策变量定义如下:

(1)

(2)

其中参数服从下列约束：

在综合考虑混流制造物流配送的生产特点的前提下，考虑到物料配送期望达到的目标：调用尽量少的车辆、总配送路径尽可能短、物料尽量在服务时间窗内到达，建立以下物料配送路径多目标优化模型：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

其中：式(3)为配送模型的总优化目标函数；式(4)为不在时间窗内的时间惩罚值。式(5)为总运输里程；式(6)为所出动的车辆数；式(7)为一个工位需求点当且仅当被一辆车服务;式(8)为车辆的载重约束；式(9)(10)为工位离开车辆号、到达车辆、与的配送车辆一致;式(11)为同一辆车先后经过两点的配送到达时间约束。

优化算法

改进混合粒子群算法

图1 改进混合粒子群算法流程图

Fig 1 Flow chart of IHPSO

PSO算法简单易实现，但是存在适应于连续优化，易陷入局部最优，后期收敛性差等问题。而模拟退火算法具有跳出局部最优的优势，遗传算法的交叉变异操作更适合与离散优化组合问题，本文采用三者结合的改进混合粒子群算法(Improved Hybrid Particle Swarm Optimization, IHPSO)。改进主要体现在以下几个方面：第一，去掉速度更新过程，然后以粒子交叉、变异的形式直接进行位置的更新。第二，改进粒子个体极值更新方式，以基于适应度的接收规则，接收目标值一定程度的变坏。第三，改进粒子编码方式降低粒子重复性，提高例子初始群体的质量，提高算法全局搜索能力。基于模拟退火和遗传算法的混合粒子群算法的流程如图1 所示

编码与初始化

1.编码与解码

编码：本文采用等长实数编码，粒子编码由两部分组成。粒子i的位置向量X分为2个n维的向量：Xg、Xk依次表示所有的配送工位和完成工位配送任务的车辆编号，其中Xg中工位的先后排列顺序代表工位的相对配送顺序。假设有9个工位,则可能的一个染色体个体可用图2表达：

图2 染色体编码

Fig 2 The code of chromosome

解码：依据配送车辆子染色体段Xk中车辆编码不同，将配送工位子染色体段Xg中的具有相同车辆编码的工位按照其自左至右的先后顺序确定车辆的配送路线。图2解码后表示为：出动4辆车配送，1号前往9、8工位；2号前往7、5工位；3号前往6、2工位；4号前往4、3、1工位。

2.基于顺序列的分组组合优化编码方式

实数编码中，在工位染色体相同的情况下，假设都为7653142。车辆子染色体1124234、1125235都与1123243意义相同，代表7个染色体被分为4组，分别为：第一组7,6；第二组5,1;第三组3,2;第四组：4。存在进化时与前后几代适应度或染色体相同的问题，而延迟进化进程。

为了降低粒子重复性，在此提出一种基于顺序列的分组组合优化编码方式。首先找到分组的子染色体，本文的分组子染色体为配送车辆子染色体。然后如图3所示编码，具体步骤如下：

图 3 基于顺序列的分组组合优化编码示意图

Fig 3 Sequence-based grouping combination optimization coding schematic

步骤1：初始化参数。初始化编码染色体的长度N,并产生一个介于1至N的随机数R

步骤2：生成分组序列。生成一个1至R自小到大的序列Lr

步骤3：生成补位序列。生成(N-R)个1至R之间自大到小补位序列Ld

步骤4：生成最终染色体编码。将序列Ld中元素依次插入序列Lr中，在插入时中元素a只能排在Lr序列中第a位之后，最后形成配送车辆子染色体L。

3.硬约束条件的粒子初始化

基于顺序列的分组组合优化编码方式,降低了粒子的重复性，适应于无硬约束条件的编码。本论路径优化属于带载重的硬约束问题，为了进一步提高粒子初始化质量，在此在上述编码规则的基础上，加入硬约束，具体步骤如下：

步骤1：用Matlab仿真软的函数randperm(n)，随机生成一个(1-n)随机排列作为配送工位子染色体R1

步骤2:将工位需求量按照工位编号大小顺序，生成需求向量G;

步骤3:函数zeros(1,n)生成配送车辆子染色体V;初始值为n个0元素组成的向量；

步骤4:从R1中左起第一个元素开始，向右侧累加硬约束值(本例为：工位需求量与载重约束)，在约束内则属于同一车辆，在V对应的位置录入车辆编码(自1开始的连续整数)，否则，记下差异量，在约束矩阵中取与之最接近的一个工位,不存在则自左第一个元素开始下一辆车的安排，以此类推。

适应度及其他机制设计

1.适度函数设计

多目标优化，首先统一量纲。企业应用中对企业来说最根本利益在于降低成本，所以适应度函数可以表示为：

(12)

适度函数表示最小成本。其中为的权重系数，且。x表示当前模型的可行解。分别为单位距离的变动成本、车辆固定成本、物料未能在规定的服务时间窗内到达的平均单位时间惩罚成本。

2.个体最优让步接收机制

在更新个体极值时，引入模拟退火思想，以一定的概率接收目标值在一定程度ρ的恶化。具体公式如下：

(13)

(14)

其中代表可以接收的恶劣程度，随迭代次数线性递减。为初始最大可接受的恶劣程度系数，N为迭代次数，Nmax为最大迭代次数。

3.其他机制设计

交叉机制：车辆编码子染色体之间的交叉意义不大，选择代表工位组合的子染色体进行基于位的顺序交叉（Order Crossover，OX）；变异机制：本文通过对车辆编码子染色体进行基于位的变异，改变配送出动的车辆数。变异概率随迭代次数线性递减如公式(15)。

(15)

其中Pmax表示最大变异概率，Pmin表示最小变异概率，n为迭代次数，Nmax为最大迭代次数。

实例验证

算法采用MATLAB2014编程。算法参数设置如下：种群规模N=40,最大迭代次数Nmax=100，交叉概率为Pm=0.85，变异概率最小值Pmin=0.05，最大值Pmax=0.1，让步接收初始恶劣程度系数=0.5，早达惩罚系数A=0.5，晚达惩罚系数B=2.5，权重系数分别为0.6，0.1，0.3。

算法分析

为了验证算法对粒子复杂度的适应性，不断扩大粒子复杂度，分别选择6、8、…、18个工位进行50次实验，结果如表2所示。18个工位时优化过程对比如图4所示。

表2 算法对粒子复杂度适应性分析

Tab 2 Adaptability analysis of particle algorithm complexity

粒子复杂度	HPSO	HPSO寻优次数	IHPSO	IHPSO寻优次数
2*6	1240	64	1550	18
2*8	1946	32	2008	40
2*10	2281	41	2280	42
2*12	2539	46	2363	32
2*14	3389	46	3340	27
2*16	3952	42	3850	32
2*18	4680	46	4520	38

图4 优化过程对比

Fig 4 Comparison of optimization processes

算法结论：通过以上分析比较发现改进的算法，随着粒子复杂度的不断增高，算法寻优优势越明显。由于改进的算法与基本算法相比在一定程度降低了粒子的多样性，在粒子复杂度较低的时候，容易陷入局部最优，寻优能力较低；随着粒子复杂度的增强，改进算法粒子多样性随之提高，同时，与基本算法粒子相比改进算法的初始群体质量更高，所以寻优能力更优。

应用分析

以某混流制造车间的配送数据为依据，随机运行本算法50次，其中最优结果图5所示。最优解为3406。单目标值分别如下：行驶路程成本1416，时间惩罚值2520，出动车辆固定成本18000。其中行驶距离和出动车辆分别为：472m 和6辆。仿真的配送路线如图5所示。

仿真路线图各辆车对应的路径如下：第1辆车的运输路线为：0->14->2->6->0；第2辆车的运输路线为：0->9->10->15->0；第3辆车的运输路线为：0->7->13->0；第4辆车的运输路线为：0->8->0；第5辆车的运输路线为：0->12->1->4->3->0；第6辆车的运输路线为：0->11->5->0

图5 最优配送路线

Fig 5 Optimal distribution route

在多目标优化时,总目标最优时,单个目标可能并不是最优。为此,权重系数依次分别设为1,其它两者为0时分别随机计算20次，取单目标最小者，结果如表3所示。

表3 单目标结果

Tab 3 Single objective results

目标值F
0	0	1	799.4
0	1	0	1800
1	0	0	796

应用结论：从实验结果可以看出来，不同的权重系数会有不一样的优化结果。在应用于实际生产过程中，可以根据物料配送中企业可以根据物料紧迫程度或实际情况调整各目标的权重，来指导物料配送。

结论

1.建立了基于混流制造车间的物料配送多目标优化模型。模型考虑了载重和时间窗约束，并考虑到混流制造车间物料种类多，各类配送任务优化指标之间存在差异性。当在同一配送系统中进行优化时，建模时设计各配送任务与优化指标之间的平衡系数，是模型与实际贴合度更高。

2.设计了改进的混合粒子群算法将遗传算法的交叉变异和模拟退火思想与粒子群算法相结合，并提出基于顺序列的优化组合编码方式，提高粒子初始化质量。验证结果表明：随着粒子复杂度的增高改进算法的寻优优势越发明显。

3.混流制造物料在种类多，需求复杂。将改进的算法应用到混流制造物料配送优化中，可以快速高效的为企业提供配送指导意见。使整个配送成本最低，配送时间最佳，配送路径更贴合企业实际需求，提高混流制造物料配送效率。另外，企业可以根据自身情况设定各目标值之间的权重系数，以满足不同需求。

[参考文献] (References)

[1] 蒋增强, 金阳, 梁军义,等. 不确定环境下混流装配生产车间的动态物料配送策略[J]. 计算机集成制造系统, 2017, 23(10):2108-2118.
[2] 周炳海, 徐佳惠, 彭涛. 基于新型线边集成超市的周期性物料配送优化[J]. 吉林大学学报(工学版), 2018, 48(2):588-595.
[3] Zhou B H, Shen C Y. Multi-objective optimization of material delivery for mixed model assembly lines with energy consideration[J]. Journal of Cleaner Production, 2018, 192:S0959652618312939.
[4] 刘旭, 楼佩煌, 钱晓明,等. 基于改进遗传算法的物料配送多AGV调度优化[J]. 机械设计与制造工程, 2015(3):16-21.
[5] 涂海宁, 徐星. 改进蚁群算法下的物料配送路径优化研究[J]. 机械设计与制造, 2017(8):265-268.
[6] 庄存波, 刘检华, 唐承统, 邢香园.复杂产品离散装配过程中的物料动态跟踪与管理技术[J].计算机集成制造系统，2015, 21(1): 108-122.
[7] 徐晓芳, 刘鑫. Job Shop作业车间物料配送小车定位方法研究[J]. 机械工程师, 2018(1):55-56.
[8] 韩曙光, 蒋欢欢, 胡觉亮. 基于电子看板的装配线物料配送优化研究[J]. 浙江理工大学学报:社会科学版, 2017, 38(2):120-126.
[9] 吴京秋, 王梓懿, 吕立,等. 基于ERP信息管理的焊接生产线物料配送控制系统的设计[J]. 自动化博览, 2018(z1):117-119.

作者简介：施贝（1993-），女，合肥工业大学硕士研究生，主要研究方向：制造系统监测、控制与管理

通信联系人：张玺（1985-），男，讲师，硕导，生产计划控制与调度、智能制造. E-mail: zhang_xi@hfut.edu.cn