基于两阶段算法的需求可拆分多车型车辆路径问题

摘要

需求可拆分车辆路径问题(SDVRP)属于车辆路径问题(VRP)的变种问题,SDVRP模型松弛了客户服务次数和允许客户需求超过车辆装载能力,能提高车辆装载率和降低车辆成本.SDVRP模型都基于相同车型的假设,这不符合实际物流配送中使用不同车型的情况;且较少分析客户需求拆分阈值对问题解的影响;此外,SDVRP研究较少应用新型仿生搜索算法.因此,本文以多车型和需求拆分阈值为新约束,建立需求可拆分的多车型车辆路径问题(SDHFVRP)混合整数规划模型;提出以路径优化和路径改进相结合的两阶段算法(TPA).最后以华北分公司大牛地气田物流系统中的污水回收路径规划为例,重新规划了大牛地气田污水回收的车辆行驶路线,并与大牛地实际回收方案对比,模拟结果有效地减少了车辆使用数目和运输成本.