于混合遗传算法的工程机械客户服务调度研究①

李 艺,叶 桦,仰燕兰

(东南大学 自动化学院,南京 210096)

在现代市场经济的竞争环境下,服务的及时性以及服务质量对客户满意度和客户的忠诚度有非常大的影响[1].一般来说,产品服务分为两大类,基于设施的服务和现场服务.基于设施的服务一般是需要客户上门,采用专业的设备进行处理.现场服务是指服务提供方前往客户的地理位置上提供服务,这其中的典型代表就是大型设备的安装、维修和保养.

现场服务调度问题,又称为现场技术人员调度问题,其优化实质是对各类资源的合理调配和时间安排.目前众多学者对其的研究主要分为两方面,一类是对优化模型的研究,另一类是对求解算法的研究.

优化模型方面,Li 等通过在团队中调度不同类型的工人服务线路来最大限度的减少工人综述和总位移[2].Kovac 等在执行具有相同优先级但具有不同时间窗口的现场服务时,从公司的角度最大限度的减少位移和外包成本[3].Dohn 在受到有限数量团队成员的限制情况下研究了如何使得任务数量最大化[4].江俊杰等提出了等待时间的概念,利用遗传算法求解该类问题[5].吴斌等首次考虑客户满意度的概念,进一步完善求解的模型[6].

求解算法方面,一部分学者将研究的重点放在技能指派方面.谈文芳等指出维修指派问题属于NP 难题,运用粒子群算法求解,建立了一种优化指派的模型,验证了粒子群优化的可行性[7].王庆建立了人员工作指派及调度的决策模型,并对人员进行分析,提出了计算员工团队匹配度和员工任务匹配度的模型,提出并改进了双层编码的混合遗传算法[8].

还有一部分学者将现场服务调度问题同已有的一些经典问题进行对比,基于经典模型已有的研究成果提出了新的策略.江俊杰等将现场服务调度问题看做多技能匹配和多旅行商问题的综合,提出了基于分段染色体遗传算法的求解方案[5].Pillac 等分析了现场调度服务问题与带时间窗车辆路径问题的区别,提出并行自适应大领域搜索算法优化解决该问题[9].曹永荣等以排队模型为基础,通过仿真的算法研究了现场服务问题[10].

相较于普通的服务产品,工程机械的现场服务调度具有一定的特殊性.一方面,工程机械设备作为基础建设的大型装备,施工地点大多位于偏远地区,交通十分不便,一般是由服务人员乘坐专用服务车赶赴现场进行维修保养服务,故涉及人车的联合调度,相较一般的调度问题更为复杂.另一方面,不同类型的工程机械在结构、性能等方面都有很大的区别,例如从大类上分,有起重机、挖掘机、装载机、泵车等种类,这就对维修保养人员的专业技能水平提出了更高的要求.如何针对具体的工程机械设备选派合适的专业技术服务人员是另一个亟待解决的问题.

工程机械人车一体化调度属于新的研究问题,要考虑技能特点与维修需求的相匹配,同时相较于一般的现场服务问题,还有额外的服务车约束.本文在现有服务调度问题的基础上,结合工程机械客户服务的特点,将其转化为一个特殊的三次匹配问题,提出了基于二分图最小权匹配的混合遗传算法进行求解.

1 工程机械人车一体化调度问题模型

1.1 问题定义

工程机械人车一体化调度问题可以定义为:多个企业的工程师从不同的起点搭载不同的服务车前往分散在不同地理位置上的多个工程机械处提供售后服务,包括安装、维护检查、故障维修等类型.工程师具备不同的技能,且技能能力存在区分度,熟练度高的工程师维修速度快.每个工程机械的维修需求不同,需要对应技能的工程师前往.

调度系统安排处于不同位置的服务车去接相关工程师去分别执行这些任务,假设服务车的设施配备满足工程师的维修需求.在满足一定的约束条件的前提下(技能匹配性、时间限制等),达到一定的目标(路程短、花费时间少、客户满意度高等).

上述问题可以描述为:m名维修人员组成的集合A={1,2,3,…,m},n辆待修机械组成的集合M={1,2,3,…,n},p辆服务车组成的集合C={1,2,3,…,p}.

提出一个包含技能需求的集{合S={1,2,}· ··,l}.维修人员k具备的技能由向量gk=g1k,g2k,···,glk表示,gnk表示该维修人员在第n项技能上的表现能力,范围在0-5 之间.gnk=0表示维修人员不具备该项技能；=h表示该维修人员具有等级为h的第n项技能,h值越大,表明具备的该相应技能水平越高,完成该项任务所需要的时间更少.

1.2 维修时长计算

服务人的技能特长与技能能力水平直接影响该项服务任务的完成时间.传统操作中,多依靠经验对技能员工进行分配,这种分配方式既费时又费力,且满意度不高.本文希望在充分考虑员工技能工种和待维修机械的切实需求的前提下,通过一些可量化、可计算的方式针对匹配双方的需求进行处理,进而获取最终的匹配方案.

若待修机械j所需的服务为Sj=m,则服务人k完成该任务的维修时长为:

tajk表示服务人k对待修机械j的维修时长.Tm表示第m类需求的标准工时.gmk=0表示维修人员k不具备该项技能m,与该工程机械不匹配,任务完成时间无限长.

1.3 统一调度模型

工程机械在故障时,能否在最短的时间内得到维修,直接关系到工程机械效能的实现,也是评价服务质量高低的重要因素.服务人到达维修地点的方法是服务车到服务人所在地,搭载相关维修设备及服务人到目标工程机械.针对若干个任务点,需要找出多工程机械-多服务人-多服务车的最优组合.

图1 多服务车-多服务人-多工程机械匹配示意图

设工程机械j到服务人k的所需时长为tdjk,服务人k到服务车v的所需时长为tdkv.

求解的目标是对于需要的维修机械j,选择合适的服务人与服务车组合,使得从分配到完成待修机械需求所花费的时间尽可能短.总体最优的目标模型为:

约束条件如下:

式(2) 是求解目标,最小化完成所有任务的总时间.xjkv是0-1 变量,服务人k、服务车v与机械j构成组合时值为1,反之为0.式(3)-式(5)是约束条件,本文是在服务资源充足的情况下,单次单任务分派的统一调度方案.服务人数目和服务车数目大于待修任务,一个服务人最多安排一项任务,一台工程机械仅由一个服务人负责.

2 基于二分图最小权分配的混合遗传算法

根据图1,三个点集A,M,C,同一点集之间没有边,MC 点集之间没有边.MA 点集之间有边,AC 点集之间有边,求组合的最小权重,这是一类组合优化问题,属于三分图的最小权匹配,称作AP3 问题[11].二分图匹配问题可以在多项式时间内有效的解决,但是AP3 问题是一个非确定多项式问题.

现有研究下,精确算法和启发式算法都有建议解决AP3 问题.在这些当中,Burkard 等人专注于AP3 可分解的成本系数[12].即使有这个特例,AP3 问题仍然是NP 难题.Aiex 等将GRASP(贪婪随机自适应算法)应用于权重调整以期望获取更好的结果[13].张树威改善束搜索算法,求解AP3 问题[14].

本文提出了一种基于二分图最小权匹配与遗传算法相结合的求解方案.

图2 AP3 问题X,(M,P)、Y(P,C)组合

如图2是一个一般的三次匹配问题.对于需要提供服务的工程机械{M1,M2,M3},提供服务的服务人组合为{P1,P3,P5},搭载服务人的服务车组合为{C2,C4,C6}.AP2 问题只涉及一个组合X,AP3 问题涉及组合X,Y.可以采用拆分的思路,假设在组合X已知的情况下,进行服务车的分配,这就是一个二分图的求解问题.如下图图3所示.

图3 AP2 问题 求解Y(P,C)组合

本节中利用匈牙利算法求解服务人与服务车的匹配,涉及二分图最小权分配.待修机械与服务人的组合利用带精英选择策略的遗传算法求解,适应度函数为工程机械到服务人到服务车的权重之和.基本的数据流程如下:

图4 服务车-服务人-工程机械调度计算过程

2.1 基于匈牙利算法求解人车匹配问题

匈牙利算法最早是由匈牙利数学家Konig D 用来求矩阵中0 元素的个数的一种方法,他证明了“矩阵中独立0 元素的最多个数等于能覆盖所有0 元素的最少直线数”.1955年由Kuhn 在求解著名的指派问题时引用了这一结论,并对具体算法做了改进,仍称为匈牙利算法.

该算法是基于效率矩阵每一行元素减去改行的最小值,每一列元素减去该列的最小值,得到新效率矩阵,原效率矩阵与新效率矩阵最优解相同.通过行/列变换让费用矩阵的每行和每列都出现0,找出不同行、列的n个0,这些0 对应的指派就是最优指派.求解步骤如下:

Step1.建立指派分配方案的效率矩阵A,A为n×m的矩阵.找出效率矩阵A每行的最小元素,每行减去该元素,对矩阵的列做相同操作.

Step2.将处理后的矩阵A转化为匈牙利算法求解所需要的标准型d×d阶矩阵B,d=max(m,n).当m小于n时,补充全零行.当m大于n时,补充全零列.

Step3.用最少直线数k覆盖所有零元素.

Step4.当k=d时停止计算,得到最优配置方案.当k≠d时,从矩阵未被覆盖的数字中找到最小数值s，未被覆盖的元素减去s,直线相交处加上s,被直线覆盖而没有相交的元素不便,得到新效率矩阵c.

Step5.重复以上步骤Step2,Step3,直至k=d.

2.2 基于二分图最小权匹配的混合遗传算法

针对统一调度问题的特征,本节介绍基于二分图最小权匹配的混合遗传算法求解方案.针对基本遗传算法面临的一些问题,收敛太快陷入局部最优,收敛太慢耗时太长的缺点,应用多种改进策略,包括内嵌精英保留策略的选择算子,动态的变异概率等.

(1) 编码方式及解码

遗传算法现有的编码方式主要有实数编码和二进制编码.本文采用实数编码作为人车一体化调度问题解的表达形式.该编码方式采用N个1～M之间互不重复的整数排列表示染色体.染色体的长度取决于待修机械的总数(此处工程机械数目为N),节点的取值为服务人的编号范围(此处服务人数目为M).图5给出了一个工程机械数目为4,服务人数目为20 的简单染色体的编码方式.

图5表示对工程机械1-4,分配的服务人编号分别为7,12,4,5.

图5 染色体编码

解码过程是根据服务人的信息,利用匈牙利算法计算最小代价的服务车信息,得到服务车编号,形成工程机械-服务人-服务车的组合信息.

(2)适应度函数计算

种群的初始化采用均匀分布法,随机产生num个不重复的染色体.首先计算服务人与待修机械的代价函数,即路程与维修所消耗时间之和.

其次,根据确定的服务人组合,利用匈牙利算法计算对应服务车组合.服务车接载服务人的时间消耗为:

对于该染色体,解码之后,该组合匹配最终的时间为:

由于本节是求解最优的组合匹配,目的是使得消耗的总时间长度最小,因而需要将目标函数映射为最大值且函数值非负的适应度函数.采用如下转化方法:

Fmax(x) 表示种群中目标函数值最大的个体对应的时间长度.

(3) 内嵌精英选择策略的轮盘赌选择算子

遗传算法的选择算子是根据个体的适应度对种群中的个体进行的优胜劣汰操作.轮盘赌选择法的基本思想是各个个体被选中的概率与其适应度大小成正比.

Rudolph 利用齐次有限马尔科夫链证明了仅仅采用交叉、变异和选择(比例选择法)三个遗传算子的标准遗传算法不能收敛到全局最优.因为存在统计误差,根据产生的随机数进行选择,可能会出现不正确的反映个体适应度的选择,导致适应度高的个体也被淘汰.Eiben 利用马尔科夫链证明了包含精英保留策略的遗传算法具有全局收敛性,另一方面,它也会使的某个局部最优个体不易被淘汰反而快速扩散,以致算法收敛于局部最优解[15].因而,它常与某些选择算法配合使用.本文采用的是采用内嵌精英选择策略的轮盘赌选择算子 ,其流程如图6所示.

图6 内嵌精英保留策略的轮盘赌选择算子

(4)染色体交叉操作

由于服务人与工程机械之间存在技能匹配,即服务人具备的技能特征与待修机械需求不符合时,无法配对.同时,对于一个服务人,只安排一项待修任务,因而染色体中不能存在重复编码.为了增加解的可行性,本文采用点对点交叉去重策略.点对点交叉可以保证技能的匹配度,去重确保染色体基因的不重复.

针对两个父代染色体,记染色体父体,染色体母体.在种群中任意选择两个染色体作为父代染色体,在父代染色体上任意选择一个基因位作为交叉位.如图7所示为简单的交叉示意图.

图7 染色体交叉简单示意图

(5) 自适应变异概率的染色体变异操作

一般来说,变异操作包括两点互换变异,以及单点特殊变异.两点互换变异是针对选择的染色体,随机交换两个基因位置.但受本文的实际场景约束,每个基因位对应着不同编号的工程机械,工程机械的维修需求需要与服务人的技能一致,交换变异很可能造成不可行的解.本节采用单点特殊变异,随机选择染色体的随机位置,进行突变.

为了让遗传算法不变为一种无目的的随机搜索算法,变异概率的取值一般为0.05-0.5.

对于小规模优化问题,变异概率通常取常数,对于大规模优化问题,变异概率通常建议取变量[16].在进化前期,变异概率较大有利于提高搜索能力,但是后期可能较大程度的破坏遗传信息,进化后期采用较小的变异概率对种群进行微小调整.本文根据文献[16]中的介绍,采用常用的线性变异方案.

设变异概率的取值范围[rmin,rmax+rmin).随着进化次数的增加,变异概率在该区间内呈现递减趋势.若用cur表示当前进化次数,curmax表示最大进化次数.则当前进化次数中的变异概率:

设置curmax=100,rmax=0.45,rmin=0.05,给出变异概率变化曲线如图8所示.

2.3 算法收敛性分析

(1) 遗传算法收敛定义

对于遗传算法而言,收敛性是指算法的迭代种群逐渐趋于某一稳定状态,如适应值的最大值或者平均值收敛于解的最优值[17].

图8 变异概率变化曲线

设h(i)={x1,x2,···,xn} 为遗传算法的第i代种群,n为当前种群中的个体总数,f(x) 为适应度函数.Zh(i)=max{f(xk) |k=1,2,···,n} 为种群最大适应度,f+=max{f(x) |x∈S}为全局最大适应度,S为所有群体的个体集合.如果:

则称遗传算法依概率收敛到全局最优解.

(2) 马尔科夫链定义

设随机序列X={Xn,n=0,1···}的离散空间为E,如果对于任意n≥0 ,以及i0,i1,···,in,j∈E,满足条件概率:

则称这类X随机过程为离散马尔科夫链,马尔科夫链具有无后效性的特点,即当前状态只与前一状态有关,而与其他状态无关.

(3) 混合遗传算法收敛性分析

将混合遗传算法看做一个离散状态空间下的随机序列,把每一代种群P(1),P(2),…看做一种状态,种群的代代演变看做是状态间的转移,二分图的匹配实际上是一种局部优化搜索.当前种群的状态仅依赖于上一代种群,与以往无关,因而可以采用马尔科夫链来证明算法的收敛性.

假设总体状态空间为H,算法中每一代种群h(t)对应马尔科夫链中的一个状态,种群的逐代进化对应马尔科夫链中的状态转移.标记每个h(i)∈H是否包含当前最优个体.根据遗传算法的收敛性以及精英选择策略的特征可知,一旦转移后的状态包含了当前最优个体,在以后的转移过程中,将一直包含最优个体状态,且其他个体状态也会一直逼近最优个体.最终:混合遗传算法将以概率1 收敛到全局最优.

3 问题求解

以某机械制造企业某段时间的报修单为例,验证本文算法的有效性.设置种群数为100,迭代次数为80,交叉概率0.8.服务车平均行驶速度以60 km/h 计算.

表1给出了待修机械的信息,表2是对应维修需求的平均维修时长.表3给出了20 个服务人,20 个服务车的信息.位置信息用经纬度表示,纬度在前,经度在后.服务人技能数组简化为[a,b],a表示员工技能类型,b表示技能等级.

表1 工程机械信息

表2 维修工种信息

与传统遗传算法搜索最优解相比较,如图9所示.

图9 混合遗传算法与传统遗传算法最优值的对比

对于上述的M×P×C=4×20×20,可以看出混合遗传算法的最优值优于传统的遗传算法,且相较传统的算法可以较快的寻到最优解.

表3 20×20 服务人、服务车信息

进一步扩展问题规模,种群数目选择为200,迭代次数选为100.将本文的基于二分图最小权匹配的混合遗传算法与传统遗传算法以及贪婪随机自适应搜索算法的结果进行比较.

从表4-表6中可以看出,基于这6 个算例,基于二分图最小权匹配的混合遗传算法的最优值和平均值均优于传统遗传算法和贪婪随机自适应搜索算法.

表4 多工程机械混合遗传算法求解结果

4 结束语

本文针对工程机械客户服务系统人车一体化调度这一特殊的调度问题,在服务资源充足的情况下,建立了最小化总时间长度为目标的优化模型.将实际模型转化为一个带技能匹配的三次匹配问题,利用匈牙利算法和遗传算法混合求解,同时为了优化解情况,引入了内嵌精英匹配的选择算子和动态的变异概率.结果证明,该算法能有效解决对应问题.

本文的研究重点是服务资源充足的情况下的单次单任务安排,即对一名服务人安排一个维修任务.但服务资源不足时,一名工人一次需要指派多个任务,这就涉及针对一个服务人的多任务安排.另外,为了进一步提高客户满意度,需要进一步完善约束条件,包括时间窗等,对相关模型的归纳求解是后续研究的方向.

图10 混合遗传算法与传统遗传算法平均值的对比

表5 扩充仿真实例

表6 三种算法对比结果