第17卷第1期 智能系统学报 Vol.17 No.1 2022年1月 CAAI Transactions on Intelligent Systems Jan.2022 D0:10.11992/tis.202108027 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20211224.1327.004html 一种面向维修资源配送调度的遗传-烟花混合算法 李猛，和伟辉2，毛攀登，齐小刚3，刘立芳 (1.西安电子科技大学计算机学院，陕西西安710071；2.西安卫星测控中心，陕西西安710049,3.西安电子科 技大学数学与统计学院，陕西西安710071) 摘要：为碱轻资源供应不及时对维修活动顺利开展的影响，本文针对配送式供应保障，基于带时间窗的多配 送中心车辆路径规划问题提出了一种半开放式的协同配送调度模型，使得多个资源库存中心之间达成了协同 合作与互相保障，从而减少了资源的供应时长和调度成本，提高了全局调度效率。为高效地求解该模型，本文 提出了一种遗传-烟花混合算法，混合算法在经典遗传算法的基础上引入了烟花算法的爆炸算子以增加种群优 秀个体的数量，丰富种群基因的多样性，从而提高算法的寻优能力。通过仿真实验对比，证明了爆炸算子对遗 传算法容易“早熟”的缺点有所改善，且混合算法具有更高的求解效率。 关键词：维修资源：配送调度；遗传算法：烟花算法；车辆路径；多配送中心：资源调度：时间窗口 中图分类号：TP391 文献标志码：A 文章编号：1673-4785(2022)01-0088-10 中文引用格式：李猛，和伟辉，毛攀登，等.一种面向维修资源配送调度的遗传-烟花混合算法.智能系统学报，2022,17(1)： 88-97. 英文引用格式：LI Meng,HE Weihui,MAO Pandeng,.etal.A genetic-.firework hybrid algorithm oriented to maintenance resource distribution scheduling J.CAAI transactions on intelligent systems,2022,17(1):88-97. A genetic-firework hybrid algorithm oriented to maintenance resource distribution scheduling LI Meng',HE Weihui',MAO Pandeng',QI Xiaogang',LIU Lifang' (1.School of Computer Science and Technology,Xidian University,Xi'an 710071,China;2.Xi'an Satellite Control Center,Xi'an 710049,China:3.School of Mathematics and Statistics,Xidian University,Xi'an 710071,China) Abstract:In order to alleviate the impact of belated supply of maintenance resources on smooth maintenance activities, in this paper,a semi-open collaborative resource distribution scheduling model is established based on the multiple dis- tribution centers'vehicle routing problem (VRP)with time-windows to achieve collaboration and mutual guarantee among multiple depots.In this way,the delivery time and the scheduling cost are reduced and the overall resource sup- ply efficiency is improved.In order to efficiently solve the model,this paper proposes a genetic-firework hybrid al- gorithm,which introduces the explosion operator of the firework algorithm into the classical genetic algorithm to in- crease the amount of good individuals and the diversity of the population,so as to improve its optimization capacity. And through comparison of simulative experiments,it is proved that the hybrid algorithm has higher solving efficiency and that the introduction of explosion operators can solve the problem that genetic algorithm is easy to converge. Keywords:maintenance resources;distribution scheduling;genetic algorithm;fireworks algorithm;VRP;multi-distri- bution center;resource scheduling:time window 自主维修保障模式是未来装备维修保障的发 展方向山，但我军现有维修保障体系与自主维修 收稿日期：2021-08-26.网络出版日期：2021-12-27. 保障模式还存在较大的差距，现行军队体制中各 基金项目：国家自然科学基金项目(61877067)：装备预研领域 军区、各兵种以及各部队单位之间的维修资源的 基金项目(80904010301). 通信作者：刘立芳.E-mail:lhiu@xidian.edu.cn 调度中存在很多不合理现象，这对我军装备维修
DOI: 10.11992/tis.202108027 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20211224.1327.004.html. 一种面向维修资源配送调度的遗传–烟花混合算法 李猛1 ，和伟辉2 ，毛攀登1 ，齐小刚3 ，刘立芳1 （1. 西安电子科技大学 计算机学院, 陕西 西安 710071; 2. 西安卫星测控中心, 陕西 西安 710049; 3. 西安电子科 技大学 数学与统计学院, 陕西 西安 710071） 摘 要：为减轻资源供应不及时对维修活动顺利开展的影响，本文针对配送式供应保障，基于带时间窗的多配 送中心车辆路径规划问题提出了一种半开放式的协同配送调度模型，使得多个资源库存中心之间达成了协同 合作与互相保障，从而减少了资源的供应时长和调度成本，提高了全局调度效率。为高效地求解该模型，本文 提出了一种遗传–烟花混合算法，混合算法在经典遗传算法的基础上引入了烟花算法的爆炸算子以增加种群优 秀个体的数量，丰富种群基因的多样性，从而提高算法的寻优能力。通过仿真实验对比，证明了爆炸算子对遗 传算法容易“早熟”的缺点有所改善，且混合算法具有更高的求解效率。 关键词：维修资源；配送调度；遗传算法；烟花算法；车辆路径；多配送中心；资源调度；时间窗口 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2022)01−0088−10 中文引用格式：李猛, 和伟辉, 毛攀登, 等. 一种面向维修资源配送调度的遗传–烟花混合算法 [J]. 智能系统学报, 2022, 17(1): 88–97. 英文引用格式：LI Meng, HE Weihui, MAO Pandeng, et al. A genetic-firework hybrid algorithm oriented to maintenance resource distribution scheduling[J]. CAAI transactions on intelligent systems, 2022, 17(1): 88–97. A genetic-firework hybrid algorithm oriented to maintenance resource distribution scheduling LI Meng1 ，HE Weihui2 ，MAO Pandeng1 ，QI Xiaogang3 ，LIU Lifang1 (1. School of Computer Science and Technology, Xidian University, Xi’an 710071, China; 2. Xi’an Satellite Control Center, Xi’an 710049, China; 3. School of Mathematics and Statistics, Xidian University, Xi’an 710071, China) Abstract: In order to alleviate the impact of belated supply of maintenance resources on smooth maintenance activities, in this paper, a semi-open collaborative resource distribution scheduling model is established based on the multiple distribution centers ’ vehicle routing problem (VRP) with time-windows to achieve collaboration and mutual guarantee among multiple depots. In this way, the delivery time and the scheduling cost are reduced and the overall resource supply efficiency is improved. In order to efficiently solve the model, this paper proposes a genetic-firework hybrid algorithm, which introduces the explosion operator of the firework algorithm into the classical genetic algorithm to increase the amount of good individuals and the diversity of the population, so as to improve its optimization capacity. And through comparison of simulative experiments, it is proved that the hybrid algorithm has higher solving efficiency and that the introduction of explosion operators can solve the problem that genetic algorithm is easy to converge. Keywords: maintenance resources; distribution scheduling; genetic algorithm; fireworks algorithm; VRP; multi-distribution center; resource scheduling; time window 自主维修保障模式是未来装备维修保障的发 展方向[1] ，但我军现有维修保障体系与自主维修 保障模式还存在较大的差距，现行军队体制中各 军区、各兵种以及各部队单位之间的维修资源的 调度中存在很多不合理现象，这对我军装备维修 收稿日期：2021−08−26. 网络出版日期：2021−12−27. 基金项目：国家自然科学基金项目 (61877067)；装备预研领域 基金项目 (80904010301). 通信作者：刘立芳. E-mail：lfliu@xidian.edu.cn. 第 17 卷第 1 期 智 能 系 统 学 报 Vol.17 No.1 2022 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2022
·89· 李猛，等：一种面向维修资源配送调度的遗传-烟花混合算法 第1期 保障的能力与速度都造成了不利的影响。而资 间段(e,)之内将资源送达需求地点，需求地在这 源供应的敏捷性会直接影响到维修保障的效率， 个时间段之外将拒绝接收资源，其中P)为惩罚函 我军自主维修保障研究中急需解决的问题之一就 数，在硬时间窗之外的惩罚值M是一个很大的值。 是如何根据设备健康管理(prognostics health man- 图2(b)表示软时间窗：配送中各种突发情况可能 agement,PHM)系统的预测信息，联合多个资源库 导致配送车辆无法在规定时间内到达，但需求地 存中心，制定合理高效的配送调度方案，对多 点对此可以接受，不过需要按照一定规则处以一定 个部队维修基地进行快速可靠的资源供应保障。 的惩罚，图2(b)即一种可能的惩罚函数。图2(c) 在现代化自主维修保障系统中，对维修资源 将硬、软两种时间窗相结合，形成了混合型时间 多采用配送式供应保障模式，将库存成本高的维 窗：在规定的时间段(e,)之内将资源送达会直接 修物资实行统一存储与管理，以缩短军需物资冗 接受，在规定时间段之外的一个较小的区间内送 长的供应链，实现对各级部队单位的直达式供应。 达，如(a,e)或（亿，b),则在加以一定惩罚后接受维修 其主要核心是根据PHM提供的预测信息，计算 资源，但在(a,b)之外将不再接受资源的供应。 具体的资源需求，确定保障资源的配送时间，然 -·实物流·信息流 后通过合理的供应路线设计，控制资源的调度成 资源需求分析 本，从而获得全局最优的资源保障渠道。 上级配送基地 目前，对配送式资源供应保障模式的研究涉 维修物资筹措 市场采购 及交通运输、供应链优化以及物流管理等领域， 军工厂生产 并且在时间上存在一定的约束，因此属于带时间 窗的多站点车辆路径问题问题(multi-depot vehicle 资源配送点1→ routing problem with time-windows,MDVRPTW). 供应调度控 库存与配送中心 资源配送点2 过去的几十年间，国内外的学者已对经典RCPSP 资源配送点n十 (resource-constrained project scheduling problem) 中 型及其求解算法进行了深人的研究，由于大规模 资源需求点1· 的调度-为NP-hard问题，目前对MDVRPTW问 资源需求地点 资源需求点2· 题的研究多集中在启发式算法的优化上®，本文 资源需求点m 将配送中心设为半开放式，然后在遗传算法和烟 调度方案评估 花算法的基础上，提出了一种混合算法，充分结 合了两种算法在全局搜索和局部搜索的优点，具 图1配送式维修资源供应 Fig.1 Distribution type maintenance resource supply 有更高的搜索效率，可以在短时间内得到更优的 调度方案。 P(t) P( P() 1问题描述 1.1配送式资源供应 自主维修保障中为减小高技术装备维修资源 的库存成本，资源主要在库存配送中心集中 (a)硬时间窗 (b)软时间窗(c)混合时间窗 存储，采用如图1所示的配送式供应模式：各级维 图2时间窗分类 修单位计划开展维修活动时，需向库存配送中心 Fig.2 Time window classification 提出具体的资源需求，调度决策者会根据全局资 2)车辆使用性约束 源的分布情况，在满足需求数量和抵达时间的约 车辆是维修资源供应过程中调度的主要执行 束条件下，将各种资源供应至需求地点。 者，对于车辆本身的许多固有属性，常常存在一 1.2约束条件 些硬性的约束，具体如下： 1)时间约束 ①承载约束 供应调度中的时间有效性约束一般采用时间 每辆配送车辆的运载能力都是有限的，在配 窗口描述，根据决策者对供应时间准确性和供应 送的过程中，通常不允许实际的装载量超过车辆 成本之间的偏好，可以分为如图2所示的3种时 的承载限制，承载限制一般考虑为车辆的最大承 间窗。图2(a)表示硬时间窗：车辆必须在规定时 重重量或车辆的最大资源容纳数量
保障的能力与速度都造成了不利的影响[2]。而资 源供应的敏捷性会直接影响到维修保障的效率， 我军自主维修保障研究中急需解决的问题之一就 是如何根据设备健康管理 (prognostics health management, PHM) 系统的预测信息，联合多个资源库 存中心，制定合理高效的配送调度方案，对多 个部队维修基地进行快速可靠的资源供应保障。 在现代化自主维修保障系统中，对维修资源 多采用配送式供应保障模式，将库存成本高的维 修物资实行统一存储与管理，以缩短军需物资冗 长的供应链，实现对各级部队单位的直达式供应[3]。 其主要核心是根据 PHM 提供的预测信息，计算 具体的资源需求，确定保障资源的配送时间，然 后通过合理的供应路线设计，控制资源的调度成 本，从而获得全局最优的资源保障渠道。 目前，对配送式资源供应保障模式的研究涉 及交通运输、供应链优化以及物流管理等领域， 并且在时间上存在一定的约束，因此属于带时间 窗的多站点车辆路径问题问题 (multi-depot vehicle routing problem with time-windows, MDVRPTW)。 过去的几十年间，国内外的学者已对经典 RCPSP (resource-constrained project scheduling problem) 模 型及其求解算法进行了深入的研究,由于大规模 的调度[4-7] 为 NP-hard 问题，目前对 MDVRPTW 问 题的研究多集中在启发式算法的优化上[8-16] ，本文 将配送中心设为半开放式，然后在遗传算法和烟 花算法的基础上，提出了一种混合算法，充分结 合了两种算法在全局搜索和局部搜索的优点，具 有更高的搜索效率，可以在短时间内得到更优的 调度方案。 1 问题描述 1.1 配送式资源供应 自主维修保障中为减小高技术装备维修资源 的库存成本[17-19] ，资源主要在库存配送中心集中 存储，采用如图 1 所示的配送式供应模式：各级维 修单位计划开展维修活动时，需向库存配送中心 提出具体的资源需求，调度决策者会根据全局资 源的分布情况，在满足需求数量和抵达时间的约 束条件下，将各种资源供应至需求地点。 1.2 约束条件 1）时间约束 供应调度中的时间有效性约束一般采用时间 窗口描述，根据决策者对供应时间准确性和供应 成本之间的偏好，可以分为如图 2 所示的 3 种时 间窗。图 2(a) 表示硬时间窗：车辆必须在规定时 (e,l) P(t) (e,l) (a, e) (l,b) (a,b) 间段 之内将资源送达需求地点，需求地在这 个时间段之外将拒绝接收资源，其中 为惩罚函 数，在硬时间窗之外的惩罚值 M 是一个很大的值。 图 2(b) 表示软时间窗：配送中各种突发情况可能 导致配送车辆无法在规定时间内到达，但需求地 点对此可以接受，不过需要按照一定规则处以一定 的惩罚，图 2(b) 即一种可能的惩罚函数。图 2(c) 将硬、软两种时间窗相结合，形成了混合型时间 窗：在规定的时间段 之内将资源送达会直接 接受，在规定时间段之外的一个较小的区间内送 达，如 或 ，则在加以一定惩罚后接受维修 资源，但在 之外将不再接受资源的供应。 供 应 调 度 控 制 中 心 资源需求分析 维修物资筹措 库存与配送中心 资源需求地点 上级配送基地 市场采购 军工厂生产 资源配送点 1 资源配送点 2 资源配送点 n 资源需求点 1 资源需求点 2 资源需求点 m 调度方案评估 实物流 信息流 ... ... 图 1 配送式维修资源供应 Fig. 1 Distribution type maintenance resource supply M e l t e l t (a) 硬时间窗 (b) 软时间窗 (c) 混合时间窗 P (t) P (t) P (t) M e l t a b 图 2 时间窗分类 Fig. 2 Time window classification 2）车辆使用性约束 车辆是维修资源供应过程中调度的主要执行 者，对于车辆本身的许多固有属性，常常存在一 些硬性的约束，具体如下： ① 承载约束 每辆配送车辆的运载能力都是有限的，在配 送的过程中，通常不允许实际的装载量超过车辆 的承载限制，承载限制一般考虑为车辆的最大承 重重量或车辆的最大资源容纳数量。 ·89· 李猛，等：一种面向维修资源配送调度的遗传–烟花混合算法 第 1 期
第17卷 智能系统学报 ·90· ②行驶上限约束 会进行处罚，增加一定的供应成本； 车辆在行驶过程中会产生成本与损耗，如油 7)车辆在每个节点存在装卸货物的时间，称 耗、器械磨损、人员体力损耗等，若这些成本或损 为服务时间，服务时间在车辆到达后才能开始计 耗达到一定的阈值，则车辆须返回进行保养与休 时，服务结束后车辆才可以离开。 整。此外，考虑到配送任务的均衡性，应该禁止 由于配送中心以及需求地点位置的分散性， 超长配送路线的出现，需要对车辆设置行驶上 协同供应调度模型可以看作一个完全无向图 限，车辆必须在行驶时间或行驶路程到达行驶上 G=(VA),其中，V={1,Vw,VN41,Vw+M}为节点 限之前返回配送中心。 集，代表了配送中心或需求地点，其位置用二维 ③使用数量约束 坐标(XY)表示；A={v),y∈V,1≠为弧集， 实际配送中不可能存在无限多的配送车辆，因 代表了节点之间的距离长度。 此需要对每个配送中心的实际可用车辆数目加以 在节点集V中，C={c,c2,…,Cw}={1,2,…,w 限制，车辆动用数量必须小于当前空闲的车辆数。 代表N个需求地点，D={d,d2,…,dw}={vw1,Vw+2,… 1.3半开放配送中心 w+M}代表M个配送中心。在弧集A中，每个弧 基本的配送式供应四保障中一般要求车辆回 (,y)∈A代表两个节点之间的路径，与之对应的 到其出发的配送中心，这种模式下车辆使用率不 参数c代表两者之间的距离。 高，并且配送中心之间没有联系和互动，资源也无 对于每个需求节点，∈C,有着与其对应的资 法共享。基于此，本文研究半开方式的配送中心： 源需求量q,装卸服务时间s,以及供应时间窗口 车辆从配送中心a出发并完成配送任务后，可以 [e,,其中e是接受配送的最早开始时间，l,是接受 根据距离因素自行选择是否返回原配送中心a; 配送的最晚时间。 若选择不返回原配送中心a,而是另一个配送中 对于每个配送中心节点∈D,有着于其对应 心b,则配送中心b在该车辆返回后，拥有该车辆 的车辆数目Ka和车位数目P,在没有需求和配 的使用权，后续可以为该车辆安排配送中心b的 送服务时，配送中心的资源需求量和服务时间都 配送任务。此外，配送中心自己也可以作为一个需 为0，即4：=s=0。 求地点，从而可以实现配送中心之间的资源共享 每个配送中心的车辆集合表示为K={1,k2,…, 和互相保障，使得供应保障体系更加高效且可 k,其中L是车辆数目，车辆有其对应的负荷量 靠。由于配送中心的半开放性，本文引入了车位的 Q,最大工作时间T,动用成本C和单位距离行 概念，增加了如下两条约束原则：仅当配送中心拥 驶成本C。记车辆k到达节点i的时间为k,车辆 有的车辆数目小于配送中心车位数目时，才允许新 在节点i的服务开始时间为a,车辆的累计工作 的车辆返回该配送中心；车辆应选择距离路线末 时长为πo 端最近的，且具有多余停车位的配送中心返回。 由于采用了软时间窗进行建模，惩罚函数以 时间的线性函数的形式表示，因此模型引人了早 2数学模型 到单位时间惩罚成本C和迟到单位时间惩罚成 本C,以及提前、推迟到达节点i的时间差T和 考虑到计算的方便性以及仿真实验的可行 T。当车辆早于时间窗的开启时刻或晚于时间窗 性，模型采用如下基本假设： 1)资源数量充足，全局的维修资源库存能够 的关闭时刻到达时，会增加调度成本，增加的成 本等于对应的单位时间惩罚成本与时差的乘积。 满足全局的资源需求： 最后，引入了本文供应调度模型中最重要决 2)车辆由一个配送中心出发后返回到多个配 策变量x,它用于判断车辆k的行驶路线，若车 送中心中的一个，每辆车不得重复调度； 3)采用同类型的配送车辆，车辆与需求地点 辆k从节点i驶向节点j,则x=1;否则x=0。 之间为一对多的关系； 根据以上的模型描述与符号定义，可对资源 4)运输道路状况和车流量忽略不计，道路距离 协同供应调度模型进行如下的公式化归纳： 按直线距离计算，单位距离的行驶时间为单位时间； minCost=∑∑∑cu,Cm+∑ce+ kEK iEV jeV 5)每个配送中心存在固定数量的车位，可用 (1) 车位数不足时，车辆不能在该配送中心停靠； 22c+c 6)车辆到达需求地点的时间应在允许的时间 st∑∑w<IKl.HeD (2) 范围内波动，如果车辆在规定时间之外到达，则 kEK jEC
② 行驶上限约束 车辆在行驶过程中会产生成本与损耗，如油 耗、器械磨损、人员体力损耗等，若这些成本或损 耗达到一定的阈值，则车辆须返回进行保养与休 整。此外，考虑到配送任务的均衡性，应该禁止 超长配送路线的出现，需要对车辆设置行驶上 限，车辆必须在行驶时间或行驶路程到达行驶上 限之前返回配送中心。 ③ 使用数量约束 实际配送中不可能存在无限多的配送车辆，因 此需要对每个配送中心的实际可用车辆数目加以 限制，车辆动用数量必须小于当前空闲的车辆数。 1.3 半开放配送中心 基本的配送式供应[20] 保障中一般要求车辆回 到其出发的配送中心，这种模式下车辆使用率不 高，并且配送中心之间没有联系和互动，资源也无 法共享。基于此，本文研究半开方式的配送中心： 车辆从配送中心 a 出发并完成配送任务后，可以 根据距离因素自行选择是否返回原配送中心 a； 若选择不返回原配送中心 a，而是另一个配送中 心 b，则配送中心 b 在该车辆返回后，拥有该车辆 的使用权，后续可以为该车辆安排配送中心 b 的 配送任务。此外，配送中心自己也可以作为一个需 求地点，从而可以实现配送中心之间的资源共享 和互相保障，使得供应保障体系更加高效且可 靠。由于配送中心的半开放性，本文引入了车位的 概念，增加了如下两条约束原则：仅当配送中心拥 有的车辆数目小于配送中心车位数目时，才允许新 的车辆返回该配送中心；车辆应选择距离路线末 端最近的，且具有多余停车位的配送中心返回。 2 数学模型 考虑到计算的方便性以及仿真实验的可行 性，模型采用如下基本假设： 1）资源数量充足，全局的维修资源库存能够 满足全局的资源需求； 2）车辆由一个配送中心出发后返回到多个配 送中心中的一个，每辆车不得重复调度； 3) 采用同类型的配送车辆，车辆与需求地点 之间为一对多的关系； 4) 运输道路状况和车流量忽略不计，道路距离 按直线距离计算，单位距离的行驶时间为单位时间； 5) 每个配送中心存在固定数量的车位，可用 车位数不足时，车辆不能在该配送中心停靠； 6) 车辆到达需求地点的时间应在允许的时间 范围内波动，如果车辆在规定时间之外到达，则 会进行处罚，增加一定的供应成本； 7) 车辆在每个节点存在装卸货物的时间，称 为服务时间，服务时间在车辆到达后才能开始计 时，服务结束后车辆才可以离开。 G = (V,A) V = {v1,··· vN, vN+1,··· vN+M} (X,Y) A = {(vi , vj ) | vi , vj ∈ Vt ,l , j } 由于配送中心以及需求地点位置的分散性， 协同供应调度模型可以看作一个完全无向图 ，其中， 为节点 集，代表了配送中心或需求地点，其位置用二维 坐标 表示； 为弧集， 代表了节点之间的距离长度。 C = {c1, c2,··· , cN} = {v1, v2,··· , vN} D = {d1,d2,··· ,dM} = {vN+1, vN+2,··· , vN+M} (vi , vj) ∈ A c11 在节点集 V 中， 代表 N 个需求地点, 代表 M 个配送中心。在弧集 A 中，每个弧 代表两个节点之间的路径，与之对应的 参数 代表两者之间的距离。 vi ∈ C qi si [ei ,li] ei li 对于每个需求节点 ，有着与其对应的资 源需求量 ，装卸服务时间 ，以及供应时间窗口 ，其中 是接受配送的最早开始时间， 是接受 配送的最晚时间。 vi ∈ D |Kd| |Pd| qi = si = 0 对于每个配送中心节点 ，有着于其对应 的车辆数目 和车位数目 ，在没有需求和配 送服务时，配送中心的资源需求量和服务时间都 为 0，即 。 K = {k1, k2,··· , kL} Qk Tk C fix k C run k k aki πk 每个配送中心的车辆集合表示为 ，其中 L 是车辆数目，车辆有其对应的负荷量 ，最大工作时间 ，动用成本 和单位距离行 驶成本 。记车辆 k 到达节点 i 的时间为 ，车辆 在节点 i 的服务开始时间为 ，车辆的累计工作 时长为 。 C earl C lat T earl ki T lat ki 由于采用了软时间窗进行建模，惩罚函数以 时间的线性函数的形式表示，因此模型引入了早 到单位时间惩罚成本 和迟到单位时间惩罚成 本 ，以及提前、推迟到达节点 i 的时间差 和 。当车辆早于时间窗的开启时刻或晚于时间窗 的关闭时刻到达时，会增加调度成本，增加的成 本等于对应的单位时间惩罚成本与时差的乘积。 xki j xki j = 1 xki j = 0 最后，引入了本文供应调度模型中最重要决 策变量 ，它用于判断车辆 k 的行驶路线，若车 辆 k 从节点 i 驶向节点 j，则 ；否则 。 根据以上的模型描述与符号定义，可对资源 协同供应调度模型进行如下的公式化归纳： minCost = ∑ k∈K ∑ i∈V ∑ j∈V ci jxki jCk run + ∑ k∈K C fix k + ∑ k∈K ∑ i∈V (T earl ki C earl +T lat ki C lat) (1) s.t.∑ k∈K ∑ j∈C xkd j ⩽ |Kd|, ∀d ∈ D (2) 第 17 卷 智 能 系 统 学 报 ·90·
·91· 李猛，等：一种面向维修资源配送调度的遗传-烟花混合算法 第1期 VieC (3) 集中在启发式算法的创新上。 遗传算法(genetic algorithm,GA)2-2]是一种 Vk∈K (4) 经典的群智能算法，针对建立的资源供应调度模 型，本文提出了一种遗传-烟花混合算法为改善 226肉-1 HR∈C,k∈K (5) 遗传算法容易“早熟”的缺陷，引入了烟花算法42 2“ 中的爆炸操作，扩大了遗传算法的局部搜索范 Vk∈K (6) 围，从而加快了对最优解的搜索速度，提高了算 22如D (7) 法的求解性能，下面对该算法进行详细的介绍。 3.1染色体编解码 x(b+s:+c-a)=0,ij∈V,k∈K (8) 1)编码规则 bu≥a贴≥0，ieC,k∈K (9) 对于资源协同供应调度模型，代表模型可行 Vk∈K (10) 解的染色体应该含有资源配送中心信息、维修地 点信息、车辆使用信息、车辆的路径信息等。因 (11) 此，本文设计了如图3所示的编码方案，使用自然数 Yk∈K,d,deD 表示的二维向量，其中第一维向量为需求地点D xe{0,1,i,jeV,k∈K (12) 的全排列，其元素不能存在重复，而第二维向量为 ={0,其他 ei-au, 需求地点对应的配送中心D,其元素可以相同。 (13) 需求地点D -{8其他> (14) 157311281210491415613 1 32132313232233 其中：式(1)的目标函数为最小化调度总成本，等 配送中心D 式右边第1项对所有车辆的行驶成本求和，第 图3染色体编码方式示意 2项对所有车辆的固定成本求和，第3项计算总 Fig.3 Chromosome coding method 的时间成本；约束(2)要求从每个配送中心出发 2)解码规则 的车辆数量不超过可用车数：约束(3)确保每个 由于染色体编码使用了需求地的直接排列， 需求地仅被一辆车服务一次；约束(4)表示每辆车从 但却没有设置分割车辆信息的基因位置，因此需 一个配送中心，并在一个配送中心结束；约束(5) 在解码阶段对车辆路径进行具体的划分。为了最 确保了车辆k的行程路径上各个需求地点已连接； 大化车辆使用效率，应使用尽量少的车辆来完成 约束(6)表示车辆不能直接从配送中心ⅰ到配送 资源的配送，染色体解码被分为了如下两个步骤： 中心；约束(7)表示车辆数量返回每个配送中心 ①整体调度路径提取。根据配送中心的D, 的数量不超过配送中心的车位数量；约束(8)描 将同一配送中心对应的基因按照从左到右的顺序 述了节点的访问顺序，若车辆k直接从节点出发 依次提取，然后组合成为一条新的“子染色体”， i到节点j,则节点j的到达时间必须等于上个节 称为整体调度路径，该路径记录了该配送中心负 点的服务开始时间+服务时间+行驶时间；约束 责保障的所有需求地点的配送顺序。 (9)确保车辆k在节点i处的启动服务时间晚于或 ②车辆行驶路径划分。对于每一条整体调度 等于其到达间：约束(10)确保车辆服务路径上的 路径，根据各种约束条件，按照从左到右的顺序，将 需求总数量小于车辆负载：约束(11)确保车辆实 其需求地向量的元素依次加人一个有序集合，该有 际工作时长（终点配送中心的到达时间-起始配 序集合称为车辆行驶路径。在加入新需求地时， 送中心离开时间)小于最大工作时长；约束(12) 若违反了模型的约束条件（如车辆运载能力、行驶 表示决策变量的范围：约束(13)和约束(14)分别 时间等)，则设置当前车辆路径终点为最近的配 计算车辆k提前、推迟到达需求地点i的时间差。 送中心，然后另起一个新的有序集合，继续为剩 3遗传一烟花混合算法 余的需求地划分车辆路径，直至当前整体调度路 径中所有需求地都归入了对应的车辆行驶路径。 供应调度问题是经典的NP-hard问题，精确 3.2算法基本要素 算法可以求得问题的最优解，但其时间复杂度却 1)初始种群 不适用大规模问题的求解，近年来的相关研究多 根据上述编码方案，按照给定的配送中心和
∑ k∈K ∑ j∈V xki j = ∑ k∈K ∑ j∈V xk ji = 1, ∀i ∈ C (3) ∑ d∈D ∑ j∈C xkd j = ∑ d∈D ∑ i∈C xkid ⩽ 1, ∀k ∈ K (4) ∑ i∈R ∑ j∈R xki j ⩽ |R| −1, ∀R ⊆ C, k ∈ K (5) ∑ i∈D ∑ j∈D xki j = 0, ∀k ∈ K (6) ∑ k∈K ∑ i∈C xkid ⩽ |Pd|,∀d ∈ D (7) xki j( bki + si +ci j −ak j) = 0, ∀i, j ∈ V, k ∈ K (8) bki ⩾ aki ⩾ 0, ∀i ∈ C, k ∈ K (9) ∑ i∈V ∑ j∈C qjxki j ⩽ Qk , ∀k ∈ K (10) πk = ∑ i∈C xkid (bki + si +cid)− ∑ i∈C xkd′ i(aki −cid′ ) ⩽ Tk , ∀k ∈ K,d,d ′ ∈ D (11) xki j ∈ {0,1}, ∀i, j ∈ V, k ∈ K (12) T earl ki = { ei −aki, aki li 0，其他 (14) 其中：式（1）的目标函数为最小化调度总成本，等 式右边第 1 项对所有车辆的行驶成本求和，第 2 项对所有车辆的固定成本求和，第 3 项计算总 的时间成本；约束（2）要求从每个配送中心出发 的车辆数量不超过可用车数；约束（3）确保每个 需求地仅被一辆车服务一次；约束（4）表示每辆车从 一个配送中心，并在一个配送中心结束；约束（5） 确保了车辆 k 的行程路径上各个需求地点已连接； 约束（6）表示车辆不能直接从配送中心 i 到配送 中心 j；约束（7）表示车辆数量返回每个配送中心 的数量不超过配送中心的车位数量；约束（8）描 述了节点的访问顺序，若车辆 k 直接从节点出发 i 到节点 j，则节点 j 的到达时间必须等于上个节 点的服务开始时间+服务时间+行驶时间；约束 （9）确保车辆 k 在节点 i 处的启动服务时间晚于或 等于其到达间；约束（10）确保车辆服务路径上的 需求总数量小于车辆负载；约束（11）确保车辆实 际工作时长（终点配送中心的到达时间–起始配 送中心离开时间）小于最大工作时长；约束（12） 表示决策变量的范围；约束（13）和约束（14）分别 计算车辆 k 提前、推迟到达需求地点 i 的时间差。 3 遗传–烟花混合算法 供应调度问题是经典的 NP-hard 问题，精确 算法可以求得问题的最优解，但其时间复杂度却 不适用大规模问题的求解，近年来的相关研究多 集中在启发式算法的创新上。 遗传算法 (genetic algorithm, GA)[21-23] 是一种 经典的群智能算法，针对建立的资源供应调度模 型，本文提出了一种遗传–烟花混合算法为改善 遗传算法容易“早熟”的缺陷，引入了烟花算法[24-25] 中的爆炸操作，扩大了遗传算法的局部搜索范 围，从而加快了对最优解的搜索速度，提高了算 法的求解性能，下面对该算法进行详细的介绍。 3.1 染色体编解码 1）编码规则 对于资源协同供应调度模型，代表模型可行 解的染色体应该含有资源配送中心信息、维修地 点信息、车辆使用信息、车辆的路径信息等。因 此，本文设计了如图 3 所示的编码方案，使用自然数 表示的二维向量，其中第一维向量为需求地点 ID 的全排列，其元素不能存在重复，而第二维向量为 需求地点对应的配送中心 ID，其元素可以相同。 1 5 7 3 11 2 8 12 10 4 9 14 15 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 3 3 需求地点 ID 配送中心 ID 图 3 染色体编码方式示意 Fig. 3 Chromosome coding method 2）解码规则 由于染色体编码使用了需求地的直接排列， 但却没有设置分割车辆信息的基因位置，因此需 在解码阶段对车辆路径进行具体的划分。为了最 大化车辆使用效率，应使用尽量少的车辆来完成 资源的配送，染色体解码被分为了如下两个步骤： ① 整体调度路径提取。根据配送中心的 ID， 将同一配送中心对应的基因按照从左到右的顺序 依次提取，然后组合成为一条新的“子染色体”， 称为整体调度路径，该路径记录了该配送中心负 责保障的所有需求地点的配送顺序。 ② 车辆行驶路径划分。对于每一条整体调度 路径，根据各种约束条件，按照从左到右的顺序，将 其需求地向量的元素依次加入一个有序集合，该有 序集合称为车辆行驶路径。在加入新需求地时， 若违反了模型的约束条件（如车辆运载能力、行驶 时间等），则设置当前车辆路径终点为最近的配 送中心，然后另起一个新的有序集合，继续为剩 余的需求地划分车辆路径，直至当前整体调度路 径中所有需求地都归入了对应的车辆行驶路径。 3.2 算法基本要素 1）初始种群 根据上述编码方案，按照给定的配送中心和 ·91· 李猛，等：一种面向维修资源配送调度的遗传–烟花混合算法 第 1 期
第17卷 智能系统学报 ·92· 需求地信息，随机产生固定数量(Popsize)的染色 在11-7、1-(2-12)-10、8-6、4-(9)-144个对应关系； 体，即可作为混合算法的初始种群。Popsize的大 插人点 插入点 小往往决定了算法的搜索性能，一般需根据模型 输入数据的规模进行调整，从而保证种群基因的 父代182996 1321323T3232213 多样性。 父代28 2)适应度函数 对于本文的保障资源供应调度模型，其优化 交叉互换 建立映射关系 预备 1573☒K822941415613 目标是使维修资源供应调度方案的总成本最小， 子代1 132112133212213 28i21049 算法的目标函数即是调度总成本，因此适应度函 预备 31☐413M4281294915085 数可用倒数函数形式表示，即 子代2 31123323I3233212 716212914 冲突检测与修复 fit(i)=1/Cost(i) (15) 式中：Cost()为种群中个体i的目标函数值；it()即 子代17308229446国 132132313232213 个体i的染色体所对应的适应度，t()越大，被选 则的几率就越大。 子代24372612149s085 312312133213212 3)停止准则 图4交叉操作流程示意 对于本文提出的混合算法，其主体结构依旧 Fig.4 Cross-operation flow diagram 是遗传算法，只需设置一个迭代次数的上限Max- ③对交换基因片段后产生的预备子代进行冲 gen,当算法的迭代次数达到该阈值时候，结束程 突检测与修复。以预备子代1为例，交换之后存 序，输出当前的满意解即可。 在重复基因7、1、6、14。而通过映射关系可知， 4)选择操作 这4个重复基因依次与基因11、10、8、14匹配， 首先通过精英保留策略直接保留最优秀的个 按照该映射规则进行替换，预备子代1中的基因 体：根据适应度的大小对当前种群中的个体降序 7、1、6、14被替换为了基因11、10、8、14，从而得 排列，将一定数量的优秀个体直接放入子代种 到了无重复基因的子代1。预备子代2也按照同 群。对于剩下的个体采用轮盘赌策略进行选择， 样的方法根据映射关系进行修复即可。 具体流程为：先通过式(16)计算保留概率P(x,然 编码第二维向量为配送中心信息，不具有唯 后对所有个体的保留概率累加，得到个体的累计 性，允许元素的重复出现。因此本文采用简单 概率分布刻度区间，最后在(0,1]区间内产生 的两点交叉策略，将父代中虚线所指的配送中心 Gap×Popsize个随机数，根据随机数掉落的刻度区 编码片段两两交换即可，如图4中虚线所示。 间确定被选中的染色体。 6)变异操作 fit(x;) P(xi)= (16) 混合算法中变异操作采用简单的两点交换策 Popsize fit(x;) 略，在种群中以一定变异概率随机选择一定数量 的个体进行基因交换，具体步骤十分简单：对选 式中：it(x)表示个体x的适应度；P(x)表示个体 中的个体，随机选择其染色体上的两个基因作为 x的保留概率。 交换点，然后交换它们的位置即可。 5)交叉操作 7)爆炸算子设计 本文对染色体编码中的两个维度采用了不同 在烟花算法中爆炸操作即为一次邻域搜索过 的交叉方法。第一维编码向量是需求地编码的全 程，且适应度值较好的烟花在较小的范围内产生 排列，具有唯一性，简单的交叉方法非常容易产 较多的火花粒子，称为“局部烟花”，适应度值较 生不可行解，因此本文采用的交叉方法为部分匹 差的烟花在较大的范围内产生较少的火花粒子， 配交叉法(partially matching crossover,PMX)。以 称为“全局烟花”。遗传算法种群中适应度最好的 图4为例，其具体步骤如下： 个体含有更为优秀的遗传信息，在很大程度上能 ①随机选择一对染色体（父代1和父代2）， 够引导算法的收敛方向，因此可以看作一个产生 在染色体上再随机选择两个插入点，作为交叉片 “局部烟花”的最佳爆炸点：而适应度最差的个体 段的起止位置： 由于其包含了和优秀个体差异程度最大的遗传信 ②根据插入点的位置，交换两个父代中的基 息，能够使得种群的遗传信息更加多样化，因此 因片段，并根据交换的具体基因建立一个两两映 可以看作产生“全局烟花”的一个较好爆炸点。 射关系集合。例如，在图4交换的基因片段中，存 由于本文染色体中需求地和配送中心两个向
需求地信息，随机产生固定数量 (Popsize) 的染色 体，即可作为混合算法的初始种群。Popsize 的大 小往往决定了算法的搜索性能，一般需根据模型 输入数据的规模进行调整，从而保证种群基因的 多样性。 2）适应度函数 对于本文的保障资源供应调度模型，其优化 目标是使维修资源供应调度方案的总成本最小， 算法的目标函数即是调度总成本，因此适应度函 数可用倒数函数形式表示，即 fit(i) = 1/Cost(i) (15) Cost(i) fit(i) fit(i) 式中： 为种群中个体 i 的目标函数值； 即 个体 i 的染色体所对应的适应度， 越大，被选 则的几率就越大。 3）停止准则 对于本文提出的混合算法，其主体结构依旧 是遗传算法，只需设置一个迭代次数的上限 Maxgen，当算法的迭代次数达到该阈值时候，结束程 序，输出当前的满意解即可。 4）选择操作 P(xi) Gap×Popsize 首先通过精英保留策略直接保留最优秀的个 体：根据适应度的大小对当前种群中的个体降序 排列，将一定数量的优秀个体直接放入子代种 群。对于剩下的个体采用轮盘赌策略进行选择， 具体流程为：先通过式（16）计算保留概率 ，然 后对所有个体的保留概率累加，得到个体的累计 概率分布刻度区间，最后在 (0， 1] 区间内产生 个随机数，根据随机数掉落的刻度区 间确定被选中的染色体。 P(xi) = fit(xj) Popsize ∑ j=1 fit(xj) (16) fit(xi) xi P(xi) xi 式中： 表示个体 的适应度； 表示个体 的保留概率。 5）交叉操作 本文对染色体编码中的两个维度采用了不同 的交叉方法。第一维编码向量是需求地编码的全 排列，具有唯一性，简单的交叉方法非常容易产 生不可行解，因此本文采用的交叉方法为部分匹 配交叉法 (partially matching crossover，PMX)。以 图 4 为例，其具体步骤如下： ①随机选择一对染色体（父代 1 和父代 2）， 在染色体上再随机选择两个插入点，作为交叉片 段的起止位置； ②根据插入点的位置，交换两个父代中的基 因片段，并根据交换的具体基因建立一个两两映 射关系集合。例如，在图 4 交换的基因片段中，存 在 11-7、1-（2-12）-10、8-6、4-（9）-14 4 个对应关系； 1 5 7 3 11 2 8 1210 4 9 1415 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 父代 1 父代 2 3 11 4 13 7 1 6 2 12 9 141510 8 5 3 1 2 3 1 2 1 3 3 2 1 3 2 1 2 1 5 7 3 1415 6 13 1 3 2 1 1 2 1 3 3 2 1 2 2 1 3 3 11 4 13 15 8 5 3 1 2 3 3 2 3 1 3 2 3 3 2 1 2 7 1 6 2 12 9 14 11 2 8 1210 4 9 1 5 7 3 1415 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 子代 1 3 11 4 13 1510 8 5 3 1 2 3 1 2 1 3 3 2 1 3 2 1 2 子代 2 1110 8 2 12 9 4 7 2 6 12 1 14 9 11 2 8 1210 4 9 7 1 6 2 12 9 14 交叉互换 建立映射关系 插入点 插入点 10 预备 子代 1 预备 子代 2 冲突检测与修复 图 4 交叉操作流程示意 Fig. 4 Cross-operation flow diagram ③对交换基因片段后产生的预备子代进行冲 突检测与修复。以预备子代 1 为例，交换之后存 在重复基因 7、1、6、14。而通过映射关系可知， 这 4 个重复基因依次与基因 11、10、8、14 匹配， 按照该映射规则进行替换，预备子代 1 中的基因 7、1、6、14 被替换为了基因 11、10、8、14，从而得 到了无重复基因的子代 1。预备子代 2 也按照同 样的方法根据映射关系进行修复即可。 编码第二维向量为配送中心信息，不具有唯 一性，允许元素的重复出现。因此本文采用简单 的两点交叉策略，将父代中虚线所指的配送中心 编码片段两两交换即可，如图 4 中虚线所示。 6）变异操作 混合算法中变异操作采用简单的两点交换策 略，在种群中以一定变异概率随机选择一定数量 的个体进行基因交换，具体步骤十分简单：对选 中的个体，随机选择其染色体上的两个基因作为 交换点，然后交换它们的位置即可。 7）爆炸算子设计 在烟花算法中爆炸操作即为一次邻域搜索过 程，且适应度值较好的烟花在较小的范围内产生 较多的火花粒子，称为“局部烟花”，适应度值较 差的烟花在较大的范围内产生较少的火花粒子， 称为“全局烟花”。遗传算法种群中适应度最好的 个体含有更为优秀的遗传信息，在很大程度上能 够引导算法的收敛方向，因此可以看作一个产生 “局部烟花”的最佳爆炸点；而适应度最差的个体 由于其包含了和优秀个体差异程度最大的遗传信 息，能够使得种群的遗传信息更加多样化，因此 可以看作产生“全局烟花”的一个较好爆炸点。 由于本文染色体中需求地和配送中心两个向 第 17 卷 智 能 系 统 学 报 ·92·
·93· 李猛，等：一种面向维修资源配送调度的遗传-烟花混合算法 第1期 量的生成规则不同，因此爆炸算子也需要对不同 R;=AX fit(x)-fitmin (18) 维度的向量分别进行操作，才能保证生成新个体 的正确性，具体的操作分为图5所示的4种策 ∑it(x)--filn） 略。对于第一维的需求地向量，爆炸算子采用一种 随机混合方案，对每一次的爆炸操作，随机采用单点 式中：Sum为预设的爆炸火花数；A为爆炸半径的 交换、插入与反转3种策略中的一种执行，如图5 基值；t(x)为个体x的适应度；fita与ftmm分别为 中(a)、(b)、(c)所示；而对于第二维的配送中心向 进行爆炸操作的个体中的最大适应度值与最小适 量，由于无需考虑冲突检测，在上述3种策略之 应度值：N为进行爆炸操作的个体的数量。 外，还加入了多点变异策略，如图5(d)。 爆炸半径规定了爆炸操作时进行邻域搜索的 范围，对于本文的自然数编码方案，爆炸半径可 交换点 交换点 以对应为爆炸操作的最大执行次数，即对于烟花 157311282104914563 i,需要随机进行1~R次爆炸操作才可以得到一个 132132313232213 新的火花。 由于在遗传算法阶段进行了相关变异操作， 15792812104314563 为避免不必要的运算，本文爆炸算子没有考虑高 132332313212213 斯变异火花。由于爆炸数量根据个体的适应度计 (a)单点交换 算的，具有一定的不确定性，因此本文对S:设置了 插人点 插人入基因 上下界： 15731128121049145613 Smax:SiS max 132132313232213 Si Smin<Si<Sma (19) 式中：Sax与S分别为的预先设置的最大、最小 15793128121041415613 132313231322213 爆炸火花数量。 (b)单点插入 最后为了保证种群规模不变，规定每次保留 反转点 反转点 S个火花作为爆炸算子产生的新个体，加入遗传 算法的种群中，进行混合算法的下一轮迭代。 157311281210491415613 132132313232213 3.3混合算法流程 混合算法的基本流程如图6所示，分为初始 化、遗传进化和爆炸优化3个阶段。 157941012821131415613 132323132312213 (开始 (c)反转 变异点1 变异点2 变异点3 初始化模型和算法中的各 项参数和变量 (结束 157311281210491415613 构建资源集合、需求地 输出最佳调度方案 132132313232213 点、配送中心及车辆集合 Y L 随机生成初代种群 是否达到终 止条件 15731128121043141563 132332113222213 采用PMX和简单交换对 将爆炸火花粒子加入子代 种群个体进行交叉操作 种群，进人下一轮迭代 (d多点变异 随机选择一定数量的个 图5爆炸算子示意 体，进行变异操作 经爆炸操作得到火花粒子 Fig.5 Flow chart of explosion operator 计算种群中每个个体的适 计算爆炸数量和爆炸半径 爆炸算子中的爆炸数量S:和爆炸半径R:的计 应度，并对其排序 + 算规则为 采用精英保留和轮盘赌选 选择子代种群中适应度最 fitmax-fit(xi) 择进入子代种群中的个体 好和最差的两个个体 S:=Sum· (17) ,(itax-fit(x》 图6遗传-烟花混合算法流程图 Fig.6 Flow chart of genetic-firework hybrid algorithm
量的生成规则不同，因此爆炸算子也需要对不同 维度的向量分别进行操作，才能保证生成新个体 的正确性，具体的操作分为图 5 所示的 4 种策 略。对于第一维的需求地向量，爆炸算子采用一种 随机混合方案，对每一次的爆炸操作，随机采用单点 交换、插入与反转 3 种策略中的一种执行，如图 5 中 (a)、(b)、(c) 所示；而对于第二维的配送中心向 量，由于无需考虑冲突检测，在上述 3 种策略之 外，还加入了多点变异策略，如图 5(d)。 插入点 插入基因 1 5 7 9 11 2 8 12 10 4 14 15 6 13 1 3 2 3 3 2 3 1 3 2 2 2 1 3 3 1 1 5 7 3 11 2 8 12 10 4 9 14 15 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 1 5 7 3 11 2 8 12 10 4 9 14 15 6 13 11 12 10 14 15 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 交换点 交换点 1 5 7 9 2 8 4 3 6 1 3 2 3 3 2 3 1 3 2 1 2 2 1 3 1 5 7 3 11 2 8 12 10 4 9 14 15 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 反转点 反转点 1 5 7 9 4 10 12 8 2 11 3 14 15 6 13 1 3 2 3 2 3 1 3 2 3 1 2 2 1 3 1 5 7 3 11 2 8 12 10 4 9 14 15 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 变异点 1 变异点 2 变异点 3 1 5 7 3 11 2 8 12 10 4 3 14 15 6 13 1 3 2 3 3 2 1 1 3 2 2 2 2 1 3 (d) 多点变异 (c) 反转 (b) 单点插入 (a) 单点交换 图 5 爆炸算子示意 Fig. 5 Flow chart of explosion operator 爆炸算子中的爆炸数量 S i和爆炸半径 Ri的计 算规则为 S i = S sum · fitmax −fit(xi) ∑N i=1 (fitmax −fit(xi)) (17) Ri = A× fit(xi)−fitmin ∑N i=1 (fit(xi)−fitmin ) (18) S sum A fit(xi) xi fitmax fitmin N 式中： 为预设的爆炸火花数； 为爆炸半径的 基值； 为个体 的适应度； 与 分别为 进行爆炸操作的个体中的最大适应度值与最小适 应度值； 为进行爆炸操作的个体的数量。 Ri 爆炸半径规定了爆炸操作时进行邻域搜索的 范围，对于本文的自然数编码方案，爆炸半径可 以对应为爆炸操作的最大执行次数，即对于烟花 i，需要随机进行 1~ 次爆炸操作才可以得到一个 新的火花。 S i 由于在遗传算法阶段进行了相关变异操作， 为避免不必要的运算，本文爆炸算子没有考虑高 斯变异火花。由于爆炸数量根据个体的适应度计 算的，具有一定的不确定性，因此本文对 设置了 上下界： Sˆ i = S max, S i > S max S i , S min < S i < S max S min, S i < S min (19) 式中： S max与 S min分别为的预先设置的最大、最小 爆炸火花数量。 S min 最后为了保证种群规模不变，规定每次保留 个火花作为爆炸算子产生的新个体，加入遗传 算法的种群中，进行混合算法的下一轮迭代。 3.3 混合算法流程 混合算法的基本流程如图 6 所示，分为初始 化、遗传进化和爆炸优化 3 个阶段。 开始 初始化模型和算法中的各 项参数和变量 随机生成初代种群 计算种群中每个个体的适 应度，并对其排序 采用 PMX 和简单交换对 种群个体进行交叉操作 是否达到终 止条件 随机选择一定数量的个 体，进行变异操作 采用精英保留和轮盘赌选 择进入子代种群中的个体 选择子代种群中适应度最 好和最差的两个个体 计算爆炸数量和爆炸半径 经爆炸操作得到火花粒子 将爆炸火花粒子加入子代 种群，进入下一轮迭代 构建资源集合、需求地 点、配送中心及车辆集合 输出最佳调度方案 结束 遗 传 搜 索 阶 段 爆 炸 优 化 阶 段 初 始 化 阶 段 Y N 图 6 遗传–烟花混合算法流程图 Fig. 6 Flow chart of genetic-firework hybrid algorithm ·93· 李猛，等：一种面向维修资源配送调度的遗传–烟花混合算法 第 1 期
第17卷 智能系统学报 ·94· 4 实验结果与分析 改造。 实验从Cordeau数据集中选择10个具有代表 4.1实验数据与算法参数 性的基础实例，为其增加了车辆、车位和工作时 由于本章建立的资源供应调度模型属于MD- 长限制，得到了A~A和B1~B两组共10个实验 VRPTW模型的一个扩展，相较于原模型增加了 算例，如表1。对于A、B两组数字序号相同的算 许多新约束，目前还没有公开标准数据可用于测 例，其节点地理分布是完全相同的，但A组算例 试验证。因此，本文引入了国际通用的MD- 具有较窄的时间窗口，B组算例具有较宽的时间 VRPTW公开基准数据集2，并对其进行了补充与 窗口。 表1实验算例基本信息 Table 1 Basic information of experimental examples Cordeau 配送中心 需求地点 配送中心 配送中心车 最大载资源 最大工作 算例编号 实例号 数量个 数量/个 车位数/个 辆数/辆 承载负荷/个 时长/min A1 pr01 4 48 4 2 200 1000 A2 pr07 6 72 4 2 200 1000 A3 pr02 96 6 3 196 960 Aa pr03 144 8 150 920 A pr08 6 144 6 3 190 850 Bi prl1 4 48 2 1 200 1000 B2 pr17 6 72 2 1 200 1000 B3 pr12 4 96 4 2 196 960 Ba pr13 144 6 3 150 920 B pr18 6 144 2 190 850 为了便于对比，相关变量及参数的取值如表2. 遗传-烟花混合算法是一种启发式算法，启发 参数测试候选值和最终取值见表3。 参数的好坏往往决定了算法的性能。因此本文使 表2模型参数值设置 用表1中的算例进行了参数评估。 Table 2 Model parameter value setting 4.2算法性能对比 模型参数名称 参数值 单个的算例的运行结果具有一定的局限性， 车辆动用成本元 1000 为了进一步对比算法的求解性能，本文对遗传算 每千米行驶成本/元 10 法、烟花算法以及混合算法在同样的硬件条件 提前到达每分钟惩罚成本/元 0.5 下，对表1中的10个算例分别进行了对比实验。 推迟到达每分钟惩罚成本/元 2 为了保障实验的公平性，对于相同的算例，3种算 车辆行驶速ms 16.6 法的候选解规模、迭代次数以及初始种群都设置 完全相同。 表3混合算法参数 1)求解质量对比 Table 3 Hybrid algorithm parameters 为了综合对比算法的求解质量，记录3种算 算法参数名称 参数测试候选值 参数取值 法10次运行结果中目标函数的最优值、平均值以 遗传种群数量个 50、100、200 100 及标准差分别如表4、表5和表6所示。 遗传种群代沟 0.5、0.7、0.9 0.9 对比表4和5中的目标函数值可以明显看 交叉概率 0.6、0.7、0.8 0.8 出，在绝大部分算例上，无论是最优值还是平均 变异概率 0.1、0.2、0.3 0.1 值，混合算法都比遗传算法和烟花算法要小，这 预设爆炸数量个 15、30、60 30 说明混合算法具有最好的求解质量，得到的满意 最大爆炸数量个 12、24、30 24 解更加逼近实际最优解，得到了调度成本最小的 最小爆炸数数/个 5、10、20 10 方案。 爆炸半径 10、20、30 20 2)求解速度对比
4 实验结果与分析 4.1 实验数据与算法参数 由于本章建立的资源供应调度模型属于 MDVRPTW 模型的一个扩展，相较于原模型增加了 许多新约束，目前还没有公开标准数据可用于测 试验证。因此，本文引入了国际通用 的 MDVRPTW 公开基准数据集[26] ，并对其进行了补充与 改造。 实验从 Cordeau 数据集中选择 10 个具有代表 性的基础实例，为其增加了车辆、车位和工作时 长限制，得到了 A1~A5 和 B1~B5 两组共 10 个实验 算例，如表 1。对于 A、B 两组数字序号相同的算 例，其节点地理分布是完全相同的，但 A 组算例 具有较窄的时间窗口，B 组算例具有较宽的时间 窗口。 表 1 实验算例基本信息 Table 1 Basic information of experimental examples 算例编号 Cordeau 实例号 配送中心 数量/个 需求地点 数量/个 配送中心 车位数/个 配送中心车 辆数/辆 最大载资源 承载负荷/个 最大工作 时长/min A1 pr01 4 48 4 2 200 1000 A2 pr07 6 72 4 2 200 1000 A3 pr02 4 96 6 3 196 960 A4 pr03 4 144 8 4 150 920 A5 pr08 6 144 6 3 190 850 B1 pr11 4 48 2 1 200 1000 B2 pr17 6 72 2 1 200 1000 B3 pr12 4 96 4 2 196 960 B4 pr13 4 144 6 3 150 920 B5 pr18 6 144 4 2 190 850 为了便于对比，相关变量及参数的取值如表 2， 参数测试候选值和最终取值见表 3。 表 2 模型参数值设置 Table 2 Model parameter value setting 模型参数名称 参数值 车辆动用成本/元 1000 每千米行驶成本/元 10 提前到达每分钟惩罚成本/元 0.5 推迟到达每分钟惩罚成本/元 2 车辆行驶速/m·s−1 16.6 表 3 混合算法参数 Table 3 Hybrid algorithm parameters 算法参数名称 参数测试候选值 参数取值 遗传种群数量/个 50、100、200 100 遗传种群代沟 0.5、0.7、0.9 0.9 交叉概率 0.6、0.7、0.8 0.8 变异概率 0.1、0.2、0.3 0.1 预设爆炸数量/个 15、30、60 30 最大爆炸数量/个 12、24、30 24 最小爆炸数数/个 5、10、20 10 爆炸半径 10、20、30 20 遗传–烟花混合算法是一种启发式算法，启发 参数的好坏往往决定了算法的性能。因此本文使 用表 1 中的算例进行了参数评估。 4.2 算法性能对比 单个的算例的运行结果具有一定的局限性， 为了进一步对比算法的求解性能，本文对遗传算 法、烟花算法以及混合算法在同样的硬件条件 下，对表 1 中的 10 个算例分别进行了对比实验。 为了保障实验的公平性，对于相同的算例，3 种算 法的候选解规模、迭代次数以及初始种群都设置 完全相同。 1）求解质量对比 为了综合对比算法的求解质量，记录 3 种算 法 10 次运行结果中目标函数的最优值、平均值以 及标准差分别如表 4、表 5 和表 6 所示。 对比表 4 和 5 中的目标函数值可以明显看 出，在绝大部分算例上，无论是最优值还是平均 值，混合算法都比遗传算法和烟花算法要小，这 说明混合算法具有最好的求解质量，得到的满意 解更加逼近实际最优解，得到了调度成本最小的 方案。 2）求解速度对比 第 17 卷 智 能 系 统 学 报 ·94·
·95· 李猛，等：一种面向维修资源配送调度的遗传-烟花混合算法 第1期 为了综合对比算法的求解速度，分别统计 满意解时的平均迭代次数及平均运行时长（单 3种算法在各算例上10次运行结果中初次找到 位：s),如图7所示。 表4目标函数最优值 Table 4 Optimal value of objective function 算例 A A2 A3 Aa As B B2 B3 Ba Bs GA 16072 22130 28327 42640 41351 14636 20484 24930 40823 39215 FWA 15474 21711 27634 41715 40700 13918 19420 23786 39601 38532 混合 14936 21322 27122 40067 39429 13565 19170 22973 38725 37783 表5目标函数平均值 Table 5 Average value of objective function 算例 Al A2 A3 Aa As B B2 B3 Ba Bs GA 16892 22910 29138 43653 42564 15421 21180 26086 41970 40585 FWA 15725 22137 28354 42405 41638 14753 20187 24786 40533 39714 混合 15270 21634 27592 41517 40727 14195 19794 23553 39022 38372 表6目标函数标准差 Table 6 Standard deviation of objective function 算例 A A2 A3 A A B B2 B3 B Bs GA 384.3 339.9 442.6 485.1 552.3 340.7 327.6 532.5 673.4 472.9 FWA 207.4 208.2 337.5 349.2 362 327.7 308.2 411.8 479.2 512.0 混合 229.6 147.4 219.7 459.9294.6 257.2 328.5 272.5 459.3 324.5 3000 法种群中适应度最好的个体其包含更为优秀的遗 新2500 传信息，对其进行爆炸操作能在很大程度上能够 2000 1500 引导算法的收敛方向，而适应度最差的个体由于 1000 包含了和优秀个体差异程度最大的遗传信息，能 500 ◆GA鲁FWA★混合 够使得种群的遗传信息更加丰富，从而扩大了局 0 A B A2 B:A:B,A.B.As B 部搜索的范围。对两种算法进行混合，充分结合 算例 了遗传算法全局搜索能力强和烟花算法局部搜索 图7初次找到满意解的平均迭代次数 能力强的特点，使得混合算法在收敛速度和搜索 Fig.7 Average number of iterations to find a satisfactory 范围上都得到了改善，从而能够以更快的速度得 solution for the first time 到更小成本的调度方案，这对于实际的资源供应 综合求解质量和求解速度的结果来看：混合 算法求解质量是最好的，其收敛速度也快于烟花 调度具有重要的经济效益。 算法和遗传算法，但在运行时间上会略慢于遗传 5结束语 算法，即混合算法在略微增加了一些运算成本的 情况下获得了更好的求解质量。而增加的运算成 本文针对建立的维修资源供应调度模型，本 本可以通过硬件配置进一步缩小，但对于求解质 文提出了一种遗传-烟花混合算法。混合算法在 量，其他两种算法却无法靠简单的硬件升级进行 遗传算法的基础上，引入了烟花爆炸算子，使得 弥补，因此混合算法是3种算法中综合性能最强 种群优秀个体的数量增多，增强了算法的局部寻 的算法。 优能力。通过仿真对比实验，结果表明本文提出 从理论上对实验结果进行分析，由于遗传算 的混合算法可以得到成本更低的调度方案，同时
为了综合对比算法的求解速度，分别统计 3 种算法在各算例上 10 次运行结果中初次找到 满意解时的平均迭代次数及平均运行时长（单 位：s），如图 7 所示。 表 4 目标函数最优值 Table 4 Optimal value of objective function 算例 A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 GA 16072 22130 28 327 42 640 41351 14636 20484 24 930 40 823 39215 FWA 15474 21711 27 634 41 715 40700 13918 19420 23 786 39 601 38532 混合 14936 21322 27 122 40 067 39429 13565 19170 22 973 38 725 37783 表 5 目标函数平均值 Table 5 Average value of objective function 算例 A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 GA 16892 22910 29 138 43 653 42564 15421 21180 26 086 41 970 40585 FWA 15725 22137 28 354 42 405 41638 14753 20187 24 786 40 533 39714 混合 15270 21634 27 592 41 517 40727 14195 19794 23 553 39 022 38372 表 6 目标函数标准差 Table 6 Standard deviation of objective function 算例 A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 GA 384.3 339.9 442.6 485.1 552.3 340.7 327.6 532.5 673.4 472.9 FWA 207.4 208.2 337.5 349.2 362 327.7 308.2 411.8 479.2 512.0 混合 229.6 147.4 219.7 459.9 294.6 257.2 328.5 272.5 459.3 324.5 GA FWA 混合 A1 0 500 1 000 1 500 2 000 2 500 3 000 B1 A2 B2 A3 B3 A4 B4 A5 B5 平均迭代次数 算例 图 7 初次找到满意解的平均迭代次数 Fig. 7 Average number of iterations to find a satisfactory solution for the first time 综合求解质量和求解速度的结果来看：混合 算法求解质量是最好的，其收敛速度也快于烟花 算法和遗传算法，但在运行时间上会略慢于遗传 算法，即混合算法在略微增加了一些运算成本的 情况下获得了更好的求解质量。而增加的运算成 本可以通过硬件配置进一步缩小，但对于求解质 量，其他两种算法却无法靠简单的硬件升级进行 弥补，因此混合算法是 3 种算法中综合性能最强 的算法。 从理论上对实验结果进行分析，由于遗传算 法种群中适应度最好的个体其包含更为优秀的遗 传信息，对其进行爆炸操作能在很大程度上能够 引导算法的收敛方向，而适应度最差的个体由于 包含了和优秀个体差异程度最大的遗传信息，能 够使得种群的遗传信息更加丰富，从而扩大了局 部搜索的范围。对两种算法进行混合，充分结合 了遗传算法全局搜索能力强和烟花算法局部搜索 能力强的特点，使得混合算法在收敛速度和搜索 范围上都得到了改善，从而能够以更快的速度得 到更小成本的调度方案，这对于实际的资源供应 调度具有重要的经济效益。 5 结束语 本文针对建立的维修资源供应调度模型，本 文提出了一种遗传–烟花混合算法。混合算法在 遗传算法的基础上，引入了烟花爆炸算子，使得 种群优秀个体的数量增多，增强了算法的局部寻 优能力。通过仿真对比实验，结果表明本文提出 的混合算法可以得到成本更低的调度方案，同时 ·95· 李猛，等：一种面向维修资源配送调度的遗传–烟花混合算法 第 1 期
第17卷 智能系统学报 ·96· 具有更快的收敛速度，并且适用于各种规模的资 [12]STODOLA P.Hybrid ant colony optimization al- 源供应调度需求。 gorithm applied to the multi-depot vehicle routing prob- lem[J].Natural computing,2020,19(2):463-475. 参考文献： [13]MIRABI M.SHOKRI N,SADEGHIEH A.Modeling [1]TADJDEH Y.F-35 logistics system faces challenges[J]. and solving the multi-depot vehicle routing problem with National defense,2018,102(772):36-37. time window by considering the flexible end depot in [2]王蕾，林涛.新时期下装备维修保障模式研究[.现代 each route[J].International journal of supply and opera- 防御技术，2020,48(5)：86-91,104 tions management,2016,3(3):1373-1390 WANG Lei,LIN Tao.Research on equipment mainten- [14]SUN Peng,VEELENTURF L P,HEWITT M,et al.Ad- ance support mode in the new period[J].Modern defence aptive large neighborhood search for the time-dependent technology,2020,48(5):86-91,104. profitable pickup and delivery problem with time win- [3]石文成，杨西龙.战备物资综合管理研究综述).军事 dows[J].Transportation research part E:logistics and 交通学院学报，2020,22(12)：47-51. transportation review,2020,138:101942 SHI Wencheng,YANG Xilong.On comprehensive man- [15]张家骅，李爱平，刘雪梅.行驶时间区间不确定的装配 agement of war readiness materials[].Journal of military 线物料配送路径规划U).中国机械工程，2021,32(18)： transportation university,2020,22(12):47-51. 2239-2246」 [4]ZAMAN F.ELSAYED S M,SAKER R,et al.Resource ZHANG Jiahua,LI Aiping,LIU Xuemei.Routing plan- constrained project scheduling with dynamic disruption ning for assembly line material distributions under inter- recovery[J].IEEE access,2020,8:144866-144879. val uncertain travel TimeChinese full text[J].China [5]CREEMERS S.The preemptive stochastic resource-con- mechanical engineering,2021,32(18):2239-2246. strained project scheduling problem[J].European journal [16] 马龙，王春嬉，张正义，等.多目标多时间窗车辆路径 of operational research,2019,277(1):238-247. 问题的鸽群-水滴算法.计算机工程与应用，2021， [6]KANNIMUTHU M.RAPHAEL B,EKAMBARAM P,et 57(2:237-250 al.Comparing optimization modeling approaches for the MA Long,WANG Chunxi,ZHANG Zhengyi,et al.Pi- multi-mode resource-constrained multi-project schedul- geon-inspired optimization and intelligent water drops ing problem[J].Engineering,construction and architectur- algorithm for multiple-objective vehicle routing prob- al management,2020,27(4):893-916. lem with multiple time WindowsChinese full TextEng- [7]OZTEMEL E,SELAM AA.Bees Algorithm for multi- lish full text (MT)[J].Computer engineering and applic- mode,resource-constrained project scheduling in mold- ations..2021,57(2):237-250. ing industry[J].Computers industrial engineering, [1]刘明德.基于群体智能的动态需求车辆路径规划D] 2017,112:187-196 哈尔滨：哈尔滨工业大学，2020. [8]滕尚儒，何成铭，丛彬.装备维修器材军民融合供应保 LIU Mingde.Research on vehicle routing problem with 障模式探索[U.物流技术，2020,39(4)：117-124 dynamic demands based on swarm intelligence[D].Har- TENG Shangru,HE Chengming,CONG Bin.Explora- bin:Harbin Institute of Technology,2020. tion on military-civilian integrated supply and support [18]ABED F,CHEN Lin,DISSER Y,et al.Scheduling mode for equipment maintenance materials[J].Logistics maintenance jobs in networks[J].Theoretical computer technology,2020,394):117-124. science,2019,754:107-121. [9]DANTZIG G B,RAMSER J H.The truck dispatching [19]TIRKOLAEE E B,GOLI A,HEMATIAN M,et al problem[J].Management science,1959,6(1):80-91. Multi-objective multi-mode resource constrained project [10]SOEANU A,RAY S,BERGER J,et al.Multi-depot scheduling problem using Pareto-based algorithms[J]. vehicle routing problem with risk mitigation:Model and Computing,2019,101(6:547-570. solution algorithm[J].Expert systems with applications, [20]CHAKRABORTTY R K.ABBASI A.RYAN MJ. 2020,145:113099 Multi-mode resource-constrained project scheduling us- [11]KARAKATIC S,PODGORELEC V.A survey of genet- ing modified variable neighborhood search heuristic[J]. ic algorithms for solving multi depot vehicle routing International transactions in operational research,2020, problem[J].Applied soft computing,2015,27:519-532. 271):138-167
具有更快的收敛速度，并且适用于各种规模的资 源供应调度需求。 参考文献： TADJDEH Y. F-35 logistics system faces challenges[J]. National defense, 2018, 102(772): 36–37. [1] 王蕾, 林涛. 新时期下装备维修保障模式研究 [J]. 现代 防御技术, 2020, 48(5): 86–91,104. WANG Lei, LIN Tao. Research on equipment maintenance support mode in the new period[J]. Modern defence technology, 2020, 48(5): 86–91,104. [2] 石文成, 杨西龙. 战备物资综合管理研究综述 [J]. 军事 交通学院学报, 2020, 22(12): 47–51. SHI Wencheng, YANG Xilong. On comprehensive management of war readiness materials[J]. Journal of military transportation university, 2020, 22(12): 47–51. [3] ZAMAN F, ELSAYED S M, SAKER R, et al. Resource constrained project scheduling with dynamic disruption recovery[J]. IEEE access, 2020, 8: 144866–144879. [4] CREEMERS S. The preemptive stochastic resource-constrained project scheduling problem[J]. European journal of operational research, 2019, 277(1): 238–247. [5] KANNIMUTHU M, RAPHAEL B, EKAMBARAM P, et al. Comparing optimization modeling approaches for the multi-mode resource-constrained multi-project scheduling problem[J]. Engineering, construction and architectural management, 2020, 27(4): 893–916. [6] OZTEMEL E, SELAM A A. Bees Algorithm for multimode, resource-constrained project scheduling in molding industry[J]. Computers & industrial engineering, 2017, 112: 187–196. [7] 滕尚儒, 何成铭, 丛彬. 装备维修器材军民融合供应保 障模式探索 [J]. 物流技术, 2020, 39(4): 117–124. TENG Shangru, HE Chengming, CONG Bin. Exploration on military-civilian integrated supply and support mode for equipment maintenance materials[J]. Logistics technology, 2020, 39(4): 117–124. [8] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management science, 1959, 6(1): 80–91. [9] SOEANU A, RAY S, BERGER J, et al. Multi-depot vehicle routing problem with risk mitigation: Model and solution algorithm[J]. Expert systems with applications, 2020, 145: 113099. [10] KARAKATIČ S, PODGORELEC V. A survey of genetic algorithms for solving multi depot vehicle routing problem[J]. Applied soft computing, 2015, 27: 519–532. [11] STODOLA P. Hybrid ant colony optimization algorithm applied to the multi-depot vehicle routing problem[J]. Natural computing, 2020, 19(2): 463–475. [12] MIRABI M, SHOKRI N, SADEGHIEH A. Modeling and solving the multi-depot vehicle routing problem with time window by considering the flexible end depot in each route[J]. International journal of supply and operations management, 2016, 3(3): 1373–1390. [13] SUN Peng, VEELENTURF L P, HEWITT M, et al. Adaptive large neighborhood search for the time-dependent profitable pickup and delivery problem with time windows[J]. Transportation research part E:logistics and transportation review, 2020, 138: 101942. [14] 张家骅, 李爱平, 刘雪梅. 行驶时间区间不确定的装配 线物料配送路径规划 [J]. 中国机械工程, 2021, 32(18): 2239–2246. ZHANG Jiahua, LI Aiping, LIU Xuemei. Routing planning for assembly line material distributions under interval uncertain travel TimeChinese full text[J]. China mechanical engineering, 2021, 32(18): 2239–2246. [15] 马龙, 王春嬉, 张正义, 等. 多目标多时间窗车辆路径 问题的鸽群-水滴算法 [J]. 计算机工程与应用, 2021, 57(2): 237–250. MA Long, WANG Chunxi, ZHANG Zhengyi, et al. Pigeon-inspired optimization and intelligent water drops algorithm for multiple-objective vehicle routing problem with multiple time WindowsChinese full TextEnglish full text (MT)[J]. Computer engineering and applications, 2021, 57(2): 237–250. [16] 刘明德. 基于群体智能的动态需求车辆路径规划 [D]. 哈尔滨: 哈尔滨工业大学, 2020. LIU Mingde. Research on vehicle routing problem with dynamic demands based on swarm intelligence[D]. Harbin: Harbin Institute of Technology, 2020. [17] ABED F, CHEN Lin, DISSER Y, et al. Scheduling maintenance jobs in networks[J]. Theoretical computer science, 2019, 754: 107–121. [18] TIRKOLAEE E B, GOLI A, HEMATIAN M, et al. Multi-objective multi-mode resource constrained project scheduling problem using Pareto-based algorithms[J]. Computing, 2019, 101(6): 547–570. [19] CHAKRABORTTY R K, ABBASI A, RYAN M J. Multi-mode resource-constrained project scheduling using modified variable neighborhood search heuristic[J]. International transactions in operational research, 2020, 27(1): 138–167. [20] 第 17 卷 智 能 系 统 学 报 ·96·
·97 李猛，等：一种面向维修资源配送调度的遗传-烟花混合算法 第1期 [21]GARCiA J M,ACOSTA C A,MESA M J.Genetic al- 作者简介： gorithms for mathematical optimization[J].Journal of 李猛，硕士研究生，主要研究方向 physics:conference series,2020,1448(1):012020. 为自主维修保障的资源调度与优化。 [22]ERMAKOV S M.SEMENCHIKOV D N.Genetic glob- al optimization algorithms[J].Communications in statist- ics-simulation and computation,2019:1-10. [23]TAN Ying,YU Chao,ZHENG Shaogiu,et al.Introduc- tion to fireworks algorithm[J].International journal of 和伟辉，硕士研究生，主要研究方 swarm intelligence research,2013,4(4):39-70. 向为健康管理与故障诊断。 [24]LI Junzhi,TAN Ying.A comprehensive review of the fireworks algorithm[J].ACM computing surveys,2020. 52(6):1-28. [25]SETHANAN K,JAMRUS T.Hybrid differential evolu- tion algorithm and genetic operator for multi-trip vehicle routing problem with backhauls and heterogeneous fleet 刘立芳，教授，博土，主要研究方 in the beverage logistics industry[J].Computers&in- 向为数据处理与智能计算。主持国家 自然科学基金项目、陕西省自然科学 dustrial engineering,2020,146:106571. 基金项目等国家和省部级项目5项。 [26]CORDEAU J F,GENDREAU M,LAPORTE G.A tabu 发表学术论文40余篇。 search heuristic for periodic and multi-depot vehicle routing problems[J].Networks,1997,30(2):105-119. 第十七届中国青年科技奖候选人推荐 为深入贯彻习近平新时代中国特色社会主义思想，贯彻落实中央人才工作会议精神，坚持面向世界科技 前沿、面向经济主战场、面向国家重大需求、面向人民生命健康，表彰在国家经济发展、社会进步和科技创 新中作出突出贡献的青年科技人才，激发创新创业创造热情，培养造就规模宏大的青年科技人才队伍，打造 大批一流科技领军人才和创新团队，为加快建设世界重要人才中心和创新高地、实现高水平科技自立自强 贡献智慧和力量，根据《中共中央组织部人力资源社会保障部中国科协共青团中央关于开展第十七届中 国青年科技奖候选人提名工作的通知》文件要求，中国人工智能学会决定开展第十七届中国青年科技奖候 选人推荐工作。详情请访问中国人工智能学会官方通知：https:mp.weixin.qq.com/s/Fil47L0 vXmXLVz-wiiHrg 报送时间： 书面材料请于2022年1月20日18：00前寄送至学会秘书处；电子版材料请于同日期发送至邮箱 msc@caai.cn,电子版材料与书面材料保持一致
GARCÍA J M, ACOSTA C A, MESA M J. Genetic algorithms for mathematical optimization[J]. Journal of physics:conference series, 2020, 1448(1): 012020. [21] ERMAKOV S M, SEMENCHIKOV D N. Genetic global optimization algorithms[J]. Communications in statistics - simulation and computation, 2019: 1–10. [22] TAN Ying, YU Chao, ZHENG Shaoqiu, et al. Introduction to fireworks algorithm[J]. International journal of swarm intelligence research, 2013, 4(4): 39–70. [23] LI Junzhi, TAN Ying. A comprehensive review of the fireworks algorithm[J]. ACM computing surveys, 2020, 52(6): 1–28. [24] SETHANAN K, JAMRUS T. Hybrid differential evolution algorithm and genetic operator for multi-trip vehicle routing problem with backhauls and heterogeneous fleet in the beverage logistics industry[J]. Computers & industrial engineering, 2020, 146: 106571. [25] CORDEAU J F, GENDREAU M, LAPORTE G. A tabu search heuristic for periodic and multi-depot vehicle routing problems[J]. Networks, 1997, 30(2): 105–119. [26] 作者简介： 李猛，硕士研究生，主要研究方向 为自主维修保障的资源调度与优化。 和伟辉，硕士研究生，主要研究方 向为健康管理与故障诊断。 刘立芳，教授，博士，主要研究方 向为数据处理与智能计算。主持国家 自然科学基金项目、陕西省自然科学 基金项目等国家和省部级项目 5 项。 发表学术论文 40 余篇。 第十七届中国青年科技奖候选人推荐 为深入贯彻习近平新时代中国特色社会主义思想，贯彻落实中央人才工作会议精神，坚持面向世界科技 前沿、面向经济主战场、面向国家重大需求、面向人民生命健康，表彰在国家经济发展、社会进步和科技创 新中作出突出贡献的青年科技人才，激发创新创业创造热情，培养造就规模宏大的青年科技人才队伍，打造 大批一流科技领军人才和创新团队，为加快建设世界重要人才中心和创新高地、实现高水平科技自立自强 贡献智慧和力量，根据《中共中央组织部 人力资源社会保障部 中国科协 共青团中央关于开展第十七届中 国青年科技奖候选人提名工作的通知》文件要求，中国人工智能学会决定开展第十七届中国青年科技奖候 选人推荐工作。详情请访问中国人工智能学会官方通知：https://mp.weixin.qq.com/s/Fi147L0vXmXLVz-IwiiHrg 报送时间： 书面材料请于 2022 年 1 月 20 日 18:00 前寄送至学会秘书处；电子版材料请于同日期发送至邮箱 msc@caai.cn，电子版材料与书面材料保持一致。 ·97· 李猛，等：一种面向维修资源配送调度的遗传–烟花混合算法 第 1 期