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

作     者：张鹏乐 肖开明 符春晓 杨克巍 ZHANG Pengle;XIAO Kaiming;FU Chunxiao;YANG Kewei

作者机构：国防科学技术大学信息系统与管理学院国防采办与体系工程管理教研室长沙410073 国防科学技术大学信息系统与管理学院C4ISR国防科技重点实验室长沙410073 

出 版 物：《系统工程理论与实践》 (Systems Engineering-Theory & Practice)

年 卷 期：2016年第36卷第3期

页      面：694-705页

核心收录：

学科分类：12[管理学] 0711[理学-系统科学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 071102[理学-系统分析与集成] 

基　　金：国家自然科学基金(71201168) 

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

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