丛扬潇，袁志高，李 素，姜缘平，王祖荣

(北京工商大学 计算机学院，北京 100048)

0 引 言

车辆路径问题[1](VRP)是典型的组合优化问题。旨在为客户安排合理的行车路线，在满足约束的前提下，得到配送方案的最优解。带时间窗车辆路径问题[2](VRPTW)是车辆路径问题的另一扩展问题。由于VRPTW模型采用精确算法对其求解的效率很低，国内外学者将重点转移到各种启发式算法上。Jacobsen-Grocott J等[3]采用遗传编程求解VRPTW。Asadi-Gangraj E等[4]提出了一种混合遗传算法求解VRPTW；马龙等[5]利用鸽群与水滴算法结合求解多目标多时间窗车辆路径问题。张瑾等[6]利用改进的蝙蝠算法求解带容量和时间窗约束的车辆路径问题。李珺等[7]利用改进的细菌觅食算法求解VRPTW。Belhaiza S等[8]提出了混合遗传变量邻域启发式搜索算法求解VRPTW。上述算法虽然在解决VRPTW方面取得了一定效果，但还有较大的提升空间。

FPA(flower pollination algorithm)是一种启发式群智能算法[9]，是受自然界中显花植物花朵授粉过程的启发而提出的，具有全局搜索能力强、选用参数少、搜索路径优及多目标问题求解能力强等特点，已成功应用于蛋白质分子对接[10]、视频跟踪[11]、车间调度[12]、机器人导航路径优化[13]和图像色彩量化[14]等方面。因此本文深入研究FPA，发现其不足之处，并用遗传算法(genetic algorithms，GA)对其改进，提出了一种改进FPA(GA-FPA)，并将其用于VRPTW求解。

1 问题描述与数学模型

VRPTW问题描述为：一组车辆从配送中心出发，根据客户的需求量和时间窗的限制制定配送路线，最终返回配送中心，使配送总成本达到最小。

带时间窗的车辆路径问题主要分为硬时间窗和软时间窗硬时间窗要求车辆必须在客户的规定时间内完成配送任务；……