带时间窗车辆路径问题的精确算法研究.pptx

带时间窗车辆路径问题的精确算法研究带时间窗的车辆路径问题(VehicleRoutingProblemwithTimeWindows,VRPTW)是经典的组合优化问题,也是目前应用最广泛的运输问题之一。本文从理论基础做起,立足于精确算法,对VRPTW的整数线性规划领域进行了较为全面的理论研究,并初步涉猎了约束规划领域。在算法上,本文选择使用当前主流的列生成算法,其中子问题是带资源约束的最短路径问题(ElementaryShortestPathProblemwithResourceConstraints,ESPPRC)。在运用列生成算法求解VRPTW时,子问题难以快速求解是一直困扰我们的主要问题,所以我们围绕子问题进行了深入研究,发现对它的研究大多都是运用动态规划的思路求解。近几年来有少数外国学者开始对ESPPRC的整数线性规划模型进行研究,但成果并不显著,所以我们选择ESPPRC的整数线性规划领域作为主要研究的对象,试图有所突破。本文主要的研究成果和创新点如下:(1)研究了ESPPRC的多胞形(polytope)结构并证明出一个小平面定义(facet-defining)的不等式。在组合优化领域,多面体结构的研究主要集中在旅行商问题和带容量约束的车辆路径问题上,在上世纪末由老一辈的学者们攻克。国内外对ESPPRC的多面体结构研究非常少,学者们更加热衷于用动态规划的方法进行求解,或者将旅行商问题中经典的不等式加以演变应用在ESPPRC中。我们运用多面体理论,对ESPPRC的多胞形(polytope)结构进行了研究与证明,找到了一个小平面定义(facet-defining)的不等式。(2)针对ESPPRC提出了三组有效不等式。通过对动态规划和约束规划相关理论的借鉴,本文对ESPPRC提出了适用于整数线性规划的统治规则。研究了ESPPRC的多面体结构,并发现了一组符合小平面定义(facet-defining)的不等式。接着,基于以上的理论,创新性地提出了三种有效不等式,并给出了证明。最后用Solomon基准测试包的修改版测试了这三个模型的性能,效果显著。(3)将二维车流的数学模型应用在VRPTW中。我们将CVRP(CapacitatedVehicleRoutingProblem)中的二维车流模型扩展至VRPTW中,用它来替代列生成算法中的分支-切割过程,为解决VRPTW提供了一种新思路。同时对最少车辆数量的理论上界进行了猜想,并用Solomon基准测试包进行了实验,本文求解出的算例均肯定了这一猜想。