《改进蚁群算法在车辆路径问题中的应用.doc》由会员分享，可在线阅读，更多相关《改进蚁群算法在车辆路径问题中的应用.doc（1页珍藏版）》请在三一文库上搜索。
1、广西民族大学学报(自然科学版)第 16 卷第 2 期JOURNAL OF GUANGXI UNIVERSITY FOR NATIONALITIESVol 16 No. 22010 年 5 月(NAtural Science Edition)May 2010改进蚁群算法在车辆路径问题中的应用.刘桂青(广西民族大学数学与计算机科学学院，广西南宁530006)5050计 算 机 技 术摘 要：从蚁那算法在求解实际问题时收敛速度慢、易陪入局部聂优的缺陷出发，对蚁郵系疑转務规则. 局部仕息素更新方而进行改进并将其应用到DCVRP问题中求解时引入候选列表和2-opt 局部搜索策略，以减少计算时间并达到亨先
2、淘汰不良珞径的目的通过与其他元启发式方法比 较实脸结果表明本文改进蚁那算法其结果明显优于另外四种主要的路径问题启发式方法.关键词：改进蚁郵算法；车鋼珞径问题;2-opt法局部搜索中图分类号：TP311文献标识码：A 文章编号：1673-8462(2010)02-0050-040 引言蚁群算法(Ant Colony Optimization, ACO) 发展至今约十多年时间，已成功地应用到许多问题当 中，如旅行商问题(TSP、调度问题(Scheduling).车 辆路径问题等取得了良好的效果.然而作为蚁群算 法的典型代表蚁群系统在求解实际问题时表现出收本文所指的车辆路径问题DCVRP(The V
3、ehicle Routing Problem under Capacity and Distance Con straints)，是指以单一配送中心(Single Depot)为中 心，以最小总行车路径距离为目标，在同时满足配送 车辆负载与行驶距离限制的条件下，来满足所有顾客 的需求问题.50敛速度慢、易陷入局部最优并导致停滞现象特点在 VRP问题上，目前以禁止搜寻法、蚊群算法、模拟退 火法、遗传算法为主，表现亦较其它启发式方法优异， 若同时考虑到车辆容量与行车路线长度的限制，对于 此类车辆路径问题截至目前为止，以OsmanW TS2 方法的应用最为突出，其相关的文献也相当丰富. AC()方法
4、虽然在VRP问题应用上的研究较为缺乏， 但其相关的综述文献的数量却仅次于TS,显示ACO 在解决VRP问题上具有相当的潜力.本文针对蚁群 系统的不足，从算法本身的性能岀发进行改进，采用 新的改进蚁群算法来求解有容量和距离限制的车辆 路径问题.1 DCVRP参数定义及数学模型站点i到站点j之成本.©：站点i到站点j之距离. 务：站点F的服务时间.G：车辆&的容量限制.尸：车辆&最大行驶路径长度限制.站点j的需求量.N：总顾客数.K：总车辆数.4 =卩，车辆怡经过站点和j% = |0,否则5050收積日期：2010-02-10,基金项目：广西民族大学研究生创新计划項目(gxun chx2009090>.作者简介：刘桂青(1979-),男，广西民族大学数学与计算机科学学院讲师，碩士研究生，研究方向：智能算法及其应用.50