摘要：设计了一种引入局部近邻机制并且能够优化不可行解的粒子群算法。该算法将粒子群分成相互重叠的子群，在各个子群内寻找近邻，提高了粒子的学习功能和寻找近邻的速度；同时将产生的不可行解进行局部优化，增强了粒子寻找最优的能力。试验结果表明该算法可以快速求得带时间窗车辆路径问题的满意解。

关键字：局部近邻；粒子群算法；车辆路径问题

1 引言

由Dantzig和Ramser^[1]于1959年首次提出的车辆路径问题(Vehicle Routing Problem, VRP)，是一个NP-hard组合优化问题^[2]。它是指对一系列发货(或收货)点，组成适当的行车路径，使车辆有序地通过它们，在满足一定约束条件（如货物需求量、发送量、交发货时间、车辆容量限制等）的情况下，达到一定的目标(如路径最短、费用最小、耗费时间尽量少等)^[3]。

带时间窗的车辆路径问题^[3](Vehicle Routing ProblemWith Time Windows，VRPTW )是在VRP的基础上增加了客户要求访问的时间窗口。在现实生活中许多问题都可以归结为VRPTW (如邮政投递、火车及公共汽车的调度等)，它是衡量企业服务质量标准之一，所以对它的研究越来越受到人们的重视。VRPTW也是NP-hard问题^[4]，先后出现了一般启发式算法和神经网络、遗传算法等智能化启发式算法，均取得了一些较好的效果。