188宝金博页面版

第 35 卷第 4 期 中南民族大学学报(自然科学版) Vol． 35 No．42016 年 12 月Journal of South-Central University for Nationalities(Nat． Sci． Edition) Dec．2016收稿日期 2016-06-10 * 通讯作者 武孟贤，研究方向:计算机网络控制、人工智能，E-mail:724996875@ qq． com作者简介 林 涛(1970-)，男，教授，博士，研究方向:计算机网络控制理论、网络管理与安全、嵌入式系统及网络控制，E-mail:lintao@ scse． hebut． edu． cn基金项目 天津市科技支撑项目(14ZCDZGX00818)基于捕食搜索策略混合遗传算法的车辆路径问题研究林 涛1，2 ，武孟贤 1，*，轩倩倩1 ，徐庆国 1，江冲1(1 河北工业大学 控制科学与工程学院，天津 300130;2 河北工业大学 计算机科学与软件学院，天津 300401)摘 要 在分析研究车辆路径问题的基础上，将其转换为经典 TSP 优化问题进行求解并建立数学模型，针对遗传算法在求解车辆路径问题时搜索效率低，容易陷入局部最优的缺点，提出了一种改进的遗传算法． 改进算法引用自适应邻域法进行种群初始化;基于捕食搜索策略动态自适应调整遗传参数，在加快寻优速度的同时防止陷入局部最优;交叉前后的种群分别实施精英个体保留策略，交叉变异之后引进进化逆转操作，继承父代较优和较多的信息． 实验结果表明:改进遗传算法搜索效率高、计算结果较为稳定;求解车辆路径最优问题较其它算法具有较好的性能．关键词 车辆路径问题;遗传算法;自适应邻域法;捕食搜索算法中图分类号 TP399 文献标识码 A 文章编号 1672-4321(2016)04-0106-05Hybrid Genetic Algorithm Based on Predatory SearchStrategy for Vehicle Ｒouting ProblemLin Tao 1，2 ，Wu Mengxian 1 ，Xuan Qianqian 1 ，Xu Qingguo 1 ，Jiang Chong 1(1 Institute of Control Science and Engineering，Hebei University of Technology，Tianjin 300130，China;2 Institute of Computer Science and Software，Hebei University of Technology，Tianjin 300401，China)Abstract On the basis of the analysis of the vehicle routing problem，it is transformed into the classical TSP optimizationproblem to solve and build a mathematical model． Standard genetic algorithm in solving the vehicle routing problem (VＲP)is not efficient since it is easy to fall local optimum． To improve the efficiency of genetic algorithm，this paper presents animproved genetic algorithm． The proposed algorithm introduces the adaptive neighborhood method into populationinitialization． In order to improve the optimization speed and prevent the local optimum，the improved algorithm dynamicadaptive adjustment of genetic parameters based on predatory search strategy． Elite individual retention strategy isintroduced to genetic operation and evolutionary reversal operation is used after crossover and mutation operation topropagate the better and more gene structure． The experimental results show that the improved genetic algorithm has highsearch efficiency and stable calculation results，and it has better performance than other algorithms in case of solving thevehicle routing problem．Keywords vehicle routing problem;genetic algorithm;adaptive neighborhood method ;predatory search algorithm作为物流运输配送系统的核心问题，车辆路径问题(VＲP)主要研究车辆从配送中心到各客户点配送最后返回配送中心的满足约束条件的最优车辆使用方案以及最优车辆路线方案 ［1］ ． 该问题是一个典型的 NP-hard(NP 难)问题，自提出以来一直受到众多专家和学者的关注，在理论研究和现实应用上均取得了丰硕的研究成果． 神经网络、模拟退火、遗传算法、蚁群算法、粒子群算法等智能算法都已实现了对该 NP 难题的求解［2］ ．近年来，随着我国电子商务行业的高速发展，使得物流配送业务大量增加，企业的配送车辆数目迅猛增多． 不合理的配送路线不仅增加了企业的配送成本，同时还影响了城市的交通和环境 ［3］ ． 求解最优路径时许多算法的搜索效率和解的质量不高，所