欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2020111863607
申请人: 重庆理工大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-01-05
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于遗传-模拟退火组合算法对物流配送的优化方法,其特征在于,包括:

步骤1,获取个体客户与配送中心的坐标数据,并对所述坐标数据进行编码,得到初始种群;

步骤2,建立数学模型,所述数学模型的目标函数Zi为:

其中,上述公式中的字符O表示配送中心,n表示客户数量,m表示车辆数,Dk第k辆车的最大载重量,DMk表示第k辆车的最大行驶里程,veh表示实际使用车辆数,cij表示客户i到客户j之间行驶距离的单位成本,qi表示每个客户对货物的需求量,dij表示客户i与客户j之间的距离,ei表示客户i要求达到的最早服务时间,li表示客户i要求达到的最晚服务时间,ti表示车辆到达客户i的时间,α表示超载惩罚系数,β表示超距惩罚系数,λ表示违反时间窗惩罚系数,cv表示超载量,dv表示超距量,tv表示违反的时间窗约束之和;

上述公式(1.1)表示目标函数、公式(1.2)-(1.3)表示第k辆车从一个点行驶到另一个店的车辆约束条件、公式(1.4)-(1.6)表示每个个体客户仅能被一辆车服务、公式(1.7)表示每辆车载货量不超过车辆的最大载重量、公式(1.8)表示每辆车行驶距离不超过车辆的最大行驶里程、公式(1.9)表示车辆从配送中心出发最终回到配送中心形成一条回路、公式(1.10)表示违反时间窗约束之和;

步骤3,通过设置所述目标函数Zi为每个个体客户的总距离,同时计算所述目标函数Zi的倒数,得到适应度函数f(xi),并基于所述适应度函数的数值判断解决方案的质量,所述适应度函数f(xi)的表达式为:其中,xi表示第i个个体客户与配送中心O的排列数组。

步骤4,基于所述适应度函数f(xi),通过遗传算法中的选择、PMX匹配交叉以及变异的处理方式,打乱所述初始种群的路径序列,使得种群多样化,同时产生一个新种群;

步骤5,对所述新种群是否达到迭代次数进行判断,若达到所述迭代次数,则输出新种群的最优解,否则,重新计算初始种群的适应度;

步骤6,从所述最优解中获取两个数值x1与x2,作为模拟退火算法的初始解代入所述目标函数,得到目标函数结果值f(x1)与f(x2);

步骤7,重新通过遗传算法中变异的处理方式产生新解,并从所述新解中获取两个数值xnew1与xnew2,作为模拟退火算法的新解代入所述目标函数,得到目标函数结果值f(xnew1)与f(xnew2);

步骤8,将所述步骤7中的目标函数结果值减去所述步骤6中的目标函数结果值,得到:

△f1=f(xnew1)-f(x1),△f2=f(xnew2)-f(x2),同时对△f1与△f2进行判断,若△f1≤0或△f2≤0,则接受所述步骤7中的新解,即xnew1=x1,f(xnew1)=f(x1)或xnew2=x2,f(xnew2)=f(x2),否则根据Metropolis准则接受新解;

步骤9,基于所述步骤8中任意一种新解,首先对新解是否达到内部迭代次数进行判断,若未达到所述内部迭代次数,则回到步骤7中重新获取新解,若达到所述内部迭代次数,则继续判断是否达到外部迭代次数进行判断,若未达到所述外部迭代次数,则通过缓慢降低温度重置内部迭代次数,回到步骤7中重新获取新解,若达到所述外部迭代次数,则运行结束。

2.根据权利要求1所述的基于遗传-模拟退火组合算法对物流配送的优化方法,其特征在于,所述遗传算法中选择的处理方式是通过所述步骤3中的适应度函数,计算每个个体客户被选中的权值,并以轮盘赌的形式选择个体客户,每个个体客户被选中的权值P(xi)的表达式为:其中,f(xi)表示是个体客户xi的适应度函数值。

3.根据权利要求2所述的基于遗传-模拟退火组合算法对物流配送的优化方法,其特征在于,所述遗传算法中PMX匹配交叉的处理方式是通过轮盘赌的形式随机挑选两组初始种群中的个体客户坐标数据,然后将被挑选的两组个体客户坐标数据的位置进行交换,并根据交换的个体客户坐标数据建立映射关系,对初始种群进行排序。

4.根据权利要求3所述的基于遗传-模拟退火组合算法对物流配送的优化方法,其特征在于,所述遗传算法的变异处理方式是通过随机合并初始种群的路径序列的奇数位置与偶数位置,增加种群的多样化,用于提高遗传算法局部随机搜索的能力。

5.根据权利要求1所述的基于遗传-模拟退火组合算法对物流配送的优化方法,其特征在于,基于所述Metropolis准则,当粒子温度在温度T时,趋于平衡的概率用exp(-ΔE/(k'T))来表示,其中,E表示粒子在温度T时的内能,△E表示内能的改变量,k'表示Boltzman常数,Metropolis准则可表示为: