□ 李 冲 □ 钱 静

江南大学 机械工程学院 江苏无锡 214122

带时间窗动态车辆路径问题 WTVRP（Vehicle RoutingOptimizationProblemwithTimeWindows）是指一定数量的工位点，各自需求不同数量的货物量，配送中心统一向工位点提供货物，通过安排一定顺序的行驶路线，使工位点在满足一定约束条件下，实现诸如路径最短、成本值最小、耗费时间最少等目标。路线安排过程中，根据工位点需求、车辆、运输网络等信息是否确定，WTVRP可以分为静态车辆路径问题SVRP（StaticVehicleRoutingOptimizationProblem）和动态车辆路径问题DVRP （DymamicVehicleRouting OptimizationProblem）［1］。 其中 DVRP 又包括了工位点需求 VRP、动态车辆 VRP和动态运输网络 VRP［2-4］。本文主要研究带时间窗的动态车辆VRP。

车辆配送过程中造成动态性主要由于两个原因：①现有车辆总载荷小于货物运输总量，为了完成配送任务，同一辆车在满足时间窗的条件下可能需要进行多次指派；②配送过程中车辆出现故障，需要重新派出车辆替换故障车辆［5］。此外，当前对蚁群算法的研究，大部分都暗含了现有车辆总载荷大于全部运输物料重量这个假设，而在实际生产中，工位配送总需求大于现有车辆载重总和的情况常会发生。考虑到运输成本，通常希望完成任务车辆数尽可能少，因此需考虑对部分车辆进行多次配送指派。

本文通过改进基本蚁群算法［6-8］，解决了对车辆进行多次派遣的问题。在算法实现中，设定先完成任务的车辆即返回原点，判断其是否满足其余还未运输路径的时间窗来判断此辆车是否接受第二次任务指派，这可以在保证时间窗的条件下使用较少的车辆数来完成任务，节省下来的车辆可以用来进行突发事件的配送或替代发生故障的车辆。……