第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 < ei 0，其他 (13) T lat ki = { aki −li , 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·