两阶段启发式算法求解带时间窗的多中心车辆路径问题

车辆路径问题(VRP)是物流研究领域中一个具有重要理论价值和现实意义的问题. 带时间窗的多中心车辆路径优化问题(MDVRPTW)是单中心带时间窗的VRP(VRPTW)的一个扩展, 其非常复杂, 难于求解. 本文提出一个两阶段的启发式算法来求解MDVRPTW. 该算法首先通过基于聚集度的启发式分类算法将MDVRPTW简化为多个VRPTW; 然后采用蚁群算法对每个VRPTW进行求解. 为了提高蚁群算法的效率, 提出了两个改进策略: 交叉算子和自适应的ant-weight信息素增量更新策略. 最后, 通过若干经典的MDVRPTW对该算法进行了验证, 结果显示结合基于聚集度的启发式分类算法和改进的蚁群算法是一个求解MDVRPTW的有力工具.

Two-stage heuristic algorithm for multi-depot vehicle routing problem with time windows

Vehicle routing problem(VRP) plays a vital role in logistics research.The multi-depot vehicle routing problem with time windows(MDVRPTW),an extension of VRP with time windows(VRPTW), is very complicated to be solved.This paper presented a two-stage heuristic to solve MDVRPTW.In the two-stage heuristic,aggregation-based clustering algorithm was firstly proposed to transfer MDVRPTW to several VRPTWs,and ant colony optimization(ACO) was developed to optimize each VRPTW.Two improvement strategies:crossover operation and adaptive ant-weight strategy,are designed to improve ACO.The performance of the two-stage heuristic was examined by use of some classic instances.Results show that the two-stage heuristic is a powerful tool for MDVRPTW.