多时间窗车辆路径问题的智能水滴算法

李珍萍， 赵 菲， 刘洪伟

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



多时间窗车辆路径问题的智能水滴算法

李珍萍， 赵 菲， 刘洪伟

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

研究了多时间窗车辆路径问题，考虑了车容量、多个硬时间窗限制等约束条件，以动用车辆的固定成本和车辆运行成本之和最小为目标，建立了整数线性规划模型。根据智能水滴算法的基本原理，设计了求解多时间窗车辆路径问题的快速算法，利用具体实例进行了模拟计算，并与遗传算法的计算结果进行了对比分析，结果显示，利用智能水滴算法求解多时间窗车辆路径问题，能够以很高的概率得到全局最优解，是求解多时间窗车辆路径问题的有效算法。

车辆路径问题；多时间窗；数学模型；智能水滴算法

0 引言

由Dantzig和Ramser于1959年提出的车辆路径问题(vehicle routing problem，简称VRP)[1]是组合优化中一类NP难问题。该问题自提出以来，引起了运筹学和管理科学工作者的广泛关注。车辆路径问题的扩展问题也不断得到广大学者的关注。车辆路径问题的扩展情况有：需求不确定的车辆路径问题、道路信息不确定的车辆路径问题。实际物流配送中的很多问题，如连锁经营超市的商品配送问题、连锁经营餐饮门店的原料配送问题[2]、快递企业的快件收取及配送问题等，都可以归结为经典的车辆路径问题或车辆路径问题的扩展情况，因此，该问题有着广泛的应用背景。其中，带时间窗的车辆路径问题(VRPTW)是在经典车辆路径问题(VRP)的基础上加上了时间窗限制、车容量限制等约束条件，该问题属于强NP难问题。……