1.一种基于场景预测的动态路径规划方法,其特征在于,包括以下步骤,S1、构建静态车辆路径规划模型;
S2、建立动态车辆路径规划的目标函数;
S3、计算潜在客户影响程度;
S4、根据潜在客户影响程度,构建预测客户集;
S5、基于预测客户集,进行动态车辆路径问题的求解;
应用于由1个仓库、n个客户、m辆运输车所组成的场景中,由所述1个仓库和n个客户构成节点集,,其中,中的客户划分为已知客户和潜在客户,从而得到已知客户集和潜在客户集;
将节点集中各个节点之间直线路径作为边集;其中,表示任意第个节点和第个节点之间的直线路径;记所述直线路径的直线距离记为;令每辆运输车的最大载重量均为;假设所有的车辆均是以仓库为起点和终点;
步骤S1具体包括,
步骤1.1、给定路径规划时长为T,并将T均为个等长的时间片,定义任一时间片的序号为q,并初始化=1;
步骤1.2、将前第个时间片出现的所有客户作为已知客户集合,将当前第个时间片出现的所有客户作为新客户集合;
步骤1.3、利用式(1)建立当前第个时间片下静态车辆路径规划模型的目标函数:(1)
式(1)表示所有车辆的总行驶路程,表示第个时间片下第辆运输车第个节点和第个节点之间的直线距离,表示第个时间片下第u辆车是否经过第个节点和第个节点之间的直线路径,若经过,则令1,否则,令;
步骤1.2、利用式(2)-式(7)构建当前第个时间片下静态车辆路径规划模型的约束条件:(2)
(3)
(4)
(5)
(6)
(7)
式(2) 和 式(3) 表明每个客户必须且只能访问一次;式(4)中m是位于仓库的车辆总数,表示从仓库出发的车辆,约束(4)确保调度的车辆数量不应大于仓库中提供的车辆总数;
式(5)是子环消除约束,表示集合中的客户数量;
式(6)、(7)中表示客户的需求,式(6)保证每条路线上的总需求不能超过车辆的容量;
步骤2中利用式(8)建立动态车辆路径规划的目标函数:(8);
步骤3包括,已知客户集中添加一个潜在客户,从而构成第l个临时客户集,根据当前第个时间片下静态车辆路径规划模型,对进行求解,得到对应客户访问路径序列,从而根据计算潜在客户的影响程度;
步骤3.1、利用式(9)计算配送车辆的容量:(9)
式(9)中,表示已知客户集中的已知客户数量;
步骤3.2、根据利用蚁群算法对构成的客户集进行求解,获得客户访问序列,并计算客户访问序列的长度为;利用蚁群算法对进行求解,获得客户访问序列,并计算客户访问序列的长度为;步骤3.3、根据获得的客户访问序列和客户访问序列的长度根据公式(10)-(14)计算潜在客户的影响程度;
(10)
(11)
(12)
(13)
(14)
函数计算方式为:将潜在客户从中删除,获得删除之后的客户访问序列,对比和相同位置上的客户的不同数量,函数表示的解中包含的客户数量;α和β为控制参数调节扰动对出行成本和路线的重要程度,式(14)中表示计算获取的潜在客户影响的程度。
2.根据权利要求1所述的基于场景预测的动态路径规划方法,其特征在于:步骤S4包括,步骤4.2、计算预测客户集需要添加的客户数量:(15)
式(15)中表示中的客户数量;
步骤4.3、根据影响程度对潜在客户中的客户进行降序排序;
步骤4.4、从潜在客户中选取前个客户加入已知客户集中,构成预测客户集,同时从潜在客户中删除对应的客户;
步骤4.5、根据静态路径问题模型优化预测场景的访问路线。
3.根据权利要求2所述的基于场景预测的动态路径规划方法,其特征在于:步骤S5具体包括,步骤5.2、第个时间片开始阶段,将新出现的客户加入当前已知客户集合;
步骤5.3、判断预测客户集的大小是否达到预期数量:(16)
式(16)中表示中的客户数量;
步骤5.4、若,根据影响程度从潜在客户集中选取一个影响程度最大的客户加入预测客户集,并将其合并到新客户集中,并从中删除;
若,根据影响程度从预测客户集中选取一个影响程度最大的潜在客户,同时从预测客户集中删除加入潜在客户集,在中连接的前一个客户和后一个客户;步骤5.5、重复步骤5.4直到;
步骤5.5、采用贪婪插入的方式将新客户集插入到路径上;
步骤5.6、局部搜索:
步骤5.7、重复5.2到5.6步骤直到时间片结束,返回动态路径规划的解。
4.根据权利要求3所述的基于场景预测的动态路径规划方法,其特征在于:步骤5.6、局部搜索,具体包括,步骤5.6.1、定义五种局部搜索算子执行操作:
1)随机选择路线中的一个客户,随机移动其位置;
2)随机选择路线中的两个客户和,交换客户的位置;
3)随机选择路线中的两条路线和,从上随机选择一个客户,从上随机选择一个客户,交换从之后,从之后的路线;
4)随机选择路线中的一条路线,从上随机选择两个客户和,将和之间的客户顺序颠倒;
5)随机选择路线中的以条路线,从上随机选择两个客户和,将和之间的客户随机插入到其他位置;
步骤5.6.2、随机选取一个搜索算子进行优化,持续优化直到时间达到当前场景分配时间。
5.一种计算机设备,包括存储器和处理器,所述存储器存储有计算机程序,其特征在于,所述计算机程序被所述处理器执行时,使得所述处理器执行如权利要求1至4中任一项所述方法的步骤。