一种车辆路径的规划方法和装置

摘要

本发明公开了一种车辆路径的规划方法和装置，涉及仓储物流技术领域。该方法的一具体实施方式包括：响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标；按照预先设置的规划参数，根据车辆途经点信息生成第一路径集合；对第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合；基于多个规划目标，通过第一路径集合和第二路径集合，生成车辆路径的规划结果。该实施方式能够设置多个规划目标，并基于进化处理和变邻域操作处理，针对多个规划目标进行路径规划，并降低路径规划的时间复杂度，提高实时响应度。

权利要求

1.一种车辆路径的规划方法，其特征在于，包括：

响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标；

按照预先设置的规划参数，根据所述车辆途经点信息生成第一路径集合；

对所述第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合；

基于所述多个规划目标，通过所述第一路径集合和所述第二路径集合，生成所述车辆路径的规划结果；

所述第二路径集合包括多个第二路径，所述对所述第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合，包括：对所述第一路径集合中的每个第一路径进行进化处理，生成进化路径集合，所述进化路径集合包括多个进化路径；对于每个进化路径，根据预设的变邻域操作类型，对所述进化路径进行变邻域操作处理，生成对应的变邻域路径，并按照所述多个规划目标，对所述进化路径和所述变邻域路径进行比较，确定所述进化路径对应的第二路径；

所述按照所述多个规划目标，对所述进化路径和所述变邻域路径进行比较，确定所述进化路径对应的第二路径，包括：按照所述多个规划目标，在所述变邻域路径支配所述进化路径的情况下，将所述变邻域路径作为所述第二路径，否则，将所述进化路径作为所述第二路径。

2.根据权利要求1所述的方法，其特征在于，所述根据预设的变邻域操作类型，对所述进化路径进行变邻域操作处理，生成对应的变邻域路径，包括：随机从预设的变邻域操作类型中确定目标变邻域操作类型，所述预设的变邻域操作类型包括部分基因向前插入、部分基因向后插入和基因乱序中的一种或多种；

按照所述目标变邻域操作类型，对所述进化路径进行变邻域操作处理，生成对应的变邻域路径。

3.根据权利要求1所述的方法，其特征在于，所述规划参数包括变邻域操作次数上限，所述基于所述多个规划目标，通过所述第一路径集合和所述第二路径集合，生成所述车辆路径的规划结果之前，还包括：获取当前变邻域操作次数，并比较所述当前变邻域操作次数和所述变邻域操作次数上限；

在所述当前变邻域操作次数小于所述变邻域操作次数上限的情况下，通过所述第二路径集合生成新的进化路径集合，重新返回至对所述进化路径进行变邻域操作处理，生成对应的变邻域路径的步骤，直到所述当前变邻域操作次数达到所述变邻域操作次数上限。

4.根据权利要求1所述的方法，其特征在于，所述基于所述多个规划目标，通过所述第一路径集合和所述第二路径集合，生成所述车辆路径的规划结果，包括：将所述第一路径集合和所述第二路径集合进行融合，得到第三路径集合，所述第三路径集合包括多个第三路径；

对所述多个第三路径进行非支配排序处理，按照支配等级从小到大的顺序，根据预设的路径数量阈值生成第四路径集合；

根据所述第四路径集合，生成所述车辆路径的规划结果。

5.根据权利要求4所述的方法，其特征在于，所述规划参数还包括迭代次数上限，所述根据所述第四路径集合，生成所述车辆路径的规划结果之前，还包括：获取当前迭代次数，并比较所述当前迭代次数和所述迭代次数上限；

在所述当前迭代次数小于所述迭代次数上限的情况下，通过所述第四路径集合生成新的第一路径集合，重新返回至对所述第一路径集合进行进化处理和变邻域操作处理的步骤，直到所述当前迭代次数达到所述迭代次数上限。

6.根据权利要求4所述的方法，其特征在于，所述根据所述第四路径集合，生成所述车辆路径的规划结果，包括：从所述多个规划目标中确定主要规划目标；

按照所述主要规划目标，从所述第四路径集合中选出所述主要规划目标最优的第四路径；

根据所述主要规划目标最优的第四路径，生成所述车辆路径的规划结果。

7.一种车辆路径的规划装置，其特征在于，包括：

请求响应模块，用于响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标；

第一路径集合生成模块，用于按照预先设置的规划参数，根据所述车辆途经点信息生成第一路径集合；

第二路径集合生成模块，用于对所述第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合；所述第二路径集合包括多个第二路径；

规划结果生成模块，用于基于所述多个规划目标，通过所述第一路径集合和所述第二路径集合，生成所述车辆路径的规划结果；

所述第二路径集合生成模块还用于：对所述第一路径集合中的每个第一路径进行进化处理，生成进化路径集合，所述进化路径集合包括多个进化路径；对于每个进化路径，根据预设的变邻域操作类型，对所述进化路径进行变邻域操作处理，生成对应的变邻域路径，并按照所述多个规划目标，对所述进化路径和所述变邻域路径进行比较，确定所述进化路径对应的第二路径；

所述第二路径集合生成模块还用于：按照所述多个规划目标，在所述变邻域路径支配所述进化路径的情况下，将所述变邻域路径作为所述第二路径，否则，将所述进化路径作为所述第二路径。

8.一种电子设备，其特征在于，包括：

一个或多个处理器；

存储装置，用于存储一个或多个程序，

当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如权利要求1‑6中任一所述的方法。

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

说明书

一种车辆路径的规划方法和装置

技术领域

[0001] 本发明涉及仓储物流技术领域，尤其涉及一种车辆路径的规划方法和装置。

背景技术

[0002] 目前智能无人车对指定范围内的多个用户进行派送时，需要设置一个规划目标，并根据该规划目标，通过剪枝法等路径规划算法对车辆路径进行规划，得到在该规划目标下最优的路径，从而按照最优的路径进行派送。

[0003] 在实现本发明过程中，发明人发现现有技术中至少存在如下问题：

[0004] 只能针对单一规划目标进行路径规划，无法满足多规划目标场景下的路径规划，并且路径规划的时间复杂度较高，实时响应度差。

发明内容

[0005] 有鉴于此，本发明实施例提供一种车辆路径的规划方法和装置，能够设置多个规划目标，并基于进化处理和变邻域操作处理，针对多个规划目标进行路径规划，并降低路径规划的时间复杂度，提高实时响应度。

[0006] 为实现上述目的，根据本发明实施例的一个方面，提供了一种车辆路径的规划方法。

[0007] 一种车辆路径的规划方法，包括：响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标；按照预先设置的规划参数，根据所述车辆途经点信息生成第一路径集合；对所述第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合；基于所述多个规划目标，通过所述第一路径集合和所述第二路径集合，生成所述车辆路径的规划结果。

[0008] 可选地，所述第二路径集合包括多个第二路径，所述对所述第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合，包括：对所述第一路径集合中的每个第一路径进行进化处理，生成进化路径集合，所述进化路径集合包括多个进化路径；对于每个进化路径，根据预设的变邻域操作类型，对所述进化路径进行变邻域操作处理，生成对应的变邻域路径，并按照所述多个规划目标，对所述进化路径和所述变邻域路径进行比较，确定所述进化路径对应的第二路径。

[0009] 可选地，所述按照所述多个规划目标，对所述进化路径和所述变邻域路径进行比较，确定所述进化路径对应的第二路径，包括：按照所述多个规划目标，在所述变邻域路径支配所述进化路径的情况下，将所述变邻域路径作为所述第二路径，否则，将所述进化路径作为所述第二路径。

[0010] 可选地，所述根据预设的变邻域操作类型，对所述进化路径进行变邻域操作处理，生成对应的变邻域路径，包括：随机从预设的变邻域操作类型中确定目标变邻域操作类型，所述预设的变邻域操作类型包括部分基因向前插入、部分基因向后插入和基因乱序中的一种或多种；按照所述目标变邻域操作类型，对所述第一路径进行变邻域操作处理，生成对应的变邻域路径。

[0011] 可选地，所述规划参数包括变邻域操作次数上限，所述基于所述多个规划目标，通过所述第一路径集合和所述第二路径集合，生成所述车辆路径的规划结果之前，还包括：获取当前变邻域操作次数，并比较所述当前变邻域操作次数和所述变邻域操作次数上限；在所述当前变邻域操作次数小于所述变邻域操作次数上限的情况下，通过所述第二路径集合生成新的进化路径集合，重新返回至对所述进化路径进行变邻域操作处理，生成对应的变邻域路径的步骤，直到所述当前变邻域操作次数达到所述变邻域操作次数上限。

[0012] 可选地，所述基于所述多个规划目标，通过所述第一路径集合和所述第二路径集合，生成所述车辆路径的规划结果，包括：将所述第一路径集合和所述第二路径集合进行融合，得到第三路径集合，所述第三路径集合包括多个第三路径；对所述多个第三路径进行非支配排序处理，按照支配等级从小到大的顺序，根据预设的路径数量阈值生成第四路径集合；根据所述第四路径集合，生成所述车辆路径的规划结果。

[0013] 可选地，所述规划参数还包括迭代次数上限，所述根据所述第四路径集合，生成所述车辆路径的规划结果之前，还包括：获取当前迭代次数，并比较所述当前迭代次数和所述迭代次数上限；在所述当前迭代次数小于所述迭代次数上限的情况下，通过所述第四路径集合生成新的第一路径集合，重新返回至对所述第一路径集合进行进化处理和变邻域操作处理的步骤，直到所述当前迭代次数达到所述迭代次数上限。

[0014] 可选地，所述根据所述第四路径集合，生成所述车辆路径的规划结果，包括：从所述多个规划目标中确定主要规划目标；按照所述主要规划目标，从所述第四路径集合中选出所述主要规划目标最优的第四路径；根据所述主要规划目标最优的第四路径，生成所述车辆路径的规划结果。

[0015] 根据本发明实施例的另一方面，提供了一种车辆路径的规划装置。

[0016] 一种车辆路径的规划装置，包括：请求响应模块，用于响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标；第一路径集合生成模块，用于按照预先设置的规划参数，根据所述车辆途经点信息生成第一路径集合；第二路径集合生成模块，用于对所述第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合；规划结果生成模块，用于基于所述多个规划目标，通过所述第一路径集合和所述第二路径集合，生成所述车辆路径的规划结果。

[0017] 可选地，所述第二路径集合包括多个第二路径，所述第二路径集合生成模块还用于：对所述第一路径集合中的每个第一路径进行进化处理，生成进化路径集合，所述进化路径集合包括多个进化路径；对于每个进化路径，根据预设的变邻域操作类型，对所述进化路径进行变邻域操作处理，生成对应的变邻域路径，并按照所述多个规划目标，对所述进化路径和所述变邻域路径进行比较，确定所述进化路径对应的第二路径。

[0018] 可选地，所述第二路径集合生成模块还用于：按照所述多个规划目标，在所述变邻域路径支配所述进化路径的情况下，将所述变邻域路径作为所述第二路径，否则，将所述进化路径作为所述第二路径。

[0019] 可选地，所述第二路径集合生成模块还用于：随机从预设的变邻域操作类型中确定目标变邻域操作类型，所述预设的变邻域操作类型包括部分基因向前插入、部分基因向后插入和基因乱序中的一种或多种；按照所述目标变邻域操作类型，对所述第一路径进行变邻域操作处理，生成对应的变邻域路径。

[0020] 可选地，所述规划参数包括变邻域操作次数上限，所述装置还包括变邻域操作次数校验模块，用于：获取当前变邻域操作次数，并比较所述当前变邻域操作次数和所述变邻域操作次数上限；在所述当前变邻域操作次数小于所述变邻域操作次数上限的情况下，通过所述第二路径集合生成新的进化路径集合，重新返回至对所述进化路径进行变邻域操作处理，生成对应的变邻域路径的步骤，直到所述当前变邻域操作次数达到所述变邻域操作次数上限。

[0021] 可选地，所述规划结果生成模块还用于：将所述第一路径集合和所述第二路径集合进行融合，得到第三路径集合，所述第三路径集合包括多个第三路径；对所述多个第三路径进行非支配排序处理，按照支配等级从小到大的顺序，根据预设的路径数量阈值生成第四路径集合；根据所述第四路径集合，生成所述车辆路径的规划结果。

[0022] 可选地，所述规划参数还包括迭代次数上限，所述装置还包括迭代次数校验模块，用于：获取当前迭代次数，并比较所述当前迭代次数和所述迭代次数上限；在所述当前迭代次数小于所述迭代次数上限的情况下，通过所述第四路径集合生成新的第一路径集合，重新返回至对所述第一路径集合进行进化处理和变邻域操作处理的步骤，直到所述当前迭代次数达到所述迭代次数上限。

[0023] 可选地，所述规划结果生成模块还用于：从所述多个规划目标中确定主要规划目标；按照所述主要规划目标，从所述第四路径集合中选出所述主要规划目标最优的第四路径；根据所述主要规划目标最优的第四路径，生成所述车辆路径的规划结果。

[0024] 根据本发明实施例的又一方面，提供了一种电子设备。

[0025] 一种电子设备，包括：一个或多个处理器；存储器，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行时，使得所述一个或多个处理器实现本发明实施例所提供的车辆路径的规划方法。

[0026] 根据本发明实施例的又一方面，提供了一种计算机可读介质。

[0027] 一种计算机可读介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现本发明实施例所提供的车辆路径的规划方法。

[0028] 上述发明中的一个实施例具有如下优点或有益效果：通过响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标；按照预先设置的规划参数，根据车辆途经点信息生成第一路径集合；对第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合；基于多个规划目标，通过第一路径集合和第二路径集合，生成车辆路径的规划结果的技术方案，能够设置多个规划目标，并基于进化处理和变邻域操作处理，针对多个规划目标进行路径规划，并降低路径规划的时间复杂度，提高实时响应度。

[0029] 上述的非惯用的可选方式所具有的进一步效果将在下文中结合具体实施方式加以说明。

附图说明

[0030] 附图用于更好地理解本发明，不构成对本发明的不当限定。其中：

[0031] 图1是根据本发明一个实施例的车辆路径的规划方法的主要步骤示意图；

[0032] 图2是根据本发明一个实施例的车辆路径的规划方法的流程示意图；

[0033] 图3是根据本发明一个实施例的车辆路径的规划装置的主要模块示意图；

[0034] 图4是本发明实施例可以应用于其中的示例性系统架构图；

[0035] 图5是适于用来实现本发明实施例的终端设备或服务器的计算机系统的结构示意图。

具体实施方式

[0036] 以下结合附图对本发明的示范性实施例做出说明，其中包括本发明实施例的各种细节以助于理解，应当将它们认为仅仅是示范性的。因此，本领域普通技术人员应当认识到，可以对这里描述的实施例做出各种改变和修改，而不会背离本发明的范围和精神。同样，为了清楚和简明，以下的描述中省略了对公知功能和结构的描述。

[0037] 需要说明的是，本发明的技术方案中，所涉及的用户个人信息的采集、收集、更新、分析、处理、使用、传输、存储等方面，均符合相关法律法规的规定，被用于合法的用途，且不违背公序良俗。对用户个人信息采取必要措施，防止对用户个人信息数据的非法访问，维护用户个人信息安全、网络安全和国家安全。

[0038] 图1是根据本发明一个实施例的车辆路径的规划方法的主要步骤示意图。

[0039] 如图1所示，本发明一个实施例的车辆路径的规划方法主要包括如下的步骤S101至步骤S104。

[0040] 步骤S101：响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标。

[0041] 其中，车辆途经点信息包括需要派送的多个用户，以及每个用户的位置信息和期望送达时间，多个规划目标可以包括最小总行驶时间和最优期望送达时间。位置信息可以为坐标信息，位置信息通过路网信息获得，路径可以认为两个位置信息之间的直线距离。

[0042]  最小总行驶时间  的计算方式可以为：

[0043]

[0044] 其中，式中ti表示无人车在派送第i个用户的物品时所花费的时间，可以通过在派送第i个用户的物品时所行驶的距离除以预设的无人车速度得到，n表示用户的总数量。

[0045] 最优期望送达时间 的计算方式可以为：

[0046] ；

[0047] 其中，tai表示无人车派送第i个用户的物品时的送达时间，tie表示第i个用户的期望送达时间。

[0048] 步骤S102：按照预先设置的规划参数，根据车辆途经点信息生成第一路径集合。其中，规划参数可以包括初始路径数量、变邻域操作次数上限、迭代次数上限、进化处理参数和变邻域操作处理参数等。

[0049] 具体地，预设的初始路径数量M可以为100个，根据车辆途经点信息随机生成100个以上初始路径，通过初始路径得到初始路径集合。对初始路径集合进行Pareto非支配排序，优先取等级为1的Pareto解集，然后取等级为2的Pareto解集，以此类推，直至选出100个初始路径作为第一路径，生成第一路径集合。

[0050] 其中，在Pareto支配关系中，以两个目标函数为例，若解（即路径）1在目标函数1和目标函数2两个方面均优于解2，则说明解1支配解2，若解1只在目标函数1或目标函数2两个函数中的一个优于解2则不能说明解1支配解2。对路径集合中的路径进行非支配排序，得到所有非支配解，则等级为1的Pareto解集为所有非支配解组成的集合，其中的解相互都不能支配。将等级为1的Pareto解集从路径集合中剔除，再次进行非支配排序，得到所有非支配解，生成等级为2的Pareto解集。重复进行非支配排序，从而将路径集合中的所有路径分到不同等级的Pareto解集中。

[0051] 步骤S103：对第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合。其中，第二路径集合可以包括多个第二路径。

[0052] 在一个实施例中，对第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合，可以包括：对第一路径集合中的每个第一路径进行进化处理，生成进化路径集合，进化路径集合包括多个进化路径；对于每个进化路径，根据预设的变邻域操作类型，对进化路径进行变邻域操作处理，生成对应的变邻域路径，并按照多个规划目标，对进化路径和变邻域路径进行比较，确定进化路径对应的第二路径。

[0053]  具体地，本发明实施例基于变邻域操作的改进NSGA‑II算法为基础算法进行路径搜索，提出了BVNO‑INSGA‑II（Based on Variable Neighborhood Operation‑Improved Non Dominated Sorting Genetic Algorithm‑II）算法，即基于变邻域操作的改进NSGA‑II算法，可以通过BVNO‑INSGA‑II算法对进化处理和变邻域操作处理。

[0054] 进化处理可以包括交叉操作和变异操作，变异操作主要用于提升算法的全局搜索能力，而交叉操作更注重在指定路径周围进行局部搜索。进化处理参数的设置可以为，重组算子的交叉概率为0.9，变异概率为1/M，在M为100的情况下，变异概率为1%。其中，交叉概率为0.9表示交叉操作的发生概率为90%，变异概率表示在种群数量为100的情况下发生的概率为1%。在进化处理中，需要将第一路径集合分为两部分，以100个第一路径为例，分成前50个第一路径与后50个第一路径，按顺序依次取出前50个第一路径中的第一个和后50个第一路径中的第一个进行交叉操作，交叉操作得到的两个交叉路径再分别进行变异操作，然后以此类推完成一个个的交叉变异操作，其中每次匹配后是否会发生交叉、变异操作则由交叉概率和变异概率控制。

[0055]  交叉操作是指模拟二进制交叉(SBX，Simulated binary crossover)，用于变量取值连续的实数编码的算法中，若两个第一路径分别为 和 ，则交叉后的两个交叉路径 和 的计算公式为：

[0056]

[0057] 其中，n为用户总数量，β是由概率密度函数生成的随机数。

[0058] 变异操作可以采用多项式变异，即以交叉路径中的元素值以一定概率加上一个服从多项式概率分布的值得到一个邻近值。变异操作的计算公式可以为：

[0059]

[0060] 其中 表示交叉路径中的元素 在突变后的值， 和 分别表示元素xj的最小取值和最大取值，δ表示一个服从多项式分布的数值。

[0061] 在一个实施例中，根据预设的变邻域操作类型，对进化路径进行变邻域操作处理，生成对应的变邻域路径，可以包括：随机从预设的变邻域操作类型中确定目标变邻域操作类型，预设的变邻域操作类型包括部分基因向前插入、部分基因向后插入和基因乱序中的一种或多种；按照多个规划目标，在变邻域路径支配进化路径的情况下，将变邻域路径作为第二路径，否则，将进化路径作为第二路径。然后获取当前变邻域操作次数，并比较当前变邻域操作次数和变邻域操作次数上限；在当前变邻域操作次数小于变邻域操作次数上限的情况下，通过第二路径集合生成新的进化路径集合，重新返回至对进化路径进行变邻域操作处理，生成对应的变邻域路径的步骤，直到当前变邻域操作次数达到变邻域操作次数上限。

[0062] 具体地，变邻域操作是针对不同邻域进行的搜索操作，通过多个不同的邻域产生不同的邻域解的集合。其搜索过程主要可以包括如下步骤：

[0063] （1）设定变邻域操作次数上限L（如5次）；

[0064] （2）设置多种变邻域操作类型，如3种变邻域操作类型，分别为部分基因向前插入、部分基因向后插入和基因乱序；

[0065] （3）针对种群中的每个进化路径，随机多种变邻域操作类型选择一种作为目标变邻域操作类型；

[0066] （4）根据目标变邻域类型的邻域操作，生成进化路径对应的变邻域路径；

[0067] （5）根据Pareto支配关系判断变邻域路径是否支配对应的进化路径，如果经过邻域操作变换后的变邻域路径支配了进化路径，则以变邻域路径作为第二路径，如果变邻域路径未支配进化路径，则舍弃变邻域路径，以进化路径作为第二路径；

[0068] （6）判断当前变邻域操作次数是否达到变邻域操作次数上限L，如果未达到该上限则将此时的第二路径更新为进化，并返回第（3）步继续进行变邻域操作，否则输出第二路径；

[0069] （7）通过最终获得的第二路径生成第二路径集合。

[0070] 其中，每个路径中可以包括多个元素序列，部分基因向前插入为从路径中的元素序列中随机选择两个部分，这两个部分包含相等数量的元素（即基因），然后将后一部分元素向前插入到前一部分元素前面；部分基因向后插入从路径中的元素序列中随机选择两个部分，这两个部分包含相等数量的元素，然后将前一部分元素向后插入到后一部分元素后面；基因乱序为将路径中的元素序列随机打乱，进行重新排列得到新的路径。

[0071] 本发明实施例中，部分基因向前插入和部分基因向后插入偏向于在原有的个体基因序列上进行小幅度的改变，这是针对于局部范围内不同的解进行变化，以提升算法的收敛性。基因乱序偏向于对原有解进行完全的重排列，这是提升算法在全局内的寻优能力，即提升最终种群的多样性。由于变邻域操作的特性，其在搜索到较差路径时并不会对原有路径进行替换，所以其每次变换后的路径一定优于原有路径，不会对原有算法产生差的影响。

[0072] 步骤S104：基于多个规划目标，通过第一路径集合和第二路径集合，生成车辆路径的规划结果。

[0073] 在一个实施例中，基于多个规划目标，通过第一路径集合和第二路径集合，生成车辆路径的规划结果，可以包括：将第一路径集合和第二路径集合进行融合，得到第三路径集合，第三路径集合包括多个第三路径；对多个第三路径进行非支配排序处理，按照支配等级从小到大的顺序，根据预设的路径数量阈值生成第四路径集合；根据第四路径集合，生成车辆路径的规划结果。

[0074] 具体地，将第一路径集合P1和第二路径集合P2进行融合，得到路径数量为2M的第三路径集合P3。对第三路径集合P3进行快速非支配排序操作，根据排序后的不同等级的Pareto解从小到大按照精英策略将最优的解依次放入到第四路径集合P4中，直到达到路径数量阈值为止。

[0075] 在精英策略中，首先计算第三路径集合P3中每个第三路径的拥挤度，拥挤度表示在同一等级的Pareto解集，第j个第三路径周围的包含第j个第三路径本身且不包含其它第四路径的长方形，可以理解为以同一等级中前后相邻个体作为顶点的长方形。第j个第三路径的拥挤度的计算公式可以为：

[0076]

[0077] 其中，f1和f2分别表示目标函数1和目标函数2，j‑1和j+1分别表示路径j的前一个路径和后一个路径。

[0078] 在生成每个第三路径的拥挤度之后，按照等级从小到大的顺序，将不同等级的Pareto解依次放入第四路径集合P4，直至取到Rank=x的Pareto解集时，如果把该Rank的所有解都放入子代种群会超出子代种群个数的话，那么就计算该Rank所有解的拥挤度，按照拥挤度从大到小进行排列优先取拥挤度大的个体，依次向下取，直至将第四路径集合P4放满。

[0079] 在一个实施例中，根据第四路径集合，生成车辆路径的规划结果之前，还可以包括：获取当前迭代次数，并比较当前迭代次数和迭代次数上限；在当前迭代次数小于迭代次数上限的情况下，通过第四路径集合生成新的第一路径集合，重新返回至对第一路径集合进行进化处理和变邻域操作处理的步骤，直到当前迭代次数达到迭代次数上限。

[0080] 在一个实施例中，根据第四路径集合，生成车辆路径的规划结果，可以包括：从多个规划目标中确定主要规划目标；按照主要规划目标，从第四路径集合中选出主要规划目标最优的第四路径；根据主要规划目标最优的第四路径，生成车辆路径的规划结果。

[0081] 具体地，在满足迭代次数后，从最终的第四路径集合中选出等级为1的Pareto解集。从最小总行驶时间和最优期望送达时间中，可以将最优期望送达时间作为主要规划目标。从选出的等级为1的Pareto解集中选出最优期望送达时间对应的第四路径，作为最优规划路径。最优规划路径中包括路径的规划方案，即多个用户的派送顺序，以及多个规划目标对应的最优值。根据最优规划路径，生成车辆路径的规划结果。

[0082] 图2是根据本发明一个实施例的车辆路径的规划方法的流程示意图。

[0083] 如图2所示，在一个实施例中，获取车辆途经点信息和多个规划目标，生成初始路径集合，并对初始路径集合进行选择，得到第一路径集合。对第一路径集合进行交叉操作和变异操作等进化处理，得到进化路径集合。对进化路径集合中的每个进化路径，随机确定目标变邻域操作类型，按照目标变邻域操作类型得到对应的变邻域路径，根据多个规划目标，从进化路径和变邻域路径中确定第二路径，从而生成第二路径集合。在当前变邻域操作次数小于变邻域操作次数上限的情况下，重复进行变邻域操作处理，直到当前变邻域操作次数达到变邻域操作次数上限。对最终得到的第二路径集合进行非支配排序，生成第四路径集合。在当前迭代次数小于迭代次数上限的情况下，重新返回至进化处理的步骤，直到当前变邻域操作次数达到变邻域操作次数上限。根据最终得到的第二路径集合，按照主要规划目标，生成车辆路径的规划结果。

[0084] 图3是根据本发明一个实施例的车辆路径的规划装置的主要模块示意图。

[0085] 如图3所示，本发明一个实施例的车辆路径的规划装置300主要包括：请求响应模块301、第一路径集合生成模块302、第二路径集合生成模块303、规划结果生成模块304。

[0086] 请求响应模块301，用于响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标。

[0087] 第一路径集合生成模块302，用于按照预先设置的规划参数，根据车辆途经点信息生成第一路径集合。

[0088] 第二路径集合生成模块303，用于对第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合。

[0089] 规划结果生成模块304，用于基于多个规划目标，通过第一路径集合和第二路径集合，生成车辆路径的规划结果。

[0090] 在一个实施例中，第二路径集合可以包括多个第二路径，第二路径集合生成模块303具体用于：对第一路径集合中的每个第一路径进行进化处理，生成进化路径集合，进化路径集合包括多个进化路径；对于每个进化路径，根据预设的变邻域操作类型，对进化路径进行变邻域操作处理，生成对应的变邻域路径，并按照多个规划目标，对进化路径和变邻域路径进行比较，确定进化路径对应的第二路径。

[0091] 在一个实施例中，第二路径集合生成模块303具体用于：按照多个规划目标，在变邻域路径支配进化路径的情况下，将变邻域路径作为第二路径，否则，将进化路径作为第二路径。

[0092] 在一个实施例中，第二路径集合生成模块303具体用于：随机从预设的变邻域操作类型中确定目标变邻域操作类型，预设的变邻域操作类型包括部分基因向前插入、部分基因向后插入和基因乱序中的一种或多种；按照目标变邻域操作类型，对第一路径进行变邻域操作处理，生成对应的变邻域路径。

[0093] 在一个实施例中，规划参数可以包括变邻域操作次数上限，装置还可以包括变邻域操作次数校验模块（图中未示出），用于：获取当前变邻域操作次数，并比较当前变邻域操作次数和变邻域操作次数上限；在当前变邻域操作次数小于变邻域操作次数上限的情况下，通过第二路径集合生成新的进化路径集合，重新返回至对进化路径进行变邻域操作处理，生成对应的变邻域路径的步骤，直到当前变邻域操作次数达到变邻域操作次数上限。

[0094] 在一个实施例中，规划结果生成模块304具体用于：将第一路径集合和第二路径集合进行融合，得到第三路径集合，第三路径集合包括多个第三路径；对多个第三路径进行非支配排序处理，按照支配等级从小到大的顺序，根据预设的路径数量阈值生成第四路径集合；根据第四路径集合，生成车辆路径的规划结果。

[0095] 在一个实施例中，规划参数还可以包括迭代次数上限，装置还可以包括迭代次数校验模块（图中未示出），用于：获取当前迭代次数，并比较当前迭代次数和迭代次数上限；在当前迭代次数小于迭代次数上限的情况下，通过第四路径集合生成新的第一路径集合，重新返回至对第一路径集合进行进化处理和变邻域操作处理的步骤，直到当前迭代次数达到迭代次数上限。

[0096] 在一个实施例中，规划结果生成模块304具体用于：从多个规划目标中确定主要规划目标；按照主要规划目标，从第四路径集合中选出主要规划目标最优的第四路径；根据主要规划目标最优的第四路径，生成车辆路径的规划结果。

[0097] 另外，在本发明实施例中车辆路径的规划装置的具体实施内容，在上面车辆路径的规划方法中已经详细说明了，故在此重复内容不再说明。

[0098] 图4示出了可以应用本发明实施例的车辆路径的规划方法或车辆路径的规划装置的示例性系统架构400。

[0099] 如图4所示，系统架构400可以包括终端设备401、402、403，网络404和服务器405。网络404用以在终端设备401、402、403和服务器405之间提供通信链路的介质。网络404可以包括各种连接类型，例如有线、无线通信链路或者光纤电缆等等。

[0100] 用户可以使用终端设备401、402、403通过网络404与服务器405交互，以接收或发送消息等。终端设备401、402、403上可以安装有各种通讯客户端应用，例如车辆路径规划类应用、物流应用、规划类应用、即时通信工具、邮箱客户端、社交平台软件等（仅为示例）。

[0101] 终端设备401、402、403可以是具有显示屏并且支持网页浏览的各种电子设备，包括但不限于智能手机、平板电脑、膝上型便携计算机和台式计算机等等。

[0102] 服务器405可以是提供各种服务的服务器，例如对用户利用终端设备401、402、403所浏览的车辆路径规划类网站提供支持的后台管理服务器（仅为示例）。后台管理服务器可以对接收到的车辆路径的规划请求等数据进行响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标；按照预先设置的规划参数，根据车辆途经点信息生成第一路径集合；对第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合；基于多个规划目标，通过第一路径集合和第二路径集合，生成车辆路径的规划结果等处理，并将处理结果（例如车辆路径的规划结果‑‑仅为示例）反馈给终端设备。

[0103] 需要说明的是，本发明实施例所提供的车辆路径的规划方法一般由服务器405执行，相应地，车辆路径的规划装置一般设置于服务器405中。

[0104] 应该理解，图4中的终端设备、网络和服务器的数目仅仅是示意性的。根据实现需要，可以具有任意数目的终端设备、网络和服务器。

[0105] 下面参考图5，其示出了适于用来实现本发明实施例的终端设备或服务器的计算机系统500的结构示意图。图5示出的终端设备或服务器仅仅是一个示例，不应对本发明实施例的功能和使用范围带来任何限制。

[0106]  如图5所示，计算机系统500包括中央处理单元（CPU）501，其可以根据存储在只读存储器（ROM）502中的程序或者从存储部分508加载到随机访问存储器（RAM）503中的程序而执行各种适当的动作和处理。在RAM 503中，还存储有系统500操作所需的各种程序和数据。CPU 501、ROM 502以及RAM 503通过总线504彼此相连。输入/输出（I/O）接口505也连接至总线504。

[0107] 以下部件连接至I/O接口505：包括键盘、鼠标等的输入部分506；包括诸如阴极射线管（CRT）、液晶显示器（LCD）等以及扬声器等的输出部分507；包括硬盘等的存储部分508；以及包括诸如LAN卡、调制解调器等的网络接口卡的通信部分509。通信部分509经由诸如因特网的网络执行通信处理。驱动器510也根据需要连接至I/O接口505。可拆卸介质511，诸如磁盘、光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器510上，以便于从其上读出的计算机程序根据需要被安装入存储部分508。

[0108] 特别地，根据本发明公开的实施例，上文参考流程图描述的过程可以被实现为计算机软件程序。例如，本发明公开的实施例包括一种计算机程序产品，其包括承载在计算机可读介质上的计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。在这样的实施例中，该计算机程序可以通过通信部分509从网络上被下载和安装，和/或从可拆卸介质511被安装。在该计算机程序被中央处理单元（CPU）501执行时，执行本发明的系统中限定的上述功能。

[0109] 需要说明的是，本发明所示的计算机可读介质可以是计算机可读信号介质或者计算机可读存储介质或者是上述两者的任意组合。计算机可读存储介质例如可以是——但不限于——电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。计算机可读存储介质的更具体的例子可以包括但不限于：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机访问存储器（RAM）、只读存储器（ROM）、可擦式可编程只读存储器（EPROM或闪存）、光纤、便携式紧凑磁盘只读存储器（CD‑ROM）、光存储器件、磁存储器件、或者上述的任意合适的组合。在本发明中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。而在本发明中，计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括但不限于：无线、电线、光缆、RF等等，或者上述的任意合适的组合。

[0110] 附图中的流程图和框图，图示了按照本发明各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段、或代码的一部分，上述模块、程序段、或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图或流程图中的每个方框、以及框图或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

[0111] 描述于本发明实施例中所涉及到的模块可以通过软件的方式实现，也可以通过硬件的方式来实现。所描述的模块也可以设置在处理器中，例如，可以描述为：一种处理器包括请求响应模块、第一路径集合生成模块、第二路径集合生成模块、规划结果生成模块。其中，这些模块的名称在某种情况下并不构成对该模块本身的限定，例如，请求响应模块还可以被描述为“用于响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标的模块”。

[0112] 作为另一方面，本发明还提供了一种计算机可读介质，该计算机可读介质可以是上述实施例中描述的设备中所包含的；也可以是单独存在，而未装配入该设备中。上述计算机可读介质承载有一个或者多个程序，当上述一个或者多个程序被一个该设备执行时，使得该设备包括：响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标；按照预先设置的规划参数，根据车辆途经点信息生成第一路径集合；对第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合；基于多个规划目标，通过第一路径集合和第二路径集合，生成车辆路径的规划结果。

[0113] 根据本发明实施例的技术方案，响应于车辆路径的规划请求，获取车辆途经点信息和多个规划目标；按照预先设置的规划参数，根据车辆途经点信息生成第一路径集合；对第一路径集合进行进化处理和变邻域操作处理，生成第二路径集合；基于多个规划目标，通过第一路径集合和第二路径集合，生成车辆路径的规划结果。能够设置多个规划目标，并基于进化处理和变邻域操作处理，针对多个规划目标进行路径规划，并降低路径规划的时间复杂度，提高实时响应度。

[0114] 上述具体实施方式，并不构成对本发明保护范围的限制。本领域技术人员应该明白的是，取决于设计要求和其他因素，可以发生各种各样的修改、组合、子组合和替代。任何在本发明的精神和原则之内所作的修改、等同替换和改进等，均应包含在本发明保护范围之内。