基于多重启动迭代扫描的需求可拆分车辆路径问题

需求可拆分车辆路径问题放松了经典车辆路径问题中对每个客户只访问一次的约束。针对这一问题,提出了一种基于改进扫描算法的两阶段方法。通过多重启动迭代扫描把客户点按照车辆负载分成最少数量的组,每组的负荷需求和分裂点由负荷率和阈值系数进行微调。采用禁忌搜索算法在每组中生成最优路径、最小化总行驶里程。为了验证该算法的可行性和有效性,在基准数据集上进行了案例研究。计算结果表明,该算法对于客户地理位置分散分布的实例来说,在距离和计算时间方面获得近优解非常明显;而对于客户地理位置集群分布的实例来说,在“最大-最小距离”聚类方法执行后所得到的各聚类上再执行该两阶段算法,非常有效。