﻿ 基于混合遗传算法的工程机械客户服务调度研究
 计算机系统应用  2019, Vol. 28 Issue (7): 191-198 PDF

Research on Customer Service Scheduling of Construction Machinery Based on Hybrid Genetic Algorithm
LI Yi, YE Hua, YANG Yan-Lan
School of Automation, Southeast University, Nanjing 210096, China
Foundation item: Open Fund of Key Laboratory of Measurement and Control of Complex Engineering Systems (Ministry of Education) (MCCSE2016B01)
Abstract: Scheduling of construction machinery customer service involves service vehicle, servicer, and engineering machinery. This study establishes a model with the goal of minimizing the total completion time under the premise that the service resources are sufficient and an engineer assigns at most one task, combining with path length, skill matching, service time, and other factors. Considering the combination of service vehicle, service person, and engineering machinery as a special three-part graph matching problem, a hybrid genetic algorithm solution based on the minimum weight matching of bipartite graphs is proposed. The roulette selection operator and dynamic mutation probability of the embedded elite strategy are introduced. The superiority of the algorithm is proved by a large-scale case study.
Key words: integrated scheduling     bipartite graph matching     genetic algorithm     elite retention strategy     dynamic variation

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

1.2 维修时长计算

 $t{a_{jk}}=\left\{ \begin{gathered} inf,\mathop {g}\nolimits_k^m = 0 \\ \mathop T\nolimits_{{m}} \frac{1}{{\mathop g\nolimits_k^m }},\mathop g\nolimits_k^m \ne 0 \\ \end{gathered} \right.,\;\; k = 1,2, \cdots, m,\;\;j = 1,2, \cdots, n$ (1)

$t{a_{jk}}$ 表示服务人k对待修机械j的维修时长. $\mathop T\nolimits_{{m}}$ 表示第m类需求的标准工时. $\mathop g\nolimits_k^m =0$ 表示维修人员k不具备该项技能m, 与该工程机械不匹配, 任务完成时间无限长.

1.3 统一调度模型

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

 $minZ = \sum {{x_{jkv}}\left( {t{a_{jk}} + t{d_{jk}} + t{d_{kv}}} \right)}$ (2)

 $\mathop \sum \limits_{k \in P,v \in C} {x_{jkv}} = 1,\forall j \in M$ (3)
 $\mathop \sum \limits_{j \in M,v \in C} {x_{jkv}} \le 1,\forall k \in P$ (4)
 $\mathop \sum \limits_{j \in M,k \in P} {x_{jkv}} \le 1,\forall v \in C$ (5)

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

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

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

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

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

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

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

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

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

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

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

(1) 编码方式及解码

 图 5 染色体编码

(2)适应度函数计算

 ${F_1}\left( x \right) = t{a_{jk}} + t{d_{jk}}$ (6)

 ${F_2}\left( x \right) = t{d_{kv}}$ (7)

 $F\left( x \right) = {F_1}\left( x \right) + {F_2}\left( x \right)$ (8)

 $f\left( x \right) = {F_{max}}\left( x \right) - F\left( x \right)$ (9)

${F_{max}}\left( x \right)$ 表示种群中目标函数值最大的个体对应的时间长度.

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

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

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

(4)染色体交叉操作

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

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

 ${r_{cur}} = {r_{max}}\left( {1 - \frac{{cur}}{{cu{r_{max}}}}} \right) + {r_{min}}$ (10)

2.3 算法收敛性分析

(1) 遗传算法收敛定义

 图 8 变异概率变化曲线

$h(i) = \left\{ {\mathop x\nolimits_1 ,\mathop x\nolimits_2 , \cdots, \mathop x\nolimits_n } \right\}$ 为遗传算法的第i代种群, n为当前种群中的个体总数, $f(x)$ 为适应度函数. $\mathop Z\nolimits_{h(i)} = max\{ f\left( {\mathop x\nolimits_k } \right)\;|\;k = 1,2, \cdots, n\}$ 为种群最大适应度, $\mathop f\nolimits^ + = max\{ f\left( x \right)\;|\;x \in S\}$ 为全局最大适应度, S为所有群体的个体集合. 如果:

 $\mathop {\lim }\limits_{i \to \infty } P\{ \mathop Z\nolimits_{h(i)} = \mathop f\nolimits^ + \} = 1$ (11)

(2) 马尔科夫链定义

 \begin{aligned} & P\left\{ \begin{gathered} X(n + 1) = j\;|\;X(0) = \mathop i\nolimits_0 ,X(1) = \mathop i\nolimits_1 , \cdots , X(n) = \mathop i\nolimits_n \\ \end{gathered} \right\} \\ & = P\left\{ {X(n + 1) = j\;|\;X(n) = \mathop i\nolimits_n } \right\} \\ \end{aligned} (12)

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

3 问题求解

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

4 结束语

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

 [1] 周建勋. 环保机械企业客户关系管理营销策略分析. 劳动保障世界, 2016(15): 51-51, 54. DOI:10.3969/j.issn.1007-7243.2016.15.034. [2] Li YZ, Lim A, Rodrigues B. Manpower allocation with time windows and job‐teaming constraints. Naval Research Logistics, 2005, 52(4): 302-311. DOI:10.1002/nav.20075. [3] Kovacs AA, Parragh SN, Doerner KF, et al. Adaptive large neighborhood search for service technician routing and scheduling problems. Journal of Scheduling, 2012, 15(5): 579-600. DOI:10.1007/s10951-011-0246-9. [4] Dohn A, Kolind E, Clausen J. The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach. Computers & Operations Research, 2009, 36(4): 1145-1157. DOI:10.1016/j.cor.2007.12.011. [5] 江俊杰, 王丽亚. 基于遗传算法的带服务匹配的现场产品服务调度. 计算机集成制造系统, 2012, 18(11): 2573-2577. DOI:10.13196/j.cims.2012.11.221.jiangjj.016. [6] 吴斌, 郭晶晶. 基于人工蜂群算法的现场服务调度问题. 科学技术与工程, 2018, 18(13): 111-116. DOI:10.3969/j.issn.1671-1815.2018.13.018 [7] 谈文芳, 赵强, 余胜阳, 等. 改进粒子群优化算法求解任务指派问题. 计算机应用, 2007, 27(12): 2892-2895. [8] 王庆. 知识型企业知识员工任务指派及调度决策问题研究[博士学位论文]. 天津: 天津大学, 2006. [9] Pillac V, Guéret C, Medaglia AL. A parallel matheuristic for the technician routing and scheduling problem. Optimization Letters, 2013, 7(7): 1525-1535. DOI:10.1007/s11590-012-0567-4. [10] 曹永荣, 韩传峰. 售后现场服务排队近似M/G/m模型仿真. 工业工程与管理, 2009, 14(5): 103-107. DOI:10.3969/j.issn.1007-5429.2009.05.019. [11] 都柄晓, 赵勇, 陈利虎, 等. 基于三分图的非共面卫星分布式加注任务规划. 中国空间科学技术, 2015, 35(1): 58-65. DOI:10.3780/j.issn.1000-758X.2015.01.008. [12] Burkard RE, Rudolf R, Woeginger GJ. Three-dimensional axial assignment problems with decomposable cost coefficients. Discrete Applied Mathematics, 1996, 65(1-3): 123-139. DOI:10.1016/0166-218X(95)00031-L [13] Aiex RM, Resende MGC, Pardalos PM, et al. GRASP with path relinking for three-index assignment. Informs Journal on Computing, 2005, 17(2): 224-247. DOI:10.1287/ijoc.1030.0059 [14] 张树威. 面向三次分配问题的高效启发式算法设计[硕士学位论文]. 大连: 大连理工大学, 2016. [15] Eiben AE, Aarts EHL, van Hee KM. Global convergence of genetic algorithms: A Markov chain analysis. Schwefel HP, Männer R. Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 1991. [16] 周蓉. 装卸一体化车辆路径问题优化模型及算法研究[博士学位论文]. 合肥: 合肥工业大学, 2016. [17] 汪民乐. 遗传算法的收敛性研究. 计算技术与自动化, 2015, 34(1): 58-62. DOI:10.16339/j.cnki.jsjsyzdh.2015.01.014.