有时间窗的车辆路径问题改进蚁群算法研究

《有时间窗的车辆路径问题改进蚁群算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、有时间窗的车辆路径问题改进蚁群算法研究摘要：针对目前蚁群算法在求解有时间窗的车辆路径问题上较少对蚁群算法本身进行优化的问题，提出了一种改进蚁群算法，通过改进状态转移概率和信息素更新规则，以及使用改进的精英蚂蚁策略，改善蚁群算法搜索能力。通过对Solomon标准数据集的实验，结果表明改进的蚁群算法在求解有时间窗车辆路径问题上是有效的。关键词：最大最小蚁群算法；有时间窗车辆路径问题；Solomon标准数据集中图分类号：U116.2文献标识码：AAbstract：Currentresearchonantcolonyalgorithmforvehicleroutingproblemwi

2、thtimewindows，theantcolonyalgorithmitselfislesstobeoptimized，soanimprovedantcolonyalgorithmwasestablishedtoimprovetheantcolonyalgorithmsearchcapabilitiesbyimprovingthestatetransitionprobabilityandpheromoneupdaterule，andusingimprovedeliteantstrategy.ByusingSolomonstandarddatasets，theexperimen

3、talresultsshowthattheimprovedantcolonyalgorithmforsolving8vehicleroutingproblemwithtimewindowsisvalid.Keywords：max-minantcolonyoptimization；vehicleroutingproblemwithtimewindows；Solomondataset0引言车辆路径问题（VehicleRoutingProblem，VRP）属于组合优化问题，其理论涉及到运筹学、管理学、交通运输、计算机应用等多个学科。VRP问题中加入节点可访问的时间窗约束即成为有时间窗

4、车辆路径问题（VehicleRoutingProblemwithTimeWindows，VRPTW）。由于现实生活中很多问题可以归结为VRPTW，因此VRPTW的研究受到学术界的广泛重视。VRPTW已被证明为NP-hard问题，这意味着当节点规模较大时，很难在多项式时间内得到问题的精确解，因此启发式算法因其快速高效构建可行解的优点成为人们的首选。Ombuki8Beatrice等[1]利用遗传算法、Tavakkoli-Moghaddam等[2]利用模拟退火算法来求解VRPTW问题，但二者都存在收敛速度慢的问题；张炯和郎茂祥[3]使用的禁忌算法、马炫等[4]使用的粒子群算法则容易陷

5、入局部最优解。为解决这些问题，蚁群算法的鲁棒性和构造简单使得其经常被用于与其他算法构成组合优化算法。但无论是殷志锋和张岩松[5]提出的基于进化规划和最大-最小蚁群算法相融合的混合蚁群算法，还是范小宁等[6]采用遗传算法和蚁群算法的结合，以及ZhangXiaoxia[7]将蚁群算法和禁忌搜索结合等都只是将蚁群算法作为构造可行解的方法，并大量使用局部搜索优化算法，而缺少对蚁群算法本身的改进。本文对ThomasThutzle和HolgerHoos提出的最大最小蚁群系统（MAX-MINantcolonysystem）在转移概率矩阵计算、信息素更新等关键因素上进行改进，以提高其全局优化能

6、力。为更好地说明本改进算法的优越性，在原始MMAS算法和本文算法测试Solomon标准数据集时均不使用局部优化算法。1有时间窗车辆路径问题的定义VRPTW的一般定义如下：从某一物流中心用多台配送车辆从多个客户取货，每个客户的位置和需求量和需求时间一定，每个客户只能由一台车辆服务一次，要求合理安排车辆配送路线，使目标函数得到最优，即在不违背约束条件下所用车辆数最少和行走路线长度最短。本文将最小化车辆数量作为第一目标，最小化车辆行驶路线长度作为第二目标。2最大最小蚁群算法及其在有时间窗车辆路径问题中的应用8MMAS对AS的关键改进在于将路径上的信息素浓度限定τ■，τ■之间，这较好地

7、避免了搜索陷入局部最优解。因为在搜索过程中，随着信息素的挥发和累积，某些路径上的信息素浓度会远远高于其他路径，从而导致搜索过早停滞。2.1状态转移概率。蚂蚁在选择下一个节点时，在满足容量约束和时间窗约束下，需要考虑如下三个因素：①通往下个节点的路径长度以及路径上的信息素浓度[8]。②时间窗因素的择优性[8]，由下个客户j的时间窗宽度和所在客户i到达下个客户j的时间等因素决定。这种择优性的优先原则为，需等待时间较短优先原则和时间窗较小优先原则。③基于Wissner-Gross，A.D.[9]的