基于量子遗传算法的垃圾运输路线优化方法及装置

摘要

本发明涉及路线规划技术领域，特别涉及一种基于量子遗传算法的垃圾运输路线优化方法及装置。方法包括：获取目标区域的目标数据；目标区域包括一个垃圾中转站和多个垃圾收集点，每个垃圾收集点的垃圾均由目标车场内的垃圾车运输至垃圾中转站，目标数据包括车辆数据、垃圾数据、道路数据、天气数据和人口数据；基于目标数据，构建以收运成本最小和居民厌恶指数最小为目标的垃圾运输路线的目标函数和相应的约束条件；基于约束条件，利用量子遗传算法对目标函数进行求解，得到垃圾运输的最优路线。本申请，可以得到兼顾经济性和居民体验的最优收运路线。

权利要求

1.一种基于量子遗传算法的垃圾运输路线优化方法，其特征在于，包括：

获取目标区域的目标数据；所述目标区域包括一个垃圾中转站和多个垃圾收集点，每个所述垃圾收集点的垃圾均由目标车场内的垃圾车运输至所述垃圾中转站，所述目标数据包括车辆数据、垃圾数据、道路数据、天气数据和人口数据；基于所述目标数据，构建以收运成本最小和居民厌恶指数最小为目标的垃圾运输路线的目标函数和相应的约束条件；

基于所述约束条件，利用量子遗传算法对所述目标函数进行求解，得到垃圾运输的最优路线；

所述收运成本包括固定成本和里程成本，所述收运成本a1的计算公式为：

式中，ag为垃圾车的固定成本，as表示垃圾车的单位距离成本，dij表示从i节点到j节点的距离，n表示节点的个数，所述节点包括所述垃圾中转站、每个所述垃圾收集点和所述目标车场；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点；

所述居民厌恶指数由拥堵厌恶指数和垃圾堆积厌恶指数构成，居民厌恶指数a2的计算公式为：式中，wij表示从i节点到j节点居民厌恶指数所占的权重，其值与从i节点到j节点的平均人流量相关；Tij为从i节点到j节点的交通拥堵厌恶指数；Sj为j节点的垃圾堆积厌恶指数，Tij∈（0,1），Sj∈（0,1）；yj表示j节点垃圾堆积厌恶指数所占的权重，yj∈（0,1）；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点；

所述目标函数是对收运成本最小目标和居民厌恶指数最小目标进行加权计算得到的，所述目标函数为：式中，b1和b2分别为收运成本最小目标和居民厌恶指数最小目标的权重；ag为垃圾车的固定成本，as表示垃圾车的单位距离成本，dij表示从i节点到j节点的距离，n表示节点的个数，所述节点包括所述垃圾中转站、每个所述垃圾收集点和所述目标车场；wij表示从i节点到j节点居民厌恶指数所占的权重，其值与从i节点到j节点的平均人流量相关；Tij为从i节点到j节点的交通拥堵厌恶指数；Sj为j节点的垃圾堆积厌恶指数，Tij∈（0,1），Sj∈（0,1）；yj表示j节点垃圾堆积厌恶指数所占的权重，yj∈（0,1）；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点；

将目标区域的运输路线划分为三个子阶段，针对每个子阶段均执行：基于所述目标数据调整当前子阶段对应的目标函数中各目标的权重；利用量子遗传算法对当前子阶段的目标函数进行求解，得到当前子阶段的最优子路线；将每个所述最优子路线进行组合，得到所述目标区域的最优路线；

将所述目标区域的运输路线划分为三个子阶段的方法为：

将从所述目标车场至任一垃圾收集点的路线划分为第一阶段；将任意两个垃圾收集点之间的路线以及任一垃圾收集点至所述垃圾中转站的路线划分为第二阶段；将从所述垃圾中转站至所述目标车场的路线划分为第三阶段。

2.根据权利要求1所述的方法，其特征在于，所述约束条件为：

垃圾车在任一节点的载重均不超过其额定载重；

垃圾车在单次行程中去往任一垃圾收集点的次数不超过1次；

任一垃圾收集点的垃圾清理时限均不超过预设时限；

垃圾车从i节点到j节点的运行时长不超过预设时长。

3.根据权利要求1所述的方法，其特征在于，所述利用量子遗传算法对所述目标函数进行求解，得到垃圾运输的最优路线，包括：S1，初始化初代种群，随机生成多个以量子比特为编码的染色体；

S2，对种群中的每个个体进行一次测量，得到对应的确定解；

S3，将所述目标函数作为适应度函数，对各确定解进行适应度评估；

S4，记录最优个体和对应的适应度；

S5，判断计算过程是否满足结束条件，若是，则解码生成最优路线，若否，则执行步骤S6；

S6，利用量子旋转门对当前种群进行更新，将更新后的种群作为新的种群，并执行步骤S2，直至满足结束条件。

4.一种基于量子遗传算法的垃圾运输路线优化装置，其特征在于，包括：

获取模块，用于获取目标区域的目标数据；所述目标区域包括一个垃圾中转站和多个垃圾收集点，每个所述垃圾收集点的垃圾均由目标车场内的垃圾车运输至所述垃圾中转站，所述目标数据包括车辆数据、垃圾数据、道路数据、天气数据和人口数据；

构建模块，用于基于所述目标数据，构建以收运成本最小和居民厌恶指数最小为目标的垃圾运输路线的目标函数和相应的约束条件；

求解模块，用于基于所述约束条件，利用量子遗传算法对所述目标函数进行求解，得到垃圾运输的最优路线；

构建模块中的收运成本包括固定成本和里程成本，收运成本a1的计算公式为：

式中，ag为垃圾车的固定成本，as表示垃圾车的单位距离成本，dij表示从i节点到j节点的距离，n表示节点的个数，节点包括垃圾中转站、每个垃圾收集点和目标车场；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点；

构建模块中的居民厌恶指数由拥堵厌恶指数和垃圾堆积厌恶指数构成，居民厌恶指数a2的计算公式为：式中，wij表示从i节点到j节点居民厌恶指数所占的权重，其值与从i节点到j节点的平均人流量相关；Tij为从i节点到j节点的交通拥堵厌恶指数；Sj为j节点的垃圾堆积厌恶指数，Tij∈（0,1），Sj∈（0,1）；yj表示j节点垃圾堆积厌恶指数所占的权重，yj∈（0,1）；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点；

构建模块构建的目标函数是对收运成本最小目标和居民厌恶指数最小目标进行加权计算得到的，目标函数为：式中，b1和b2分别为收运成本最小目标和居民厌恶指数最小目标的权重；ag为垃圾车的固定成本，as表示垃圾车的单位距离成本，dij表示从i节点到j节点的距离，n表示节点的个数，节点包括垃圾中转站、每个垃圾收集点和目标车场；wij表示从i节点到j节点居民厌恶指数所占的权重，其值与从i节点到j节点的平均人流量相关；Tij为从i节点到j节点的交通拥堵厌恶指数；Sj为j节点的垃圾堆积厌恶指数，Tij∈（0,1），Sj∈（0,1）；yj表示j节点垃圾堆积厌恶指数所占的权重，yj∈（0,1）；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点；

所述获取模块还用于执行：将目标区域的运输路线划分为三个子阶段，针对每个子阶段均执行：基于所述目标数据调整当前子阶段对应的目标函数中各目标的权重；利用量子遗传算法对当前子阶段的目标函数进行求解，得到当前子阶段的最优子路线；将每个所述最优子路线进行组合，得到所述目标区域的最优路线；将所述目标区域的运输路线划分为三个子阶段的方法为：将从所述目标车场至任一垃圾收集点的路线划分为第一阶段；将任意两个垃圾收集点之间的路线以及任一垃圾收集点至所述垃圾中转站的路线划分为第二阶段；将从所述垃圾中转站至所述目标车场的路线划分为第三阶段。

5.一种电子设备，包括存储器和处理器，所述存储器中存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时，实现如权利要求1‑3中任一项所述的方法。

6.一种存储介质，其上存储有计算机程序，其特征在于，当所述计算机程序在计算机中执行时，令计算机执行权利要求1‑3中任一项所述的方法。

说明书

基于量子遗传算法的垃圾运输路线优化方法及装置

技术领域

[0001] 本发明涉及路线规划技术领域，特别涉及一种基于量子遗传算法的垃圾运输路线优化方法及装置。

背景技术

[0002] 随着城市化进程的加快和人口的增长，城市生活垃圾所造成的社会和环境影响日益受到人们的重视，如何对日益增长的城市生活垃圾进行高效收集和运输，已经成为亟待解决的现实问题。

[0003] 相关技术中，城市生活垃圾的收运路线规划主要考虑垃圾的收运成本，只注重经济效益，而未考虑在收运过程中由于线路规划不合理导致的某些垃圾收集点垃圾堆积、运输过程导致的交通拥堵以及散发气味对居民的影响。

[0004] 因此，目前亟待需要一种基于量子遗传算法的垃圾运输路线优化方法及装置来解决上述技术问题。

发明内容

[0005] 本发明实施例提供了一种基于量子遗传算法的垃圾运输路线优化方法及装置，可以得到兼顾经济性和居民体验的最优收运路线。

[0006] 第一方面，本发明实施例提供了一种基于量子遗传算法的垃圾运输路线优化方法，包括：

[0007] 获取目标区域的目标数据；所述目标区域包括一个垃圾中转站和多个垃圾收集点，每个所述垃圾收集点的垃圾均由目标车场内的垃圾车运输至所述垃圾中转站，所述目标数据包括车辆数据、垃圾数据、道路数据、天气数据和人口数据；

[0008] 基于所述目标数据，构建以收运成本最小和居民厌恶指数最小为目标的垃圾运输路线的目标函数和相应的约束条件；

[0009] 基于所述约束条件，利用量子遗传算法对所述目标函数进行求解，得到垃圾运输的最优路线。

[0010] 在一些实施方式中，所述收运成本包括固定成本和里程成本，所述收运成本的计算公式为：

[0011]

[0012] 式中， 为垃圾车的固定成本， 表示垃圾车的单位距离成本，dij表示从i节点到j节点的距离，n表示节点的个数，所述节点包括所述垃圾中转站、每个所述垃圾收集点和所述目标车场；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点。

[0013] 在一些实施方式中，所述居民厌恶指数由拥堵厌恶指数和垃圾堆积厌恶指数构成，居民厌恶指数 的计算公式为：

[0014]

[0015] 式中，wij表示从i节点到j节点居民厌恶指数所占的权重，其值与从i节点到j节点的平均人流量相关；Tij为从i节点到j节点的交通拥堵厌恶指数；Sj为j节点的垃圾堆积厌恶指数，Tij∈（0,1），Sj∈（0,1）；yj表示j节点垃圾堆积厌恶指数所占的权重，yj∈（0,1）；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点。

[0016] 在一些实施方式中，所述目标函数是对收运成本最小目标和居民厌恶指数最小目标进行加权计算得到的，所述目标函数为：

[0017]

[0018] 式中，b1和b2分别为收运成本最小目标和居民厌恶指数最小目标的权重； 为垃圾车的固定成本， 表示垃圾车的单位距离成本，dij表示从i节点到j节点的距离，n表示节点的个数，所述节点包括所述垃圾中转站、每个所述垃圾收集点和所述目标车场；wij表示从i节点到j节点居民厌恶指数所占的权重，其值与从i节点到j节点的平均人流量相关；Tij为从i节点到j节点的交通拥堵厌恶指数；Sj为j节点的垃圾堆积厌恶指数，Tij∈（0,1），Sj∈（0,1）；yj表示j节点垃圾堆积厌恶指数所占的权重，yj∈（0,1）；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点。

[0019] 在一些实施方式中，所述约束条件为：

[0020] 垃圾车在任一节点的载重均不超过其额定载重；

[0021] 垃圾车在单次行程中去往任一收集点的次数不超过1次；

[0022] 任一垃圾收集点的垃圾清理时限均不超过预设时限；

[0023] 垃圾车从i节点到j节点的运行时长不超过预设时长。

[0024] 在一些实施方式中，所述利用量子遗传算法对所述目标函数进行求解，得到垃圾运输的最优路线，包括：

[0025] S1，初始化初代种群，随机生成多个以量子比特为编码的染色体；

[0026] S2，对种群中的每个个体进行一次测量，得到对应的确定解；

[0027] S3，将所述目标函数作为适应度函数，对各确定解进行适应度评估；

[0028] S4，记录最优个体和对应的适应度；

[0029] S5，判断计算过程是否满足结束条件，若是，则解码生成最优路线，若否，则执行步骤S6；

[0030] S6，利用量子旋转门对当前种群进行更新，将更新后的种群作为新的种群，并执行步骤S2，直至满足结束条件。

[0031] 第二方面，本发明实施例还提供了一种基于量子遗传算法的垃圾运输路线优化装置，包括：

[0032] 获取模块，用于获取目标区域的目标数据；所述目标区域包括一个垃圾中转站和多个垃圾收集点，每个所述垃圾收集点的垃圾均由目标车场内的垃圾车运输至所述垃圾中转站，所述目标数据包括车辆数据、垃圾数据、道路数据、天气数据和人口数据；

[0033] 构建模块，用于基于所述目标数据，构建以收运成本最小和居民厌恶指数最小为目标的垃圾运输路线的目标函数和相应的约束条件；

[0034] 求解模块，用于基于所述约束条件，利用量子遗传算法对所述目标函数进行求解，得到垃圾运输的最优路线。

[0035] 第三方面，本发明实施例还提供了一种电子设备，包括存储器和处理器，所述存储器中存储有计算机程序，所述处理器执行所述计算机程序时，实现本说明书任一实施例所述的方法。

[0036] 第四方面，本发明实施例还提供了一种计算机可读存储介质，其上存储有计算机程序，当所述计算机程序在计算机中执行时，令计算机执行本说明书任一实施例所述的方法。

[0037] 本发明实施例提供了一种基于量子遗传算法的垃圾运输路线优化方法及装置。该方法首先确定路线规划的目标区域，该目标区域内存在多个垃圾收集点和一个中转站，每个垃圾收集点的垃圾均由目标车场内的垃圾车输运至该中转站。然后获取该目标区域的目标数据，包括历史数据和实时数据，通过该目标数据可以预测各垃圾收集点的垃圾产生速度、运输过程中的天气情况和路况，包括人流量和车流量等。基于该目标数据，构建以运输成本最小和居民厌恶指数最小为目标的目标函数，如此，在规划运输路线时，不仅只考虑经济效益，还能将对居民生活的影响降到最低，在保证运输成本满足要求的情况下，提高居民体验，降低投诉率。此外，通过量子遗传算法对目标函数进行求解，可以提高路线规划的速度和准确性。

附图说明

[0038] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0039] 图1是本发明一实施例提供的一种基于量子遗传算法的垃圾运输路线优化方法流程图；

[0040] 图2是本发明一实施例提供的一种电子设备的硬件架构图；

[0041] 图3是本发明一实施例提供的一种基于量子遗传算法的垃圾运输路线优化装置结构图。

具体实施方式

[0042] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例，基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0043] 现有技术中，通常使用垃圾车将各垃圾收集点的垃圾运输至垃圾中转站，然后再由大型的专用垃圾车将垃圾运输至集中处理中心进行集中处理。目前，在垃圾运输的路线选择时，运输公司主要考虑自身的运输成本，以期达到收运成本最低。然而生活垃圾存在很多危害，一方面，生活垃圾长时间堆放后会造成垃圾腐烂霉变，释放出大量有害气体，粉尘和细小颗粒物随风飞扬，危害周围大气环境。另一方面，虽然现有垃圾车具有一定密闭性，但随着车辆使用年限的增长以及司机操作不当，运输过程中仍存在泄露问题，从而散发出有害物质，给运输途中的行人造成影响。基于上述原因，当车辆以运输成本最小作为目标选择路线时，往往会给居民的生活造成不便，例如为了缩短车程，走距离较近但人流量较大的路线，使人们吸入不健康气体的概率增大；亦或者某些垃圾收集点的垃圾量较少，车辆会选择避开该收集点，造成该部分的垃圾清理不及时，给附近居民的生活造成不便。据投诉中心统计，近年来由于垃圾收运问题导致的投诉率逐年增高，可见，垃圾收运不能只考虑经济问题，而是要以人为本，结合居民的需求综合规划，在保证运输成本满足要求的情况下，提高居民体验，降低投诉率。

[0044] 基于上述问题，发明人提出可以将收运成本最小和居民厌恶指数最小为综合目标，基于综合目标构建垃圾运输路线的目标函数，然后通过量子遗传算法求解该目标函数，得出能够均衡运输成本和居民体验的最优路线。

[0045] 请参考图1，本发明实施例提供了一种基于量子遗传算法的垃圾运输路线优化方法，包括：

[0046] 步骤100，获取目标区域的目标数据；所述目标区域包括一个垃圾中转站和多个垃圾收集点，每个所述垃圾收集点的垃圾均由目标车场内的垃圾车运输至所述垃圾中转站，所述目标数据包括车辆数据、垃圾数据、道路数据、天气数据和人口数据；

[0047] 步骤102，基于所述目标数据，构建以收运成本最小和居民厌恶指数最小为目标的垃圾运输路线的目标函数和相应的约束条件；

[0048] 步骤104，基于所述约束条件，利用量子遗传算法对所述目标函数进行求解，得到垃圾运输的最优路线。

[0049] 本发明实施例中，垃圾的收运是以特定区域为研究对象，首先确定路线规划的目标区域，该目标区域内存在多个垃圾收集点和一个中转站，每个垃圾收集点的垃圾均由目标车场内的垃圾车输运至该中转站。然后获取该目标区域的目标数据，包括历史数据和实时数据，通过该目标数据可以预测各垃圾收集点的垃圾产生速度、运输过程中的天气情况和路况（如人流量和车流量）等。基于该目标数据，构建以运输成本最小和居民厌恶指数最小为目标的目标函数，如此，在规划运输路线时，不仅只考虑经济效益，还能将对居民生活的影响降到最低，在保证运输成本满足要求的情况下，提高居民体验，降低投诉率。此外，通过量子遗传算法对目标函数进行求解，可以提高路线规划的速度和准确性。

[0050] 下面描述图1所示的各个步骤的执行方式。

[0051] 首先，针对步骤100，获取目标区域的目标数据；目标区域包括一个垃圾中转站和多个垃圾收集点，每个垃圾收集点的垃圾均由目标车场内的垃圾车运输至垃圾中转站，目标数据包括车辆数据、垃圾数据、道路数据、天气数据和人口数据。

[0052] 在该步骤中，目标区域以实际运行区域为准，例如可以是一个县级行政区，在该行政区内，所有垃圾收集点的垃圾均通过某个目标车场的垃圾车运输至特定的中转站。目标区域确定后，可以通过相关部门获取与该目标区域相关的数据。例如，可以从目标车场获取垃圾车的类型、使用年限、最大载荷以及油耗等、从交通部门获取不同时段、不同路段的交通拥堵状态和平均人流量等、从环保部门获取各垃圾收集点的历史垃圾类型以及垃圾产生速度等、从气象部门获取实时的天气状况以及从人口统计局获取各垃圾收集点的人口分布情况等。此外，通过地图定位功能，垃圾中转站、目标车场以及每个垃圾收集点的位置都是已知的。

[0053] 然后，针对步骤102，基于目标数据，构建以收运成本最小和居民厌恶指数最小为目标的垃圾运输路线的目标函数和相应的约束条件。

[0054] 在该步骤中，收运成本主要由固定成本和里程成本构成。其中，固定成本主要由司机和工作人员的工资组成。里程成本主要由油费、维修费和折旧费组成，对于确定的垃圾车，其车辆类型、使用年限是已知的，因此，相应的油费、维修费和折旧费也是可预估的，因此，可以根据这些费用折算出垃圾车的单位距离成本。

[0055] 在一些实施方式中，收运成本 的计算公式为：

[0056]

[0057] 式中， 为垃圾车的固定成本， 表示垃圾车的单位距离成本，dij表示从i节点到j节点的距离，n表示节点的个数，节点包括垃圾中转站、每个垃圾收集点和目标车场；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点。

[0058] 在该实施中，虽然在目标区域内存在多个垃圾收集点，但是垃圾车在单次行程中不会途径每个垃圾收集点，而是结合自身承载能力、各节点之间的距离以及人口数据等选择最佳的收集点。途经的收集点不同，垃圾车行驶的距离也不同，产生的单位距离成本也不同。因此，收运成本是根据收运路线的不同而变动的，路线优化就是为了找出使收运成本最小的路线。

[0059] 然而，随着人们对生活质量要求的提高，垃圾收运不能仅以经济成本最小为目标，而要同时考虑收运过程对居民的影响。例如，将居民厌恶指数最小作为路线优化目标。

[0060] 在一些实施方式中，居民厌恶指数由拥堵厌恶指数和垃圾堆积厌恶指数构成，居民厌恶指数 的计算公式为：

[0061]

[0062] 式中，wij表示从i节点到j节点居民厌恶指数所占的权重，其值与从i节点到j节点的平均人流量相关；Tij为从i节点到j节点的交通拥堵厌恶指数；Sj为j节点的垃圾堆积厌恶指数，Tij∈（0,1），Sj∈（0,1）；yj表示j节点垃圾堆积厌恶指数所占的权重，yj∈（0,1）；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点。

[0063] 在该实施例中，wij是基于i节点与j节点之间的平均人流量确定的，平均人流量是基于历史交通数据确定的。根据历史交通数据，将平均人流量划分为多个等级，不同等级对应不同的权重，根据i节点与j节点之间的平均人流量与每个等级的包含关系，确定wij的数值。例如，平均人流量共有5个等级，A等级的平均人流量为大于200人/分钟，权重为0.8；B等级的平均人流量为150‑200人/分钟，权重为0.7；C等级的平均人流量为100‑150人/分钟，权重为0.6；D等级的平均人流量为50‑100人/分钟，权重为0.4；E等级的平均人流量为0‑50人/分钟，权重为0.2。那么，当根据历史交通数据确定出相同时刻从1节点到2节点的平均人流量为80人/分钟，其值位于D等级的区间内，则w12=0.4；从2节点到4节点的平均人流量为220人/分钟，其值位于A等级的区间内，则w24=0.8；依此类推，可以确定任意两个节点之间居民厌恶指数所占的权重。需要说明的是，平均人流量与时段相关，用户可以根据垃圾车的实际收运时段，调取对应时段的平均人流量。

[0064] 交通厌恶指数Tij是基于i节点与j节点之间的平均拥堵时间确定的，平均拥堵时间是基于历史交通数据确定的。根据历史交通数据，将平均拥堵时间划分为多个等级，不同等级对应不同的权重，根据i节点与j节点之间的平均拥堵时间与每个等级的包含关系，确定Tij的数值。例如，平均拥堵时间共有5个等级，A等级的平均拥堵时间大于8分钟，权重为0.8；B等级的平均拥堵时间为6‑8分钟，权重为0.7；C等级的平均拥堵时间为4‑6分钟，权重为
0.6；D等级的平均拥堵时间为2‑4分钟，权重为0.4；E等级的平均拥堵时间为0‑2分钟，权重为0.2。那么，当根据历史交通数据确定出相同时刻从1节点到2节点的平均拥堵时间为6分钟，其值位于B等级的区间内，则T12=0.7；从2节点到4节点的平均拥堵时间为1分钟，其值位于E等级的区间内，则T24=0.2；依此类推，可以确定任意两个节点之间居民厌恶指数所占的权重。需要说明的是，平均拥堵时间与时段相关，用户可以根据垃圾车的实际收运时段，调取对应时段的平均拥堵时间。

[0065] 垃圾堆积厌恶指数Sj是基于垃圾的清理实效确定的，垃圾的剩余量越大，清理时限越长，堆积厌恶指数越大。用户可以基于各垃圾收集点的历史数据为各垃圾收集点确定相应的堆积厌恶指数。

[0066] 此外，yj的权重与垃圾收集点的位置有关，垃圾收集点的位置距离人群聚集地越远，yj的权重小，反之越大。

[0067] 在一些实施方式中，目标函数是对收运成本最小目标和居民厌恶指数最小目标进行加权计算得到的，目标函数为：

[0068]

[0069] 式中，b1和b2分别为收运成本最小目标和居民厌恶指数最小目标的权重； 为垃圾车的固定成本， 表示垃圾车的单位距离成本，dij表示从i节点到j节点的距离，n表示节点的个数，节点包括垃圾中转站、每个垃圾收集点和目标车场；wij表示从i节点到j节点居民厌恶指数所占的权重，其值与从i节点到j节点的平均人流量相关；Tij为从i节点到j节点的交通拥堵厌恶指数；Sj为j节点的垃圾堆积厌恶指数，Tij∈（0,1），Sj∈（0,1）；yj表示j节点垃圾堆积厌恶指数所占的权重，yj∈（0,1）；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点。

[0070] 在该实施例中，b1和b2的取值是基于收运公司的效益和社会效益综合确定的，在确定二者的权重时，要保证收运公司的盈利阈值。此外，b1和b2的取值与季节相关，例如，夏季温度较高，垃圾霉变腐烂的过程较快，这时垃圾堆积散发的气味以及运输途中散发的气味较重，此时应该将b2的取值适当增大。而冬季气温较低，垃圾霉变速度变、气味小，则可以适当降低b2的权重。实际应用中，用户可以根据天气状况、运输公司的运营情况和社会因素调整两个目标之间的权重。

[0071] 还需要说明的是，垃圾车上设置有实时通讯系统，基于该通讯系统，待优化的垃圾车可以与目标区域的其它垃圾车通讯，并且可以实时获取目标区域内的交通数据（包括人流量、车流量和道路情况等）、垃圾数据（包括各垃圾收集点的位置和垃圾量）和天气数据等。用户可以根据实时获取的数据，调整目标函数中的各参数，并将计算出的最优路线实时反馈给司机。

[0072] 在一些实施方式中，在对目标函数进行求解时，需要制定相应的约束条件，包括：

[0073] 垃圾车在任一节点的载重均不超过其额定载重；

[0074] 垃圾车在单次行程中去往任一收集点的次数不超过1次；

[0075] 任一垃圾收集点的垃圾清理时限均不超过预设时限；

[0076] 垃圾车从i节点到j节点的运行时长不超过预设时长。

[0077] 基于上述约束条件对目标函数进行求解，可以得出满足要求的最优路线。当然，用户也可以根据要求增加更多约束，如垃圾车的负荷不能低于最小阈值等，基于不同的约束，可以得到不同的结果。

[0078] 最后，针对步骤104，基于约束条件，利用量子遗传算法对目标函数进行求解，得到垃圾运输的最优路线，包括：

[0079] S1，初始化初代种群，随机生成多个以量子比特为编码的染色体；

[0080] S2，对种群中的每个个体进行一次测量，得到对应的确定解；

[0081] S3，将目标函数作为适应度函数，对各确定解进行适应度评估；

[0082] S4，记录最优个体和对应的适应度；

[0083] S5，判断计算过程是否满足结束条件，若是，则解码生成最优路线，若否，则执行步骤S6；

[0084] S6，利用量子旋转门对当前种群进行更新，将更新后的种群作为新的种群，并执行步骤S2，直至满足结束条件。

[0085] 在该实施例中，通过量子遗传算法对目标函数进行求解，可以提高路线规划的速度和准确性。

[0086] 需要说明的是，当确定好数学模型后，如何建立初代种群，以及如何利用量子遗传算法对初代种群进行更新求解是本领域技术人员的公知常识，本申请不再赘述。

[0087] 上述实施例是将垃圾车从目标车场出发，途经多个垃圾收集点和垃圾中转站后再返回目标车场作为一个整体进行路线规划。而未考虑垃圾车状态的改变以及路况的差异对路线的影响。

[0088] 因此，在一些实施方式中，还可以将目标区域的运输路线划分为多个子阶段，针对每个子阶段均执行：

[0089] 基于所述目标数据调整当前子阶段对应的目标函数中各目标的权重；

[0090] 利用量子遗传算法对当前子阶段的目标函数进行求解，得到当前子阶段的最优子路线。最后，再将每个所述最优子路线进行组合，得到所述目标区域的最优路线。

[0091] 在一些实施方式中，子阶段的数量为三个，将所述目标区域的运输路线划分为三个子阶段的方法为：

[0092] 将从所述目标车场至任一垃圾收集点的路线划分为第一阶段；

[0093] 将任意两个垃圾收集点之间的路线以及任一垃圾收集点至所述垃圾中转站的路线划分为第二阶段；

[0094] 将从所述垃圾中转站至所述目标车场的路线划分为第三阶段。

[0095] 在第一阶段，垃圾车通常以空车状态从目标车场去往垃圾收集点，由于垃圾车内没有垃圾，因此基本不会散发有害气体，对居民造成的影响相对较小，此时主要考虑经济指标以及各垃圾点的垃圾量。因此，该阶段可以适当增大b1的权重，降低b2的权重。

[0096] 在第二阶段，垃圾车内已经装载有部分垃圾，此时需要结合垃圾车本身的密封性、垃圾的类别和路况等确定运输过程散发的气味对居民的影响，拥堵时间越长，给途经路线的行人造成的影响越大，此时需要避开平均人流量大的区间，适当降低一些经济指标。因此，该阶段可以适当降低b1的权重，而增大b2的权重。

[0097] 在第三阶段，垃圾车已经将运输的垃圾全部卸载至垃圾中转站，处于空车状态，气味较小且不再需要考虑各垃圾收集点的垃圾量，此时可以将尽快返回目标车场作为主要考虑因素。因此，该阶段可以将b1的权重设置为最大。

[0098] 该实施例通过将路线分段优化，可以有效提高路线规划的合理性。

[0099] 最后，将每个最优子路线进行组合，得到目标区域的最优路线。具体方法为：将第一子阶段的末端节点作为第二子阶段的起点，将第二子阶段的末端节点作为第三子阶段的起点，以此类推，即可得到最优路线。

[0100] 需要说明的是，每个子阶段的初代种群为能够连接该子阶段中起始节点和末端节点的全部可行路线。此外，利用量子遗传算法对当前子阶段的目标函数进行求解，得到当前子阶段的最优子路线的方法，与利用量子遗传算法对全程目标函数的求解方法相同，此处不再进行赘述。

[0101] 如图2、图3所示，本发明实施例提供了一种基于量子遗传算法的垃圾运输路线优化装置。装置实施例可以通过软件实现，也可以通过硬件或者软硬件结合的方式实现。从硬件层面而言，如图2所示，为本发明实施例提供的一种基于量子遗传算法的垃圾运输路线优化装置所在电子设备的一种硬件架构图，除了图2所示的处理器、内存、网络接口、以及非易失性存储器之外，实施例中装置所在的电子设备通常还可以包括其他硬件，如负责处理报文的转发芯片等等。以软件实现为例，如图3所示，作为一个逻辑意义上的装置，是通过其所在电子设备的CPU将非易失性存储器中对应的计算机程序读取到内存中运行形成的。本实施例提供的一种基于量子遗传算法的垃圾运输路线优化装置，包括：

[0102] 获取模块300，用于获取目标区域的目标数据；目标区域包括一个垃圾中转站和多个垃圾收集点，每个垃圾收集点的垃圾均由目标车场内的垃圾车运输至垃圾中转站，目标数据包括车辆数据、垃圾数据、道路数据、天气数据和人口数据；

[0103] 构建模块302，用于基于目标数据，构建以收运成本最小和居民厌恶指数最小为目标的垃圾运输路线的目标函数和相应的约束条件；

[0104] 求解模块304，用于基于约束条件，利用量子遗传算法对目标函数进行求解，得到垃圾运输的最优路线。

[0105] 在本发明实施例中，获取模块300可用于执行上述方法实施例中的步骤100，构建模块302可用于执行上述方法实施例中的步骤102，求解模块304可用于执行上述方法实施例中的步骤104。

[0106] 在一些实施方式中，构建模块302中的收运成本包括固定成本和里程成本，收运成本 的计算公式为：

[0107]

[0108] 式中， 为垃圾车的固定成本， 表示垃圾车的单位距离成本，dij表示从i节点到j节点的距离，n表示节点的个数，节点包括垃圾中转站、每个垃圾收集点和目标车场；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点。

[0109] 构建模块302中的居民厌恶指数由拥堵厌恶指数和垃圾堆积厌恶指数构成，居民厌恶指数 的计算公式为：

[0110]

[0111] 式中，wij表示从i节点到j节点居民厌恶指数所占的权重，其值与从i节点到j节点的平均人流量相关；Tij为从i节点到j节点的交通拥堵厌恶指数；Sj为j节点的垃圾堆积厌恶指数，Tij∈（0,1），Sj∈（0,1）；yj表示j节点垃圾堆积厌恶指数所占的权重，yj∈（0,1）；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点。

[0112] 构建模块302构建的目标函数是对收运成本最小目标和居民厌恶指数最小目标进行加权计算得到的，目标函数为：

[0113]

[0114] 式中，b1和b2分别为收运成本最小目标和居民厌恶指数最小目标的权重； 为垃圾车的固定成本， 表示垃圾车的单位距离成本，dij表示从i节点到j节点的距离，n表示节点的个数，节点包括垃圾中转站、每个垃圾收集点和目标车场；wij表示从i节点到j节点居民厌恶指数所占的权重，其值与从i节点到j节点的平均人流量相关；Tij为从i节点到j节点的交通拥堵厌恶指数；Sj为j节点的垃圾堆积厌恶指数，Tij∈（0,1），Sj∈（0,1）；yj表示j节点垃圾堆积厌恶指数所占的权重，yj∈（0,1）；Zij∈{0,1}，其中，Zij=1表示垃圾车从i节点移动到j节点，Zij=0表示垃圾车未从i节点移动到j节点。

[0115] 在一些实施方式中，构建模块302中的约束条件为：

[0116] 垃圾车在任一节点的载重均不超过其额定载重；

[0117] 垃圾车在单次行程中去往任一收集点的次数不超过1次；

[0118] 任一垃圾收集点的垃圾清理时限均不超过预设时限；

[0119] 垃圾车从i节点到j节点的运行时长不超过预设时长。

[0120] 在一些实施方式中，求解模块304用于执行如下操作：

[0121] S1，初始化初代种群，随机生成多个以量子比特为编码的染色体；

[0122] S2，对种群中的每个个体进行一次测量，得到对应的确定解；

[0123] S3，将目标函数作为适应度函数，对各确定解进行适应度评估；

[0124] S4，记录最优个体和对应的适应度；

[0125] S5，判断计算过程是否满足结束条件，若是，则解码生成最优路线，若否，则执行步骤S6；

[0126] S6，利用量子旋转门对当前种群进行更新，将更新后的种群作为新的种群，并执行步骤S2，直至满足结束条件。

[0127] 可以理解的是，本发明实施例示意的结构并不构成对一种基于量子遗传算法的垃圾运输路线优化装置的具体限定。在本发明的另一些实施例中，一种基于量子遗传算法的垃圾运输路线优化装置可以包括比图示更多或者更少的部件，或者组合某些部件，或者拆分某些部件，或者不同的部件布置。图示的部件可以以硬件、软件或者软件和硬件的组合来实现。

[0128] 上述装置内的各模块之间的信息交互、执行过程等内容，由于与本发明方法实施例基于同一构思，具体内容可参见本发明方法实施例中的叙述，此处不再赘述。

[0129] 本发明实施例还提供了一种电子设备，包括存储器和处理器，所述存储器中存储有计算机程序，所述处理器执行所述计算机程序时，实现本发明任一实施例中的一种基于量子遗传算法的垃圾运输路线优化方法。

[0130] 本发明实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序在被处理器执行时，使所述处理器执行本发明任一实施例中的一种基于量子遗传算法的垃圾运输路线优化方法。

[0131] 具体地，可以提供配有存储介质的系统或者装置，在该存储介质上存储着实现上述实施例中任一实施例的功能的软件程序代码，且使该系统或者装置的计算机（或CPU或MPU）读出并执行存储在存储介质中的程序代码。

[0132] 在这种情况下，从存储介质读取的程序代码本身可实现上述实施例中任何一项实施例的功能，因此程序代码和存储程序代码的存储介质构成了本发明的一部分。

[0133] 用于提供程序代码的存储介质实施例包括软盘、硬盘、磁光盘、光盘（如CD‑ROM、CD‑R、CD‑RW、DVD‑ROM、DVD‑RAM、DVD‑RW、DVD+RW）、磁带、非易失性存储卡和ROM。可选择地，可以由通信网络从服务器计算机上下载程序代码。

[0134] 此外，应该清楚的是，不仅可以通过执行计算机所读出的程序代码，而且可以通过基于程序代码的指令使计算机上操作的操作系统等来完成部分或者全部的实际操作，从而实现上述实施例中任意一项实施例的功能。

[0135] 此外，可以理解的是，将由存储介质读出的程序代码写到插入计算机内的扩展板中所设置的存储器中或者写到与计算机相连接的扩展模块中设置的存储器中，随后基于程序代码的指令使安装在扩展板或者扩展模块上的CPU等来执行部分和全部实际操作，从而实现上述实施例中任一实施例的功能。

[0136] 需要说明的是，在本文中，诸如第一和第二之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个…”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同因素。

[0137] 本领域普通技术人员可以理解：实现上述方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成，前述的程序可以存储在计算机可读取的存储介质中，该程序在执行时，执行包括上述方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质中。

[0138] 最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。