本发明涉及一种基于粗细粒度变异的不确定多仓库多物流车调度方法，属于物流车调度。
背景技术：
1、得益于物联网、云计算及人工智能等新一代信息技术的广泛应用，物流行业正在从被动遵循传统模式向主动实施智能决策与高效运营的模式转变。在物流运输方面，现有的对于物流车调度的研究以单仓库的调度问题为主，但是随着行业发展，不确定多仓库的多物流车调度场景增加，现有的针对单仓库场景下的物流运输规划方法难以满足复杂不确定多仓库调度优化的要求。同时，传统的路径规划方式忽略了物流车间的负载均衡性，所规划的路径可能不合理，并且并非最优或近优路径，会增加物流运输时间与运输成本，造成物流车配送效率低和运输成本高的缺陷。
技术实现思路
1、本发明要解决的技术问题是，针对不确定多仓库多物流车调度问题，提供一种基于粗细粒度变异的不确定多仓库多物流车调度方法，能够对物流车调度路径进行优化设计，在优化物流车路径长度的同时维持不同物流车之间路径长度的均衡性，能够提升物流调度效率和降低运输成本。
2、为解决上述技术问题，本发明采用的技术方案为：
3、一种基于粗细粒度变异的不确定多仓库多物流车调度方法，包括以下步骤：
4、步骤a，读取待优化的不确定多仓库多物流车调度实例信息，以及确定不确定多仓库多物流车调度问题的优化目标与约束条件，基于不确定多仓库多物流车调度实例信息初始化遗传算法的参数，得到初始化遗传算法参数，并基于约束条件在多物流车调度问题的解空间中随机生成初始种群，初始种群中的每个解为物流车的一种调度方案，每辆物流车按照调度方案中对应的服务序列中的客户编号依序服务目标客户；
5、步骤b，对初始种群的每个个体进行适应值评估，得到个体适应值，所述个体适应值为个体表征的物流调度方案中最长物流车服务序列长度的倒数；
6、步骤c，采用轮盘赌策略根据个体适应值选择种群中优秀个体参与种群的后续更新，将所选择的个体进行随机两两配对，而后根据初始化遗传算法参数中交叉概率对每对个体进行改进的稳态分组交叉操作，产生的新个体组成新种群；
7、步骤d，依根据初始化遗传算法参数中变异概率从新种群中选择参与变异的个体；而后针对每个参与变异的个体依概率执行粗粒度或细粒度变异策略产生新的物流车服务序列；随后，针对新物流车服务序列进行局部搜索操作以进一步优化得到优化后物流车服务序列；
8、步骤e，评估经历上述操作后的新种群中的每个个体所表征的优化后物流车服务序列的适应值，并根据优化目标用适应值最大的个体来更新全局最优物流车调度方案；
9、步骤f，重复步骤c、步骤d和步骤e，直至满足终止条件，输出全局最优物流车调度方案。
10、步骤a中，所述不确定多仓库多物流车调度实例信息包括客户信息和物流车信息，所述客户信息包括待服务目标客户个数和目标客户坐标，所述物流车信息包括物流车个数 m；所述优化目标为最小化最长物流车服务序列长度，所述约束条件为每一个客户只能被一辆物流车服务一次，每辆物流车将一个客户作为仓库，从这个作为仓库的客户点出发服务其他客户，最后返回这个作为仓库的客户点。
11、步骤a中，所述遗传算法的参数包括种群数量 np、交叉概率 p c、变异概率 p m、最大适应值评估次数 eval max，初始时适应值评估次数被初始化为0，在步骤b和步骤e中每对一个个体进行一次评估，则适应值评估数加1，终止条件为适应值评估数达到初始化遗传算法参数中最大适应值评估次数 eval max。
12、步骤b中，所述个体适应值的公式如下所示：
13、 （1）；
14、其中， f(·)表示适应值函数， x k表示当前的物流车调度方案， d1、 d2… d m分别表示第1、2…… m条物流车服务序列路径长度，max{ d1, d2,…, d m}表示最长的物流车服务序列路径长度；
15、设第 j条物流车服务序列中的目标客户用 c表示，目标客户之间的距离用 d表示，则第 j条物流车服务序列路径长度 d j为：
16、 （2）；
17、其中， n j表示第 j个物流车服务的客户数量，表示客户节点与客户节点 c i+1之间的距离，其中 c i表示第 j条物流车服务序列中的第 i个客户， c i+1表示第 j条物流车服务序列中的第 i+1个客户，表示客户节点与客户节点 c1之间的距离，其中表示第 j条物流车服务序列中的第 n j个客户， c1表示第 j条物流车服务序列中的第1个客户。
18、步骤c中，根据轮盘赌策略选择优秀个体来参与种群的更新，具体为：先从种群中依概率选择优秀个体；设当前的物流车调度方案为 x k，则在单次选择中这个个体被选中的概率 p( x k)为：
19、 （3）；
20、其中，为当前个体适应值，为第 m条物流车调度方案适应值，由于单次选择仅选取一个个体进入新种群，所以将重复放回地选 np次， np为种群数量，来源于初始化遗传算法参数，最终选择np个体形成新种群；
21、然后根据初始化遗传算法参数中交叉概率 p c对于种群内的个体进行交叉操作；具体为将 np个个体两两进行随机配对，并产生一个在(0, 1)之间的均匀随机数；如果该随机数小于系统预设的交叉概率 p c，则将这两个个体使用交叉算子进行交叉产生子代。
22、步骤c中，交叉操作采用改进的稳态分组交叉，具体包括以下步骤：
23、步骤g，随机从需要进行交叉的两个个体中选择一个个体；将该个体中长度最短的物流车服务序列复制给子代，所述子代为将要生成的个体，其中长度最短的路径就是个体中最短的物流车服务序列，然后在两个亲本中删除这条服务序列中的客户；
24、步骤h，重复所述步骤g，直到后代包含 m条服务序列；
25、步骤i，将执行完步骤h后剩下的未分配的目标客户分配给后代中的物流车服务序列；采用以下两种方法：第一种方法是将目标客户插入到导致路径长度最少增量的序列及其相应位置中；第二种方法是随机选择一条序列，而后将目标客户插入到导致这条序列路径长度最少增量的位置中，第一种方法和第二种方法分别以95%与5%的概率进行二选一使用。
26、当步骤h执行过程中存在后代中尚未包含 m条服务序列但是所有目标客户均已包含在现有服务序列中的情况时，进行修正操作，具体为将至少服务4个目标客户且满足路径长度最长的序列一分为二，同时使得总物流车服务序列长度最短。
27、步骤d中，变异操作分为粗粒度变异与细粒度变异策略，在执行变异操作时，对于种群中的每个个体，每次生成一个在(0, 1)之间的均匀随机数，如果该随机数小于0.5则执行细粒度变异操作，否则执行粗粒度变异操作；
28、所述细粒度变异是随机选取一条含有至少三个客户的物流车服务序列，选取这条序列中的随机一个客户并移出序列，接着使用贪心策略将这个被移出的客户插入到使物流车服务序列路径长度增量最小的序列位置；
29、所述粗粒度变异操作是随机选取一条含有至少四个客户的物流车服务序列，选取这条服务序列中的一条子序列并移出序列，同时保证被移出子序列的剩余物流车服务序列中至少含有两个客户，接着使用贪心策略将这个被移出的子序列插入到使物流车服务序列长度增量最小的序列位置。
30、步骤d中，局部搜索操作使用2-opt算子，具体包括以下步骤：对于每个物流车调度方案，依次遍历它的每条物流车服务序列，对于每条至少有四个客户的物流车服务序列，设其中不相邻的两个客户分别为第一客户 c1与第二客户 c2，第一客户 c1与第二客户 c2所对应的后继客户分别为第一后继客户 c3与第二后继 c4，将局部搜索前的两条边，即边( c1, c3)与边( c2, c4)删除，并增加新边( c1, c4)与新边( c2, c3)，比较新的物流车服务序列与原本的物流车服务序列长度；如果新的物流车服务序列长度更短，则对物流车服务序列进行更新，否则原物流车服务序列保持不变，继续遍历下一个客户对，直至遍历完整条物流车服务序列。
31、步骤e中，对于种群中的每个物流车调度方案，如果个体的适应值大于当前系统中的全局最优适应值，代表物流车服务序列质量更高，则将相应的全局最优物流车调度方案更新为当前物流车调度方案；
32、设全局最优个体为 x best，当前的物流车调度方案为 x k，则更新公式如下所示：
33、 （4）；
34、其中， 表示第 k个物流车调度方案的适应值，表示目前最优的物流车调度方案的适应值。
35、本发明的有益效果：本发明提供的一种基于粗细粒度变异的不确定多仓库多物流车调度方法，通过改进的稳态分组交叉和粗粒度与细粒度变异策略，对于种群中的解不断改进更新，易于跳出局部最优，获得全局最优的优势，将其运用在本发明的不确定多仓库多物流车调度上，可以在少量的迭代次数下获得多物流车调度的近优路径，从路径设计上提升物流调度效率，以及实现降低运输成本的效果。
1.一种基于粗细粒度变异的不确定多仓库多物流车调度方法，其特征在于：包括以下步骤：
2.根据权利要求1所述一种基于粗细粒度变异的不确定多仓库多物流车调度方法，其特征在于：步骤a中，所述不确定多仓库多物流车调度实例信息包括客户信息和物流车信息，所述客户信息包括待服务目标客户个数和目标客户坐标，所述物流车信息包括物流车个数m；所述优化目标为最小化最长物流车服务序列长度，所述约束条件为每一个客户只能被一辆物流车服务一次，每辆物流车将一个客户作为仓库，从这个作为仓库的客户点出发服务其他客户，最后返回这个作为仓库的客户点。
3.根据权利要求1所述一种基于粗细粒度变异的不确定多仓库多物流车调度方法，其特征在于：步骤a中，所述遗传算法的参数包括种群数量np、交叉概率pc、变异概率pm、最大适应值评估次数evalmax，初始时适应值评估次数被初始化为0，在步骤b和步骤e中每对一个个体进行一次评估，则适应值评估数加1，终止条件为适应值评估数达到初始化遗传算法参数中最大适应值评估次数evalmax。
4.根据权利要求1所述的一种基于粗细粒度变异的不确定多仓库多物流车调度方法，其特征在于：步骤b中，所述个体适应值的公式如下所示：
5.根据权利要求1所述一种基于粗细粒度变异的不确定多仓库多物流车调度方法，其特征在于：步骤c中，根据轮盘赌策略选择优秀个体来参与种群的更新，具体为：先从种群中依概率选择优秀个体；设当前的物流车调度方案为xk，则在单次选择中这个个体被选中的概率p(xk)为：
6.根据权利要求5所述一种基于粗细粒度变异的不确定多仓库多物流车调度方法，其特征在于：步骤c中，交叉操作采用改进的稳态分组交叉，具体包括以下步骤：
7.根据权利要求6所述一种基于粗细粒度变异的不确定多仓库多物流车调度方法，其特征在于：当步骤h执行过程中存在后代中尚未包含m条服务序列但是所有目标客户均已包含在现有服务序列中的情况时，进行修正操作，具体为将至少服务4个目标客户且满足路径长度最长的序列一分为二，同时使得总物流车服务序列长度最短。
8.根据权利要求1所述一种基于粗细粒度变异的不确定多仓库多物流车调度方法，其特征在于：步骤d中，变异操作分为粗粒度变异与细粒度变异策略，在执行变异操作时，对于种群中的每个个体，每次生成一个在(0, 1)之间的均匀随机数，如果该随机数小于0.5则执行细粒度变异操作，否则执行粗粒度变异操作；
9.根据权利要求1所述一种基于粗细粒度变异的不确定多仓库多物流车调度方法，其特征在于：步骤d中，局部搜索操作使用2-opt算子，具体包括以下步骤：对于每个物流车调度方案，依次遍历它的每条物流车服务序列，对于每条至少有四个客户的物流车服务序列，设其中不相邻的两个客户分别为第一客户c1与第二客户c2，第一客户c1与第二客户c2所对应的后继客户分别为第一后继客户c3与第二后继c4，将局部搜索前的两条边，即边(c1, c3)与边(c2, c4)删除，并增加新边(c1, c4)与新边(c2, c3)，比较新的物流车服务序列与原本的物流车服务序列长度；如果新的物流车服务序列长度更短，则对物流车服务序列进行更新，否则原物流车服务序列保持不变，继续遍历下一个客户对，直至遍历完整条物流车服务序列。
10.根据权利要求1所述的一种基于粗细粒度变异的不确定多仓库多物流车调度方法，其特征在于：步骤e中，对于种群中的每个物流车调度方案，如果个体的适应值大于当前系统中的全局最优适应值，代表物流车服务序列质量更高，则将相应的全局最优物流车调度方案更新为当前物流车调度方案；
