一种基于区间多目标混合蛙跳算法的医疗废物清运方法

1.本发明涉及计算智能和车辆路径规划技术领域，具体而言涉及一种基于区间多目标混合蛙跳算法的医疗废物清运方法。


背景技术：

2.医疗废物清运的背景可以追溯到20世纪80年代，当时人们意识到医疗废物的产生是一种严重的生态问题。随着医疗技术的不断进步，医疗废物的数量也在持续增加。医疗废物中含有各种危险物质，如化学品、放射性物质和传染病毒等，如果没有处理好，会对环境和人类健康造成巨大的威胁。为了高效率、低成本和低风险的清运这些医疗废物，需要建立完备的医疗废物清运处理系统。区别于一般的垃圾清运调度，考虑到在实际的调度过程中，受交通拥堵，天气等因素的影响，车辆的行驶速度通常是不确定的，容易影响车辆的实际到达时间和任务的完成时间。因此，对车辆行驶速度不确定性医疗废物清运的研究非常有必要。
3.对于车辆路径规划，目前已经涌现出许多研究。其中主要采用的方法包括遗传算法、蚁群算法等。遗传算法是一种适用范围较广的算法，能够很好地处理大规模问题，但其缺点是容易陷入局部最优解；蚁群算法在求解效率和性能上较为优秀，但对于种群的初始化和调参有较高要求。


技术实现要素：

4.混合蛙跳算法是元启发式算法的一种，与传统求解车辆路径问题的优化算法相比，sfla特有的搜索机制使得它能够更好地维护局部搜索和全局搜索之间的平衡，区间多目标混合蛙跳算法是混合蛙跳算法的改进算法，它将医疗废物清运的问题信息与混合蛙跳算法的结构特点相融合，在初始调度时刻生成对不确定环境具有较强鲁棒性的调度方案，减少不确定性对调度性能的负面影响。此外，对于新增客户请求或需求变动，需要及时对调度方案进行调整。
5.因此，本发明提供了一种基于区间多目标混合蛙跳算法的医疗废物清运方法，能够在车辆容量和工作时间等约束下，通过优化车辆的清运路径，以最小化调度总成本和废物清运风险。
6.为达成上述目的，本发明通过以下技术方案予以实现：
7.第一方面，提供一种基于区间多目标混合蛙跳算法的医疗废物清运方法，包括：
8.获取初始清运请求和路况信息；
9.在初始调度周期，基于初始清运请求和路况信息，采用区间多目标混合蛙跳算法对预构建的医疗废物清运路径规划模型进行求解，得到初始车辆清运路径；
10.车辆按初始车辆清运路径进行垃圾采集，直至垃圾清运任务完成；
11.若垃圾清运任务未完成且进入下一周期性调度时刻点，根据上一调度周期内获取的动态请求集合和所述医疗废物清运路径规划模型，采用结构重组法对初始车辆清运路径
进行调整得到车辆清运子路径；从车场出发新车执行车辆清运子路径，直至完成垃圾清运任务。
12.在一些实施例中，所述的基于区间多目标混合蛙跳算法的医疗废物清运方法，还包括：当周期性调度中发生动态事件请求时，采用动态响应机制更新车辆清运路径和动态请求集合；其中所述动态响应机制，包括：
13.动态事件请求指的是调度过程中客户产生的请求，包括：新增的医疗机构医疗废物清运请求和客户的期望处理时间的调整；其中，新增的医疗机构医疗废物清运请求是指在调度过程中出现新的客户请求，包括新客户出现的时间、位置及其需求量；客户的期望处理时间的调整是指客户对医疗废物的期望处理时间主动请求提前或延误；
14.判断能否处理该动态事件请求，若能，通过动态修补法将动态事件请求更新至已有路径中，车辆按更新后的路径继续行驶；否则，车辆按原路径继续行驶，并将请求放入动态请求集合δh中，等待下一个周期性调度时刻点统一处理；
15.其中，所述动态修补法包括：在时刻t(t∈[0,t])有新增的医疗机构hu的废物清运需求，则基于所述医疗废物清运路径规划模型将新增医疗机构插入到当前的清运路径中，以最大程度的减少路径的变动，从而适应医疗机构的动态需求。
[0016]
在一些实施例中，所述初始清运请求和路况信息包括医疗废物运输车辆需要访问的医疗机构数量、医疗机构坐标信息、医疗废物处理站坐标信息、车场坐标信息和期望处理时刻；
[0017]
所述动态请求集合存放的是上一个调度周期过程中产生的动态请求，此类请求无法即时处理，而统一由下一个调度周期开始时刻进行处理，且将已完成的清运请求从动态请求集合中清除。
[0018]
在一些实施例中，所述医疗废物清运路径规划模型包含三个强耦合的子问题：
[0019]
(1)多行程确定，在一个调度周期内，为每辆车确定行程数以及每个行程经过的医疗机构；
[0020]
(2)医疗机构分配，为医疗机构分配服务车辆；
[0021]
(3)车辆选择，按照废物清运路径选择车辆；
[0022]
子问题的调度由三个决策变量来表示：
[0023]
多行程确定
[0024]
医疗机构分配
[0025]
车辆选择
[0026]
在一些实施例中，在医疗废物清运路径规划问题中，共有n家医疗机构hu、m家废物处理站rq和1个车场d，其中u＝1,2,...,n，q＝1,2,...,m；车辆在初始时刻从车场出发，依次到各医疗机构收集废物，然后送至任意一个适当的废物处理站进行处理，最后返回车场结束任务；在清运过程中，车辆允许有多个行程，tripk为车辆k的行程集合，
为车辆k的第w次行程，lk是车辆k的最后一个行程；医疗机构、废物处理站和车场的集合用v＝{h1,h2,...,hn,r1,...,rm,d}表示，这些地点之间的路径长度用边集e＝{(pi,pj)|pi,pj∈v,i≠j}表示，其中，pipj为车辆访问的节点，pipj∈h∪r∪{d}，h为医疗机构hu的集合，r为废物处理站rq的集合；考虑到道路路况的不确定性，对于每条边e
ij
，都有相对应的行驶速度的区间数其中v
ij
和分别代表车辆在边e
ij
的最小和最大行驶速度；工作时间段为[0,tm]，tm为最大工作时长；t
l
(l＝1,2,...,|ts|)为周期性调度的调度时刻点，ts为调度时刻t
l
的集合；
[0027]
所述医疗废物清运路径规划模型包括目标函数和约束条件；
[0028]
其中目标函数以最小化调度成本和感染风险为优化目标，表示为：
[0029]
min f1＝cost1+cost2+cost3+cost4[0030]
min f2＝risk1+risk2[0031]
其中调度成本f1包括固定成本cost1、油耗成本cost2、加班成本cost3和污染成本cost4；感染风险f2包括运输风险risk1和废物处理风险risk2；
[0032][0033]
其中，zk表示车辆k选择是否被使用，k为所有车辆的集合，cv表示调用一次车辆需要支出的司机报酬及启动成本；
[0034][0035]
其中，fc
ij
表示车辆通过路段e
ij
的油耗成本，αk和βk为路况和车辆的特征参数；q0，v
ij
和d
ij
分别为车辆净重、车辆负载、车辆的行驶速度和行驶距离，dis
ij
为点pi到点pj的欧式距离，cf为燃油的价格；x
ijkw
为车辆k的第w次行程从点pi到点pj；
[0036][0037]
其中，co为加班工资，trk为车辆k最后一次行程返回车场的时刻；
[0038][0039]
其中，cp为污染成本，为车辆k到达点pj的时刻，etj为废物处理站的期望处理时刻；
[0040][0041]
其中，为车辆从pi点到pj点花费的时间(小时)，为车辆k离开点pi时的载重(吨)，p
ij
为路径e
ij
附近的人口数量；
[0042]
[0043]
其中，r为废物处理站rj的集合，mj为废物处理站rj的废物处理量，vdj为废物处理站rj处理废物的速度，为废物处理站rj附近的人口数量。
[0044]
在一些实施例中，所述医疗废物清运路径规划模型的约束条件包括：
[0045]
(1)所有车辆的第一次行程均从车场出发，在服务完行程的最后一个医疗机构后，到达任意一个废物处理站卸料；
[0046][0047]
其中，x
uqkw
为车辆k的第w次行程从医疗机构hu到废物处理站rq；
[0048]
(2)车辆的下一次行程从当前行程运往的废物处理站出发；
[0049][0050]
(3)车辆最后一次行程在废物处理站卸料后，必须返回车场；
[0051][0052]
其中，为车辆k的最后一次行程lk从废物处理站rq返回车场d；
[0053]
(4)车辆到达医疗机构hu后必须从hu离开，且该辆车至多只能到达和离开医疗机构hu一次；
[0054][0055][0056]
其中，x
jukw
为车辆k的第w次行程从点pj到医疗机构hu；x
ujkw
为车辆k的第w次行程从医疗机构hu到点pj；y
uk
为医疗机构hu由车辆k负责；
[0057]
(5)服务某个医疗机构的车辆有且只有一辆；
[0058][0059]
(6)车辆每次行程运输的废物量不超过车辆容量q；
[0060][0061]
其中，gu是医疗机构的垃圾清运量
[0062]
(7)从车场出发的车辆数量不超过最大可用车辆数；
[0063][0064]
其中，x
dukw
为车辆k的第w次行程从车场d到医疗机构hu。
[0065]
在一些实施例中，采用区间多目标混合蛙跳算法对预构建的医疗废物清运路径规划模型进行求解，包括：
[0066]
s301：初始化种群；
[0067]
s302：对种群进行区间非支配排序，并根据序值划分子组；
[0068]
s303：对每个子组通过基因重组和贪婪交叉策略生成新个体；
[0069]
s304：采用目标增强机制对非支配个体进行搜索；
[0070]
s305：筛选下一代种群；
[0071]
s306：判断是否达到最大目标评价次数，若达到，则终止，输出最优个体，对个体解码，解码后的路径即为医疗废物清运路径；否则，转步骤s302。
[0072]
在一些实施例中，所述对每个子组通过基因重组贪婪和交叉策略生成新个体，具体包括：
[0073]
(1)贪婪交叉策略
[0074]
贪婪交叉策略是一种由出发点开始逐步构造路径的个体更新策略；基于贪心思想，在待交叉个体中，从与新个体起点相邻的医疗机构中选择最近的点作为新个体的下一个医疗机构，以保留交叉个体中的有效信息；通过重复执行贪婪选择步骤以生成完整的转运路径；
[0075]
(2)基因重组策略
[0076]
用上述贪婪交叉策略得到的优解替换差解，并对差解的编码进行调整，使得各医疗机构所在列的出发点和废物处理站与原编码一致，由此得到个体；然后，更新出发点；计算新个体每一列出发点到医疗机构的距离，选取距离最远的前rand1个出发点和医疗机构，其中，rand1为1到医疗机构数量n之间的随机数；用优解中医疗机构对应的出发点替换原有出发；最后，以同样方式更新废物处理站。
[0077]
在一些实施例中，根据上一调度周期内获取的动态请求集合和所述医疗废物清运路径规划模型，采用结构重组法对初始车辆清运路径进行调整得到车辆清运子路径，包括：
[0078]
将动态请求集合中的医疗机构打乱，生成编码串；
[0079]
从两元素优化算子、嵌入优化算子和交换优化算子中随机选择一种作为策略，根据所述医疗废物清运路径规划模型对所述编码串进行优化求解，得到调整后的最优车辆清运子路径。
[0080]
第二方面，本发明提供了一种基于区间多目标混合蛙跳算法的医疗废物清运装置，包括处理器及存储介质；
[0081]
所述存储介质用于存储指令；
[0082]
所述处理器用于根据所述指令进行操作以执行根据第一方面所述的方法。
[0083]
第三方面，本发明提供了一种设备，包括，
[0084]
存储器；
[0085]
处理器；
[0086]
以及
[0087]
计算机程序；
[0088]
其中，所述计算机程序存储在所述存储器中，并被配置为由所述处理器执行以实现上述第一方面所述的方法。
[0089]
第四方面，本发明提供了一种存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现第一方面所述的方法。
[0090]
有益效果：
[0091]
本发明提供了一种基于区间多目标混合蛙跳算法的医疗废物清运方法，与现有技
术相比具备以下有益效果：
[0092]
(1)考虑车辆行驶速度的不确定性，建立了具有动态不确定性特征的医疗废物清运车辆路径问题模型。
[0093]
(2)设计了动态调度机制，能够根据实时清运请求情况或需求调整动态调整车辆的清运路径
附图说明
[0094]
图1为根据本发明一实施例的基于区间多目标混合蛙跳算法的医疗废物清运方法流程示意图；
[0095]
图2为根据本发明一实施例的超体积比率hvr上整体平均值mean和最佳值best的比较示意图；
[0096]
图3为根据本发明一实施例的反世代距离igd上整体平均值mean和最佳值best的比较示意图。
具体实施方式
[0097]
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。
[0098]
以下结合具体实施例对本发明的具体实现进行详细描述。
[0099]
实施例1
[0100]
第一方面，本实施例提供了一种基于区间多目标混合蛙跳算法的医疗废物清运方法，包括：
[0101]
获取初始清运请求和路况信息；
[0102]
在初始调度周期，基于初始清运请求和路况信息，采用区间多目标混合蛙跳算法对预构建的医疗废物清运路径规划模型进行求解，得到初始车辆清运路径；
[0103]
车辆按初始车辆清运路径进行垃圾采集，直至垃圾清运任务完成；
[0104]
若垃圾清运任务未完成且进入下一周期性调度时刻点，根据上一调度周期内获取的动态请求集合和所述医疗废物清运路径规划模型，采用结构重组法对初始车辆清运路径进行调整得到车辆清运子路径；从车场出发新车执行车辆清运子路径，直至完成垃圾清运任务。
[0105]
在一些实施例中，所述的基于区间多目标混合蛙跳算法的医疗废物清运方法，还包括：当周期性调度中发生动态事件请求时，采用动态响应机制更新车辆清运路径和动态请求集合；其中所述动态响应机制，包括：
[0106]
动态事件请求指的是调度过程中客户产生的请求，包括：新增的医疗机构医疗废物清运请求和客户的期望处理时间的调整；其中，新增的医疗机构医疗废物清运请求是指在调度过程中出现新的客户请求，包括新客户出现的时间、位置及其需求量；客户的期望处理时间的调整是指客户对医疗废物的期望处理时间主动请求提前或延误；
[0107]
判断能否处理该动态事件请求，若能，通过动态修补法将动态事件请求更新至已有路径中，车辆按更新后的路径继续行驶；否则，车辆按原路径继续行驶，并将请求放入动
态请求集合δh中，等待下一个周期性调度时刻点统一处理；
[0108]
其中，所述动态修补法包括：在时刻t(t∈[0,t])有新增的医疗机构hu的废物清运需求，则基于所述医疗废物清运路径规划模型将新增医疗机构插入到当前的清运路径中，以最大程度的减少路径的变动，从而适应医疗机构的动态需求。
[0109]
在一些具体实施例中，如图1所示，一种基于区间多目标混合蛙跳算法的医疗废物清运方法，具体包括以下步骤：
[0110]
s1，初始化清运请求和路况信息，清空动态请求集合；
[0111]
s2，考虑行驶速度的不确定性，建立医疗废物清运路径规划模型；
[0112]
s3，采用区间多目标混合蛙跳算法确定满足约束条件的初始车辆清运路径；
[0113]
s4，若垃圾清运任务没有完成，车辆按车辆清运路径进行垃圾采集，否则，输出车辆清运路径；
[0114]
s5，当清运车辆到达周期性调度时刻点时，则根据当前时刻产生的动态请求集合，采用结构重组法得到车辆清运子路径；从车场出发新车执行车辆清运子路径，更新车辆清运路径并清空动态请求集合，直至完成垃圾清运任务；当周期性调度中发生动态事件时，采用动态响应机制更新车辆清运路径和动态请求集合。
[0115]
在医疗废物清运车辆路径规划问题中，共有n家医疗机构hu，(u＝1,2,...,n)，m家废物处理站rq(q＝1,2,...,m)和1个车场d；车辆在初始时刻从车场出发，依次到各医疗机构收集废物，然后送至任意一个适当的废物处理站进行处理，最后返回车场结束任务；在清运过程中，车辆允许有多个行程，tripk为车辆k的行程集合，为车辆k的第w次行程，lk是车辆k的最后一个行程；医疗机构、废物处理站和车场的集合用v＝{h1,h2,...,hn,r1,...,rm,d}表示，这些地点之间的路径长度用边集e＝{(pi,pj)|pi,pj∈v,i≠j}表示，其中，pipj为车辆访问的节点，pipj∈h∪r∪{d}，h为医疗机构hu的集合，r为废物处理站rq的集合；考虑到道路路况的不确定性，对于每条边e
ij
，都有相对应的行驶速度的区间数其中v
ij
和分别代表车辆在边e
ij
的最小和最大行驶速度；工作时间段为[0,tm]，tm为最大工作时长；当周期性调度中发生动态事件时，t
l
(l＝1,2,...,|ts|)为周期性调度的调度时刻点，ts为调度时刻t
l
的集合(例如，周期为2小时，医疗机构上班时间从8点至16点，医疗废物清运从10点至16点，则ts＝{10,12,14,16})；而动态事件指的是调度过程中客户产生的请求，包括：新增的医疗机构医疗废物清运请求和客户的期望处理时间的调整；其中，新增的动态请求是指在调度过程中出现新的客户请求，包括新客户出现的时间、位置及其需求量等；客户的期望处理时间的调整是指客户对医疗废物的期望处理时间主动请求提前或延误。
[0116]
具体地，步骤s1中所述清运请求和路况信息包括医疗废物运输车辆需要访问的医疗机构数量、医疗机构坐标信息、医疗废物处理站坐标信息、车场坐标信息和期望处理时刻；动态请求集合存放的是调度过程中产生的动态请求，此类请求无法即时处理，而统一由下一个调度周期开始时刻进行处理。
[0117]
具体地，步骤s2中所述医疗废物清运路径规划模型包含三个强耦合的子问题：
[0118]
(1)多行程确定，在一个调度周期内，为每辆车确定行程数以及每个行程经过的医疗机构；
[0119]
(2)医疗机构分配，为医疗机构分配服务车辆；
[0120]
(3)车辆选择，按照废物清运路径选择车辆。
[0121]
具体地，子问题的调度由三个决策变量来表示：
[0122]
多行程确定
[0123]
医疗机构分配
[0124]
车辆选择
[0125]
具体地，步骤s2中所述医疗废物清运路径规划模型的目标函数是最小化调度成本和感染风险。
[0126]
(1)调度成本
[0127]
调度成本f1包括固定成本cost1、油耗成本cost2、加班成本cost3和污染成本cost4，它们的定义式分别是：
[0128][0129]
其中，k和k分别为车辆的索引和所有车辆的集合，cv表示调用一次车辆需要支出的司机报酬及启动成本；
[0130][0131]
其中，fc
ij
表示车辆通过路段e
ij
的油耗成本，αk和βk为路况和车辆的特征参数；q0，v
ij
和d
ij
分别为车辆净重(千克)、车辆负载(千克)、车辆的行驶速度(米/秒)和行驶距离(米)，dis
ij
为点pi到点pj的欧式距离(公里)，cf为燃油的价格(元/升)；
[0132][0133]
其中，co为加班工资(元/小时)，trk为车辆k最后一次行程返回车场的时刻；
[0134][0135]
其中，cp为污染成本(元/小时)，为车辆k到达点pj的时刻，etj为废物处理站的期望处理时刻。
[0136]
min f1＝cost1+cost2+cost3+cost4[0137]
(2)感染风险
[0138]
感染风险f2包括运输风险risk1和废物处理风险risk2，它们的定义分别是：
[0139]
[0140]
其中，为车辆从pi点到pj点花费的时间(小时)，为车辆k离开点pi时的载重(吨)，p
ij
为路径e
ij
附近的人口数量；
[0141][0142]
其中，r为废物处理站rj的集合，mj为废物处理站rj的废物处理量(吨)，vdj为废物处理站rj处理废物的速度(吨/小时)，为废物处理站rj附近的人口数量。
[0143]
min f2＝risk1+risk2[0144]
具体地，步骤s3中确定的初始车辆清运路径需要满足以下约束条件：
[0145]
(1)所有车辆的第一次行程均从车场出发，在服务完行程的最后一个医疗机构后，到达任意一个废物处理站卸料；
[0146][0147]
(2)车辆的下一次行程从当前行程运往的废物处理站出发；
[0148][0149]
(3)车辆最后一次行程在废物处理站卸料后，必须返回车场；
[0150][0151]
(4)车辆到达医疗机构hu后必须从hu离开，且该辆车至多只能到达和离开医疗机构hu一次；
[0152][0153][0154]
(5)服务某个医疗机构的车辆有且只有一辆；
[0155][0156]
(6)车辆每次行程运输的废物量不超过车辆容量；
[0157][0158]
(7)从车场出发的车辆数量不超过最大可用车辆数；
[0159][0160]
具体地，步骤s3中所述一种基于区间多目标混合蛙跳算法求解车辆清运路径的步骤如下：
[0161]
s301：初始化种群；
[0162]
s302：对种群进行区间非支配排序，并根据序值划分子组；
[0163]
s303：对每个子组通过基因重组和贪婪交叉策略生成新个体；
[0164]
s304：采用目标增强机制对非支配个体进行搜索；
[0165]
s305：筛选下一代种群；
[0166]
s306：判断是否达到最大目标评价次数，若达到，则终止，输出最优个体，对个体解码，解码后的路径即为医疗废物清运路径。否则，转步骤s302。
[0167]
具体地，步骤s303中所述对每个子组通过基因重组贪婪和交叉策略生成新个体包括：
[0168]
(1)贪婪交叉策略
[0169]
贪婪交叉策略是一种由出发点开始逐步构造路径的个体更新策略；基于贪心思想，在待交叉个体中，从与新个体起点相邻的医疗机构中选择最近的点作为新个体的下一个医疗机构，以保留交叉个体中的有效信息；通过重复执行贪婪选择步骤以生成完整的转运路径。
[0170]
(2)基因重组策略
[0171]
用上述贪婪交叉策略得到的优解替换差解，并对差解的编码进行调整，使得各医疗机构所在列的出发点和废物处理站与原编码一致，由此得到个体；然后，更新出发点。计算新个体每一列出发点到医疗机构的距离，选取距离最远的前rand1个出发点和医疗机构，其中，rand1为1到医疗机构数量n之间的随机数；用优解中医疗机构对应的出发点替换原有出发点；最后，以同样方式更新废物处理站。
[0172]
具体地，步骤s5中所述动态响应机制步骤如下：
[0173]
判断能否处理该请求，若能，通过动态修补法将新请求更新至已有路径中，车辆按更新后的路径继续行驶；否则，车辆按原路径继续行驶，并将请求放入动态请求集合δh中，等待下一个调度点统一处理。
[0174]
其中，动态修补法，即在时刻t(t∈[0,t])有新增的医疗机构hu的废物清运需求，则通过将新增医疗机构插入到当前的清运路径中，以最大程度的减少路径的变动，从而适应医疗机构的动态需求。
[0175]
具体地，步骤s5中所述结构重组法，包括如下步骤：
[0176]
首先，将动态请求集合中的医疗机构打乱，生成编码串；
[0177]
令当前最优解等于编码串，从优化算子o＝{2-opt,insert,exchange}中随机选择一种策略，对编码串进行优化生成解s；
[0178]
若解s区间支配编码串，则编码串等于解s；
[0179]
若解s支配最优解，则最优解等于s；
[0180]
当连续三次优化新解s无法支配编码串时，输出当前最优解。
[0181]
验证例
[0182]
以南京市鼓楼区、建邺区、秦淮区、栖霞区和玄武区5个区二级以上的医院为例，构建医疗废物清运动态车辆路径问题实例。五个区共59家医院，设置三个废物处理站。在初始时刻已得到40家医院的清运请求，其余19家医院的请求将随调度过程出现。此外，根据实际医疗废物清运过程的动态特性，从常用的cordeau-mdvrp测试集中选取了规模依次递增的6个仿真算例进行修改。其中站点数量、站点坐标等信息均与原测试集中的静态算例保持一致。假设上午7点开始工作，最大连续工作时间为4小时。新增医疗机构的位置随机生成，每个医疗机构的废物量(吨)在[0.5，2]上随机产生，其期望处理时间在工作时间内随机产生。并设置加班工资为20元/小时，污染成本为50元/小时，清运车辆的最大载重为2吨，固定成
本为100元/辆车，车辆在垃圾处理站的卸料时间为0.1小时。
[0183]
图2为根据本实施例的超体积比率hvr上整体平均值mean和最佳值best的比较示意图；
[0184]
图3为根据本实施例的反世代距离igd上整体平均值mean和最佳值best的比较示意图。
[0185]
本实施例采用多目标优化中常用的超体积比率hvr和反世代距离igd作为算法的评价指标。hvr越大，说明算法求得的pareto前沿收敛精度越高，且分布范围越广。igd越小，表示算法搜索到的pareto前沿收敛性和解分布的多样性越好。
[0186]
由图2～图3可知，与6种已有算法相比，区间多目标混合蛙跳算法的超体积比率hvr和反世代距离igd在所有算例上取得了最佳的整体最佳值best和整体平均值mean，统计测试结果也表明区间多目标算法显著优于对比算法。所提算法的优越性能得益于多个策略的综合应用，在个体更新阶段，基于贪心选择的思想和不定规模的启发式替换，提升了算法的探索能力。在目标增强阶段，采用优化目标驱动的增强的搜索机制，充分利用问题的启发信息，强化了算法的利用能力，从而使得算法在探索和利用之间达到平衡。
[0187]
本发明建立了医疗废物清运路径规划模型，该模型考虑了清运过程中产生的动态需求和车辆行驶速度的不确定性，在车辆容量和工作时间等约束下，通过优化车辆的清运路径，以最小化调度总成本和废物清运风险。为求解该模型，提出了一种基于区间多目标混合蛙跳算法的医疗废物清运方法。
[0188]
实施例2
[0189]
第二方面，基于实施例1，本实施例提供了一种基于区间多目标混合蛙跳算法的医疗废物清运装置，包括处理器及存储介质；
[0190]
所述存储介质用于存储指令；
[0191]
所述处理器用于根据所述指令进行操作以执行根据实施例1所述的方法。
[0192]
实施例3
[0193]
第三方面，基于实施例1，本实施例提供了一种设备，包括，
[0194]
存储器；
[0195]
处理器；
[0196]
以及
[0197]
计算机程序；
[0198]
其中，所述计算机程序存储在所述存储器中，并被配置为由所述处理器执行以实现实施例1所述的方法。
[0199]
实施例4
[0200]
第四方面，基于实施例1，本实施例提供了一种存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现实施例1所述的方法。
[0201]
本领域内的技术人员应明白，本技术的实施例可提供为方法、系统、或计算机程序产品。因此，本技术可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本技术可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、cd-rom、光学存储器等)上实施的计算机程序产品的形式。
[0202]
本技术是参照根据本技术实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0203]
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0204]
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0205]
尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。

技术特征：
1.一种基于区间多目标混合蛙跳算法的医疗废物清运方法，其特征在于，包括：获取初始清运请求和路况信息；在初始调度周期，基于初始清运请求和路况信息，采用区间多目标混合蛙跳算法对预构建的医疗废物清运路径规划模型进行求解，得到初始车辆清运路径；车辆按初始车辆清运路径进行垃圾采集，直至垃圾清运任务完成；若垃圾清运任务未完成且进入下一周期性调度时刻点，根据上一调度周期内获取的动态请求集合和所述医疗废物清运路径规划模型，采用结构重组法对初始车辆清运路径进行调整得到车辆清运子路径；从车场出发新车执行车辆清运子路径，直至完成垃圾清运任务。2.根据权利要求1所述的基于区间多目标混合蛙跳算法的医疗废物清运方法，其特征在于，还包括：当周期性调度中发生动态事件请求时，采用动态响应机制更新车辆清运路径和动态请求集合；其中所述动态响应机制，包括：动态事件请求指的是调度过程中客户产生的请求，包括：新增的医疗机构医疗废物清运请求和客户的期望处理时间的调整；其中，新增的医疗机构医疗废物清运请求是指在调度过程中出现新的客户请求，包括新客户出现的时间、位置及其需求量；客户的期望处理时间的调整是指客户对医疗废物的期望处理时间主动请求提前或延误；判断能否处理该动态事件请求，若能，通过动态修补法将动态事件请求更新至已有路径中，车辆按更新后的路径继续行驶；否则，车辆按原路径继续行驶，并将请求放入动态请求集合δh中，等待下一个周期性调度时刻点统一处理；其中，所述动态修补法包括：在时刻t(t∈[0,t])有新增的医疗机构h
u
的废物清运需求，则基于所述医疗废物清运路径规划模型将新增医疗机构插入到当前的清运路径中，以最大程度的减少路径的变动，从而适应医疗机构的动态需求。3.根据权利要求1所述的基于区间多目标混合蛙跳算法的医疗废物清运方法，其特征在于，所述初始清运请求和路况信息包括医疗废物运输车辆需要访问的医疗机构数量、医疗机构坐标信息、医疗废物处理站坐标信息、车场坐标信息和期望处理时刻；和/或，所述动态请求集合存放的是上一个调度周期过程中产生的动态请求，此类请求无法即时处理，而统一由下一个调度周期开始时刻进行处理，且将已完成的清运请求从动态请求集合中清除。4.根据权利要求1所述的基于区间多目标混合蛙跳算法的医疗废物清运方法，其特征在于，所述医疗废物清运路径规划模型包含三个强耦合的子问题：(1)多行程确定，在一个调度周期内，为每辆车确定行程数以及每个行程经过的医疗机构；(2)医疗机构分配，为医疗机构分配服务车辆；(3)车辆选择，按照废物清运路径选择车辆；子问题的调度由三个决策变量来表示：多行程确定医疗机构分配
车辆选择5.根据权利要求4所述的基于区间多目标混合蛙跳算法的医疗废物清运方法，其特征在于，在医疗废物清运路径规划问题中，共有n家医疗机构h
u
、m家废物处理站r
q
和1个车场d，其中u＝1,2,...,n，q＝1,2,...,m；车辆在初始时刻从车场出发，依次到各医疗机构收集废物，然后送至任意一个适当的废物处理站进行处理，最后返回车场结束任务；在清运过程中，车辆允许有多个行程，trip
k
为车辆k的行程集合，为车辆k的行程集合，为车辆k的第w次行程，l
k
是车辆k的最后一个行程；医疗机构、废物处理站和车场的集合用v＝{h1,h2,...,h
n
,r1,...,r
m
,d}表示，这些地点之间的路径长度用边集e＝{(p
i
,p
j
)p
i
,p
j
∈v,i≠j}表示，其中，p
i
p
j
为车辆访问的节点，p
i
p
j
∈h∪r∪{d}，h为医疗机构h
u
的集合，r为废物处理站r
q
的集合；考虑到道路路况的不确定性，对于每条边e
ij
，都有相对应的行驶速度的区间数其中v
ij
和分别代表车辆在边e
ij
的最小和最大行驶速度；工作时间段为[0,tm]，tm为最大工作时长；t
l
(l＝1,2,...,|t
s
|)为周期性调度的调度时刻点，t
s
为调度时刻t
l
的集合；所述医疗废物清运路径规划模型包括目标函数和约束条件；其中目标函数以最小化调度成本和感染风险为优化目标，表示为：min f1＝cost1+cost2+cost3+cost4min f2＝risk1+risk2其中调度成本f1包括固定成本cost1、油耗成本cost2、加班成本cost3和污染成本cost4；感染风险f2包括运输风险risk1和废物处理风险risk2；其中，z
k
表示车辆k选择是否被使用，k为所有车辆的集合，cv表示调用一次车辆需要支出的司机报酬及启动成本；其中，fc
ij
表示车辆通过路段e
ij
的油耗成本，α
k
和β
k
为路况和车辆的特征参数；q0，v
ij
和d
ij
分别为车辆净重、车辆负载、车辆的行驶速度和行驶距离，dis
ij
为点p
i
到点p
j
的欧式距离，cf为燃油的价格；x
ijkw
为车辆k的第w次行程从点p
i
到点p
j
；其中，co为加班工资，tr
k
为车辆k最后一次行程返回车场的时刻；其中，cp为污染成本，为车辆k到达点p
j
的时刻，et
j
为废物处理站的期望处理时刻；
其中，为车辆从p
i
点到p
j
点花费的时间，为车辆k离开点p
i
时的载重，p
ij
为路径e
ij
附近的人口数量；其中，r为废物处理站r
j
的集合，m
j
为废物处理站r
j
的废物处理量，vd
j
为废物处理站r
j
处理废物的速度，为废物处理站r
j
附近的人口数量。6.根据权利要求5所述的基于区间多目标混合蛙跳算法的医疗废物清运方法，其特征在于，所述医疗废物清运路径规划模型的约束条件包括：(1)所有车辆的第一次行程均从车场出发，在服务完行程的最后一个医疗机构后，到达任意一个废物处理站卸料；其中，x
uqkw
为车辆k的第w次行程从医疗机构h
u
到废物处理站r
q
；(2)车辆的下一次行程从当前行程运往的废物处理站出发；(3)车辆最后一次行程在废物处理站卸料后，必须返回车场；其中，x
qdklk
为车辆k的最后一次行程l
k
从废物处理站r
q
返回车场d；(4)车辆到达医疗机构h
u
后必须从h
u
离开，且该辆车至多只能到达和离开医疗机构h
u
一次；次；其中，x
jukw
为车辆k的第w次行程从点p
j
到医疗机构h
u
；x
ujkw
为车辆k的第w次行程从医疗机构h
u
到点p
j
；y
uk
为医疗机构h
u
由车辆k负责；(5)服务某个医疗机构的车辆有且只有一辆；(6)车辆每次行程运输的废物量不超过车辆容量q；其中，g
u
是医疗机构的垃圾清运量；(7)从车场出发的车辆数量不超过最大可用车辆数；
其中，x
dukw
为车辆k的第w次行程从车场d到医疗机构h
u
。7.根据权利要求1所述的基于区间多目标混合蛙跳算法的医疗废物清运方法，其特征在于，采用区间多目标混合蛙跳算法对预构建的医疗废物清运路径规划模型进行求解，包括：s301：初始化种群；s302：对种群进行区间非支配排序，并根据序值划分子组；s303：对每个子组通过基因重组和贪婪交叉策略生成新个体；s304：采用目标增强机制对非支配个体进行搜索；s305：筛选下一代种群；s306：判断是否达到最大目标评价次数，若达到，则终止，输出最优个体，对个体解码，解码后的路径即为医疗废物清运路径；否则，转步骤s302。8.根据权利要求7所述的基于区间多目标混合蛙跳算法的医疗废物清运方法，其特征在于，步骤s303中，所述对每个子组通过基因重组贪婪和交叉策略生成新个体，具体包括：(1)贪婪交叉策略贪婪交叉策略是一种由出发点开始逐步构造路径的个体更新策略；基于贪心思想，在待交叉个体中，从与新个体起点相邻的医疗机构中选择最近的点作为新个体的下一个医疗机构，以保留交叉个体中的有效信息；通过重复执行贪婪选择步骤以生成完整的转运路径；(2)基因重组策略用上述贪婪交叉策略得到的优解替换差解，并对差解的编码进行调整，使得各医疗机构所在列的出发点和废物处理站与原编码一致，由此得到个体；然后，更新出发点；计算新个体每一列出发点到医疗机构的距离，选取距离最远的前rand1个出发点和医疗机构，其中，rand1为1到医疗机构数量n之间的随机数；用优解中医疗机构对应的出发点替换原有出发；最后，以同样方式更新废物处理站。9.根据权利要求1所述的基于区间多目标混合蛙跳算法的医疗废物清运方法，其特征在于，根据上一调度周期内获取的动态请求集合和所述医疗废物清运路径规划模型，采用结构重组法对初始车辆清运路径进行调整得到车辆清运子路径，包括：将动态请求集合中的医疗机构打乱，生成编码串；从两元素优化算子、嵌入优化算子和交换优化算子中随机选择一种作为策略，根据所述医疗废物清运路径规划模型对所述编码串进行优化求解，得到调整后的最优车辆清运子路径。10.一种基于区间多目标混合蛙跳算法的医疗废物清运装置，其特征在于，包括处理器及存储介质；所述存储介质用于存储指令；所述处理器用于根据所述指令进行操作以执行根据权利要求1至9任一项所述的方法。

技术总结
本发明公开了一种基于区间多目标混合蛙跳算法的医疗废物清运方法，包括：获取初始清运请求和路况信息；在初始调度周期，基于初始清运请求和路况信息，采用区间多目标混合蛙跳算法对预构建的医疗废物清运路径规划模型进行求解，得到初始车辆清运路径；车辆按初始车辆清运路径进行垃圾采集，直至垃圾清运任务完成；若垃圾清运任务未完成且进入下一周期性调度时刻点，根据上一调度周期内获取的动态请求集合和所述医疗废物清运路径规划模型，采用结构重组法对初始车辆清运路径进行调整得到车辆清运子路径；从车场出发新车执行车辆清运子路径，直至完成垃圾清运任务。本发明降低了调度总成本和废物清运风险，提高了车辆的清运效率。率。率。


技术研发人员：申晓宁 毛鸣健 葛忠佩 许新苏
受保护的技术使用者：南京信息工程大学
技术研发日：2023.07.13
技术公布日：2023/9/26