一种便民服务任务路线规划方法、系统及其相关组件

技术领域

本发明涉及路线规划技术领域，尤其涉及一种便民服务任务路线规划方法、系统及其相关组件。

背景技术

在物业服务场景中，业主对于一些便民服务，例如送水任务服务、维修服务等的需求也急剧增长，便民服务路径规划问题的目的是通过搜索服务人员取件和服务的最优顺序以及完成服务任务的最佳路线，找到下达给服务人员一系列指令的最佳解决方案。由于其动态性，任务可以在提供服务的过程中被分配给服务人员，这最终使得解决方案转化为实时路径规划问题。这种任务的动态性是全天候的，并且服务人员在取件和服务的过程中可能会持续地接收任务至待完成任务列表中。一般来说，机器学习和启发式搜索方法一直是解决路径问题的首选方法。启发式搜索方法通常将该问题建模为PDPTW(带时间窗的取件和行驶问题)，以达到最小化时间延迟和实现最短行程距离。此外，一些研究将该问题建模为一个路线推荐问题，其中通过使用启发式方法来限制搜索空间从而找到最短路径，然而另一些研究使用深度学习方法通过路径行程中的空间模式来定位流行路径。如果使用特定路径，预测两个地点之间的到达时间也可用于估计到达时间。

机器学习和启发式搜索方法采取不同的方法来解决路径优化问题，但都有各自的缺点。深度学习方法通过试图预测服务人员的最短旅行时间和/或将选择的路线，将问题建模为一个预测问题，而不是仅仅寻找最佳路线。这种预测方法完全依赖于服务人员的反馈是有效的，但如果服务人员在某个社区缺乏经验，或者不熟悉给定路线，或者系统中的新任务地点无效时，则预测方法可能会达不到要求。另一方面，启发式方法不依赖服务人员反馈，而仅考虑路网。另外，使用启发式方法的路线搜索空间非常大，会影响其解的质量。当出现新的任务地点且历史任务地点信息不可用时，启发式方法可能比深度学习方法更有效。同时，大多数启发式方法都存在可扩展性问题，在动态问题中表现不佳。因此，对于为服务人员找到更好的任务路线以满足客户需求非常重要。

发明内容

本发明实施例提供了一种便民服务任务路线规划方法、系统及其相关组件，旨在解决现有技术中无法实时为服务人员获取最优的任务路线的问题。

第一方面，本发明实施例提供了一种便民服务任务路线规划方法，包括：

实时获取人员信息、环境信息及任务信息，将所述人员信息、环境信息及任务信息输入至深度学习模块中进行路线预测和时间预测，生成实时路线概率图和实时时间序列图，并根据实时路线概率图生成初始执行路线序列；

将所述初始执行路线序列输入至过程挖掘模块，通过所述过程挖掘模块从数据库中查询所述初始执行路线序列中相邻序列点的历史行程信息，根据相邻序列点的历史行程信息计算相邻序列点之间的路线的执行概率和平均时间，并生成历史执行概率图和历史平均时间图；

基于实时路线概率图、实时时间序列图、历史执行概率图和历史平均时间图利用最短路线算法计算最优执行路线；

在执行所述最优执行路线时，当获取到新的任务信息时，利用深度学习模块重新进行路线预测和时间预测，并得到优化执行路线序列，将优化执行路线序列输入至过程挖掘模块进行过程挖掘，得到新的历史执行概率图和历史平均时间图，并重新利用最短路线算法计算新的最优执行路线。

第二方面，本发明实施例提供了一种便民服务任务路线规划系统，其包括：

深度学习模块预测单元，用于实时获取人员信息、环境信息及任务信息，将所述人员信息、环境信息及任务信息输入至深度学习模块中进行路线预测和时间预测，生成实时路线概率图和实时时间序列图，并根据实时路线概率图生成初始执行路线序列；

历史行程信息查询单元，用于将所述初始执行路线序列输入至过程挖掘模块，通过所述过程挖掘模块从数据库中查询所述初始执行路线序列中相邻序列点的历史行程信息，根据相邻序列点的历史行程信息计算相邻序列点之间的路线的执行概率和平均时间，并生成历史执行概率图和历史平均时间图；

最优执行路线计算单元，用于基于实时路线概率图、实时时间序列图、历史执行概率图和历史平均时间图利用最短路线算法计算最优执行路线；

最优执行路线更新单元，用于在执行所述最优执行路线时，当获取到新的任务信息时，利用深度学习模块重新进行路线预测和时间预测，并得到优化执行路线序列，将优化执行路线序列输入至过程挖掘模块进行过程挖掘，得到新的历史执行概率图和历史平均时间图，并重新利用最短路线算法计算新的最优执行路线。

第三方面，本发明实施例又提供了一种计算机设备，其包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现上述第一方面所述的便民服务任务路线规划方法。

第四方面，本发明实施例还提供了一种计算机可读存储介质，其中所述计算机可读存储介质存储有计算机程序，所述计算机程序当被处理器执行时使所述处理器执行上述第一方面所述的便民服务任务路线规划方法。

本发明实施例提供了一种便民服务任务路线规划方法、系统及其相关组件，该方法包括：实时获取人员信息、环境信息及任务信息，将所述人员信息、环境信息及任务信息输入至深度学习模块中进行路线预测和时间预测，生成实时路线概率图和实时时间序列图，并根据实时路线概率图生成初始执行路线序列；将所述初始执行路线序列输入至过程挖掘模块，通过所述过程挖掘模块从数据库中查询所述初始执行路线序列中相邻序列点的历史行程信息，根据相邻序列点的历史行程信息计算相邻序列点之间的路线的执行概率和平均时间，并生成历史执行概率图和历史平均时间图；基于实时路线概率图、实时时间序列图、历史执行概率图和历史平均时间图利用最短路线算法计算最优执行路线；在执行所述最优执行路线时，当获取到新的任务信息时，利用深度学习模块重新进行路线预测和时间预测，并得到优化执行路线序列，将优化执行路线序列输入至过程挖掘模块进行过程挖掘，得到新的历史执行概率图和历史平均时间图，并重新利用最短路线算法计算新的最优执行路线。本发明实施例通过深度学习模块获取实时数据，利用过程挖掘模块获取历史数据，最后基于实时数据和历史数据通过最短路线算法计算出最优执行路线，并在任务更新时实时更新最优执行路线，从而解决了服务人员执行任务过程中，增加新任务后无法快速更新最优执行路线的问题，提高了服务人员的服务效率。

附图说明

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

图1为本发明实施例提供的便民服务任务路线规划方法的流程示意图；

图2为本发明实施例提供的便民服务任务路线规划方法的子流程示意图；

图3为本发明实施例提供的便民服务任务路线规划方法的深度学习模块的网络框架示意图；

图4为本发明实施例提供的便民服务任务路线规划方法的工作流程示意图；

图5为本发明实施例提供的便民服务任务路线规划方法的另一子流程示意图；

图6为本发明实施例提供的便民服务任务路线规划系统的示意性框图；

图7为本发明实施例提供的便民服务任务路线规划系统的子单元示意性框图；

图8为本发明实施例提供的便民服务任务路线规划系统的另一子单元示意性框图。

具体实施方式

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

应当理解，当在本说明书和所附权利要求书中使用时，术语“包括”和“包含”指示所描述特征、整体、步骤、操作、元素和/或组件的存在，但并不排除一个或多个其它特征、整体、步骤、操作、元素、组件和/或其集合的存在或添加。

还应当理解，在此本发明说明书中所使用的术语仅仅是出于描述特定实施例的目的而并不意在限制本发明。如在本发明说明书和所附权利要求书中所使用的那样，除非上下文清楚地指明其它情况，否则单数形式的“一”、“一个”及“该”意在包括复数形式。

还应当进一步理解，在本发明说明书和所附权利要求书中使用的术语“和/或”是指相关联列出的项中的一个或多个的任何组合以及所有可能组合，并且包括这些组合。

请参阅图1，图1为本发明实施例提供的一种便民服务任务路线规划方法的流程示意图，该方法包括步骤S101～S104。

S101、实时获取人员信息、环境信息及任务信息，将所述人员信息、环境信息及任务信息输入至深度学习模块中进行路线预测和时间预测，生成实时路线概率图和实时时间序列图，并根据实时路线概率图生成初始执行路线序列；

S102、将所述初始执行路线序列输入至过程挖掘模块，通过所述过程挖掘模块从数据库中查询所述初始执行路线序列中相邻序列点的历史行程信息，根据相邻序列点的历史行程信息计算相邻序列点之间的路线的历史执行概率和历史平均时间，并生成历史执行概率图和历史平均时间图；

S103、基于实时路线概率图、实时时间序列图、历史执行概率图和历史平均时间图利用最短路线算法计算最优执行路线；

S104、在执行所述最优执行路线时，当获取到新的任务信息时，利用深度学习模块重新进行路线预测和时间预测，并得到新的执行路线序列，将新的执行路线序列输入至过程挖掘模块进行过程挖掘，得到新的历史执行概率图和历史平均时间图，并重新利用最短路线算法计算新的最优执行路线。

在本实施例中，通过将所述人员信息、环境信息及任务信息输入深度学习模块进行路线预测和时间预测，生成实时路线概率图和实时时间序列图，再根据实时路线概率图生成初始执行路线序列；过程挖掘模块利用所述深度学习模块生成的所述初始执行路线序列，从数据库中查询相邻序列点的对应的历史行程信息，根据查询结果计算相邻序列点之间的路线的历史执行概率和历史平均时间，并生成历史执行概率图和历史平均时间图；最后基于路线概率图、时间序列图、历史执行概率图和历史平均时间图计算出最优执行路线；在按照最优执行路线执行任务时，当获取到新的任务信息时，同时获取对应的人员信息和环境信息，并重新计算新的最优执行路线。其中，所述人员信息包括服务人员的人数以及每个服务人员对应的个人信息，所述环境信息包括每个任务点之间的路线数量以及每条路线的环境情况，所述任务信息包括每个服务人员需要执行的任务以及每个任务对应的任务点信息。

在一具体应用场景中，请参见表1，服务任务路径问题的目标是为服务人员找到分配的派送任务集O中的每个任务从取件点

TD(t)＝[TD

其中，t表示一天中的时刻，i,j表示2个地点，N满足N＝(n*2)+1，n为所有任务数量。

搜索空间中的解决方案是所有点的排列组合，且完成一系列服务任务的总时间可以表示为

其中，

1.路线一定要从l

2.到达每个任务取件点的时间一定要在到达任务点的时间之前；

3.每个任务取件时间不能早于PT

注意到服务人员需要从l

其中，TD

表1

本实施例通过采用深度学习模块和过程挖掘模块获取实时数据和历史数据，并利用最短路线算法计算最优执行路线，从而解决上述问题。

具体的，在执行当前最优执行路线之前或者按照当前最优执行路线从当前序列点移动到下一序列点后，若获取到新的任务信息，则重新计算新的最优执行路线；若在按照当前最优执行路线从当前序列点移动到下一序列点的过程中，获取到新的任务信息时，则在到达下一序列点时重新计算新的最优执行路线，并按照新的最优执行路线继续执行任务。

深度学习模块采用了被分配了一系列派送任务服务人员的历史相关信息，并预测出可行的路线以及任务时间帮助服务人员执行任务。本实施例中的深度学习模块可以采用FDNET路线时间预测算法预测路线和时间，并根据预测结果生成深度学习信息素图(DeepLPG，即实时路线概率图)。DeepLPG图中记录了采用每一路线分支的概率，从而得到采用每一条路线的概率，生成初始执行路线序列。同理，从一个地点到另一个地点的时间也可以通过深度学习模块进行预测，并将预测结果保存至深度时间图(DeepTG，即实时时间序列图)中。

在过程挖掘模块中，通过深度学习模块预测的初始执行路线序列被作为主要输入。给定1个初始执行路线序列[a,b,c,…,n]，过程挖掘模块将此序列拆分成连续的序列，如[a,b],[b,c],…,[n-1,n]。在这个模块中，1个序列只有当服务人员正在完成1个任务时可以被使用，例如：对于序列[a,b]，服务人员从任务a的位置移动到任务b时，序列[a,b]才会被使用，而剩余的序列[b,c],…,[n-1,n]只有在完成序列[a,b]后才会继续被使用。这是因为在完成一个任务后，即下一个序列开始前，可能会有新的任务分配给服务人员，改变了原有的序列，因此需要重新获取新的执行序列。考虑这种情况：当服务人员位于位置a，将要去往位置b时，查询两地之间便民服务任务数据库中的历史服务人员行驶数据，当得到查询结果后，选择1个特定路线分支的概率可以使用选择1个特定路线分支的服务人员数量除以总的查询记录计算得到。如此可以提供服务人员在两个地点之间行驶的历史执行概率。历史执行概率信息会被存储在服务人员信息图(DriverLPG，即历史执行概率图)中。所有服务人员从1个路线分支到另一个路线分支的平均行驶时间也可以计算出来并存储在服务人员时间图(DriverTG，即历史平均时间图)中。

基于实时路线概率图、实时时间序列图、历史执行概率图和历史平均时间图，并使用最短路线算法计算最优执行路线。本实施例可以采用蚁群算法计算最优执行路线。

在本实施例中，如图2所示，所述将所述人员信息、环境信息及任务信息输入至深度学习模块中进行路线预测和时间预测，生成实时路线概率图和实时时间序列图，包括：

S201、将服务人员的人员信息、环境信息及任务信息输入至FDNET框架的路线预测模块进行路线预测，得到每个序列点之间的路线的执行概率；

S202、将每个序列点之间的路线的执行概率输入至FDNET框架的时间预测模块进行时间预测，得到每个序列点之间的路线对应的时间；

S203、根据每个序列点之间的路线的执行概率和每个序列点之间的路线对应的时间生成实时路线概率图和实时时间序列图。

在本实施例中，所述深度学习模块采用FDNET框架，包括用于路线预测的路线预测模块和用于时间预测的时间预测模块，先将服务人员的人员信息、环境信息及任务信息输入至路线预测模块内预测每个序列点之间的路线的执行概率，然后时间预测模块根据每个序列点之间的路线的执行概率预测每个序列点之间的路线对应的时间，并生成对应的实时路线概率图和实时时间序列图。

具体的，如图3所示，所述深度学习模块包括路线预测模块和时间预测模块。所述路线预测模块的输入为人员信息、环境信息及任务信息，输出为可行的路线。所述路线预测模块根据过去的行为和当前的条件，预测服务人员下一步将到达的每个可行位置的概率。这意味着路线预测模块对于给定的服务人员可预测出针对性的路线。路线预测模块采用公式

在一具体应用场景中，结合图4，给定一组任务[O

DeepLPG图中每条路线的概率可以通过以下公式计算：

DeepLPG(t)＝[P

DeepTG图中每条路线的时间可以通过以下公式计算：

DeepTG(t)＝[Pt

其中，i和j表示2个地点，P

在一实施例中，所述通过所述过程挖掘模块从数据库中查询所述初始执行路线序列中相邻序列点的历史行程信息，根据相邻序列点的历史行程信息计算相邻序列点之间的路线的执行概率和平均时间，并生成历史执行概率图和历史平均时间图，包括：

获取一段时间内相邻序列点之间的历史服务人员行驶信息条目，并根据历史服务人员行驶信息条目中的行驶日志或轨迹，计算相邻序列点之间的路线对应的执行概率和平均时间，并生成历史执行概率图和历史平均时间图。

在本实施例中，根据一段时间内每个相邻序列点之间的历史服务人员行驶信息条目中的行驶日志或轨迹，计算每个相邻序列点之间的路线所对应的执行概率以及平均时间，生成对应的历史执行概率图和历史平均时间图。

过程挖掘模块根据所述初始执行路线序列中的序列点，去查询2个序列点之间的历史行程信息。对于给定的示例序列

在一具体实施例中，按下式计算执行概率：

其中，k为循环迭代的变量，k∈(1,2,3…m)，m是查询结果的数量，TD

相邻序列点之间的路线对应的平均时间也可以计算出来，并保存在对应的图DriverTG(即历史平均时间图)中。具体通过下式计算平均时间：

其中，TD

在一实施例中，如图5所示，所述基于实时路线概率图、实时时间序列图、历史执行概率图和历史平均时间图利用最短路线算法计算最优执行路线，包括：

S301、将实时路线概率图、实时时间序列图、历史执行概率图和历史平均时间图按照预设的分组规则进行分组，并根据预定义的信息素图对每一组进行初始化，得到多组初始化序列；

S302、按照预设的概率规则选择每一组初始化序列的路线，并对每一组初始化序列的路线进行迭代处理，得到最优执行路线。

在本实施例中，先按照预设的分组规则对实时路线概率图、实时时间序列图、历史执行概率图和历史平均时间图进行分组，然后利用预定义的信息素图对每一组进行初始化，得到多组初始化序列；然后按照预设的概率规则选择每一组的路线，并进行迭代，得到最优执行路线。

本实施例采用的最短路线算法可以是蚁群算法，先对实时路线概率图(DeepLPG)、实时时间序列图(DeepTG)、历史执行概率图(DriverLPG)和历史平均时间图(DriverTG)进行分组，可以分为7组，分别是：1.DeepLPG+DeepTG；2.DeepLPG+DriverTG；3.DriverLPG+DeepTG；4.DriverLPG+DriverTG；5.DeepLPG+DriverLPG+DeepTG；6.DeepLPG+DriverLPG+DriverTG；7.DeepLPG+DriverLPG+DeepTG+DriverTG。

每一组即为蚁群算法的一个蚁群，利用预定义的信息素图对每一个蚁群进行初始化。蚁群算法模拟真实蚂蚁寻找通往食物来源路线的集体行为。在蚁群优化算法中，蚂蚁使用信息素轨迹来构造优化问题的解，并且经过一条路线后，会留下一条信息素轨迹，因此，每一条信息素轨迹即相当于路线轨迹。在蚁群算法中，每个蚁群中的蚂蚁根据概率规则来选择下一条路线或下一个序列点，则利用以下公式计算每两个序列点之间的路线概率：

其中[τ

蚁群算法在初始期间有一个固定的浓度值，在每一次迭代完成之后，所有出去的蚂蚁回来后，会对所走过的路线进行计算，然后更新相应的边的信息素浓度。经过一次次的迭代，两个序列点之间的路线距离越近，信息素的浓度越高，从而得到最优执行路线。

每一次迭代，信息素浓度会随之进行更新，按照以下公式进行迭代计算：

其中，ρ是挥发率，范围为(0,1]，τ

在经过多次迭代后，处于最优执行路线的蚂蚁释放的信息素如下所示：

好的蚂蚁选择的路线，τ

请参阅图6，图6为本发明实施例提供的一种便民服务任务路线规划系统的示意性框图，该便民服务任务路线规划系统200包括：

深度学习模块预测单元201，用于实时获取人员信息、环境信息及任务信息，将所述人员信息、环境信息及任务信息输入至深度学习模块中进行路线预测和时间预测，生成实时路线概率图和实时时间序列图，并根据实时路线概率图生成初始执行路线序列；

历史行程信息查询单元202，用于将所述初始执行路线序列输入至过程挖掘模块，通过所述过程挖掘模块从数据库中查询所述初始执行路线序列中相邻序列点的历史行程信息，根据相邻序列点的历史行程信息计算相邻序列点之间的路线的执行概率和平均时间，并生成历史执行概率图和历史平均时间图；

最优执行路线计算单元203，用于基于实时路线概率图、实时时间序列图、历史执行概率图和历史平均时间图利用最短路线算法计算最优执行路线；

最优执行路线更新单元204，用于在执行所述最优执行路线时，当获取到新的任务信息时，利用深度学习模块重新进行路线预测和时间预测，并得到优化执行路线序列，将优化执行路线序列输入至过程挖掘模块进行过程挖掘，得到新的历史执行概率图和历史平均时间图，并重新利用最短路线算法计算新的最优执行路线。

在一实施例中，如图7所示，所述深度学习模块预测单元201，包括：

路线预测单元301，用于将服务人员的人员信息、环境信息及任务信息输入至FDNET框架的路线预测模块进行路线预测，得到每个序列点之间的路线的执行概率；

时间预测单元302，用于将每个序列点之间的路线的执行概率输入至FDNET框架的时间预测模块进行时间预测，得到每个序列点之间的路线对应的时间；

路线概率图及时间序列图生成单元303，用于根据每个序列点之间的路线的执行概率和每个序列点之间的路线对应的时间生成实时路线概率图和实时时间序列图。

在一实施例中，所述历史行程信息查询单元202，包括：

执行概率及平均时间计算单元，用于获取一段时间内相邻序列点之间的历史服务人员行驶信息条目，并根据历史服务人员行驶信息条目中的行驶日志或轨迹，计算相邻序列点之间的路线对应的执行概率和平均时间，并生成历史执行概率图和历史平均时间图。

在一实施例中，所述执行概率及平均时间计算单元，包括：

执行概率公式计算单元，用于按下式计算执行概率：

其中，k为循环迭代的变量，k∈(1,2,3…m)，m是查询结果的数量，TD

在一实施例中，如图8所示，所述最优执行路线计算单元203，包括：

多组初始化序列获取单元401，用于将实时路线概率图、实时时间序列图、历史执行概率图和历史平均时间图按照预设的分组规则进行分组，并根据预定义的信息素图对每一组进行初始化，得到多组初始化序列；

初始化序列路线迭代单元402，用于按照预设的概率规则选择每一组初始化序列的路线，并对每一组初始化序列的路线进行迭代处理，得到最优执行路线。

在一实施例中，所述初始化序列路线迭代单元，包括：

路线概率计算单元，用于利用以下公式计算每两个序列点之间的路线概率：

其中[τ

在一实施例中，所述初始化序列路线迭代单元，包括：

迭代公式计算单元，用于按照以下公式进行迭代计算：

其中，ρ是挥发率，范围为(0,1]，τ

本发明实施例还提供一种计算机设备，包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现如上所述的便民服务任务路线规划方法。

本发明实施例还提供一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如上所述的便民服务任务路线规划方法。

说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的系统而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以对本发明进行若干改进和修饰，这些改进和修饰也落入本发明权利要求的保护范围内。

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