陈 磊

（兰州交通大学 交通运输学院，甘肃 兰州730070）

车 辆 路 径 问 题 （Vehicle Routing Problem，VRP）已被证明是NP难题，带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows，VRPTW）由于增加了时间约束，使得问题在求解中变得更加复杂，VRP为组合优化问题，本文选用的配送车辆为多车型，这使得问题的解呈几何型增长，当配送点的数目增大时，采用精确算法很难求得问题的精确解。因此用启发式算法在一定的时间内求得问题的满意解已成为研究的主要方向。

Dorigo等人首先提出了蚁群算法，它是一种新的种群启发式算法，利用一群人工蚂蚁的协同工作来进行寻优，每只蚂蚁都遵循一定的规则随机选择下一个节点，并在到达下一节点后释放一定量的信息素，从而对下一只蚂蚁起到引导作用，最后蚂蚁将会倾向于选择路程最短的路径。其具有很强的鲁棒性，是解决组合优化问题的有效手段，该思想已被应用到各个研究领域，并取得了大量的研究成果，而在VRPTW方面的研究则较少，本文在蚁群系统的基础上，将蚂蚁周期算法与最大最小蚂蚁系统（MMAS）相结合，在寻找最优解的过程中采用信息素动态挥发策略；在对下一个客户的选择中，考虑了时间窗跨度及服务等待时间等因素，使问题的解更接近实际情况；通过转移状态规则求得可行节点的概率后，为避免算法陷入局部最优，采用轮盘选择来确定下一点；在求得问题可行解后，为了在不丢失最优解的情况下，更快地产生最优解，采用路径内的2－opt及路径间的2－opt＊优化策略。……