1.一种基于路径规划的城市众包配送任务优化调度方法，其特征在于，包括如下步骤：步骤1：构建众包配送网络图；

步骤2：获取众包骑手和众包配送任务信息；

步骤3：构建基于路径规划的众包配送任务优化调度模型；

步骤4：基于贪心策略对初始众包任务调度方案进行求解；

步骤5：基于变邻域搜索对众包配送任务进行优化调度；

所述步骤1，构建众包配送网络图具体如下：

众包配送网络图可表示为图G＝(V,E)，其中，V＝VS∪VC为节点集合，每个节点表示一个商家或客户，VS＝{1,2,…,ns}为商家的集合，VC＝{ns+1,ns+2,…,nc}为客户的集合，ns和nc分别为商家和客户的数量；E＝{(i,j)|i,j∈V}为边的集合，对于每条边(i,j)∈E，dij表示节点i与节点j之间的距离，dij＝dji，dii＝0；

所述步骤2，获取众包骑手和众包配送任务信息具体如下：

众包骑手表示为集合K＝{1,2,…,nk}，nk为众包骑手的数量，对于每个骑手k∈K，Qk表示骑手k的最大载重量，vk表示骑手k的平均行驶速度，d′ki表示骑手k从所在位置到节点i∈V的距离；

众包配送任务表示为集合T＝{1,2,…,nt}，nt为配送任务的数量，每个配送任务t∈T表示为一个六元组：(st,ct,bt,ft,et,wt)，其中，st∈VS表示任务t的取货商家，ct∈VC表示任务t的送货客户，bt表示任务t的最早开始时间，即从商家st的最早开始取货时间，ft表示任务t的最晚开始时间，即从商家st的最晚开始取货时间，et表示任务t的最晚结束时间，即货物送到客户ct的最晚结束时间，wt表示任务t的货物重量，每个配送任务的货物重量都不超过任意骑手的最大载重，即wt≤min{Qk|k∈K}；

对于每个节点i∈V，令si表示在节点i每个任务的平均服务时间，如果i∈VS，si表示骑手在商家i的平均取货时间，如果i∈VC，si表示骑手在客户i的平均送货时间，任务的平均服务时间根据历史数据采用数理统计的方法进行计算；

所述步骤3，构建基于路径规划的众包配送任务优化调度模型具体如下：建立任务配送方案：一个任务分配方案表示为一个从众包配送任务集合T到众包骑手集合K的映射函数a:T→K∪{0}，对于任务t∈T，如果a(t)＝k∈K，表示将任务t分配给骑手k来配送，如果a(t)＝0，表示任务t没有被分配；令Ta(k)＝{t∈T|a(t)＝k,k∈K}表示分配给骑手k的任务集合，如果 表示没有给骑手k分配配送任务；令Ta表示所有被分配的任务集合，则Ta＝∪k∈KTa(k)；从集合T到集合K存在许多分配方案，令Ω(T,K)表示从T到K的所有任务分配方案的集合；

定义任务序列和配送路径：a表示为一个任务分配方案，a∈Ω(T,K)，分配给骑手k的任务集合表示为 Ta(k)的一个任务序列为多重集的一个全排列，表示为：pak＝pak(1),pak(2),…,pak(2|Ta(k)|)，其中，pak(l)为任务序列pak中第l个位置所对应的任务，l＝1,2,…,2|Ta(k)|；

a∈Ω(T,K)表示为一个任务分配方案，Ta(k)表示为分配给骑手k的任务集合，pak∈Pa(k)表示为一个任务序列，则pak的配送路径为一条从骑手k的所在位置出发依次经过pak中的每个任务所对的商家或客户节点的序列，表示为vak＝vak(0),vak(1),…,vak(2|Ta(k)|)，其中，vak(0)＝k，表示骑手k所在的位置，vak(l)表示Pa(k)中的第l个任务所对应的节点，l＝

1,2,…,2|Ta(k)|，由于任务序列中的每个任务出现两次‑‑取货和送货，我们规定排在前面的任务所对应的节点为商家节点，排在后面的任务所对应的节点为客户节点；

配送距离函数表示为 其中，pak∈Pa(k)为一个

任务序列，vak为所对应的配送路径， 表示从骑手k到第一个节点vak(1)的距离，k＝vak(0)， 表示vak中相邻两个节点之间的距离之和，如果两个相邻节点为同一个节点，则其距离为0；

设置时间约束和负载约束：时间约束函数表示为H(pak,t)∈{true,false}，其中，t∈Ta(k)表示为一个任务，pak∈Pa(k)表示为一个任务序列，如果任务t按照pak中所对应的配送路径vak配送货物满足商家的最晚取货时间和客户的最晚送货时间约束，则H(pak,t)＝true，否则，H(pak,t)＝false；

负载约束函数表示为Q(pak)∈{true,false}，其中，pak∈Pa(k)为一个任务序列，如果骑手k按照任务序列pak所对应的配送路径vak配送货物能够满足其最大载重约束，则Q(pak)＝true，否则Q(pak)＝false；

定义基于路径规划的众包配送任务优化调度模型为：

max∑k∈K|Ta(k)|    (1)

min∑k∈Kd(pak)    (2)

s.t.

Q(pak)＝true pak∈Pa(k)              (3)H(pak)＝true pak∈Pa(k)              (4)pak∈Pa(k) a∈Ω(T,K),k∈K    (5)a∈Ω(T,K)           (6)。

2.根据权利要求1所述的一种基于路径规划的城市众包配送任务优化调度方法，其特征在于，所述步骤4，基于贪心策略对初始众包任务调度方案进行求解具体方法如下：

0 0

定义Ta(k)为当前已分配给骑手k的任务集，pak为骑手k当前满足约束的任务序列，t∈

0 0

T‑∪k∈KTa(k)为一个未分配的任务，如果将t插入到pak的两个适当位置后所得到新的任务

0 1 0

序列仍满足负载约束和时间约束，则称t为pak的一个可扩展任务，Ta(k)＝T a(k)∪{t}为插入任务t后骑手k的任务集；

0

将任务t插入到任务序列p ak有两种方式：相邻和相隔；相邻插入是指将任务t插入到

0 0

pak后，任务t在新任务序列中两个位置是相邻的；相隔插入是指任务t插入到pak后，任务t在新任务序列中两个位置是不相邻的；

具体步骤如下：

Step 1：根据骑手ki的位置，得到骑手ki与所有未配送任务商家点的距离集合S，得到所有未配送任务完成的最短路径长度集合D，两个集合对应下标值相加，按相加和从小到大排0

序，并保存至任务分配序列Ta(ki)；

0

Step 2：在Ta(ki)选取第一个任务t1，将该任务添加到骑手ki的任务配送序列pa(ki)，作为骑手ki的第一个配送任务，同时该任务状态置为已配送状态；

0

Step 3：添加第二个任务，将Ta(ki)中每个任务t2,t3,…,tj，利用相邻和相隔插入策略都添加至pa(ki)中一遍，若其中某种插入策略得到的pa(ki)满足t1和tj的时间约束，骑手ki的容量约束，则保存任务tj按照该种插入策略添加至骑手的任务配送序列pa(ki)的位置和路径长度至序列R中，待所有任务都插入一遍后，将序列R升序排列，路径长度最小的任务tj作为第二个配送任务，按照插入位置添加至pa(ki)中，同时将新的任务配送序列pa(ki)作为添加下一个任务的任务配送序列，tj状态变为已配送；若所有插入策略得到的pa(ki)都不满足约束，则pa(ki)为最终骑手ki的任务配送序列；

Step 4：当序列R为空时，根据pa(ki)和任务关系图获取骑手ki的Vaki，同时得到骑手ki配送pa(ki)的路径长度d(paki)；令t＝t+1，返回Step 2；

Step 5：当t＝nt+1或者所有任务的状态均是已配送时，算法结束，得到初始解集。

3.根据权利要求2所述的一种基于路径规划的城市众包配送任务优化调度方法，其特征在于，所述步骤5，基于变邻域搜索对众包配送任务进行优化调度包括四个邻域结构，分别为：(1)随机两个骑手，随机两个其任务序列中的任务，进行交换；

(2)随机交换一个骑手的任务序列中两个任务的商家点；

(3)随机交换一个骑手的任务序列中两个任务的客户点；

(4)随机两个骑手，随机一个骑手的任务序列中的任务，加在另一个骑手的任务序列中；

具体步骤如下：

Step 1：获取骑手k的初始解pak，设最优解为pak_best；

Step 2：定义邻域结构集合Ns，s＝1,2…,smax作为扰动操作，其中Ns包括交换骑手任务操作、交换任务序列商家点操作、交换任务序列客户点操作和迁移骑手任务操作；

Step 3：定义邻域结构集合Nq，q＝1,2…,qmax作为邻域搜索，其中Nq包括交换骑手任务操作、交换任务序列商家点操作、交换任务序列客户点操作和迁移骑手任务操作；

Step 4：令s＝1，q＝1；

Step 5：使用Ns对pak进行扰动，生成解p’ak；

Step 6：使用Nq对p’ak进行搜索，生成解p”ak；

Step 7：若d(p’ak)

Step 8：若q

Step 9：若d(p”ak)

Step 10：若s

Step 11：输入最优解pak_best，算法结束。