【作者】 蒋文霞；

【导师】 黄樟灿；

【作者基本信息】 武汉理工大学 ， 应用数学， 2007， 硕士

【摘要】 配送是物流系统中很重要的一个环节,是一系列狭义的物流活动的集成,它要求在规定的时间内以一定的方式将确定的货物送到指定的地点。而车辆路径问题是研究货物运输成本最小的物流配送问题。车辆路径问题是运输组织优化中的核心问题,由于它将运筹学理论与生产实践紧密地结合,因此近几十年取得了丰富的研究成果,并且被称为“最近几十年运筹学领域最成功的研究之一”。本文分析和总结了车辆路径问题的历史和研究现状,以及常用模型、时间复杂度,以综合性能的角度对求解VRPTW问题的算法进行了一定的归纳和分析,并在此基础上确定了本文的研究方法和目标。同时结合实际提出了本文的研究问题——带时间窗的车辆路径问题(VRPTW),建立了以车辆容量和客户需求等为约束条件,以配送运输成本为目标函数的VRPTW数学模型。提出了一种两步优化的实现策略。第一步,选取动态的push forward insertion heuristics(StochasticPFIH)算法产生机制构建问题的初始解,保证了初始解的多样性,同时在产生的初始解中设置了限制条件,实现对初始解的筛选,为第二阶段路径优化提供了高质量的初始解;以改进的大规模邻域搜索为新解产生机制,并将模拟退火算法和大规模邻域搜索算法混合来进行路径优化,得到问题的最优解,该混合算法充分利用了两种算法的优点,克服了它们的缺点。第二步,提出一种时间窗修正规则来调整时间窗,使得车辆在每个客户的等待时间为零,真正实现了路径的优化,节省了成本,并给出了理论证明。最后通过VC++编程在计算机上实现,以Solomon的标准数据中的C101系列数据进行数值实验,实验结果验证了本文算法的有效性。更多还原

【Abstract】 Distribution plays an important role in logistic system, it is the integration of a series of logistic campaign in a narrow sense, and logistic distribution requires delivering the right commodities to the right place by the right method at the right time. Vehicle routing problem involves the design of a set of minimum-cost vehicle routes, delivering the right commodities to the right location by the very method at the very time. So vehicle routing problem represents a very important part of any logistic distribution systems and they are named as one of the most successful areas in Operations Research in the past decades.In this dissertation, the main research work and innovative points as follows:We firstly describe the characteristics and classification of these problems, and the state-of-the-art in the solution algorithms. On the base of reality, we purpose the research problem—vehicle routing problem with time window (VRPTW) and construct a mathematical model: defines an objective function. Meanwhile,we give a review of the past research on vehicle routing problems and their solution methods, establishing the base of algorithm in this dissertation. In this paper,we propose a two-stage optimization strategy for VRPTW. In the first step, for constructing a good initial solution ,this work used the stochastic PFIH, which based on the algorithm known as Push-Forward Insertion Heuristic (PFIH), guaranteeing the diversity of the initial solution,at the same time , give a limit in the process of the constructing initial solution, realizing the filtration of initial solution. The producing mechanism of the new solution is betterment of large neighbor search, then a different hybrid system based on the combination of SA and LNS is proposed to optimize the initial solution .In the second step,a regression iterative strategy is put forward to tune time windows for the customers and figure out the best time for each vehicle departing, it can make the total waiting time zero. Finally, this method is implemented on computer in VC++. It is proved by the experiment that the hybrid strategy can solve VRPTW efficiently and quickly .Comparing with other algorithms, it has practicality and effectiveness, simultaneously, author provide an efficient algorithm to solve VRPTW.更多还原