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

基于混合遗传算法的大规模VRP问题算法研究 　　摘要：物流配送的车辆路径问题（VRP）是近年来物流领域中的研究热点，该问题属于NP难题，较难得到最优解和满意解。在建立了车辆路径问题数学模型的基础上，该问题被分解为两个阶段进行研究，分别为利用基于基地启发式分区算法进行区域划分和利用改进的遗传算法来确定具体的一条配送线路的先后次序。通过此改进的混合遗传算法最终得到优化配送路径。仿真计算结果表明，在大规模车辆路径问题中改进后的算法相比于传统的遗传算法最优解的质量得到一定提高。 　　关键词： 物流配送；大规模；车辆路径；分区算法； 遗传算法 　　中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）18-0182-03 　　Research on Large Scale VRP Problem Based on Hybrid Genetic Algorithm 　　RAN Chong-shan，ZHANG Yan 　　（Shaanxi University of Science Technology， Xi’an 710021， China） 　　Abstract：The vehicle routing problem （VRP） is a research hotspot in the logistics field in recent years. The problem is a NP problem， and it is difficult to obtain the optimal solution and the satisfactory solution. On the basis of the mathematical model of vehicle routing problem， the problem is decomposed into two stages were studied， namely the use of the base heuristic partitioning algorithm for region partition and the improved genetic algorithm to determine the sequence of specific a distribution line. Through this improved hybrid genetic algorithm to optimize the distribution path. The simulation results show that the improved algorithm can improve the quality of the optimal solution compared to the traditional genetic algorithm in the large-scale vehicle routing problem. 　　Key words：logistics distribution； large-scale； Vehicle routing； Partitioning algorithm； logistics distribution 　　1 引言 　　随着物流产业的迅猛发展、物流配送点大规模的增加，车辆路径问题的解决方案成为了目前研究的一个重点。解决车辆路径问题的算法很多，比较常用的有旅行商法、动态规划法、分区配送算法[1]、蚁群算法、粒子群算法、遗传算法等。新改进的混合遗传算法是在传统遗传算法的基础上采用精华模型和比例选择相结合的选择策略，构造了一种用于求解大规模车辆路径问题的混合遗传算法。在于文献[1]提出的改进遗传算法进行对比后，可知此改进遗传算法具有较强的全局有哪些信誉好的足球投注网站能力和较快的收敛速度。 　　2 物流配送车辆路径优化问题的数学模型 　　物流配送车辆路径优化问题的数学模型可以描述为：从配送中心用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，要求合理安排汽车行驶路线，使总运距最短，并满足以下条件： 　　1）每条配送路径上各需求点的需求量之和不超过汽车载重量； 　　2）每条配送路径的长度不超过汽车一次配送的最大行驶距离； 　　3）每个需求点的需求必须满足，且只能由一辆汽车送货。 　　设配送中心拥有K台容量为q的车辆，i个客户的需求量为g，且gi≤q，i=1，2，…，i，将配送中心编号为0，配送中心和客户用i（i=0，1，...，i）表示，且有 　　Bramel和Simchi-Levi提出了基于基地启发式分区算法[2]，本文借助其算法思想，将它分解成一