【作者】 邓薇；

【导师】 高成修；

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

【摘要】 1956年,Dantizig和Ramser提出了车辆路线问题(Vehicle Routing Problem,VRP),该问题自提出以来就成为运筹学领域的一个热点,相关的文献不断涌现。然而,实际问题中不仅要考虑地理因素,时间因素也是不可忽略的,带时间窗的车辆路线问题(Vehicle Routing Problem with Time Windows,VRPTW)就是基于这样的实际背景提出的组合优化问题。VRPTW问题寻求在满足顾客的时间窗和车辆的容量约束的条件下,使总的代价最小的一组车辆路线。关于VRPTW问题以及其衍生问题的研究都相当丰富,其优化算法和启发式算法都在不断发展和完善。 本文致力于VRPTW算法研究,其主要工作在于对两类VRPTW问题:带车辆数目和时间窗限制的车辆路线问题(m-VRPTW)和带时间窗的车辆路线双目标优化问题(BVRPTW)建立了数学模型,并分别构造了基于并行插入算法和禁忌搜索算法的混合式算法。并对Solomon的经典数据集进行了数值实验,其结果表明,我们的算法是有效的。更多还原

【Abstract】 Vehicle routing problem (VRP) has been a well-known problem in operation research since it was presented by Dantizig and Ramser in 1978. But VRP only concerns the spatial aspects and ignores the temporal aspects. This is not enough in the real life application, so vehicle routing problem with time windows (VRPTW) was presented which is to determine the most favorable vehicle routes that minimize the total cost when the capacity constrains and time window constrains are satisfied. VRPTW and extensions of it draw attentions from many researchers and the optimal algorithms and heuristic algorithms have developed.This paper is devoted to researching on the algorithms for VRPTW. The main work is that we proposed mathematic models and hybrid heuristic algorithms which are based on parallel inserting heuristics and Tabu search heuristics for vehicle routing problem with time windows where a limited number of vehicles is given (m-VRPTW) and the bi-objective vehicle routing problem with time windows (BVRPTW). The results of the computational experiments showed that the proposed algorithms are successful.更多还原