求解大规模VCVRP问题的快速动态规划算法

摘要：

车辆路径问题是一类典型的组合优化问题,大部分研究都只考虑车辆能力固定的情形,实际中受货物形状特性及客户需求变化,车辆的能力是受限变化的,针对能力受限变化的车辆路径问题(varied capacitated vehicle routing problem,VCVRP),基于动态规划理论,提出一种求解大规模VCVRP问题的快速动态规划算法.该算法以传统的最佳适应降序算法(best fit decreasing,BFD)和最小生成树(mininum spanning tree,MST)算法为基础,引入K步回溯,短途优先原则,实现了VCVRP中的货物装箱问题和路由选择问题的近似解耦.同时给出了该算法的优化目标车辆旅程的理论上界,短途优先原则的局部最小的理论分析与证明.最后以乘用车物流运输案例为背景,给出了计算实例,并从算法参数与算例规模多个角度进行求解质量与算法性能的分析.

关键词：车辆路径问题、VCVRP问题、动态规划、组合优化、快速算法、启发式算法

所属期刊栏目：36

分类号：O22;N945(运筹学)

资助基金：国家自然科学基金71201168 National Natural Science Foundation of China 71201168

在线出版日期：2017-05-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：694-705