基于改进蚁群算法的多时间窗车辆路径问题

朱 杰，张培斯，张询影，余微微

(北京物资学院 信息学院，北京 101149)

0 引 言

多时间窗车辆路径问题是车辆路径问题[1]的扩展，它源于现实生活中人们对服务时间的需求。例如某甲要为周边多个用户提供配送服务，假设用户乙在[8:00，10:00]和[12:00，13:00]时间段有空闲时间接受服务，用户丙在[12:00，12:30]和[16:30，17:20]时间段内有空闲时间接受服务，用户丁等也具有多个互不重叠的时间窗；这就需要甲安排合理的路线，在满足用户要求的情况下实现成本最低、路程最短或用车最少等目标。

从时间窗的数量角度划分，带时间窗的车辆路径问题可分为单时间窗问题和多时间窗问题；目前关于带时间窗的车辆路径问题研究主要集中在单时间窗[2-4]类型，而多时间窗的车辆路径问题研究文献相对较少。Belhaiza等[5]提出了变邻域禁忌搜索算法求解最小等待和延误时间的多时间窗车辆路径问题；Beheshti等[6]设计了协同进化多目标量子遗传算法求解带有优先级顺序的多时间窗车辆路径问题；Favaretto等[7]提出了允许多次访问的多时间窗车辆路径问题；马华伟等[8]设计了一种求解允许分割配送的多时间窗车辆路径问题的改进蚁群算法；黄秋爱等[9]通过引入最优个体保留机制改进传统的遗传算法，并设计数学模型进行求解，验证了算法及其模型的有效性；朱玲玲等[10]提出一种协同禁忌优化算法，通过扫描算法求得初始解，再设计自适应修改禁忌长度的算法和多个子禁忌算法进行协同优化进行求解；李珍萍等[11]运用智能水滴算法对多时间窗车辆路径问题进行了有效探索；……