一种配送任务的分配方法及装置与流程

1.本说明书一个或多个实施例涉及任务调度技术领域，尤其涉及一种配送任务的分配方法及装置。

背景技术：

2.在物流配送领域，配送成本占整个物流成本的比例较大，而影响配送成本的其中一个主要因素就是如何合理的安排物流配送路线。相关技术中，对于物流配送路线的规划，可以采用模糊聚类的方式将多个待配送的任务地址信息进行聚类划分，聚类得到的每一个任务地址信息的集合可以由一个配送员进行配送。
3.但是这种方式的缺点是，配送任务的分配不均衡，比如，配送员有时要去距离自己所在位置较远的任务地址信息进行配送，而该任务地址信息实际上距离另一个配送员更近，即配送任务分配不合理。而这就导致物流配送的路程更远，物流配送的成本较高。

技术实现要素：

4.有鉴于此，本说明书一个或多个实施例提供一种配送任务的分配方法及装置，以降低物流配送的成本。
5.为实现上述目的，本说明书一个或多个实施例提供技术方案如下：
6.根据本说明书一个或多个实施例的第一方面，提出了一种配送任务的分配方法，该方法包括：
7.分别获取n个任务地址信息、以及m个配送服务方中每个配送服务方的配送起点位置，所述n和m是正整数；每个所述任务地址信息对应一笔配送任务，所述配送起点位置表示负责执行配送任务的配送服务方的配送起点；
8.根据所述m个配送服务方的配送起点位置，构建得到m个泰森多边形，每个泰森多边形的内部包括一个所述配送服务方的配送起点位置；
9.将所述n个任务地址信息分配至所述m个泰森多边形中，以使得每个泰森多边形内包括的配送起点位置对应的配送服务方执行分配至所述泰森多边形的各任务地址信息对应的配送任务。
10.根据本说明书一个或多个实施例的第二方面，提出了一种配送任务的分配装置，所述装置包括：
11.数据获取模块，用于分别获取n个任务地址信息、以及m个配送服务方中每个配送服务方的配送起点位置，所述n和m是正整数；每个所述任务地址信息对应一笔配送任务，所述配送起点位置表示负责执行配送任务的配送服务方的配送起点；
12.泰森图构造模块，用于根据所述m个配送服务方的配送起点位置，构建得到m个泰森多边形，每个泰森多边形的内部包括一个所述配送服务方的配送起点位置；
13.任务分配模块，用于将所述n个任务地址信息分配至所述m个泰森多边形中。
14.根据本说明书一个或多个实施例的第三方面，提供了一种电子设备，包括：
15.处理器；
16.用于存储处理器可执行指令的存储器；
17.其中，所述处理器通过运行所述可执行指令以实现本说明书任一实施例的方法。
18.根据本说明书一个或多个实施例的第四方面，提供了一种计算机可读存储介质，其上存储有计算机指令，该指令被处理器执行时实现如本说明书任一实施例的方法。
19.本说明书实施例的配送任务的分配方法及装置，通过基于配送服务方的配送起点位置构建泰森多边形，并将任务地址信息分配至各个泰森多边形，使得配送任务能够较为均衡的得到分配，而更为均衡合理的任务分配，有助于使得节省物流成本。
附图说明
20.为了更清楚地说明本公开一个或多个实施例或相关技术中的技术方案，下面将对实施例或相关技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本公开一个或多个实施例中记载的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。
21.图1a是一示例性实施例提供的一种配送任务的分配方法的流程图。
22.图1b是一示例性实施例提供的一种任务地址信息的确定方式示意图。
23.图2是一示例性实施例提供的构造三角网的示意图。
24.图3是一示例性实施例提供的外心点集合的示意图。
25.图4是一示例性实施例提供的泰森多边形的示意图。
26.图5a是一示例性实施例提供的一种凸包的计算流程图。
27.图5b是一示例性实施例提供的一种外卖送餐场景下的配送任务的分配示意图。
28.图5c是一示例性实施例提供的另一种外卖送餐场景下的配送任务的分配示意图。
29.图6是一示例性实施例提供的一种配送任务的分配方法的流程图。
30.图7是一示例性实施例提供的一种交点统计的示意图。
31.图8是一示例性实施例提供的一种交点统计的示意图。
32.图9是一示例性实施例提供的一种任务地址信息的分配的示意图。
33.图10是一示例性实施例提供的另一种配送任务的分配方法的流程示意图。
34.图11是一示例性实施例提供的一种配送任务的分配装置的结构示意图。
35.图12是一示例性实施例提供的一种配送任务的分配装置的结构示意图。
具体实施方式
36.这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本说明书一个或多个实施例相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本说明书一个或多个实施例的一些方面相一致的装置和方法的例子。
37.需要说明的是：在其他实施例中并不一定按照本说明书示出和描述的顺序来执行相应方法的步骤。在一些其他实施例中，其方法所包括的步骤可以比本说明书所描述的更多或更少。此外，本说明书中所描述的单个步骤，在其他实施例中可能被分解为多个步骤进
行描述；而本说明书中所描述的多个步骤，在其他实施例中也可能被合并为单个步骤进行描述。
38.物流配送的场景中，通常可以是由m个配送服务方协同对n个任务地址信息对应的配送任务进行配送。其中，n和m是正整数。例如，假设n等于8，m等于3，那就是由这3个配送服务方共同对所述的8个任务地址信息对应的配送任务进行配送，并且，各个配送服务方负责配送的配送任务不能重复。
39.示例性的，以n个任务地址信息是n个配送任务的配送目的地为例，配送服务方y1可以由所在起点出发，去往任务地址信息s1、s2、s3和s4配送货物，完成配送后回到起点。配送服务方y2由其所在起点出发，去往任务地址信息s5和s6配送货物，完成配送后回到起点。配送服务方y3由其所在起点出发，去往任务地址信息s7和s8配送货物，完成配送后回到起点。如此，每个配送服务方负责配送了部分的任务地址信息，3个配送服务方(y1/y2/y3)协同完成了8个任务地址信息(s1至s8)的配送。
40.在上述的物流配送场景中，涉及到要为m个配送服务方分配物流配送的任务，比如，每一个配送服务方负责去往哪些任务地址信息进行配送，以及在为配送服务方分配好任务地址信息之后，还可以为该配送服务方规划这些任务地址信息之间的物流配送路线。如何合理的进行物流任务的分配，以及如何合理的为配送服务方规划配送路线，是一项关系到物流成本的问题。如果物流任务分配不合理，或者物流配送路线的路线规划的不合理，都可能会增加物流成本，且用户体验也不好。例如，为m个配送服务方分配物流任务以及规划配送路线的问题，可以抽象为mmtsp(multi starting point and multi-objective traveling salesman problem，多起点多目标旅行商问题)，该mmtsp问题即：m个配送服务方协同遍历全部的n个任务地址信息，且该m个配送服务方分别从m个起点出发遍历其中的部分任务地址信息，该m个配送服务方协同遍历n个任务地址信息的总路程最短。
41.该mmtsp问题可以用数学模型描述如下：
42.目标函数：
[0043][0044]
上述的公式(1)表示，m个配送服务方协同遍历全部的n个任务地址信息，且总路程最短。其中，d
pq
表示配置目的位置p到配置目的位置q的直线距离。
[0045]
约束条件：
[0046][0047]
其中，公式(2)表示：任意一个任务地址信息p，存在且仅存在唯一一个任务地址信
息q，存在某个配送服务方i由任务地址信息p到任务地址信息q；
[0048]
公式(3)表示：任意一个任务地址信息q，存在且仅存在唯一一个任务地址信息p，存在某个配送服务方i由任务地址信息p到任务地址信息q；
[0049]
公式(4)表示：m个人协同遍历全部的n个任务地址信息，且无任务地址信息被遍历多次；
[0050]
公式(5)表示：当第i个配送服务方经任务地址信息p到任务地址信息q时，t
ipq
＝1，否则t
ipq
＝0。
[0051]
即，上述mmtsp问题的目标可以总结为：m个配送服务方协同遍历全部的n个任务地址信息，所有的任务地址信息都能被遍历到，并且不会有任务地址信息被重复遍历，每一个任务地址信息只被其中一个配送服务方遍历，并且，当该m个配送服务方协同遍历完成n个任务地址信息时，其总路程是最短的。
[0052]
本公开实施例提供一种配送任务的分配方法，该方法可以用于解决上述的mmtsp问题，实现对配送服务方的配送任务的分配或物流配送路线的规划。其中，该方法采用了泰森图来求解物流配送的mmtsp问题。泰森图也称voronoi图。利用泰森图求解该问题能够满足上述mmtsp问题的约束条件。
[0053]
图1a是一示例性实施例提供的一种配送任务的分配方法的流程示意图，如图1a所示，该方法可以包括如下处理：
[0054]
在步骤100中，分别获取n个任务地址信息、以及m个配送服务方中每个配送服务方的配送起点位置。
[0055]
本步骤中，可以获取m个配送服务方中每个配送服务方的配送起点位置，并获取该m个配送服务方要协同遍历的n个任务地址信息。所述的配送起点位置和任务地址信息可以用位置坐标(x,y)表示，其中，示例性的，x可以是经度，y可以是纬度。或者该位置坐标(x,y)也可以是自定义的其他坐标系下的坐标，不一定是经纬度坐标，比如还可以是投影坐标等。
[0056]
每个所述任务地址信息对应一笔配送任务。比如，该任务地址信息可以表示一笔配送任务的配送终点，所述配送起点位置表示负责执行配送任务的配送服务方的配送起点。比如，一笔配送任务可以是由配送服务方所在的配送起点位置，配送货物到上述任务地址信息对应的配送终点，当配送服务方去往各个任务地址信息完成配送后，可以回到该起点位置，或者也可以不回到该起点位置。
[0057]
此外，本说明书实施例中的配送任务可以是配送任何对象，比如，配送餐食，配送快递，配送货物等。本实施例中的不同的任务地址信息，包括但不限于：不同的城市、或者同一城市的不同小区，或者同一仓库内的不同区域，等。所述的配送服务方，包括但不限于：外卖员、快递员、货车司机、无人机、或者物流机器人等。比如，多个货车司机可以协同在多个城市间进行物流配送，或者多个快递员协同遍历同一个城市的不同小区，或者多个机器人协同在同一仓库系统的不同存储区域间进行配送，等。
[0058]
示例一种本实施例的方法的执行场景：比如，可以通过该方法为快递员分配订单，以及为快递员规划配送路线。如果有m个快递员要协同进行n个小区的快递配送，可以通过本实施例的方法为各个快递员分配待配送的小区，该方法能够使得尽可能的将距离快递员较近的小区分配给快递员。在该例子中，上述协同的m个快递员可以是具有不同的配送起点位置。此外，该方法的执行时机可以比较灵活，比如，假设快递公司是早晨统一为各个配送
服务方分配订单，那可以在早晨通过该方法为各个配送服务方分配好任务甚至规划好配送路线。假如下午3点50分又有一批快递要配送，那可以过滤出等待接单的物流配送任务以及需要接单的配送服务方，然后再通过本实施例的方法再执行一次任务分配。
[0059]
再示例一种本实施例的方法的执行场景：比如，可以通过该方法为送餐的外卖员分配订单，以及为外卖员规划配送路线。如果有m个外卖员要协同进行n个小区的外卖餐食的配送，可以通过本实施例的方法为各个外卖员进行外卖订单的分配，该方法能够使得尽可能的将距离外卖员较近的小区的订单分配给该外卖员。
[0060]
本步骤中所述的n个任务地址信息，其中的每一任务地址信息对应着一笔配送任务。即该任务地址信息能够用于表征配送任务的所在位置，其可以包括多种情况，如下示例两种：
[0061]
例如，该任务地址信息可以是一笔配送任务的配送终点，即货物要送达的地址。
[0062]
又例如，该任务地址还可以是用于粗略的表示配送任务大致位于何种区域。以外卖送餐为例，对于用户创建的任一笔外卖订单，该笔外卖订单就是一个配送任务，该配送任务可以包括一个供货地址和一个收货地址。其中，所述供货地址用于表示提供配送货物的商家地址，所述收货地址用于表示收取所述配送货物的用户地址。比如，用户c1在家订了饭馆h1的餐食，那这一笔订单的供货地址就是饭馆h1的位置，收货地址就是用户c1的家庭位置。对于一笔外卖订单可以基于所述供货地址和收货地址确定重心位置，并将所述重心位置作为这笔外卖订单对应的任务地址信息。
[0063]
示例性的，请参见图1b所示，图1b示出了一笔外卖订单的供货地址和一个收货地址，即用户c1的家庭位置11和饭馆h1的位置12，所述的重点位置可以是家庭位置11和饭馆h1的位置12之间连线的中点，可以将该中点作为重心位置13。可以理解的是，所述的将供货地址和收货地址的连线中点作为重心位置，只是一个示例，实际实施中不局限于此，还可以是基于所述供货地址、收货地址以及其他因素来确定重心位置，本实施例不做限制。
[0064]
如上，在外卖送餐的场景中，所述的任务地址信息就可以不是配送任务的实际配送终点。但是，即使不是实际配送终点，也同样可以根据该任务地址信息进行配送任务的分配。比如，在后续步骤的构建泰森多边形以及分配任务的各个阶段，仍然是以该任务地址信息来执行该分配方法即可。如果将该任务地址信息分配至某个泰森多边形，就相当于是将该任务地址信息对应的配送任务分配到了该泰森多边形。
[0065]
此外，对于本步骤所述的m个配送服务方的配送起点位置，即配送服务方是从该配送起点位置出发。例如，在外卖送餐的场景中，外卖员的位置是随机的，可以将外卖员的实时定位位置，作为该外卖员的配送起点位置。比如当要分配外卖订单时，可以看当前外卖员的实时定位位置，即这些外卖员都是分布在哪里，并将当前定位的位置作为配送服务方的配送起点位置。
[0066]
在步骤102中，根据所述m个配送服务方的配送起点位置，构建得到m个泰森多边形，每个泰森多边形的内部包括一个所述配送服务方的配送起点位置。
[0067]
本步骤可以构造泰森图，即基于m个配送服务方的配送起点位置构建泰森多边形。
[0068]
首先，可以根据m个配送服务方的配送起点位置构建delaunay三角网，例如，可以利用分治算法结合双向链接边表快速构造三角网。请参见图2的示意，图2中左侧的各个离散点即分别为各个配送服务方的配送起点位置，基于这些配送起点位置构造得到了三角
网。该三角网中包括相邻接的多个三角形，每个三角形中包括三个顶点，每个顶点对应一个配送服务方的配送起点位置。
[0069]
接着，可以遍历所述三角网中的各个三角形，分别获取每个三角形的外心点。所述的外心点即三角形的外接圆的圆心。
[0070]
然后，在获取了三角网中的各个三角形的外心点的基础上，分别获取每个顶点对应的外心点集合。其中，对于任一顶点来说，该顶点对应的外心点集合即包括所述顶点的各个三角形的外心点组成的外心点的集合。
[0071]
请参见图3的示意，对于顶点d1来说，共有1/2/3/4/5/6/7这七个三角形都是以该顶点d1为其中一个顶点，比如，三角形1的三个顶点中包括该顶点d1，三角形4的三个顶点中也包括该顶点d1，以此类推，该顶点d1是上述七个三角形的共同顶点。这种情况可以将1/2/3/4/5/6/7这七个三角形的外心点组成的集合，作为该顶点d1对应的外心点集合。图3中示例了两个外心点，比如，三角形4的外心点w1，三角形7的外心点w2，其他三角形分别对应的外心点将不再示出。
[0072]
最后，基于每一个顶点对应的外心点集合，计算由所述外心点集合中的外心点组成的凸包。该凸包即为泰森多边形，该泰森多边形中包括所述顶点对应的配送服务方的起点位置。例如，图4示意了其中一个泰森多边形，该泰森多边形是一个凸多边形，其各个顶点是上述的外心点集合中的外心点，并且该泰森多边形的内部包括顶点d1。而该顶点d1对应一个配送服务方的起点位置，因此可以称为每一个配送服务方的起点位置对应一个泰森多边形，m个配送服务方可以对应有m个泰森多边形。
[0073]
在一个实施例中，基于每一个顶点对应的外心点集合，计算由所述外心点集合中的外心点组成的凸包的步骤，可以是分别计算上凸包和下凸包，再将上下凸包组合得到最后的凸包。
[0074]
例如，可以参见图5a所示的流程，图5a示例了凸包的计算步骤，包括：
[0075]
在步骤500中，基于外心点集合中的各个外心点的坐标，按照坐标从小到大的顺序进行排序。
[0076]
例如，假设某个外心点的坐标是(x,y)，可以将各个外心点，按照x坐标从小到大的顺序排序。如果两个外心点的x坐标相等，则按照y坐标从小到大的顺序排序。
[0077]
在步骤502中，将排序在前两位的外心点的坐标放入上凸包集合，并依照排序遍历剩余的外心点坐标，将剩余的外心点坐标中满足右转定理的外心点坐标逐个加入所述上凸包集合，当剩余外心点坐标遍历结束时得到上凸包集合。
[0078]
本步骤中，可以将排序后位于前两位的两个外心点p0和p1加入到上凸包集合upperconvex，此时上凸包集合upperconvex包括两个外心点。上凸包集合中的外心点的数量uppercount＝2。
[0079]
接着，依照排序遍历剩余的外心点坐标，比如，将位于p0和p1之后的外心点p2的坐标加入到上凸包集合upperconvex中，并将uppercount加1。判断上凸包集合upperconvex中的后三个外心点p0、p1、p2是否满足右转定理。如果满足，继续将位于p2之后的下一个外心点p3加入上凸包集合。如果不满足，则将上凸包集合中的倒数第二个外心点从集合中去掉，并将外心点的数量uppercount减1，比如该例子中，就是将p1去掉。然后继续在上凸包集合中加入下一个外心点。
[0080]
例如，假设上述例子中，p0、p1、p2满足右转定理，则继续在上凸包集合中加入p3。然后判断该集合中的后三个外心点p1、p2、p3是否满足右转定理。假设这三个外心点不满足右转定理，则集合中去掉倒数第二个外心点p2。然后再将p4加入上凸包集合，该集合中的后三个外心点就是p1、p3和p4，继续判断是否满足右转定理，不再详述。
[0081]
如上所述的，依照排序遍历剩余的外心点坐标，将剩余的外心点坐标中满足右转定理的外心点坐标逐个加入所述上凸包集合，当剩余外心点坐标遍历结束时得到上凸包集合。
[0082]
其中，上述的右转定理表示如下：
[0083]
假设三个外心点的坐标分别为：(x1、y1)、(x2、y2)、(x3、y3)。
[0084]
如果该三个坐标满足如下的公式(6)，则表明满足右转定理。
[0085]
(x
2-x1)
×
(y
3-y2)-(x
3-x2)
×
(y
3-y2)》0
…
(6)
[0086]
如果该三个坐标满足如下的公式(7)，则表明不满足右转定理。
[0087]
(x
2-x1)
×
(y
3-y2)-(x
3-x2)
×
(y
3-y2)≤0
……
(7)
[0088]
在步骤504中，将排序在后两位的外心点的坐标放入下凸包集合，并依照排序遍历剩余的外心点坐标，将剩余的外心点坐标中满足右转定理的外心点坐标逐个加入所述下凸包集合，当剩余外心点坐标遍历结束时得到下凸包集合。
[0089]
上面描述了上凸包集合的获得过程。下凸包集合lowconvex的获得过程与此类似，具体的，可以将排序在后两位的外心点的坐标放入下凸包集合lowconvex，比如，假设外心点集合中共有10个外心点，排序后依次分别是外心点p0、p1直至外心点p9，那么可以将排序后两位的p9和p8放入下凸包集合。然后，依照排序遍历剩余的外心点坐标，将剩余的外心点坐标中满足右转定理的外心点坐标逐个加入所述下凸包集合，当剩余外心点坐标遍历结束时得到下凸包集合。
[0090]
例如，可以将p7放入下凸包集合，判断p9、p8、p7是否满足右转定理。如果满足，则继续将p6加入下凸包集合，判断p8、p7和p6是否满足右转定理。如果p9、p8、p7不满足右转定理，则将倒数第二位的p8从下凸包集合去掉，再继续加入p6，判断p9、p7和p6是否满足右转定理。以此类推，不再详述。当下凸包集合中加入新的外心点坐标时，下凸包集合中的外心点的数量lowcount要加1。
[0091]
在步骤506中，组合所述上凸包集合和下凸包集合中的各个外心点，得到所述外心点组成的凸包。
[0092]
最后，组合所述上凸包集合和下凸包集合中的各个外心点，得到外心点组成的凸包。其中，最终得到的凸包中的外心点的数量是：
[0093]
convexpointcount＝uppercount+lowcount-2
……
(8)
[0094]
其中，convexpointcount是最终得到的凸包中的外心点的数量，uppercount是上凸包集合中的外心点的数量，lowcount是下凸包集合中的外心点的数量。
[0095]
此外，在组合上凸包集合和下凸包集合中的各个外心点时，依照各个外心点加入集合中的顺序来组合。例如，假设按照上面所述的方式，依次将p0、p2、p3、p5、p7、p9加入上凸包集合，并依次将p9、p8、p6、p1、p4、p0加入下凸包集合。那么依次顺序，最终的凸包中包括的各外心点依次为：p0、p2、p3、p5、p7、p9、p8、p6、p1、p4，这些外心点依次连接，最后p4连接到p0，构成了一个泰森多边形。
[0096]
本步骤中，在根据所述m个配送服务方的配送起点位置构建泰森多边形的过程中，在完成构造三角网的基础上，通过计算与配送服务方的配送起点位置对应的凸包从而得到泰森多边形，该方式可以较为快速的完成泰森图的构造。而泰森图的快速构造，也有利于物流配送路线的整个规划过程的效率提升。
[0097]
此外，本实施例通过“上下凸包法”分别计算上凸包和下凸包，该方式也能够提高泰森多边形的计算效率，加快构造得到泰森图。例如，经过实验测试，分别采用传统的graham扫描法构造凸包以及采用本实施例的凸包法构造凸包去计算一定数量离散点的凸包，graham扫描法构造凸包耗时359毫秒，本实施例的上下凸包法耗时为30毫秒，计算效率得到了明显的提升。比如，在构造泰森图(泰森图也称泰森多边形)的过程中，通过结合分治算法构造三角网，并且采用上下凸包法计算泰森多边形，实验证明泰森图的构建效率得到了明显提升。
[0098]
在步骤104中，将所述n个任务地址信息分配至所述m个泰森多边形中。
[0099]
在步骤102中，已经得到了多个泰森多边形，每一个泰森多边形的内部包括一个所述配送服务方的配送起点位置。本步骤将在此基础上进行配送任务的分配，将n个任务地址信息分配至所述m个泰森多边形中。
[0100]
例如，假设3个配送服务方，10个任务地址信息，最终分配完成后，每一个配送服务方对应的泰森多边形内可以都包括一部分任务地址信息，比如，其中一个配送服务方的泰森多边形内分配了4个任务地址信息，另一个配送服务方的泰森多边形内分配了3个任务地址信息，最后一个配送服务方的泰森多边形内分配了3个任务地址信息。每一个泰森多边形就相当于该配送服务方的配送范围，配送服务方只需要在该泰森多边形内的多个任务地址信息进行配送即可。比如，对于某一个配送服务方来说，其对应的泰森多边形内分配了小区q1、小区q2和小区q3，即该配送服务方负责在这三个小区内送快递，这三个小区的快递物品都是由该配送服务方负责配送。当然，在后续的步骤106中再去解决为泰森多边形内的多个任务地址信息规划配送路线的问题。
[0101]
本步骤中，将n个任务地址信息分配至所述m个泰森多边形中可以有多种方式，比如，可以采用射线法判断二维空间中的某个点是否落在多边形内，如果点落在多边形内则分配至该泰森多边形。
[0102]
此外，本步骤中在将n个位置分配至各个泰森多边形时，也有可能出现的情况是，一个泰森多边形内只分配了一个任务地址信息或者0个任务地址信息。这种情况的出现可以是该配送服务方为离点，不给他分配任务也是合理的。例如，一个配送服务方在西藏，但任务全部在北京，此时分给他的任务就应该为0，因为若分配给他会导致其成本过高。当然，该例子仅仅是示意。
[0103]
本实施例的配送任务的分配方法，基于泰森图来求解物流配送场景下的mmtsp问题，构造得到的各个泰森多边形具有如下性质：
[0104]
1)每一泰森多边形内仅包含一个离散点，该离散点即配送服务方的配送起点位置；
[0105]
2)每一泰森多边形内的任意一点(分配至该泰森多边形内的任一个任务地址信息)到该泰森多边形内的离散点距离最近；
[0106]
3)每一泰森多边形边上的点到该边两侧相应的离散点距离相等。
[0107]
基于泰森多边形的上述性质，可以得到，在基于泰森图进行配送任务分配时，可以使得各个配送服务方之间的配送任务的划分高效且明确，而且，由于泰森多边形内的任意一点到该泰森多边形内的离散点距离最近，所以有助于满足各配送服务方的配送总路程最短的要求。此外，由于每一泰森多边形边上的点到该边两侧相应的离散点距离相等，该性质使得各个配送服务方之间的配送任务的划分更加均衡。
[0108]
也就是说，根据构造的泰森多边形的性质来看，利用泰森多边形来进行配送任务的分配，将使得配送任务的分配更加均衡，并有助于使得m个配送服务方协同遍历n个任务地址信息的配送总路程最短。因此，本实施例的配送任务的分配方法，将使得物流成本降低。
[0109]
经过实验测试，将本说明书实施例的基于泰森图确定进行物流分配的方法与其他方法相比较，本实施例的基于泰森图的方法得到的结果对应的目标函数数值明显更优，并且，当配送服务方和任务地址信息数量较多时，本实施例的基于泰森图的方法具有较为明显的优势，目标函数的数值相较其他方法更好，任务划分均衡性也更好。
[0110]
在一个示例中，在将各个任务地址信息分配至各个泰森多边形之后，还可以对于任一泰森多边形，继续进行物流配送路线的规划，请参见步骤106。
[0111]
在步骤106中，对于任一泰森多边形，确定所述泰森多边形内的配送服务方执行该泰森多边形内的各个任务地址信息对应的配送任务时的最短配送路线。
[0112]
本步骤不限制所述最短配送路线的求解方式。
[0113]
例如，对于任一个泰森多边形，可以通过求解tsp(travelling salesman problem，旅行商问题)得到该泰森多边形内的物流配送路线。在一个例子中，所述的物流配送路线是该泰森多边形内的配送服务方从起点位置到多边形内的各个任务地址信息之间的路线。比如，上面提到的例子中，某一个配送服务方对应的泰森多边形内包括三个任务地址信息：小区q1、小区q2和小区q3，最终求解得到的物流配送路线可以是：该配送服务方从配送起点位置先去小区q3，接着去小区q2，最后去小区q1配送，完成配送后返回到所述配送起点位置，当然也可以不回到配送起点。
[0114]
本实施例不限制求解tsp问题的具体方式，例如，可以采用模拟退火、遗传算法、启发式搜索法、hopfield神经网络法、蚁算法等多种方法来求解tsp问题。
[0115]
如果任务地址信息的数量和配送服务方的数量不多，也可以采用枚举计算的方式求解最短配送路线。
[0116]
对于上面实施例所述的配送任务的分配方法，接下来以外卖送餐的场景为例，描述在外卖送餐场景中如何使用该方法。
[0117]
其中，每一个外卖订单都可以称为一个配送任务，该配送任务包括：一个供货地址和一个收货地址。其中，供货地址即餐饮商家的地址，收货地址是外卖订单的用户地址。在该外卖送餐的场景中，配送服务方可以是负责配送外卖的配送员。
[0118]
请结合参见图5b所示，该图5b示意了部分的外卖订单。例如，其中一个外卖订单包括供货地址511和收货地址512，本实施例可以将该供货地址511和收货地址512作为一个集合51，该集合51就代表一个外卖订单。并且，本实施例还将供货地址511和收货地址512之间的连接线设置成箭头线的形式，从供货地址511指向收货地址512。
[0119]
同理，图5b还示意了另一个外卖订单对应的集合52，其中包括了供货地址521和收
货地址522。此外，还包括集合53和集合54分别对应的外卖订单，该集合53的外卖订单中包括供货地址531和收货地址532，集合54的外卖订单中包括供货地址541和收货地址542。
[0120]
图5b示意了上述的四个外卖订单，实际实施中可以有更多的订单。
[0121]
接着参见图5b，对于每一个外卖订单，可以基于其供货地址和收货地址，确定该订单对应的任务地址信息，该任务地址信息可以是根据供货地址和收货地址确定的重心位置。例如，图中示意了该4个订单分别对应的任务地址信息：重心513、重心523、重心533和重心543。
[0122]
在进行任务分配时，每一个外卖的配送员构建一个对应的泰森多边形。例如，配送员s1对应一个泰森多边形，配送员s2对应另一个泰森多边形。然后，将上述的外卖订单的任务地址信息分配到这些泰森多边形中，比如，重心513和重心523被分配到配送员s1对应的泰森多边形中，重心533和重心543被分配到配送员s2对应的泰森多边形中。上述的重心分配到泰森多边形，也就相当于将该重心对应的外卖订单分配到了该泰森多边形。即，配送员s1要负责配送重心513和重心523对应的外卖订单，配送员s2负责配送重心533和重心543对应的外卖订单。
[0123]
接下来，在将各个外卖订单分配给配送员后，可以继续计算配送员进行外卖配送的最短配送路线。其中，可以将配送员的实时定位位置，作为所述配送员的配送起点位置。配送员可以从配送起点位置出发，去往各个外卖订单的供货地址和收货地址。
[0124]
以配送员s1为例，在规划该配送员s1送餐的最短配送路线时，可以先获取分配至对应泰森多边形的配送任务节点集合。该配送任务节点集合中可以包括多个配送任务节点，该配送任务节点即外卖订单的供货地址和收货地址。比如，{供货地址511、收货地址512、供货地址521、收货地址522}作为一个配送任务节点的集合。本实施例要计算配送员s1要从配送起点位置到该集合中的各个配送任务节点的最短配送路线。
[0125]
示例性的，配送起点位置——》供货地址511——》供货地址521——》收货地址522——》收货地址512，即为一个配送员s1的配送路线，即配送员s1先去供货地址511取餐，接着去供货地址521取餐，然后先去给收货地址522的用户送餐，最后给收货地址512的用户送餐。可以通过求解tsp问题得到配送员送餐的最短配送路线，本实施例不再详述。
[0126]
不过，考虑到外卖送餐场景的特点，对于一个外卖订单来说，配送员是要先取餐，才能去给用户送餐，所以，在确定配送员的配送路线时，需要满足如下条件：对于任一配送任务，所述配送员到达所述配送任务中的供货地址的时间先于收货地址。比如，配送员s1去往供货地址511的时间一定先于去往收货地址512，不可能出现配送员s1先去收货地址512，后去其对应的供货地址511的情况。
[0127]
基于上述，外卖送餐的场景也只是一个示例，在其他的应用场景中，同样可以根据场景自身的配送特点，来为配送路线的规划设置对应的条件。此外，本说明书实施例的配送任务的分配方法，不局限于用于外卖送餐场景，其他场景也可以。比如，上述的外卖送餐场景的特点是“配送员位置随机、配送任务的任务地址信息也随机”，其他类似的场景也可以使用该方法。
[0128]
在又一个例子中，外卖送餐的场景还可能出现的情况是：不同的用户订了同一家餐饮商家的餐食，或者，同一个用户订了不同餐饮商家的餐食，按照前述的方式，一个外卖订单计算一个对应的任务地址信息，所以在任务分配时，仍然是以单个的外卖订单为分配
的基本单位即可，不同的外卖订单可以由不同的配送员进行配送。
[0129]
结合图5c的示意，其中示意了另一个外卖订单对应的集合55，该集合55中包括收货地址552和供货地址531，该订单对应的任务地址信息是重心553。也就是说，收货地址532和收货地址552的两个用户，都订了供货地址531对应的餐饮商家对应的餐食。但是由于这是两个外卖订单，就可以按照前述的分配方式进行任务的分配，如图5c所示，最后的分配结果可能会是，重心553被分配到了配送员s3对应的泰森多边形中，即外卖订单55被分配给了配送员s3，同理，重心533被分配到了配送员s2对应的泰森多边形中，即外卖订单53被分配给了配送员s2。那么这两个配送员可以分别送这两个订单。
[0130]
图6是一示例性实施例提供的一种配送任务的分配方法，本实施例的方法，对图1示例的方法做了进一步的改进，在图1所示方法的基础上进一步提高基于泰森图解决mmtsp问题的效率。具体是在将n个任务地址信息分配至m个泰森多边形的任务分配阶段，提高该阶段的任务分配的效率。
[0131]
如图6所示，该方法包括如下处理步骤，其中，该图6主要描述将n个任务地址信息分配至m个泰森多边形中的处理过程，其他步骤可以结合参见图1，不再详述。
[0132]
在步骤600中，对于任一个任务地址信息，以所述任务地址信息位置为起点做单向射线。
[0133]
本实施例以其中一个任务地址信息为例，描述如何获得该任务地址信息所在的泰森多边形。
[0134]
本步骤中，以该任务地址信息为起点做单向射线，所述的单向射线指的是向一个方向延伸的射线。例如，可以是与x轴平行向右侧做单边射线，或者，也可以是与x轴平行向左侧做单边射线；或者，还可以是与x轴夹角40度的倾斜方向做单边射线，等。对于所有的任务地址信息，可以均以相同的方向做单向射线，比如，均以与x轴平行向左侧做单边射线。
[0135]
本实施例以从任务地址信息为起点向左侧水平做射线为例。
[0136]
在步骤602中，统计单向射线与参与判断的泰森多边形的各条边之间的交点的总数量，所述泰森多边形中的每条边的两个端点都去除了一个端点不参与所述统计，且各条边去除的是同向端点。
[0137]
首先，所述参与判断的泰森多边形，可以是：将任务地址信息逐个的分别与各个泰森多边形进行交点数量的判断，那么，正在判断的泰森多边形即为参与判断的多边形。举例来说：假设有3个泰森多边形(v1、v2和v3)，并且有10个任务地址信息。对于其中一个任务地址信息来说，可以逐个的与所述三个泰森多边形进行判断，如果本实施例正在执行该任务地址信息与其中的泰森多边形v1的判断，判断该任务地址信息是否位于v1内部，那么可以将v1称为参与判断的泰森多边形。如果该任务地址信息不属于v1，则继续判断该任务地址信息是否位于泰森多边形v2内，v2即作为参与判断的泰森多边形。
[0138]
其次，本实施例中，泰森多边形中的每条边包括两个端点，本实施例将去掉其中一个端点不参与统计。例如，可以去掉位于目标方向上的坐标较大的端点，或者，也可以去掉位于目标方向上的坐标较小的端点。示例性的，所述的目标方向可以是y方向，目标方向上的坐标可以是y坐标。
[0139]
所述的去掉位于目标方向上的坐标较大的端点，可以是泰森多边形中的每一条边的y坐标较大的端点不参与统计，即，即使单向射线与该y坐标较大的端点相交，也不增加交
点的数量，记录交点数量的计数器的数值不变。
[0140]
所述的去掉位于目标方向上的坐标较小的端点，可以是泰森多边形中的每一条边的y坐标较小的端点不参与统计，即，即使单向射线与该y坐标较小的端点相交，也不增加交点的数量，记录交点数量的计数器的数值不变。
[0141]
如上，每条边去掉的都是y坐标较大的端点，或者y坐标较小的端点，这可以称为：各条边去除的是同向端点。这里的同向端点指的是均为目标方向上的坐标较大的端点，或坐标较小的端点。
[0142]
请参见图7的示意，图7示意了一个泰森多边形71，还示意了两个任务地址信息72和73。
[0143]
以任务地址信息72为例，以该任务地址信息为起点向左侧水平做射线s1，逐个边判断该射线s1与泰森多边形71的各条边的交点的数量，经统计得到，该射线s1与泰森多边形71的各条边的交点的总数量是3。
[0144]
再看任务地址信息73，以该任务地址信息为起点向左侧水平做射线s2，由于泰森多边形中的每条边都去掉y坐标较大的端点不参与统计，基于此，射线s2与泰森多边形的边711和边712相交，并且都是与这两条边的y坐标较小的端点相交，根据上述原则，那么，射线s2与泰森多边形71的各条边的交点的总数量是2。
[0145]
此外，在另一个例子中，如果泰森多边形的一条边的两个端点在位于目标方向上的坐标相等，则确定所述单向射线与所述边的交点的数量是0。这种情况可以参见图8的示意，图8示意了泰森多边形81，还示意了任务地址信息82。以该任务地址信息82为起点向左侧水平做射线s3，该射线s3与泰森多边形73的各条边相交。其中有一条边811，该边811的两个端点的y坐标相等。根据上述的规则，射线s3与边811的交点的数量是0，那么，射线s3就只有与边812和边813的交点，交点总数量是2。
[0146]
在步骤604中，响应于所述交点的总数量满足预设数量条件，确定所述任务地址信息在所述泰森多边形内，将所述任务地址信息分配至所述泰森多边形。
[0147]
例如，所述的预设数量条件可以是：交点的总数量是奇数。即如果交点的总数量是奇数，则可以确定任务地址信息在所述泰森多边形内，将该任务地址信息分配至所述泰森多边形。
[0148]
比如，图7中的任务地址信息72与泰森多边形71的各条边的交点的总数量是3，是奇数，则可以确定任务地址信息72落在泰森多边形71内，将该任务地址信息72分配至泰森多边形71。
[0149]
又比如，图8中的任务地址信息82与泰森多边形81的各条边的交点的总数量是2，是偶数，则可以确定任务地址信息82没有在泰森多边形81内，则不将该任务地址信息82分配至泰森多边形81。可以继续判断任务地址信息82与另一个泰森多边形。
[0150]
此外，还有一种情况是：如果任务地址信息位于泰森多边形的其中一条边上，则确定该任务地址信息在多边形上，可以将所述任务地址信息分配至所述泰森多边形。比如，某个任务地址信息位于泰森多边形v1和泰森多边形v2的邻接边上，请参见图9的示意，任务地址信息xx位于邻接边b上，b是泰森多边形v1和泰森多边形v2共有的一条边。那么，可以将任务地址信息xx分配给泰森多边形v1，也可以将任务地址信息xx分配给泰森多边形v2，均可。
[0151]
本实施例的配送任务的分配方法，通过在统计以任务地址信息为起点的单向射线
与泰森多边形的交点总数量时，将多边形的每条边都去除了一个同向端点不参与统计，该方式使得可以简化交点数量的判断，提高交点数量判断的效率。此外，本实施例中提到的两个端点在位于目标方向上的坐标相等，则确定所述单向射线与所述边的交点的数量是0等判断逻辑，都可以使得交点数量判断较为快速，从而使得配送任务的分配效率提升，实现了在保证配送总路程最短、配送任务分配均衡的基础上，配送任务的分配效率也得到提高。
[0152]
图10是一示例性实施例提供的另一种配送任务的分配方法，本实施例的方法，对分配方法做了进一步的改进，旨在进一步提高基于泰森图解决mmtsp问题的效率。具体是通过gpu并行运算的方式，从硬件上提升运算效率。
[0153]
其中，本实施例主要是将gpu并行运算应用于计算泰森多边形、配送任务的分配、以及单旅行商问题tsp的求解。实际实施中，上述三个方面的计算，可以是至少其中一个方面应用gpu并行运算，比如，可以通过多个gpu并行执行所述根据m个配送服务方的起点位置，构建得到m个泰森多边形。或者，也可以通过多个gpu并行运算，执行所述将所述n个任务地址信息分配至所述m个泰森多边形中。或者，还可以是通过多个gpu并行运算，执行所述通过求解旅行商问题确定所述泰森多边形内的配送服务方由所述起点位置到所述泰森多边形内的各个任务地址信息之间的物流配送路线。可以是其中任一个方面采用gpu并行运算，也可以是其中任两个方面采用gpu并行，还可以是三个方面都采用gpu并行。
[0154]
如下的图10是以将计算泰森多边形、配送任务的分配、以及单旅行商问题tsp的求解均采用gpu并行运算为例，来提升mmtsp问题的运算效率。
[0155]
在步骤1001中，分别获取n个任务地址信息、以及m个配送服务方中每个配送服务方的配送起点位置。
[0156]
例如，n个任务地址信息分别是c1、c2、c3、
……cn
，m个配送服务方的起点位置分别是p1、p2、p3、
……
pm。
[0157]
在步骤1002中，根据所述m个配送服务方的配送起点位置，构建三角网。
[0158]
在步骤1003中，遍历所述三角网中的各个三角形，分别获取每个三角形的外心点，并且，对于任一顶点，将包括所述顶点的各个三角形的外心点组成的外心点集合，作为与所述顶点对应的外心点集合。
[0159]
例如，对于配送服务方的配送起点位置p1，获得对应该p1的外心点集合h1。对于配送服务方的配送起点位置p2，获得对应该p2的外心点集合h2，以此类推，对于配送服务方的配送起点位置pm，获得对应该pm的外心点集合hm。
[0160]
在步骤1004中，通过多个gpu并行执行，利用上下凸包法计算各个配送服务方的配送起点位置对应的泰森多边形。
[0161]
例如，基于外心点集合h1，计算配送起点位置p1对应的泰森多边形t1；基于外心点集合h2，计算配送起点位置p2对应的泰森多边形t2；以此类推，基于外心点集合hm，计算配送起点位置pm对应的泰森多边形tm。
[0162]
其中，本实施例所述的多个gpu并行，本实施例不限制每个gpu上运算的数据数量，比如，可以一个gpu负责计算一个泰森多边形，例如，其中一个gpu负责计算配送起点位置p1对应的泰森多边形t1，另一个gpu负责计算配送起点位置p2对应的泰森多边形t2。或者，也可以是一个gpu上负责计算两个或更多个泰森多边形。
[0163]
在步骤1005中，通过多个gpu并行运算，执行所述将所述n个任务地址信息分配至
所述m个泰森多边形中。
[0164]
例如，计算c1、c2、c3、
……cn
中分配至泰森多边形t1的点，即确定分配至起点位置p1对应的配送服务方的任务地址信息。计算c1、c2、c3、
……cn
中分配至泰森多边形t2的点，即确定分配至起点位置p2对应的配送服务方的任务地址信息。以此类推，计算c1、c2、c3、
……cn
中分配至泰森多边形tm的点，即确定分配至起点位置pm对应的配送服务方的任务地址信息。
[0165]
同样的，本实施例所述的多个gpu并行，本实施例不限制每个gpu上运算的数据数量，比如，可以一个gpu负责计算一个泰森多边形内的任务地址信息分配，例如，其中一个gpu负责哪些任务地址信息分配至泰森多边形t1，另一个gpu负责计算哪些任务地址信息分配至泰森多边形t2。或者，也可以是一个gpu上负责计算两个或更多个泰森多边形内的任务地址信息分配。
[0166]
后续步骤的求解tsp问题也是同理，不限制每个gpu上运算的数据数量。
[0167]
在步骤1006中，通过多个gpu并行运算，执行所述通过求解旅行商问题确定所述泰森多边形内的配送服务方由所述配送起点位置到泰森多边形内的各个任务地址信息之间的物流配送路线。
[0168]
例如，基于分配给泰森多边形t1的任务地址信息，求解tsp问题，得到配送起点位置p1对应的配送服务方的物流配送路线。又例如，基于分配给泰森多边形t2的任务地址信息，求解tsp问题，得到配送起点位置p2对应的配送服务方的物流配送路线。以此类推，基于分配给泰森多边形tm的任务地址信息，求解tsp问题，得到配送起点位置pm对应的配送服务方的物流配送路线。
[0169]
在步骤1007中，输出m个配送服务方协同遍历n个任务地址信息的各自的物流配送路线。
[0170]
例如，如上所述的，对于每个泰森多边形，都可以通过tsp问题得到该多边形内的配送服务方到多边形内的各个任务地址信息的物流配送路线，汇总各个泰森多边形的配送路线的计算结果，就是整个mmtsp问题的求解结果，即得到了m个配送服务方各自的任务分配，每个配送服务方负责配送哪些任务地址信息，以及配送服务方在自己负责的各任务地址信息之间的物流配送路线。通过求解该mmtsp问题，最终得到的结果，m个配送服务方协同遍历n个任务地址信息的总路程最短。
[0171]
本实施例的物流配送路线的确定方法，通过采用gpu并行运算的方式，计算泰森多边形、配送任务的分配、以及单旅行商问题tsp的求解，使得物流配送路线的计算效率进一步得到了提高。
[0172]
图11是一示例性实施例提供的一种配送任务的分配装置的结构示意图，该装置可以用于实现本说明书任一实施例的方法。如下对该装置的各个功能模块做简单说明，各模块的详细处理可以结合参见方法实施例部分的描述。如图11所示，该装置可以包括：数据获取模块1101、泰森图构造模块1102和任务分配模块1103。
[0173]
数据获取模块1101，用于分别获取n个任务地址信息、以及m个配送服务方中每个配送服务方的配送起点位置，所述n和m是正整数。每个所述任务地址信息对应一笔配送任务，所述配送起点位置表示负责执行配送任务的配送服务方的配送起点。
[0174]
泰森图构造模块1102，用于根据所述m个配送服务方的配送起点位置，构建得到m个泰森多边形，每个泰森多边形的内部包括一个所述配送服务方的配送起点位置。
[0175]
任务分配模块1103，用于将所述n个任务地址信息分配至m个泰森多边形中。
[0176]
在一个例子中，如图12所示，该图12是一示例性实施例提供的一种配送任务的分配装置的结构示意图。该装置还可以包括：路线规划模块1104，用于对于任一泰森多边形，确定所述泰森多边形内的配送服务方执行分配到所述泰森多边形内的各个任务地址信息对应的配送任务的最短配送路线。
[0177]
在一个例子中，泰森图构造模块1102，在用于据所述m个配送服务方的配送起点位置，构建得到m个泰森多边形时，包括：
[0178]
根据所述m个配送服务方的配送起点位置，构建三角网，所述三角网包括相邻接的多个三角形，每个三角形中的三个顶点分别对应三个配送服务方的配送起点位置。
[0179]
遍历所述三角网中的各个三角形，分别获取每个三角形的外心点。
[0180]
对于任一顶点，将包括所述顶点的各个三角形的外心点组成的外心点集合，作为与所述顶点对应的外心点集合。
[0181]
根据每一个顶点对应的外心点集合，计算由所述外心点集合中的外心点组成的凸包，所述凸包作为包括所述顶点对应的配送服务方的配送起点位置的泰森多边形。
[0182]
在一个例子中，泰森图构造模块1102，在用于根据每一个顶点对应的外心点集合，计算由所述外心点集合中的外心点组成的凸包时，包括：
[0183]
基于所述外心点集合中的各个外心点的坐标，按照坐标从小到大的顺序进行排序。
[0184]
将排序在前两位的外心点的坐标放入上凸包集合，并依照排序遍历剩余的外心点坐标，将剩余的外心点坐标中满足右转定理的外心点坐标逐个加入所述上凸包集合，当剩余外心点坐标遍历结束时得到上凸包集合。
[0185]
将排序在后两位的外心点的坐标放入下凸包集合，并依照排序遍历剩余的外心点坐标，将剩余的外心点坐标中满足右转定理的外心点坐标逐个加入所述下凸包集合，当剩余外心点坐标遍历结束时得到下凸包集合。
[0186]
组合所述上凸包集合和下凸包集合中的各个外心点，得到所述外心点组成的凸包。
[0187]
在一个例子中，任务分配模块1103，在用于将所述n个任务地址信息分配至m个泰森多边形中时，包括：
[0188]
对于任一个任务地址信息，以所述任务地址信息为起点做单向射线。
[0189]
统计所述单向射线与参与判断的泰森多边形的各条边之间的交点的总数量，所述泰森多边形的每条边的两个端点中去除其中一个端点不参与所述统计，且各条边去除的是同向端点。
[0190]
响应于所述交点的总数量满足预设数量条件，确定所述任务地址信息在所述参与判断的泰森多边形内，将所述任务地址信息分配至所述泰森多边形。
[0191]
在一个例子中，所述泰森多边形的每条边的两个端点中去除其中一个端点不参与所述统计，且各条边去除的是同向端点，包括：所述泰森多边形中的每条边的两个端点中，去除y坐标较大的端点；或者，所述泰森多边形中的每条边的两个端点中，去除y坐标较小的端点。任务分配模块1103，在用于统计所述单向射线与参与判断的泰森多边形的各条边之间的交点的总数量时，若所述泰森多边形的一条边的两个端点的y坐标相等，则确定所述单
向射线与所述边的交点的数量是0。
[0192]
在一个例子中，任务分配模块1103，在用于将所述n个任务地址信息分配至m个泰森多边形中时，包括：若所述任务地址信息位于所述泰森多边形的其中一条边上，则将所述任务地址信息分配至所述泰森多边形。
[0193]
在一个例子中，泰森图构造模块1102，在用于根据所述m个配送服务方的起点位置，构建得到m个泰森多边形时，包括：通过多个gpu并行执行所述根据m个配送服务方的配送起点位置，构建得到m个泰森多边形。
[0194]
在一个例子中，任务分配模块1103，在用于将所述n个任务地址信息分配至m个泰森多边形中时，包括：通过多个gpu并行运算，执行所述将n个任务地址信息分配至所述m个泰森多边形中。
[0195]
在一个例子中，路线规划模块1104，具体用于：通过多个gpu并行运算，通过求解旅行商问题，确定所述泰森多边形内的配送服务方由所述配送起点位置到所述泰森多边形内的各个任务地址信息之间的最短的物流配送路线。
[0196]
在一个例子中，所述分别获取n个任务地址信息、以及m个配送服务方中每个配送服务方的配送起点位置，包括：获取m个配送服务方中每个配送服务方的实时定位位置，作为所述配送服务方的配送起点位置；获取待分配的n个配送任务，每个配送任务包括：一个供货地址和一个收货地址，所述供货地址用于表示提供配送货物的商家地址，所述收货地址用于表示收取所述配送货物的用户地址；对于所述n个配送任务中的每一配送任务，基于所述供货地址和收货地址确定重心位置，并将所述重心位置作为所述配送任务对应的任务地址信息。
[0197]
在一个例子中，所述将所述n个任务地址信息分配至所述m个泰森多边形中之后，所述方法还包括：对于任一泰森多边形，获取分配至所述泰森多边形内的配送任务节点集合，所述配送任务节点集合中的各配送任务节点，包括：分配至所述泰森多边形内的各任务地址信息对应的配送任务的供货地址和收货地址；根据所述配送任务节点集合，确定所述泰森多边形内的配送服务方由配送起点位置到所述配送任务节点集合中的各个配送任务节点的最短配送路线；并且，确定的所述最短配送路线满足：对于任一配送任务，所述配送服务方到达所述配送任务中的供货地址的时间先于收货地址。
[0198]
本说明书实施例还提供一种电子设备，在硬件层面，该设备包括处理器、内部总线、网络接口、内存以及非易失性存储器，当然还可能包括其他业务所需要的硬件。本说明书一个或多个实施例可以基于软件方式来实现，比如由处理器从非易失性存储器中读取对应的计算机程序到内存中然后运行。当然，除了软件实现方式之外，本说明书一个或多个实施例并不排除其他实现方式，比如逻辑器件抑或软硬件结合的方式等等，也就是说以下处理流程的执行主体并不限定于各个逻辑单元，也可以是硬件或逻辑器件。
[0199]
上述实施例阐明的系统、装置、模块或单元，具体可以由计算机芯片或实体实现，或者由具有某种功能的产品来实现。一种典型的实现设备为计算机，计算机的具体形式可以是个人计算机、膝上型计算机、蜂窝电话、相机电话、智能电话、个人数字助理、媒体播放器、导航设备、收发设备、游戏控制台、平板计算机、可穿戴设备或者这些设备中的任意几种设备的组合。
[0200]
在一个典型的配置中，计算机包括一个或多个处理器(cpu)、输入/输出接口、网络
接口和内存。
[0201]
内存可能包括计算机可读介质中的非永久性存储器，随机存取存储器(ram)和/或非易失性内存等形式，如只读存储器(rom)或闪存(flash ram)。内存是计算机可读介质的示例。
[0202]
计算机可读介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括，但不限于相变内存(pram)、静态随机存取存储器(sram)、动态随机存取存储器(dram)、其他类型的随机存取存储器(ram)、只读存储器(rom)、电可擦除可编程只读存储器(eeprom)、快闪记忆体或其他内存技术、只读光盘只读存储器(cd-rom)、数字多功能光盘(dvd)或其他光学存储、磁盒式磁带、磁盘存储、量子存储器、基于石墨烯的存储介质或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。按照本文中的界定，计算机可读介质不包括暂存电脑可读媒体(transitory media)，如调制的数据信号和载波。
[0203]
本公开实施例还提供了一种计算机程序产品，该计算机程序产品用于实现本公开任一实施例所述的配送任务的分配方法。
[0204]
还需要说明的是，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、商品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、商品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、商品或者设备中还存在另外的相同要素。
[0205]
上述对本说明书特定实施例进行了描述。其它实施例在所附权利要求书的范围内。在一些情况下，在权利要求书中记载的动作或步骤可以按照不同于实施例中的顺序来执行并且仍然可以实现期望的结果。另外，在附图中描绘的过程不一定要求示出的特定顺序或者连续顺序才能实现期望的结果。在某些实施方式中，多任务处理和并行处理也是可以的或者可能是有利的。
[0206]
在本说明书一个或多个实施例使用的术语是仅仅出于描述特定实施例的目的，而非旨在限制本说明书一个或多个实施例。在本说明书一个或多个实施例和所附权利要求书中所使用的单数形式的“一种”、“所述”和“该”也旨在包括多数形式，除非上下文清楚地表示其他含义。还应当理解，本文中使用的术语“和/或”是指并包含一个或多个相关联的列出项目的任何或所有可能组合。
[0207]
应当理解，尽管在本说明书一个或多个实施例可能采用术语第一、第二、第三等来描述各种信息，但这些信息不应限于这些术语。这些术语仅用来将同一类型的信息彼此区分开。例如，在不脱离本说明书一个或多个实施例范围的情况下，第一信息也可以被称为第二信息，类似地，第二信息也可以被称为第一信息。取决于语境，如在此所使用的词语“如果”可以被解释成为“在
……
时”或“当
……
时”或“响应于确定”。
[0208]
以上所述仅为本说明书一个或多个实施例的较佳实施例而已，并不用以限制本说明书一个或多个实施例，凡在本说明书一个或多个实施例的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本说明书一个或多个实施例保护的范围之内。

技术特征：

1.一种配送任务的分配方法，其特征在于，所述方法包括：分别获取n个任务地址信息、以及m个配送服务方中每个配送服务方的配送起点位置，所述n和m是正整数；每个所述任务地址信息对应一笔配送任务，所述配送起点位置表示负责执行配送任务的配送服务方的配送起点；根据所述m个配送服务方的配送起点位置，构建得到m个泰森多边形，每个泰森多边形的内部包括一个所述配送服务方的配送起点位置；将所述n个任务地址信息分配至所述m个泰森多边形中，以使得每个泰森多边形内包括的配送起点位置对应的配送服务方执行分配至所述泰森多边形的各任务地址信息对应的配送任务。2.根据权利要求1所述的方法，其特征在于，所述根据所述m个配送服务方的配送起点位置，构建得到m个泰森多边形，每个泰森多边形的内部包括一个所述配送服务方的配送起点位置，包括：根据所述m个配送服务方的配送起点位置，构建三角网，所述三角网包括相邻接的多个三角形，每个三角形中的三个顶点分别对应三个配送服务方的配送起点位置；遍历所述三角网中的各个三角形，分别获取每个三角形的外心点；对于任一顶点，将包括所述顶点的各个三角形的外心点组成的外心点集合，作为与所述顶点对应的外心点集合；根据每一个顶点对应的外心点集合，计算由所述外心点集合中的外心点组成的凸包，所述凸包作为包括所述顶点对应的配送服务方的配送起点位置的泰森多边形。3.根据权利要求2所述的方法，其特征在于，所述根据每一个顶点对应的外心点集合，计算由所述外心点集合中的外心点组成的凸包，包括：基于所述外心点集合中的各个外心点的坐标，按照坐标从小到大的顺序进行排序；将排序在前两位的外心点的坐标放入上凸包集合，并依照排序遍历剩余的外心点坐标，将剩余的外心点坐标中满足右转定理的外心点坐标逐个加入所述上凸包集合，当剩余外心点坐标遍历结束时得到上凸包集合；将排序在后两位的外心点的坐标放入下凸包集合，并依照排序遍历剩余的外心点坐标，将剩余的外心点坐标中满足右转定理的外心点坐标逐个加入所述下凸包集合，当剩余外心点坐标遍历结束时得到下凸包集合；组合所述上凸包集合和下凸包集合中的各个外心点，得到所述外心点组成的凸包。4.根据权利要求1所述的方法，其特征在于，所述将所述n个任务地址信息分配至所述m个泰森多边形中，包括：对于任一个任务地址信息，以所述任务地址信息为起点做单向射线；统计所述单向射线与参与判断的泰森多边形的各条边之间的交点的总数量，所述泰森多边形的每条边的两个端点中去除其中一个端点不参与所述统计，且各条边去除的是同向端点；响应于所述交点的总数量满足预设数量条件，确定所述任务地址信息在所述参与判断的泰森多边形内，将所述任务地址信息分配至所述泰森多边形。5.根据权利要求4所述的方法，其特征在于，所述泰森多边形的每条边的两个端点中去除其中一个端点不参与所述统计，且各条边
去除的是同向端点，包括：所述泰森多边形中的每条边的两个端点中，去除y坐标较大的端点；或者，所述泰森多边形中的每条边的两个端点中，去除y坐标较小的端点；所述统计所述单向射线与参与判断的泰森多边形的各条边之间的交点的总数量，包括：若所述泰森多边形的一条边的两个端点的y坐标相等，则确定所述单向射线与所述边的交点的数量是0。6.根据权利要求1所述的方法，其特征在于，所述将所述n个任务地址信息分配至所述m个泰森多边形中，包括：若所述任务地址信息位于所述泰森多边形的其中一条边上，则将所述任务地址信息分配至所述泰森多边形。7.根据权利要求1～6任一所述的方法，其特征在于，所述分别获取n个任务地址信息、以及m个配送服务方中每个配送服务方的配送起点位置，包括：获取m个配送服务方中每个配送服务方的实时定位位置，作为所述配送服务方的配送起点位置；获取待分配的n个配送任务，每个配送任务包括：一个供货地址和一个收货地址，所述供货地址用于表示提供配送货物的商家地址，所述收货地址用于表示收取所述配送货物的用户地址；对于所述n个配送任务中的每一配送任务，基于所述供货地址和收货地址确定重心位置，并将所述重心位置作为所述配送任务对应的任务地址信息。8.根据权利要求7所述的方法，其特征在于，所述将所述n个任务地址信息分配至所述m个泰森多边形中之后，所述方法还包括：对于任一泰森多边形，获取分配至所述泰森多边形内的配送任务节点集合，所述配送任务节点集合中的各配送任务节点，包括：分配至所述泰森多边形内的各任务地址信息对应的配送任务的供货地址和收货地址；根据所述配送任务节点集合，确定所述泰森多边形内的配送服务方由配送起点位置到所述配送任务节点集合中的各个配送任务节点的最短配送路线；并且，确定的所述最短配送路线满足：对于任一配送任务，所述配送服务方到达所述配送任务中的供货地址的时间先于收货地址。9.一种配送任务的分配装置，其特征在于，所述装置包括：数据获取模块，用于分别获取n个任务地址信息、以及m个配送服务方中每个配送服务方的配送起点位置，所述n和m是正整数；每个所述任务地址信息对应一笔配送任务，所述配送起点位置表示负责执行配送任务的配送服务方的配送起点；泰森图构造模块，用于根据所述m个配送服务方的配送起点位置，构建得到m个泰森多边形，每个泰森多边形的内部包括一个所述配送服务方的配送起点位置；任务分配模块，用于将所述n个任务地址信息分配至所述m个泰森多边形中。10.一种电子设备，其特征在于，包括：处理器；用于存储处理器可执行指令的存储器；其中，所述处理器通过运行所述可执行指令以实现如权利要求1-8中任一项所述的方
法。11.一种计算机可读存储介质，其上存储有计算机指令，其特征在于，该指令被处理器执行时实现如权利要求1-8中任一项所述方法的步骤。

技术总结

本说明书一个或多个实施例提供一种配送任务的分配方法及装置，其中，所述方法包括：分别获取N个任务地址信息、以及M个配送服务方中每个配送服务方的配送起点位置，所述N和M是正整数；根据所述M个配送服务方的配送起点位置，构建得到M个泰森多边形，每个泰森多边形的内部包括一个所述配送服务方的配送起点位置；将所述N个任务地址信息分配至所述M个泰森多边形中。形中。形中。