基于改进分支定价算法的器具取配送运输问题研究

为解决物流集装单元化背景下器具运输成本高且灵活性差问题,本文提出集装器具循环调拨与回收的运输方式,在此运输方式下的器具运输问题属于供需未匹配与需求可拆分的取送货车辆路径问题(USDSPDVRP)。为在准确描述问题的基础上使模型易于求解,提出两阶段建模思路,设计解决USDSPDVRP模型的改进分支定价算法,通过Dantzig-Wolfe分解将模型分解为选择运输方案使用数量的限制主问题与根据主问题结果生成新运输方案的子问题,并设计相适应的路径缩减策略改进算法,实现高效求解复杂子问题的目的。算例结果表明,提出的改进分支定价算法相比Gurobi求解器,求解时间平均减少了83.9%,求得的可行解与精确解目标值间隔平均为2.8%。并对比分析了循环运输与直达运输的运输效益指标,证明了循环调拨与回收的运输方式能够有效减少运输总费用和车辆使用数,提高车辆满载率。