1.一种物流调度方法,其特征在于,包括以下步骤:
获取某一时间段内的物流订单,所述物流订单至少包括一条订单,每条所述订单均至少包括一个客户点i及其位置(xi,yi)和货物需求量qi;
根据所述物流订单中货物需求总量以及运输车辆的限载确定运输车辆数M和路径数M;
其中M≤N,N为物流订单中的客户点数;
根据每个客户点i的位置(xi,yi)和配送中心位置(x0,y0)计算得到M台运输车辆执行所述物流订单的可行方案;
根据实际场景及优化目标构建物流调度优化模型;
构建超启发式优化池,所述超启发式优化池包含多种开发策略;
基于所述物流调度优化模型,采用所述超启发式优化池中的开发策略对所述可行方案进行调整,输出最优可行方案;
其中,采用所述超启发式优化池中的开发策略对所述可行方案进行调整的具体实现过程为:步骤6.1:采用所述超启发式优化池中的全部开发策略对所述可行方案进行T轮次全策略调整,得到T轮次后的第一可行方案以及每种开发策略的归一化调整概率;其中T≥1;
步骤6.2:在所述超启发式优化池中随机选择一种开发策略对所述第一可行方案进行扰动,得到第二可行方案;
步骤6.3:根据每种开发策略的归一化调整概率选择超启发式优化池中的开发策略对所述第二可行方案进行优化调整,得到第三可行方案,并计算优化调整后每种开发策略的选择调整概率;
步骤6.4:基于优化调整后每种开发策略的选择调整概率,对所述第三可行方案重复执行步骤6.2和6.3,直到所述第三可行方案连续G次无替换,则输出最优可行方案。
2.根据权利要求1所述的物流调度方法,其特征在于,当每台运输车辆的限载相同时,所述运输车辆数M或路径数M的计算公式为:其中,Q为单台运输车辆的限载, 为取整符号;
当每台运输车辆的限载不同时,满足下式的最小M值即为运输车辆数或路径数,具体公式为:其中,Qk为第k台运输车辆的限载。
3.根据权利要求1所述的物流调度方法,其特征在于,得到M台运输车辆执行所述物流订单的可行方案的具体实现过程为:步骤3.1:定义客户集合V和路径集合R,其中V={1,2,…,i,…,N},R={1,2,…,k,…,M},且设初始时路径集合R中的M条路径为空路径;
步骤3.2:计算集合V中每个客户点i到配送中心的距离di0;
步骤3.3:计算将客户点i插入到第k条路径的插入成本,得到客户点i插入到M条路径的插入成本,所述插入成本的具体公式为:其中, 为客户点i插入到第k条路径的插入成本, 为未插入客户点i时第k条路径的运输成本, 为插入客户点i时第k条路径的运输成本,|Rk|为未插入客户点i时第k路径上的客户点数,|Rk′|为插入客户点i时第k路径上的客户点数, 为第k条路径上客户点j与客户点j+1之间的距离, 为第k条路径上配送中心与第一个客户点之间的距离, 为第k条路径上第|Rk|个客户点与配送中心之间的距离, 为第k条路径上插入客户点i与配送中心之间的距离;
步骤3.4:对所述客户点i对应的M个插入成本进行升序排序,并计算所述客户点i的遗憾值,具体公式为:其中,RVi为客户点i的遗憾值, 为客户点i对应的M个插入成本中排第三的插入成本,为客户点i对应的M个插入成本中排第一的插入成本, 所对应的路径即为客户点i的插入成本最小路径;
步骤3.5:重复执行步骤3.3和3.4,得到集合V中每个客户点i的遗憾值;
步骤3.6:提取出集合V中最大遗憾值所对应的客户点imax,将客户点imax插入到其插入成本最小路径的末尾;
步骤3.7:在集合V中删除客户点imax;
步骤3.8:判断集合V是否为空;当集合V不为空时,重复执行步骤3.3~3.8;当集合V为空时,得到M台运输车辆执行所述物流订单的可行方案。
4.根据权利要求1所述的物流调度方法,其特征在于,所述物流调度优化模型的具体表达式为:其中,V0={0,1,2,…,N},V={1,2,…,i,…,N},R={1,2,…,k,…,M},V为客户集合,V0为客户和配送中心的集合,i,j=0表示配送中心,j≠i,R为路径集合;C为运输成本;dij为点i到点j之间的距离; 为二值变量, 取值为1或0,当 时,表示在第k路径中运输车辆由点i驶向点j;Qk为第k台运输车辆的限载。
5.根据权利要求1所述的物流调度方法,其特征在于,所述超启发式优化池包括节点重分配策略、两节点交换策略、顶点弧交换策略、两弧交换策略、三弧交换策略、链重定位策略和交叉交换策略。
6.根据权利要求1所述的物流调度方法,其特征在于,所述步骤6.1中,T轮次所述全策略调整的具体实现过程为:步骤6.11:对所述超启发式优化池中的所有开发策略进行随机排序;
步骤6.12:采用排序中的开发策略对所述可行方案进行调整,得到调整后的可行方案;
步骤6.13:当调整后的可行方案满足所述物流调度优化模型中的约束条件,且调整后的可行方案的运输成本小于调整前的可行方案的运输成本时,采用调整后的可行方案替换调整前的可行方案,并记录当前开发策略的替换次数;
步骤6.14:进入下一个开发策略,重复执行步骤6.12~6.14,直到完成所述超启发式优化池中的所有开发策略,即完成当前循环;
步骤6.15:循环次数+1,并判断循环次数是否等于设定循环次数;如果否,则对当前循环得到的可行方案重复执行步骤6.12~6.15;如果是,则得到当前轮次的第一可行方案以及每种开发策略的总替换次数;其中循环次数的初始值为0;
步骤6.16:轮次+1,并判断轮次是否等于设定轮次T,如果否,则对当前轮次得到的第一可行方案重复执行步骤6.12~6.16;如果是,则得到T轮次后的第一可行方案以及每种开发策略的总替换次数;其中轮次的初始值为0。
7.根据权利要求6所述的物流调度方法,其特征在于,在全策略调整后,根据每种开发策略的总替换次数计算其归一化调整概率,具体计算公式为:其中, 为全策略调整后第i种开发策略的归一化调整概率, 为全策略调整后第i种开发策略的修正调整概率,NT为超启发式优化池中开发策略数, 为全策略调整后第i种开发策略的总替换次数,σ为修正参数,S为每轮次中的循环次数。
8.根据权利要求1所述的物流调度方法,其特征在于,所述步骤6.2中,扰动的具体实现过程为:步骤6.21:根据所述物流调度优化模型计算所述第一可行方案的运输成本C1;
步骤6.22:在[M,2M]之间随机选择一整数赋给m;
步骤6.23:从所述超启发式优化池中随机选择一种开发策略对所述第一可行方案进行调整,得到调整后的可行方案,并计算调整后的可行方案的运输成本;
步骤6.24:重复执行m-1次步骤6.23,得到m个调整后的可行方案及其运输成本;
步骤6.25:从m个调整后的可行方案中挑选出运输成本小于(1+dev)C1的可行方案,其中dev为成本容忍系数;
步骤6.26:从运输成本小于(1+dev)C1的可行方案中随机选择一个方案作为第二可行方案。
9.根据权利要求1所述的物流调度方法,其特征在于,所述步骤6.3中,根据每种开发策略的调整概率采用轮盘赌选择算法选择超启发式优化池中的开发策略对所述第二可行方案进行优化调整。
10.根据权利要求1所述的物流调度方法,其特征在于,所述步骤6.3中,优化调整后每种开发策略的选择调整概率的计算公式为:其中, 为第g+1次优化调整过程中第i种开发策略的选择调整概率, 为第g次优化调整过程中第i种开发策略的归一化调整概率, 为全策略调整后第i种开发策略的归一化调整概率,a为历史经验系数, 为第g次优化调整过程中第i种开发策略的修正调整概率,σ为修正参数, 为第g次优化调整过程中第i种开发策略的替换次数, 为第g次优化调整过程中第i种开发策略的选用次数,NT为超启发式优化池中开发策略数。
11.一种电子设备,包括存储器和处理器,所述存储器上存储有能够在所述处理器上运行的计算机程序,其特征在于,所述处理器运行所述计算机程序时执行权利要求1~10中任一项所述物流调度方法的步骤。
12.一种计算机可读存储介质,所述计算机可读存储介质为非易失性存储介质或非瞬态存储介质,其上存储有计算机程序,其特征在于,所述计算机程序被处理器运行时执行权利要求1~10中任一项所述物流调度方法的步骤。