loading有时间窗的车辆路径问题改进蚁群算法研究
董 攀，陈 阳（长沙理工大学 经济与管理学院，湖南 长沙 401114）
【摘 要】针对目前蚁群算法在求解有时间窗的车辆路径问题上较少对蚁群算法本身进行优化的问题，提出了一种改进蚁群算法，通过改进状态转移概率和信息素更新规则，以及使用改进的精英蚂蚁策略，改善蚁群算法搜索能力。通过对Solomon标准数据集的实验，结果表明改进的蚁群算法在求解有时间窗车辆路径问题上是有效的。【期刊名称】物流科技【年(卷),期】2014(037)007【总页数】4
【关键词】最大最小蚁群算法；有时间窗车辆路径问题；Solomon标准数据集
0 引言
车辆路径问题（Vehicle Routing Problem,VRP）属于组合优化问题，其理论涉及到运筹学、管理学、交通运输、计算机应用等多个学科。VRP问题中加入节点可访问的时间窗约束即成为有时间窗车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）。由于现实生活中很多问题可以归结为VRPTW，因此VRPTW的研究受到学术界的广泛重视。
VRPTW已被证明为NP-hard问题，这意味着当节点规模较大时，很难在多项式时间内得到问题的精确解，因此启发式算法因其快速高效构建可行解的优点成为人们的首选。Ombuki Beatrice等[1]利用遗传算法、Tavakkoli-Moghaddam等[2]利用模拟退火算法来求解VRPTW问题，但二者都存在收敛速度慢的问题；张炯和郎茂祥[3]使用的禁忌算法、马炫等[4]使用的粒子群算法则容易陷入局部最优解。为解决这些问题，蚁群算法的鲁棒性和构造简单使得其经常被用于与其他算法构成组合优化算法。但无论是殷志锋和张岩松[5]提出的基于进化规划和最大-最小蚁群算法相融合的混合蚁群算法，还是范小宁等[6]采用遗传算法和蚁群算法的结合，以及Zhang Xiaoxia[7]将蚁群算法和禁忌搜索结合等都只是将蚁群算法作为构造可行解的方法，并大量使用局部搜索优化算法，而缺少对蚁群算法本身的改进。
本文对Thomas Thutzle和Holger Hoos提出的最大最小蚁群系统（MAX-MIN ant colony system）在转移概率矩阵计算、信息素更新等关键因素上进行改进，以提高其全局优化能力。为更好地说明本改进算法的优越性，在原始MMAS算法和本文算法测试Solomon标准数据集时均不使用局部优化算法。
1 有时间窗车辆路径问题的定义
VRPTW的一般定义如下：从某一物流中心用多台配送车辆从多个客户取货，每个客户的位置和需求