动态物流中多源多点最佳路径算法研究
|
摘要
多源多点环境下,动态物流中涉及货物装载和产品配送的路径优化是一个非常复杂的问题.针对现实配送过程中存在的货物需求多样化以及多车配送空载率过高的路径寻优问题,本文提出了一种新的调度配送方式.通过建立车辆装载配送路径模型,以多源多点,重量修正,路径最佳等为约束条件,使用模拟细胞分裂的新方式产生下一代,改进现有的遗传算法进行求解,优化了初始种群的产生,可以快速得到全局最优解,跳出遗传早熟收敛,取得最佳路径,从而降低配送成本,提高配送效率.
In the multi-source and multi-point environment, the path optimization involving dynamic loading and product distribution in dynamic logistics is a very complicated problem. Aiming at the diversification of goods demand in the actual distribution process and the path optimization problem of multi-vehicle delivery and high idling rate, this study proposes a new scheduling and distribution method. By establishing a vehicle loading and distribution path model, using the multi-source point multi-destination, weight correction, path optimization, etc. as constraints, a new way of simulating cell division is used to generate the next generation and improved the existing genetic algorithm to solve the problem.This method optimizes the generation of the initial population can quickly obtain the global optimal solution, jump out of the genetic premature convergence, get the best path, reduce the distribution cost and improve the distribution efficiency.
In the multi-source and multi-point environment, the path optimization involving dynamic loading and product distribution in dynamic logistics is a very complicated problem. Aiming at the diversification of goods demand in the actual distribution process and the path optimization problem of multi-vehicle delivery and high idling rate, this study proposes a new scheduling and distribution method. By establishing a vehicle loading and distribution path model, using the multi-source point multi-destination, weight correction, path optimization, etc. as constraints, a new way of simulating cell division is used to generate the next generation and improved the existing genetic algorithm to solve the problem.This method optimizes the generation of the initial population can quickly obtain the global optimal solution, jump out of the genetic premature convergence, get the best path, reduce the distribution cost and improve the distribution efficiency.
引文
1焦李成,刘静,钟伟才.协同进化计算与多智能体系统.北京:科学出版社,2006.
2王小平,曹立明.遗传算法--理论,应用与软件实现.西安:西安交通大学出版社,1998.
3孙刘诚,孙焰.带订单选择车辆路径问题的模型与算法.交通运输系统工程与信息,2018,18(2):194-200.
4涂伟,李清泉,方志祥.基于网络Voronoi图的大规模多仓库物流配送路径优化.测绘学报,2014,43(10):1075-1082.
5 Zhao ZY,Zhan YR.A cost analysis method on location planning for logistics distribution network system Proceedings of the 16th International Conference on Industrial Engineering and Engineering Management Beijing,China.2009.395-399.
6丁蓓,魏振春,孙仁浩.基于遗传算法的最小成本配送策略研究.合肥工业大学学报(自然科学版),2018,41(2):273-278.[doi:10.3969/j.issn.1003-5060.2018.02.025]
7范文兵,冯文.混合遗传算法的带时间窗卷烟物流车辆路径优化.现代电子技术,2018,41(11):119-123,128.
8 Nazif H,Lee LS.Optimised crossover genetic algorithm for capacitated vehicle routing problem.Applied Mathematical Modelling,2012,36(5):2110-2117.[doi:10.1016/j.apm2011.08.010]
9袁麟博,章卫国,李广文.一种基于遗传算法-模式搜索法的无人机路径规划.弹箭与制导学报,2009,29(3):279-282.[doi:10.3969/j.issn.1673-9728.2009.03.082]
10邝航宇,金晶,苏勇.自适应遗传算法交叉变异算子的改进.计算机工程与应用,2006,42(12):93-96,99.[doi:10.3321/j.issn:1002-8331.2006.12.028]
11卢月品,赵阳,孟跃强,等.基于改进遗传算法的狭窄空间路径规划.计算机应用研究,2015,32(2):413-418.[doi:10.3969/j.issn.1001-3695.2015.02.021]
12雷伟军,程筱胜,戴宁,等.基于改进遗传算法的多模型加工路径规划.机械工程学报,2014,50(11):153-161.
13庄健,杨清宇,杜海峰,等.一种高效的复杂系统遗传算法软件学报,2010,21(11):2790-2801.
14王振锋,王旭,葛显龙.基于遗传算法的不同约束条件车辆调度问题研究.计算机应用研究,2010,27(10):3673-3675.
15 Montemanni R,Gambardella LM,Rizzoli AE,et al.Ant colony system for a dynamic vehicle routing problem Journal of Combinatorial Optimization,2005,10(4):327-343.[doi:10.1007/s10878-005-4922-6]
2王小平,曹立明.遗传算法--理论,应用与软件实现.西安:西安交通大学出版社,1998.
3孙刘诚,孙焰.带订单选择车辆路径问题的模型与算法.交通运输系统工程与信息,2018,18(2):194-200.
4涂伟,李清泉,方志祥.基于网络Voronoi图的大规模多仓库物流配送路径优化.测绘学报,2014,43(10):1075-1082.
5 Zhao ZY,Zhan YR.A cost analysis method on location planning for logistics distribution network system Proceedings of the 16th International Conference on Industrial Engineering and Engineering Management Beijing,China.2009.395-399.
6丁蓓,魏振春,孙仁浩.基于遗传算法的最小成本配送策略研究.合肥工业大学学报(自然科学版),2018,41(2):273-278.[doi:10.3969/j.issn.1003-5060.2018.02.025]
7范文兵,冯文.混合遗传算法的带时间窗卷烟物流车辆路径优化.现代电子技术,2018,41(11):119-123,128.
8 Nazif H,Lee LS.Optimised crossover genetic algorithm for capacitated vehicle routing problem.Applied Mathematical Modelling,2012,36(5):2110-2117.[doi:10.1016/j.apm2011.08.010]
9袁麟博,章卫国,李广文.一种基于遗传算法-模式搜索法的无人机路径规划.弹箭与制导学报,2009,29(3):279-282.[doi:10.3969/j.issn.1673-9728.2009.03.082]
10邝航宇,金晶,苏勇.自适应遗传算法交叉变异算子的改进.计算机工程与应用,2006,42(12):93-96,99.[doi:10.3321/j.issn:1002-8331.2006.12.028]
11卢月品,赵阳,孟跃强,等.基于改进遗传算法的狭窄空间路径规划.计算机应用研究,2015,32(2):413-418.[doi:10.3969/j.issn.1001-3695.2015.02.021]
12雷伟军,程筱胜,戴宁,等.基于改进遗传算法的多模型加工路径规划.机械工程学报,2014,50(11):153-161.
13庄健,杨清宇,杜海峰,等.一种高效的复杂系统遗传算法软件学报,2010,21(11):2790-2801.
14王振锋,王旭,葛显龙.基于遗传算法的不同约束条件车辆调度问题研究.计算机应用研究,2010,27(10):3673-3675.
15 Montemanni R,Gambardella LM,Rizzoli AE,et al.Ant colony system for a dynamic vehicle routing problem Journal of Combinatorial Optimization,2005,10(4):327-343.[doi:10.1007/s10878-005-4922-6]