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

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

Fast dynamic programming algorithm for the large scale VCVRP problem

Vehicle routing problem (VRP) is a kind of typical combination optimization problems. Most of the researches focus on VRP with fixed transportation capacity; however, the capacity of vehicles is varied with the cargo shape and customer requirement. Therefore, we propose a varied capacitated vehicle routing problem (VCVRP) to deal with the practical problems. In this paper, a fast dynamic programming algorithm is proposed for large-scale VCVRP. And it is based on the traditional best fit decreasing (BFD) algorithm and minimum spanning tree (MST) algorithm. A K-backtracking strategy and a principle of short-priority are introduced to the dynamic programming algorithm. In this fast algorithm, the bin packing problem and routing problem are decoupled approximately. Analysis of the upper bound of objective total distance is given theoretically. Finally, experimental results of practical logistics of passenger vehicles are discussed to illustrate the quality and efficiency of the proposed algorithm.