基于改进遗传算法的多目标物料配送方法研究

马磊磊，王 强

(合肥工业大学机械与汽车工程学院，合肥 230009)

0 引言

由于市场需求多变，装配车间的生产过程时刻都有可能产生各种不确定因素(紧急插单、订单取消、交货期变更)导致生产计划重排。同时生产车间环境复杂多变，各种扰动随机出现，这对生产装配车间物料配送提出更高的要求，因此企业急需新的技术来处理各种不确定因素下物料配送问题［1］。

面对实际的生产车间中不确定因素条件下的物料配送要求的不断提高，一些学者对此进行了研究。李运霞等［2］针对路径柔性车间调度问题，提出一种多种群遗传算法，并验证其可行性。曹二保等［3］均研究了模糊需求条件下路径规划问题。张建勇等［4-6］分别对各种模糊的工位需求、旅行时间、预约时间等条件下的车辆路径规划问题进行了研究。李晋航等［1］在多模糊信息条件下，构建了机会约束规划模型，并对传统遗传算法进行改进，研究了不同因子的设置对路径规划结果的影响。

在以往的车辆路径问题的研究中不仅仅需要考虑各种不确定因素，还要考虑配送过程中工位对服务时间偏好程度、配送车辆行驶距离、车辆载荷率和车辆数等多目标的优化。王君等［7］首先在模糊预约时间描述的基础上提出满意度表示的新方法，然后构建多目标优化模型，通过实例验证了所提出算法解决多目标优化问题的有效性。GAO Gui-bing［8］等用多目标进化算法研究了混合生产系统下物料配送路径问题。Tang［9］等把VRPFDT分成两个阶段的子问题:第一阶段是通常的带时间窗的车辆路径问题，以车辆行驶距离为优化目标;第二阶段在最小化车辆行驶距离的基础上，对顾客的满意度进行优化求解，但在此过程中无法做到同时使多个目标都达到优化的目的。

物料配送中车辆路径规划问题是整个生产车间装配环节的重要问题，该问题的求解结果将在一定程度上决定生产车间的装配效率以及企业制造过程的物流成本。因此，本文在前述研究的基础上，给出模糊预约时间的一种新的表示方法，以工位满意度为一个优化目标构建多目标优化模型，并且对传统遗传算法进行改进，采用可行插入法生成初始种群以加快收敛速度，提出狭义基因相似度的概念避免相似度高的个体交叉操作，同时将双变异机制加入到变异过程控制全局解空间的搜索范围和收敛速度，最后通过实例验证模型和算法的有效性和可行性。

1 物料配送问题描述

1.1 问题描述

每个工位由仓库部门发出的配送工具进行服务，任意一个配送工具所服务的各个工位的物料需求量Qi之和不得大于最大运载能力Q。配送工具满载物料离开仓库，为所需要物料的工位配送物料，最后回到仓库。在一次物料配送过程中，所有工位的集合为{Xi，i=0，1，2，…，N}，其中X0代表配送中心，配送工具的集合为{Vk，k=0，1，2，…，K }，每个工位物料需求量和服务时间窗已知，并且每个工位有且仅有一个配送工具服务一次。

1.2 模糊预约时间和工位满意度

2 数学模型建立

2.1 决策变量

2.2 多目标数学模型(P)

根据上述问题的描述，构建了以下数学模型:

2.2.1 优化目标:

2.2.2 约束条件:

式中，N为工位数;K为配送工具数;Q为运载能力;Qi为工位i的需求量;Dij为从工位i和j间的距离;Ti为在工位i的服务时间;Tij为从工位i到工位j的行驶时间;Wi为在工位i处的等待时间;ti为开始服务工位i的时间。

式(2)～式(5)表示目标函数，依次为配送工具行驶距离、使用数量、工位满意度、运载率;式(6)表示不得在时间窗外对开始服务;式(7)表示运载能力约束;式(8)表示每个工位有且仅有一个配送工具服务;式(9)～式(10)表示两变量xijk和yik之间的关系;式(11)～式(12)表示配送工具由仓库离开，最后驶回仓库;式(13)为支路消除约束。

3 用改进的遗传算法求解模型

生产车间物料配送路径规划问题是一个NP问题。目前，许多启发式算法在解决多目标多约束优化问题时都有其自身的缺陷，如进行求解时收敛速度慢易发生未成熟收敛、全局寻优能力和局部搜索能力不均衡［11-12］。因此，本文对遗传算法进行改进以求解问题(P)，即基于遗传算法的进化方式借鉴遗传算法的编码方式［13］，同时运用行插入法得到初始种群，交叉操作中用狭义基因相似度区分染色体的相似性，将双变异率加入到进化过程的变异操作。

3.1 构造染色体，产生初始种群

初始种群生成的质量决定了算法搜索的起始点，高质量的种群可加速算法的收敛提高求解效率。张建勇［6］等所研究初始种群生成步骤中，当前配送工具路径不存在可行插入位置时，新开一配送工具，而本文在此基础上进行改进，如步骤4所述。

定义1:最佳插入位置既在当前路径的可行插入位置的集合中，使工位的综合满意度值最大的位置［6］。

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

步骤1:将N个工位随机排列，得到工位序列集合X={x1，x2，…，xN}，然后从左向右依次分配给车辆，最后初始化配送路径编号Car_Code=0;

步骤2:置Car_Code=Car_Code+1，新开配送工具，其路径编号为Car_Code，将当前X中最左边工位安排给该新路径，从X中删除该工位;

步骤3:判断X是否为空。如果是，转步骤5;否则转步骤4。

步骤4:取当前集合X中最左边的工位，判断当前配送工具路径是否存在可行插入位置。若存在，则将其插入当前配送工具路径的最佳插入位置，转步骤3;若不存在，依次按配送工具路径编号从小到大判断是否存在，若存在则将其插入该路径的最佳插入位置，转步骤3，否则转步骤2;

步骤5:计算生成的可行染色体的最佳开始服务时间，使该染色体的工位平均满意度达到最大;

步骤6:重复步骤2～步骤5，当生成可行染色体达到规定数量时停止。

其中，可行插入位置及最佳开始服务时间的确定如下:

(1)可行插入位置的确定

设已建立的某配送工具的可行配送路径为(x1，x2，...，xi，...，xp)，在工位 xi处的开始服务时间为txi，则配送工具到达工位的最大推迟时间为［7］:

在其可行路径中第i个工位后(xi和xi+1之间，若i=0时即x1之前)插入一个工位xs后该路径仍是可行的，则应满足:

条件2:时间约束条件:

①配送工具达到工位s的时间不得晚于该工位时间窗的下限，既 txi+Txi+Txi，s≤ LTs，当 i=0 时，txi=Txi=0，Tx1，s=T0，s;

②当i≤p－1时，配送工具到达工位Xi+1必须满足:max{txi+Txi+Txi，s，ETs}+Ts+Ts，xi+1≤ txi+1+max_pone(xi+1)－Wxi+1。

(2)最佳开始服务时间的确定

在以上操作得到的可行路径中，工位综合满意度不是最佳的。在张建勇［6］最佳开始服务时间的确定方法研究基础上，本文是从配送工具路径的最后面的工位进行时间的调整，省去了确定不可推部分，同时在最大可推迟量的计算上有所改进。

最佳开始服务时间的计算步骤如下:

步骤 1:假设某配送工具配送路径为 (x1，x2，......，xp)。

步骤2:将该配送工具路径划分为若干个片段(xi，xi+1，xi+2，…，xj)，满足条件 Wxi+1=Wxi+2= ...=Wxj=0，且有:i≠1时，Wxi≠0;Wxj＜ p时，Wxj+1≠0。

步骤4:取当前配送工具路径中已调整片段的前一片段按照步骤3的方法进行调整;若该片段与当前配送工具路径中的后一片段形成新的片段，则重新对新形成的片段进行调整;否则转步骤5。

步骤5:继续重复步骤4，直到完成该配送工具路径中所有工位开始服务时间的确定。

3.2 适应度函数

根据每个个体优化目标值及权重参数计求解其适应度。求解函数如下所示:

其中，hk表示第k个染色体;dk、vk、uk、lk分别表示染色体hk的行驶距离、配送工具使用总数、工位平均满意度、配送工具运载率;dmax、vmax、umax、lmax分别表示当前种群中染色体的最大行驶距离、最大配送工具使用数、最大工位平均满意度、最大运载率;αi(i=1，2，3，4)为权重系数。

3.3 用狭义基因相似度区分染色体的相似性

为避免标准遗传算法存在的缺陷，防止可能出现的大量相似个体的交叉，本文采用狭义基因相似度概念来区分染色体的相似性。

定义2:狭义基因相似度Mxy是两个染色体x、y中，具有相同工位路线的所有工位数量与总工位数之比［1，14］。如染色体 09320480675010 和 04806750310290的相同路径有06750和0480(包含5个工位)，工位总数为9，则Mxy=5/9。当且仅当染色体等价时(Mxy=1)，狭义基因相似度为1。

3.4 双变异率的改进遗传算法

通过狭义基因相似度概念的定义，避免相似高的染色体交叉操作。同时将双变异机制加入传统遗传算法中控制全局解空间搜索范围和收敛速度。

双变异率［14］，既局部小变异率和全局大变异率，其出现的位置、起到的作用以及面对的对象是不一样的。当交叉操作产生的个体数TempPop_size小于种群个体数Pop_size时，表明由选择操作产生的个体间的相似度高。为了提高染色体的多样性，扩大算法的搜索区域，保证染色体的解充满整个可行解空间，避免局部收敛，对交叉后的种群进行局部小变异。为了保持解种群的优良性，局部变异的概率Local_Pm取值范围一般为0.07～0.15。对变异操作产生的种群，首先以选择操作来淘汰一批不良染色体，然后计算两个体间的基因相似度，对小于某规定值Mxy'的个体进行交叉操作。狭义基因相似度概念的加入，成功的避免了相似个体间的交叉操作，抑制未成熟收敛。同时，计算每一代交叉操作的个体适应度值以及运用轮盘赌法选择较优个体，然后对该群体以大变异率Global_Pm进行全局大变异，以保证整个过程的全局性。

3.5 改进遗传算法步骤

改进遗传算法操作步骤如下:

步骤1:运用3.1的方法生产初始种群;

步骤2:用如图1的流程对种群进行交叉变异操作;

步骤3:适应度函数计算;

步骤4:用轮盘赌法选择染色体;

步骤5:对Step4中产生的新一代种群中每一个染色体按3.1相同的方法重新分配保证可行性;

步骤6:重复步骤2～5直到完成给定的循环次数;

步骤7:找出最优个体，既配送路径的最优方案。改进遗传算法具体操作流程如图1所示:

图1 改进遗传算法流程图

4 实例验证

生产车间某次物料配送中，有9个工位和一个仓库，配送工具的运载力为12个单位，各工位的服务时间、预约时间和需求量如表1所示，各工位间的行驶时间及行驶距离如表2所示;改进遗传算法基本参数，取种群大小Pop_size=100，迭代次数Max_gen=200，选择概率Px=0.8，交叉概率Pc=0.8，双变异概率 Local_Pm=0.1 和 Global_Pm=0.2。

表1 各工位信息表

表2 工位间距离和行驶时间表

根据上述算法利用Matlab仿真，对不同权重设置情况下进行计算，结果如表3所示。

从表3中可以看出，优化目标权重参数的设置对实验结果有很大的影响。d、l与v密切相关，即d随着v的增加而呈现增加的趋势，l随着v的增加呈降低的趋势;而u与d、v、l等目标相对立，即u的提高是以d和v的增加以及l的降低为代价的。

为证明本文所提出的改进遗传算法的有效性，以改进遗传算法分别取权重α1=1、α2=1、α3=1，与传统的遗传算法相应的单目标求解作对比(由于l与v成反比例关系，所以在此不作α4=1分析)。采用传统遗传算法计算本例，初始种群大小为100，选择概率、交叉概率均为 0.8，变异概率为 0.1。

图2 配送工具行驶距离收敛比较

图3 配送工具使用数收敛比较

图4 工位平均满意度收敛比较

如图2所示取α1=1时，改进遗传算法在30代以后呈现稳定下降的趋势，至55代收敛;而传统遗传算法在中后期收敛速度很慢，直到126代才开始收敛。如图3所示取α2=1时，改进的遗传算法基本无波动现象，从整个图像看两者下降的趋势，既开始点和收敛点的连线，改进遗传算法的斜率明显大于传统遗传算法的斜率。如图4所示取α3=1时，同样改进遗传算法收敛速度快，随着迭代次数的增加呈现稳定上升的趋势。综上所述，由图2、3、4的收敛图可知，显然改进遗传算法优于传统遗传算法。

5 结论

(1)本文运用模糊预约时间窗，考虑了工位对时间窗的偏好，同时使工位期望服务时间是在时间窗内服从正态分布的随机变量，且以工位的满意度为其中的一个优化目标，更切实际地解决不确定因素下的物料配送问题。

(2)针对传统遗传算法存在易发生未成熟收敛及其收敛速度低等缺陷，本文采用可行插入法生成初始种群以加快收敛速度。提出狭义基因相似度的概念避免相似度高的个体交叉操作，同时将双变异机制加入到变异过程更好地控制全局解空间的搜索范围和收敛速度。

(3)采用线性加权模型解决多目标优化问题中的权重选择问题，设置不同的权重因子其求解的结果亦有很大的不同，决策者可以根据生产车间物料配送的实际要求选择不同权重参数。

［1］李晋航，黄刚，贾艳.多模糊信息条件下的物料配送路径规划问题研究［J］.机械工程学报，2011，47(1):124－131.

［2］李运霞，杜鹃，孙王路.基于多种群遗传算法的路径柔性车间调度问题［J］.组合机床与自动化加工技术，2014(3):152－155.

［3］曹二保，赖明勇，张汉江.模糊需求车辆路径问题研究［J］.系统工程，2007，25(11):14 －18.

［4］张建勇，郭耀煌，李军.模糊需求信息条件下的车辆路径问题研究［J］.系统工程学报，2004，19(1):74 －78.

［5］张建勇，李军.具有模糊旅行时间的VRP的一种混合遗传算法［J］.管理工程学报，2006，20(4):13－16.

［6］张建勇，李军，郭耀煌.具有模糊预约时间的VRP混合遗传算法［J］.管理科学学报，2005，8(3):64－71.

［7］王君，李波.带模糊预约时间的车辆路径问题的多目标禁忌搜索算法［J］.计算机集成制造系统，2011，17(4):858－866.

［8］GAO Guibing，ZHANG Guojun，HUANG Gang，ZHU Haiping，GU Peihua.Solving material distribution routing problem in mixed manufacturing systems with a hybrid multi-objective evolutionary algorithm［J］.J.Cent.South Univ.2012，19:433－442.

［9］TANG Jiafu，PAN Zhendong，FUN G R Y K，et al.Vehicle routing problem with fuzzy time windows［J］.Fuzzy Sets and Systems，2009，160(5):683 －695.

［10］赵燕伟，李川，张景玲，等.一种新的求解多目标随机需求车辆路径问题的算法［J］.计算机集成制造系统，2012，18(3):523－530.

［11］刘明周，张明伟，蒋增强，等.基于混合粒子群算法的多目标柔性Job-Shop调度方法［J］.农业机械学报，2008，39(5):122－127.

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

［13］齐晓宁，汪永超，贾婧，等.基于遗传算法的面向绿色制造的车间调度优化［J］.组合机床与自动化加工技术，2012(10):16－18.

［14］王杰，马雁，王非.一种双变异率的改进遗传算法及其仿真研究［J］.计算机工程与应用，2008，44(3):57 －59.