混合蚁群算法求解带时间窗的车辆路径问题.pdf

《混合蚁群算法求解带时间窗的车辆路径问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、·混合蚁群算法求解带时间窗的车辆路径问题·文章编号：10O2-4581(2015)03—0006—06混合蚁群算法求解带时间窗的车辆路径问题王建，李红云，杨燕飞WangJian，LiHongyun，YangYanfei(北京航空航天大学交通科学与工程学院，北京100191)摘要：采用营运车辆的最短行驶距离作为带时间窗车辆路径问题的优化目标，在混合蚁群算法中采用信息素3层更新策略以完成对车辆的调度，信息素挥发自适应策略充分考虑实时路况，考虑信息素空间扩散特性的局部更新策略，更加忠实于自然界的真实蚂蚁系统，可以提高算法的收敛速度，采用阈值判断的全局信息素更新策

2、略可以防止算法陷入局部最优。通过cjfj}语言实现了混合蚁群算法的计算机求解，最后对10个仿真实例进行仿真计算，结果表明，混合蚁群算法收敛快，寻优结果稳定。关键词：车辆路径；时间窗；信息素更新策略；蚁群算法中图分类号：U491．2l：TP391．9文献标志码：ADOI：10．14175~．issn．1002．4581．2015．03．002车辆路径问题(VehicleRoutingProblem，善蚁群算法的全局收敛性，并拓宽蚁群算法的应VRP)是营运车辆研究领域中一个具有重要理论用领域。和现实意义的问题L1J。由于该问题属于NP—hard文中对蚁群算法的

3、分布和协作机制进行了深(Non—deterministicPolynomialHard，非确定性多项入研究，在分析已有蚁群系统的优缺点的基础上式难题)，所以寻找到一种高效而精确的算法的可提出了基于实时路况的3层信息素更新策略，提能性微乎其微，而自然界中生物群体的合作与竞出了考虑时间窗约束的基于多种蚁群系统的混合争等复杂行为产生的群体智能往往对解决某些特蚁群算法(MixedAntColonyAlgorithm，MACO)，定的随机寻优问题提供了高效的解决方法，因此在算法中充分考虑实时路况更新对道路通行能力人们开始尝试利用仿生智能算法求解。的影响，以增强蚁群算

4、法在求解动态车辆路径问蚁群算法模型来源于对自然界真实蚂蚁行为题的算法性能。的观测，蚁群在解决优化以及分布控制问题上具有很高的智能性，因此蚁群算法对解决复杂寻优1车辆路径问题描述问题的新型算法的开发与应用具有重要的启发价值。蚁群算法随机寻优机制的核心内容是分布性营运车辆的调度问题属于车辆路径问题，但和协作性，而营运车辆具有同蚁群相似的分布性在普通的车辆路径问题上增加了一些约束，主要与协作性。目前采用蚁群算法求解车辆路径问题体现在以下3个方面：已经取得了很多的研究成果[2-4]。但是蚁群算法也1)营运车辆的调度不只是单纯地考虑最短路存在着前期收敛速度慢，容易陷

5、入局部最优等缺径，同时考虑车辆运行过程中所经路径等级、运点。国内外学者针对蚁群算法存在的缺点进行一行时间等问题，最终达到降低整体成本的目的；系列的改进，包括Max—Min蚂蚁系统，精英蚂蚁2)营运车辆作为一种商业化的信息沟通形系统，基于排序的蚂蚁系统，基于混沌理论的蚂式，要充分考虑以人为本，要注重企业形象、提蚁系统等【5]，这些改进有一个共同的目的，就是高顾客满意度；在合理时间复杂度的限制条件下，尽可能提高蚁3)营运车辆数目有限，载货量一定并且客户群算法在一定空间复杂度下的寻优能力，从而改的订单具有时间要求。·混合蚁群算法求解带时间窗的车辆路径问题·营运车

6、辆领域的车辆路径问题可以简单描述从蚁巢和食物源之间出发，路径AB的长度等于路为：每个厂商都有一个仓库和一批客户集合，仓径BC的长度，并且均为路径AD以及DC的2倍。库即是配送中心，拥有辆可用于调度的运输车此时路径ABC与路径ADC上的信息素浓度均为辆，车辆的最大载重量、最大行驶距离和车况已，蚂蚁选择路径的概率严格与信息素浓度成线知，每个客户的位置信息、需求信息已知，车辆性比例关系，因此分别有p／2只蚂蚁选择ABC与都由仓库出发，经过若干客户点之后返回仓库，ADC。当到达什时刻时，DC路径上的蚂蚁已形成一个子回路，假如若干车辆构成的子回路集经从出发地到达目的

7、地，然而由于路径较长，AB合可以完成对客户点的不重复遍历，那么就构成路径和BC路径上的蚂蚁在点相遇，此时路径车辆路径问题的一个可行解。通过一定的算法以ADC的信息素浓度为及约束条件寻找可行解，并从可行解的集合中发TADc+n)=f(f)一f()+P·f()(1)掘满足总行程最短或者总体成本最低的可行解就是营运车辆领域的车辆路径问题。而此时路径ABC上的信息素浓度为鉴于营运车辆调度问题与普通的车辆路径问c-I-)=(f)一f()+·()(2)题存在以上不同，同时我国“十二五”提出到2015年构建完善的营运车辆车联网系统，以完成对路式中，zip)表示挥发掉的信

8、息素数量，，．c)表况信息的实时更新，因此有必要对蚁群算法做出示每