带装载能力的离散拆分VRP及其禁忌搜索算法

摘要

车辆路径问题(VRP)在物流配送领域有着广泛的应用价值.基于配送成本最小化,研究了带装载能力约束的需求可离散拆分VRP.文中将以往客户需求不可拆分的条件松弛为需求可拆分,且限定若拆分则只能依装载项来离散拆分,即单个装载项的需求量不可再拆.文中以车辆数最少和行驶距离最短为双目标,以单车场、单车型、路长和载重限制、需求依装载项拆分等为约束条件,建立了相应的双目标数学规划模型.设计了一种具有自适应性和多种邻域结构体的禁忌搜索算法,经算例测试对比,表明了禁忌搜索算法的有效性,也验证说明了需求离散拆分相比不拆分确实可以降低行驶成本.