基于混合遗传算法的大规模vrp问题算法研究

《基于混合遗传算法的大规模vrp问题算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于混合遗传算法的大规模VRP问题算法研宄摘要：物流配送的车辆路径问题(VRP)是近年来物流领域中的研宄热点，该问题属于NP难题，较难得到最优解和满意解。在建立了车辆路径问题数学模型的基础上，该问题被分解为两个阶段进行研宄，分别为利用基于基地启发式分区算法进行区域划分和利用改进的遗传算法来确定具体的一条配送线路的先后次序。通过此改进的混合遗传算法最终得到优化配送路径。仿真计算结果表明，在大规模车辆路径问题中改进后的算法相比于传统的遗传算法最优解的质量得到一定提高。关键词：物流配送；大规模；车辆路径；分区J法；遗传算法中图分类号：TP301文献标识码：A文章编

2、号1009-3044(2016)18-0182-03ResearchonLargeScaleVRPProblemBasedonHybridGeneticAlgorithmRANChong-shan,ZHANGYan(ShaanxiUniversityofScience&Technology,Xi^an710021,China)Abstract：Thevehicleroutingproblem(VRP)isaresearchhotspotinthelogisticsfieldinrecentyears.TheproblemisaNPproblem，anditi

3、sdifficulttoobtaintheoptimalsolutionandthesatisfactorysolution.Onthebasisofthemathematicalmodelofvehicleroutingproblem,theproblemisdecomposedintotwostageswerestudied,namelytheuseofthebaseheuristicpartitioningalgorithmforregionpartitionandtheimprovedgeneticalgorithmtodeterminetheseq

4、uenceofspecificadistributionline.Throughthisimprovedhybridgeneticalgorithmtooptimizethedistributionpath.Thesimulationresultsshowthattheimprovedalgorithmcanimprovethequalityoftheoptimalsolutioncomparedtothetraditionalgeneticalgorithminthelarge-scalevehicleroutingproblem.Keywords:log

5、isticsdistribution；large-scale；Vehiclerouting；Partitioningalgorithm；logisticsdistribution1引言随着物流产业的迅猛发展、物流配送点大规模的增加，车辆路径问题的解决方案成为了目前研宄的一个重点。解决车辆路径问题的算法很多，比较常用的有旅行商法、动态规划法、分区配送算法［1］、蚁群算法、粒子群算法、遗传算法等。新改进的混合遗传算法是在传统遗传算法的基础上采用精华模型和比例选择相结合的选择策略，构造了一种用于求解大规模车辆路径问题的混合遗传算法。在于文献［1］提出的改进遗传算法

6、进行对比后，可知此改进遗传算法具有较强的全局搜索能力和较快的收敛速度。2物流配送车辆路径优化问题的数学模型物流配送车辆路径优化问题的数学模型可以描述为：从配送中心用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，要求合理安排汽车行驶路线，使总运距最短，并满足以下条件：1）每条配送路径上各需求点的需求量之和不超过汽车载重量；2）每条配送路径的长度不超过汽车一次配送的最大行驶距离；3）每个需求点的需求必须满足，且只能由一辆汽车送货。设配送中心拥有K台容量为q的车辆，i个客户的需求量为g，且gi

7、为0,配送中心和客户用i（i=0,1,...，i）表示，且有Bramel和Simchi-Levi提出了基于基地启发式分区算法［2］，本文借助其算法思想，将它分解成一个分派问题（P1）和一个单车线路优化问题（P2）。P1：且满足如下约束条件：P1中，zk表示车辆k所能服务的客户集合，满即足yki=l的客户集合，f（zk）表示在zk中满足约束条件的客户最优旅行线路的长度，由p2确定。且满足如下约束条件：前两个等式描述了两个变量之间的关系，对于客户i，只有两个客户与i相连；第三个等式消除了子回环，表示没有任何子回路解产生。3算法原理及改进3.1算法原理针对大规模车

8、辆问题，本文首先用基于基地启发式分区算法进行区域划分