CN110866629B - 面向异构任务的车辆路径优化方法及装置 - Google Patents

Abstract

本发明提供一种面向异构任务的车辆路径优化方法，该方法包括：获取异构任务集合和路网数据；构建车辆协执行所述异构任务集合的路径规划模型；确定所述异构任务集合中所有线任务的多种执行方向组合，构建每一种执行方向组合所对应的一个访问距离矩阵；将所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径，将该最短路径记为候选最短路径；将多种执行方向组合下对应的多个候选最短路径进行比较，将最小的候选最短路径作为目标最短路径。本发明采用指派问题求解算法计算所述车辆完成所有任务时的最短路径，可以非常方便简单的找到最优匹配，得到最优路径。

Description

面向异构任务的车辆路径优化方法及装置

技术领域

本发明涉及路径优化技术领域，具体涉及一种面向异构任务的车辆路径优化方法、装置、计算机设备和存储介质。

背景技术

目前，通过车辆来执行任务的模式在很多领域中都有应用，例如地理测绘、污染检测、交通巡逻、物流配送、电力巡检等。在车辆执行任务的过程中，可能会遇到很多问题，例如，执行的任务既包括点任务也包括线任务即任务集合为异构任务集合，再例如，车辆的行驶路径是否经过了所有的任务等。为此，需要提供一种车辆单独执行异构任务集合时的路径优化方案。

发明内容

(一)解决的技术问题

本发明提供了一种面向异构任务的车辆路径优化方法、装置、计算机设备和存储介质，可以提高路径求解的效率。

(二)技术方案

为实现以上目的，本发明通过以下技术方案予以实现：

第一方面，本申请提供一种面向异构任务的车辆路径优化方法，包括：获取异构任务集合和路网数据；其中，所述异构任务集合中包括道路交点对应的点任务和道路线段对应的线任务；构建车辆协执行所述异构任务集合的路径规划模型；其中，所述路径规划模型以将车辆从预设控制中心出发、执行完所述异构任务集合中所有任务并返回到所述预设控制中心所耗费的总时间最小化为优化目标，所述路径规划模型的约束条件为根据车辆执行所述异构任务集合的预设场景而设置；确定所述异构任务集合中所有线任务的多种执行方向组合，构建每一种执行方向组合所对应的一个访问距离矩阵；将所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径，将该最短路径记为候选最短路径；将多种执行方向组合下对应的多个候选最短路径进行比较，将最小的候选最短路径作为目标最短路径；其中，所述访问距离矩阵中第i行第j列的元素的值表示第i行对应的任务与第j列对应的任务之间的最短距离，所述异构任务集合中的所有任务作为行方向上的任务，且作为列方向上的任务。

第二方面，本申请提供一种面向异构任务的车辆路径优化装置，包括：任务输入模块，用于获取异构任务集合和路网数据；其中，所述异构任务集合中包括道路交点对应的点任务和道路线段对应的线任务；构建车辆协执行所述异构任务集合的路径规划模型；其中，所述路径规划模型以将车辆从预设控制中心出发、执行完所述异构任务集合中所有任务并返回到所述预设控制中心所耗费的总时间最小化为优化目标，所述路径规划模型的约束条件为根据车辆执行所述异构任务集合的预设场景而设置；路径计算模块，用于确定所述异构任务集合中所有线任务的多种执行方向组合，构建每一种执行方向组合所对应的一个访问距离矩阵；将所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径，将该最短路径记为候选最短路径；将多种执行方向组合下对应的多个候选最短路径进行比较，将最小的候选最短路径作为目标最短路径；其中，所述访问距离矩阵中第i行第j列的元素的值表示第i行对应的任务与第j列对应的任务之间的最短距离，所述异构任务集合中的所有任务作为行方向上的任务，且作为列方向上的任务。

第三方面，本发明提供一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现第一方面所提供的方法的步骤。

第四方面，本发明提供一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现第一方面所提供的方法的步骤。

(三)有益效果

本发明实施例提供了一种面向异构任务的车辆路径优化方法、装置、计算机设备和存储介质，由车辆完成异构任务集合中的所有任务，在路径规划过程中根据执行任务时的实际场景设置约束条件，使得到的路径符合实际的场景需求。车辆的速度一定，当车辆路径最短时，所耗费的时间也最短，进而实现优化目标，提高工作效率。进一步的，本发明中所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径，即通过指派问题求解方式进行求解，可以简化求解步骤，提高求解的效率。

附图说明

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

图1为本申请一实施例中面向异构任务的车辆路径优化方法的流程示意图；

图2为本申请一实施例中面向异构任务的车辆路径优化装置的结构示意图。

具体实施方式

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

第一方面，本发明提供一种面向异构任务的车辆路径优化方法，如图1所示，该方法包括：

S100、获取异构任务集合和路网数据；其中，所述异构任务集合中包括道路交点对应的点任务和道路线段对应的线任务；

可理解的是，路网数据为道路网路的相关数据，例如，路段长度、道路交点等。

由于点任务和线任务都在道路网络中，并且车辆在道路网络中执行任务，因此将道路网络离散简化为一个连通图G＝(V,E)，道路网络中可通行的道路交点集合为连通图G的点集合V＝(V₀,V₂,L,V_v-1)，v表示道路交点的数量。路段的集合则为连通图G的边集合E＝{e_ij＝(V_i,V_j)}，边的数量用e表示。每条边e_ij∈E上有非负权重w(e_ij)，表示边(即路段) 的长度，当

时，w(e_ij)＝0。同时基于实际的道路情况，连通图设计为有向图，即e_ij≠e_ji。在本文中根据实际情况建立一个简化的城市路网连通图。

在上述道路网络连通图中，我们设V₀为预设控制中心作为起始点和终止点，所描述的点任务集合表示为

其中

k＝{1,2,…,m}，i＝{1,2,…,v}，m≤v；所描述的线任务集合表示为

其中

k＝{1,2,…,n},(V_i,V_j)∈E，同时n≤e。因此，异构任务集合为T^V和T^E的并集。可理解的是，由于车辆是一定从预设控制中心出发的，因此V₀一定包括在T^V内。

S200、构构建车辆协执行所述异构任务集合的路径规划模型；其中，所述路径规划模型以将车辆从预设控制中心出发、执行完所述异构任务集合中所有任务并返回到所述预设控制中心所耗费的总时间最小化为优化目标，所述路径规划模型的约束条件为根据车辆执行所述异构任务集合的预设场景而设置；

为了计算方便，我们假设车辆在道路中是匀速行驶的，单位路程所耗费的时间我们用C_V表示，即，车辆行驶单位路程所耗费的时间为 C_V。对于城市的每个子管辖范围，车辆可视为无限续航。由于在整个过程中车辆需要从预设控制中心出发并最终返回，相当于V₀访问了两次，因此我们将所有车辆能出发的点设为V_S＝{V₀,V₁,…,V_v-1}，将所有车辆能返回的点设为V_E＝{V₁,V₂,…,V_v}，其中V_v等价于V₀。

可理解的是，车辆从预设控制中心出发，并返回到预设控制中心，因此可以用车辆行驶的总时间作为整个工作所耗费的时间，因此上述路径规划模型的目标函数为：

min t_v

式中，t_v为所述车辆从所述预设控制中心出发至返回到所述预设控制中心的时间。

在一些实施例中，约束条件是依据车辆的实际工作场景而设置的，例如，所述车辆从所述预设控制中心出发的总次数为1、所述车辆返回到所述预设控制中心的总次数为1、所述异构任务集合中所有的任务都被执行完成等。

S300、确定所述异构任务集合中所有线任务的多种执行方向组合，构建每一种执行方向组合所对应的一个访问距离矩阵；将所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径，将该最短路径记为候选最短路径；将多种执行方向组合下对应的多个候选最短路径进行比较，将最小的候选最短路径作为目标最短路径；其中，所述访问距离矩阵中第i行第j列的元素的值表示第i行对应的任务与第j列对应的任务之间的最短距离，所述异构任务集合中的所有任务作为行方向上的任务，且作为列方向上的任务；

其中，所述确定所述异构任务集合中所有线任务的多种执行方向组合可以包括：针对[0，2ⁿ-1]范围内的每一个整数，确定一个对应的执行方向组合，具体为：将该整数转化为对应的n位二进制数；根据所述n位二进制数，确定n个线任务对应的执行方向组合；其中，n 为所述异构任务集合中所有线任务的数量。

举例来说，该步骤S300的具体过程可以包括如下步骤：

S310、针对[0，2ⁿ-1]范围内的每一个整数，确定一个对应的候选最短路径，n为所述异构任务集合中线任务的数量，确定过程包括：将该整数转化为对应的n位二进制数；根据所述n位二进制数，确定n 个线任务对应的执行方向组合；根据所述执行方向组合，构建一个访问距离矩阵，其中，所述访问距离矩阵中第i行第j列的元素的值表示第i行对应的任务与第j列对应的任务之间的最短距离，所述异构任务集合中的所有任务作为行方向上的任务，且作为列方向上的任务；将所述访问距离矩阵转化为指派问题进行求解，得到在所述执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径，并将该最短路径记为候选最短路径；

可理解的是，若用车辆进行任务访问，本质是找到这些异构任务的访问顺序和任务间的访问路径，由于任务有点任务和线任务之分，因此线任务可以理解为两个必须连续访问的任务节点，执行线任务时需要从其中一个端点进入路段，并在另一个端点驶出，从而完成对该线任务的执行，对于网络中任务间的访问路径有三种方式：(1)点任务与点任务；(2)点任务到线任务；(3)线任务到点任务；(4)线任务到线任务。针对第(1)种，两点之间的最短距离即为两个点任务之间的最短距离；针对第(2)种，点任务与线任务中的进入端点之间的最短距离为点任务到线任务之间的最短距离；针对第(3)种，线任务中的驶出端点与点任务之间的最短距离为线任务到点任务的最短距离；针对第(4)种，第一个线任务中的驶出端点与第二个线任务的进入端点之间的最短距离为第一个线任务到第二个线任务之间的最短距离。

可见，对于线任务来说，进入端点和驶出端点不同，会导致线任务与其前置任务之间的最短距离以及线任务与其后置任务之间的最短距离是不同的，但是上述路径规划模型的可行解是一个所有异构任务的混合访问顺序，其中路段具有方向性。

举例来说，在异构任务集合中有2个点任务和3个线任务，针对[0， 2³-1]即[0，7]范围内的每一个整数：0、1、2、3、4、5、6、7都执行上述步骤，一共有2³个整数。例如，针对整数0，转化为3位二进制数为000，000对应的是三个线任务的执行方向组合，假设二进制数中的0为方向不变，二进制数中的1为方向改变，第一位二进制数对应第一个线任务，第二个二进制数对应第二个线任务，第三个二进制数对应第三个线任务，也就是说，000代表这三个线任务的执行方向都不变。假设第一个线任务原本的执行方向为L1-L2，第二个线任务原本的执行方向为L3-L4，第三个线任务原本的执行方向为L5-L6，当二进制数为 000时，这三个线任务的执行方向均不变。再例如，针对整数3，转化为3位二进制数为011，也就是说，第一个线任务的执行方向不变，第二个线任务的执行方向改变，第三个线任务的执行方向改变，此时第一个任务的执行方向仍为L1-L2，第二个线任务的执行方向变为L4-L3，第三个线任务的执行方向变为L6-L5，可见第一个线任务的执行方向不变，而其他两个线任务的方向均发生了改变。

在确定了各个线任务的执行方向之后，可以确定一个对应的访问距离矩阵，举例来说，在一个异构任务集合中有两个点任务和两个线任务，两个点任务为P1和P2，两个线任务为L1-L2和L3-L4，此时的执行方向只是初始方向，在最优路径中可能会发生变化。针对[0，3] 中的整数0，转化为2位的二进制数为00，表示两个线任务的方向不变，仍为L1-L2和L3-L4。针对这四个任务，构建的访问距离矩阵可以参考如下表1：

表1整数0所对应的访问距离矩阵表

从上表1中，灰色的部分为真正的访问距离矩阵，相同点任务之间的最短距离设置为预设的最大值即MAX，相同线任务之间的最短距离设置为预设的最大值即MAX，这样可以避免某个任务的后置任务为自身的情况发生。点任务之间的最短距离是对称的，例如，P1与P2 之间的最短距离为a3，P2与P1之间的最短距离也为a3。但是点任务与线任务或者线任务之间的最短距离并不是对称的，例如，T0到线任务L1-L2(该线段的进点为L1，出点为L2)之间的最短距离为T0与 L1之间的最短距离，而L1-L2到T0之间的最短距离为L2与T0之间的最短距离。L1-L2到L3-L4的最短距离为L2-L3，而L3-L4到L1-L2 的最短距离为L4-L1。其中，T0即V₀，为预设控制中心。点任务间、点任务与线任务的某一个端点之间、线任务的相邻端点之间的最短距离由在路网图中的最短路径算法求得。将上述访问距离矩阵转化为一个指派问题，进而计算得到一个最短路径。

可理解的是，所谓的指派问题也可称之为匈牙利算法，例如，某单位需完成n项工作，恰好有n个人可承担这些工作。由于每人的专长不同，各人完成工作所费时间不同。于是产生应指派哪个人去完成哪项工作，使完成n项工作的所需总时间最小，这类问题称为指派问题。可以理解的是，本申请中的异构任务集合中的各个任务为上述n 个人，异构任务集合中的各个任务也为上述n项工作，进而可以依据指派问题求解上述访问距离矩阵，进而得到车辆执行所有任务时的最短路径。

在实际中，利用指派问题求解后得到解未必是可行解，例如，利用指派问题求解后得到解为0→4→3→0和1→2→1。由于0→4→3→0 中未包括任务1和任务2，没有执行完所有的任务，因此为非可行解。由于1→2→1的起始点和终止点为非0，且未包括所有的任务，因此也为非可行解。因此在利用指派问题求解得到解后，步骤S310还包括：判断将所述访问距离矩阵转化为指派问题进行求解所得到的最短路径是否为可行解，若否，则对所述述访问距离矩阵进行修改，直至将所述访问距离矩阵转化为指派问题进行求解所得到的最短路径为可行解；其中，采用所述约束条件判断得到的最短路径是否为可行解，所述所述约束条件包括：所述车辆从所述预设控制中心出发的总次数为 1、所述车辆返回到所述预设控制中心的总次数为1以及所述异构任务集合中所有的任务都被执行完成。

可理解的是，上述所述约束条件至少为：路径的开头为0，结尾为 0，中间不可包含0，且中间包含所有的任务。

可理解的是，之所以会出现非可行解的一个重要原因是：异构任务集合中有些任务相距较远。例如，一共有4个任务，任务1～3之间相距较近，而任务1～3与任务4之间相距较远，这时候得到的解就可能会遗漏任务4，此时逐渐拉近任务4与其他3个任务的距离，距离拉近一次，计算一次访问距离矩阵，计算一次解，直至计算得到的解为可行解。也就是说，如果判断为非可行解时，对上述访问距离矩阵进行修改，修改的方式可以为逐渐缩小相距较远的任务之间的距离，直至缩小到利用利用指派问题求解后得到解为可行解。

举例来说，参见表2，可以看出通过转化为指派问题进行求解得到的路径为：T0-[L3-L4]-[L1-L2]-T0、P1-P2，从第一条路径中没有P1、 P2，在第二条路径中没有T0、L1-L2、L3-L4，且第二条路径不是一个闭合的路径，这说明，T0、L1-L2、L3-L4相距较近，P1、P2相距较近，但T0、L1-L2、L3-L4与P1、P2相距较远。可以通过逐渐缩小T0与 P1、P2的距离，P1与L1-L2、L3-L4的距离、P2与L1-L2、L3-L4的距离，即缩小下表2中向下箭头所表示的距离。

表2利用指派问题求解得到的解的表格

	T0	P1	P2	L1-L2	L3-L4
						T0		↓	↓		1
P1	↓		1	↓	↓
						P2	↓	1		↓	↓
L1-L2	1	↓	↓
						L3-L4		↓	↓	1

通过上述阐述可知，如果在异构任务集合中有n个线任务，就会产生2ⁿ个访问距离矩阵，从而得到2ⁿ个解即2ⁿ个最短距离，这2ⁿ个最短距离作为2ⁿ个候选最短距离。

S320、将2ⁿ个执行方向组合下对应的候选最短路径进行比较，将最小的候选最短路径作为目标最短路径。

由于针对包含n个线任务的异构任务集合，可以得到车辆执行所有任务时的候选最短路径有2ⁿ个，此时对这2ⁿ个候选最短路径进行比较，将其中的最小值作为目标最短路径，也就是步骤S300需要计算的车辆单独完成所述异构任务集合中所有任务时的最短路径。

本发明提供的面向异构任务的车辆路径优化方法，由车辆完成异构任务集合中的所有任务，在路径规划过程中根据执行任务时的实际场景设置约束条件，使得到的路径符合实际的场景需求。车辆的速度一定，当车辆路径最短时，所耗费的时间也最短，进而实现优化目标，提高工作效率。进一步的，本发明中所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径，即通过指派问题求解方式进行求解，可以简化求解步骤，提高求解的效率。

第二方面，本发明提供一种面向异构任务的车辆路径优化装置，如图2所示，该装置400包括：

任务输入模块410，用于获取异构任务集合和路网数据；其中，所述异构任务集合中包括道路交点对应的点任务和道路线段对应的线任务；构建车辆协执行所述异构任务集合的路径规划模型；其中，所述路径规划模型以将车辆从预设控制中心出发、执行完所述异构任务集合中所有任务并返回到所述预设控制中心所耗费的总时间最小化为优化目标，所述路径规划模型的约束条件为根据车辆执行所述异构任务集合的预设场景而设置；

路径计算模块420，用于确定所述异构任务集合中所有线任务的多种执行方向组合，构建每一种执行方向组合所对应的一个访问距离矩阵；将所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径，将该最短路径记为候选最短路径；将多种执行方向组合下对应的多个候选最短路径进行比较，将最小的候选最短路径作为目标最短路径；其中，所述访问距离矩阵中第i行第j列的元素的值表示第i行对应的任务与第j列对应的任务之间的最短距离，所述异构任务集合中的所有任务作为行方向上的任务，且作为列方向上的任务。

在一些实施例中，所述路径计算模块执行的所述确定所述异构任务集合中所有线任务的多种执行方向组合，包括：针对[0，2ⁿ-1]范围内的每一个整数，确定一个对应的执行方向组合，具体为：将该整数转化为对应的n位二进制数；根据所述n位二进制数，确定n个线任务对应的执行方向组合；其中，n为所述异构任务集合中所有线任务的数量。

在一些实施例中，所述访问距离矩阵中第i行第i列的元素的值为预设最大值。

在一些实施例中，所述路径计算模块在将所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径之后，还用于：判断将所述访问距离矩阵转化为指派问题进行求解所得到的最短路径是否为可行解，若否，则对所述访问距离矩阵进行修改，直至将所述访问距离矩阵转化为指派问题进行求解所得到的最短路径为可行解；其中，采用所述约束条件判断得到的最短路径是否为可行解，所述约束条件包括：所述车辆从所述预设控制中心出发的总次数为1、所述车辆返回到所述预设控制中心的总次数为1以及所述异构任务集合中所有的任务都被执行完成。

第三方面，本发明提供一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现第一方面所提供的方法的步骤。

第四方面，本发明提供一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现第一方面所提供的方法的步骤。

可理解的是，第二方面提供的装置、第三方面提供的计算机设备和第四方面提供的计算机可读存储介质中有关内容的解释、举例、实施例、有益效果等部分可以参考第一方面中的内容，此处不再赘述。

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

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

Claims (10)

1.一种面向异构任务的车辆路径优化方法，其特征在于，包括：

获取异构任务集合和路网数据；其中，所述异构任务集合中包括道路交点对应的点任务和道路线段对应的线任务；

构建车辆协执行所述异构任务集合的路径规划模型；其中，所述路径规划模型以将车辆从预设控制中心出发、执行完所述异构任务集合中所有任务并返回到所述预设控制中心所耗费的总时间最小化为优化目标，所述路径规划模型的约束条件为根据车辆执行所述异构任务集合的预设场景而设置；

确定所述异构任务集合中所有线任务的多种执行方向组合，构建每一种执行方向组合所对应的一个访问距离矩阵；将所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径，将该最短路径记为候选最短路径；将多种执行方向组合下对应的多个候选最短路径进行比较，将最小的候选最短路径作为目标最短路径；其中，所述访问距离矩阵中第i行第j列的元素的值表示第i行对应的任务与第j列对应的任务之间的最短距离，所述异构任务集合中的所有任务作为行方向上的任务，且作为列方向上的任务。

2.根据权利要求1所述的方法，其特征在于，所述确定所述异构任务集合中所有线任务的多种执行方向组合，包括：

针对[0，2ⁿ-1]范围内的每一个整数，确定一个对应的执行方向组合，具体为：将该整数转化为对应的n位二进制数；根据所述n位二进制数，确定n个线任务对应的执行方向组合；其中，n为所述异构任务集合中所有线任务的数量。

3.根据权利要求1所述的方法，其特征在于，所述访问距离矩阵中第i行第i列的元素的值为预设最大值。

4.根据权利要求1所述的方法，其特征在于，将所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径之后，所述方法还包括：判断将所述访问距离矩阵转化为指派问题进行求解所得到的最短路径是否为可行解，若否，则对所述访问距离矩阵进行修改，直至将所述访问距离矩阵转化为指派问题进行求解所得到的最短路径为可行解；其中，采用所述约束条件判断得到的最短路径是否为可行解，所述约束条件包括：所述车辆从所述预设控制中心出发的总次数为1、所述车辆返回到所述预设控制中心的总次数为1以及所述异构任务集合中所有的任务都被执行完成。

5.一种面向异构任务的车辆路径优化装置，其特征在于，包括：

任务输入模块，用于获取异构任务集合和路网数据；其中，所述异构任务集合中包括道路交点对应的点任务和道路线段对应的线任务；构建车辆协执行所述异构任务集合的路径规划模型；其中，所述路径规划模型以将车辆从预设控制中心出发、执行完所述异构任务集合中所有任务并返回到所述预设控制中心所耗费的总时间最小化为优化目标，所述路径规划模型的约束条件为根据车辆执行所述异构任务集合的预设场景而设置；

路径计算模块，用于确定所述异构任务集合中所有线任务的多种执行方向组合，构建每一种执行方向组合所对应的一个访问距离矩阵；将所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径，将该最短路径记为候选最短路径；将多种执行方向组合下对应的多个候选最短路径进行比较，将最小的候选最短路径作为目标最短路径；其中，所述访问距离矩阵中第i行第j列的元素的值表示第i行对应的任务与第j列对应的任务之间的最短距离，所述异构任务集合中的所有任务作为行方向上的任务，且作为列方向上的任务。

6.根据权利要求5所述的装置，其特征在于，所述路径计算模块执行的所述确定所述异构任务集合中所有线任务的多种执行方向组合，包括：针对[0，2ⁿ-1]范围内的每一个整数，确定一个对应的执行方向组合，具体为：将该整数转化为对应的n位二进制数；根据所述n位二进制数，确定n个线任务对应的执行方向组合；其中，n为所述异构任务集合中所有线任务的数量。

7.根据权利要求5所述的装置，其特征在于，所述访问距离矩阵中第i行第i列的元素的值为预设最大值。

8.根据权利要求5所述的装置，其特征在于，所述路径计算模块在将所述访问距离矩阵转化为指派问题进行求解得到在对应执行方向组合下车辆单独完成所述异构任务集合中所有任务时的最短路径之后，还用于：判断将所述访问距离矩阵转化为指派问题进行求解所得到的最短路径是否为可行解，若否，则对所述访问距离矩阵进行修改，直至将所述访问距离矩阵转化为指派问题进行求解所得到的最短路径为可行解；其中，采用所述约束条件判断得到的最短路径是否为可行解，所述约束条件包括：所述车辆从所述预设控制中心出发的总次数为1、所述车辆返回到所述预设控制中心的总次数为1以及所述异构任务集合中所有的任务都被执行完成。

9.一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至4中任一项所述方法的步骤。

10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至4中任一项所述的方法的步骤。

Images