带时间窗车辆路径问题的精确算法研究
带时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)是经典的组合优化问题,也是目前应用最广泛的运输问题之一。本文从理论基础做起,立足于精确算法,对VRPTW的整数线性规划领域进行了较为全面的理论研究,并初步涉猎了约束规划领域。
在算法上,本文选择使用当前主流的列生成算法,其中子问题是带资源约束的最短路径问题(Elementary Shortest Path Problem with Resource Constraints,ESPPRC)。在运用列生成算法求解VRPTW时,子问题难以快速求解是一直困扰我们的主要问题,所以我们围绕子问题进行了深入研究,发现对它的研究大多都是运用动态规划的思路求解。