1.一种基于改进混合蚁群算法的物流路径规划方法,其特征在于,包括:
S1:根据物流中配送点与配送点的路线关系、配送点与配送中心的路线关系以及各个配送点、配送路线配送车辆的约束信息生成物流配送任务调度网络模型;
S2:综合考虑最小化成本、最小化客户失望度以及驾驶员负载不均衡最小化三项目标,建立物流配送任务调度网络模型的目标函数;
综合考虑最小化成本、最小化客户失望度以及驾驶员负载不均衡最小化三项目标,建立物流配送任务调度网络模型的目标函数,包括:最小化成本成本函数:
其中,f1表示最小化总成本的目标函数,表示配送时产生的运输成本以及未能在时间窗内完成配送任务所产生的惩罚成本;c表示单位距离所产生的配送成本,dij表示配送点i与j之间的距离,表示物流车辆k服务配送点i后是否服务配送点j,pi表示未能在时间窗内服务所产生的惩罚成本,n表示配送点数量;
最小化客户失望度成本函数:
其中,f2表示最小化客户的平均失望度的目标函数,downi表示客户的失望度,[ETi,LTi]表示节点i的时间窗范围,表示配送点i最佳服务时间窗,ti表示为客户提供的服务时间,如果为客户提供服务时间ti在最佳服务时间窗内,那么客户的失望度为0,为客户i提供服务的时间距离最佳服务时间窗越远,配送点i的失望度越高,在服务时间窗[ETi,LTi]外为配送点i提供服务时失望度为1,且会产生惩罚成本,n表示配送点数量;
最小化驾驶员负载不均衡成本函数:
其中,Wk表示配送车辆k的配送距离,dij表示配送点i与j之间的距离,表示车辆k服务配送点i后是否服务配送点j,车辆配送间的距离是不平衡的,K表示配送车辆数量;
S3:根据物流配送的路径规划设计改进混合蚁群算法;
S4:采用改进混合蚁群算法求解目标函数,并以NSGA-Ⅲ快速非支配排序算法获取更好的非支配解,得到非支配解解集,从非支配解解集中获取物流配送路径规划的最优解。
2.根据权利要求1所述的一种基于改进混合蚁群算法的物流路径规划方法,其特征在于,根据物流配送的路径规划设计改进混合蚁群算法,包括:在算法的初始阶段,引入节约矩阵更新概率公式引导蚂蚁进行路径搜索;采用分段函数来改进信息素挥发因子,得到分段式的信息素挥发因子;精英蚁群采用蚁周模型来更新信息素,普通蚂蚁采用蚁量模型来更新信息素;采用3-opt算法来提高混合蚁群算法的局部搜索能力。
3.根据权利要求2所述的一种基于改进混合蚁群算法的物流路径规划方法,其特征在于,引入节约矩阵更新概率公式引导蚂蚁进行路径搜索,包括:其中,表示蚂蚁k服务完配送点i的客户后服务配送点j的客户的概率,Vjk表示t时刻蚂蚁k下一步允许服务的客户集(即还没有服务的客户);ξ和分别表示第一、第二权重系数,满足0≤ξ,且α表示信息启发式因子,反映了残留的信息量在蚁群的探索过程中的相对重要程度,β表示期望启发式因子(能见度系数),反映了路径期望值在蚁群的探索过程中的相对重要程度;γ表示节约矩阵启发因子,反映了节约矩阵在蚁群的探索过程中的相对重要程度;ηij表示由配送点i到配送点j的能见度,τij表示配送点i到配送点j的信息素浓度,ETj表示节点j允许的最早服务时间,LTj表示节点LTj允许的最晚服务时间,Uij表示节约矩阵,tj表示配送车辆为配送点j的客户的服务时间。
4.根据权利要求2所述的一种基于改进混合蚁群算法的物流路径规划方法,其特征在于,采用分段函数来改进信息素挥发因子,包括:其中,ρ表示信息素挥发因子,NC表示当前迭代次数,NCmax表示初始设置的最大迭代次数。
5.根据权利要求2所述的一种基于改进混合蚁群算法的物流路径规划方法,其特征在于,精英蚁群采用蚁周模型来更新信息素,普通蚂蚁采用蚁量模型来更新信息素,包括:精英蚁群采用蚁周模型来更新信息素:
其中,τij表示配送点i到配送点j路径上的信息素浓度,ρ表示信息素挥发因子,表示精英蚂蚁比普通蚂蚁多出的信息素含量,表示精英蚂蚁k经过i→j的路径后新增信息素含量,ω表示精英蚂蚁信息素增量系数,t表示时间;
普通蚂蚁采用蚁量模型来更新信息素:
其中,τij表示配送点i到配送点j路径上的信息素浓度,ρ表示信息素挥发因子,Δτij表示所有的普通蚂蚁经过i→j的路径后新增信息素含量总和,表示精英蚂蚁k经过i→j的路径后新增信息素含量。
6.根据权利要求2所述的一种基于改进混合蚁群算法的物流路径规划方法,其特征在于,采用3-opt算法来提高混合蚁群算法的局部搜索能力,包括:使用3-opt算法删除路径中三对不相邻的配送点连接,然后计算其他7种不同连接方式的路径长度,对比之后选取最短的路径作为新的连接方式,3-opt相对于2-opt局部搜索能力更强,但是由于3-opt产生的新的连接方式相比于2-opt更多,导致3-opt相对耗时更多,所以我们修改算法中使用局部搜索算法的条件,在蚁群迭代时,若是新一代的最优路径与上一代的最优路径相同,则不使用局部搜索算法,若是不同则使用3-opt局部优化算法来提升算法的局部搜索能力。
7.根据权利要求1所述的一种基于改进混合蚁群算法的物流路径规划方法,其特征在于,所述S4,具体包括:步骤1:初始化参数:输入蚂蚁种群数量k,信息素启发因子α,能见度启发因子β,节约矩阵启发因子γ,两个权重系数ξ和蚁群算法迭代次数NC,NSGA-Ⅲ算法的种群数量n;
步骤2:将K只蚂蚁放到配送中心;
步骤3:将物流配送任务调度网络模型中的配送点作为节点,蚂蚁从节点集合中使用轮盘赌法选择下一个节点,在将所经过的节点存入禁忌表中;
步骤4:判断蚂蚁是否完成所有节点的遍历,若没有,则转到步骤3,反之转到步骤5;
步骤5:判断这一次迭代中所有的蚂蚁是否都完成了遍历,若没有,则将蚂蚁数量加1后返回步骤3,反之跳转到步骤6;
步骤6:完成遍历的蚂蚁根据物流配送任务调度网络模型的目标函数计算每只蚂蚁的路径,得到三项目标下的最优路径,对每个目标的最优路径使用3-opt局部优化算法,并对3-opt局部优化算法产生的7种新路径分析可行性,若可行,则根据物流配送任务调度网络模型的目标函数通过新路径重新计算路径,若更优,则替换原路径,反之使用原路径;
步骤7:根据改进混合蚁群算法的分段式的信息素挥发因子、信息素更新方式、以及迭代次数更新信息素;
步骤8:根据更新的信息素使用NSGA-Ⅲ算法对种群进行非支配排序,得到种群中的非支配解集;
步骤9:判断是否达到了初始化时设置的最大迭代次数,若没有达到,返回步骤2,反之跳转到步骤10;
步骤10:从非支配解集中选取同时优化三项目标的最优解,得到具体的运输工具配送路线。
8.根据权利要求7所述的一种基于改进混合蚁群算法的物流路径规划方法,其特征在于,对每个目标的最优路径使用3-opt局部优化算法,并对3-opt局部优化算法产生的7种新路径分析可行性,包括:删除路径中三对不相邻的配送点连接,对剩下的路径排列组合得到7种不同连接方式的路径,对比原路径与7种新路径之后选取最短的路径作为新的连接方式。
9.根据权利要求7所述的一种基于改进混合蚁群算法的物流路径规划方法,其特征在于,使用NSGA-Ⅲ算法对种群进行非支配排序,包括:通过非支配排序算法对种群规模为n′的种群进行分层,对迭代后的新种群的解集中的解进行非支配排序,第一层记为f1,其非支配序值irank为1,表示此层解不被其他所有的解所支配,是整个种群的非支配解集;之后抹除f2,对剩下的种群进行非支配排序,得到序列值irank为2的第2层非支配解f2,f2为其后一层的非支配解集,以此类推,对所有解分层,选择第一层的解为整体的非支配解集。