刘巍巍， 孙宇彤， 安小宇， 高鑫禹， 孙晨曦

(1. 沈阳工业大学 机械工程学院， 沈阳 110870； 2. 郑州轻工业大学 电气信息工程学院， 郑州 450002)

车辆路径问题(vehicle routing problem，VRP)是Dantzing和Razmer在1959年提出的一个典型NP难问题[1]，一般通过启发式算法和精确算法来进行求解.启发式算法具有效率高、求解精度高的特点，相比之下，精确算法效率较低且通常只有在问题规模较小时才能获得精确解.现如今，学者们的研究重点主要放在启发式算法上，包括蚁群算法、遗传算法、人工神经网络算法、粒子群算法、模拟退火算法等.蚁群算法具有在解决车辆路径问题方面较强的全局搜索能力和较大的算法改进弹性优势，但传统蚁群系统(ant colony system，ACS)算法在寻优过程中存在过早收敛、容易陷入局部最优，且收敛到全局最优要花费较长时间等缺点[2].因此，探寻一种改进的ACS算法，使其能够同时提高VRP问题的求解速度和求解质量具有重要意义.

近年来，国内外许多专家学者提出了不同的改进方案以使蚁群算法更适配于VRP问题.Kao等[3]针对蚁群算法求解VRP时信息素停滞问题，混合蚁群算法和粒子群算法在蚁群算法中嵌入了信息素干扰的方法，提高了算法准确性，但容易过早收敛；Huang等[4]为了避免蚁群算法陷入局部最优，使用角运动改进蚁群算法应用于应急服务救援车辆的路径规划，并进一步使用经典ACS的转移概率选择规则的路径权重矩阵，以提高路径搜索的准确性，但该算法较为复杂且导致计算耗时较长；胡立栓……