【作者】 张俊；

【导师】 王征；

【作者基本信息】 大连理工大学 ， 计算机应用技术， 2010， 硕士

【摘要】 车辆路径问题是研究如何通过合理规划车辆的行驶路线来实现成本优化的一类优化调度问题,其相关理论和方法对于降低物流成本具有重要的应用价值,因此一直是运筹学和组合优化领域的研究热点。多年来车辆路径问题已经派生出众多研究分支,如多车场车辆路径问题、带时间窗车辆路径问题、开放式车辆路径问题、周期性车辆路径问题和装卸货车辆路径问题等,并取得了大量的研究成果。在现实生活中,存在这样一类车辆路径问题：大型的物流公司拥有多个车场,而每个车场都有若干车辆用于配送；同时公司的客户对其服务时间有较为严格的要求,他们希望能在事先指定的时间范围内(时间窗)得到服务。因此在规划车辆的行驶路线时,决策者需要根据客户的所在位置以及客户的时间窗将客户分配到合适的车场和车辆中。这一类问题可以抽象为多车场带时间窗的车辆路径问题。由于多车场和时间窗双重约束的引进,对此类车辆路径问题的求解会变得更加困难。本文针对多车场带时间窗车辆路径问题的模型和求解算法进行了研究,主要研究工作如下：建立多车场带时间窗车辆路径问题的数学模型,并对求解多车场带时间窗车辆路径问题的常用启发式算法进行介绍。设计并实现了一种求解多车场带时间窗车辆路径问题的改进型变邻域搜索算法,分别将混合局部搜索算子、后优化过程以及模拟退火算法融合到变邻域搜索算法的基本框架中。在Cordeau标准算例上对提出的算法进行实验,求解结果更新了多组算例的目前最优解。并通过与其他优化算法的比较,验证了该算法在求解多车场带时间窗车辆路径问题时的有效性。更多还原

【Abstract】 Vehicle routing problem is a class of optimizaion problems, whose objective is to construct a set of feasible routes with minimal transportation cost. The correlative theories and methods have great application values for reducing the logistic cost, thus they are always the research hotspot of operations research and combinatorial optimization domains. For decades, a lot of variants of the vehicle routing problem have been derived, such as multi depot vehicle routing problem, vehicle routing problem with time windows, open vehicle routing problem, periodic vehicle routing problem, vehicle routing problem with pickup and delievery and so on, a great deal of research results have been achieved.In real life, there exists such a class of vehicle routing problem:A big logistic company has more than one depot located in different area, and each depot uses several vehicles to do the distribution tasks. Meanwhile, the customers have strict limit to their service time and hope to be served in appointed time intervals (time windows). Therefore, the decision-makers need to assign the customers to appropriate depots and vehicles according to their locations and time windows. The problem above can be abstracted as multi depot vehicle routing problem with time windows. For the introduction of dual constraints of multi depot and time windows, it becomes much more difficult to solve this type of vehicle routing problem.The models and algorithms of multi depot vehicle routing problem with time windows are studied in this paper. The main research works are as follows:A mathematical model of multi depot vehicle routing problem with time windows was constructed, and the heuristic algorithms commonly used to solve the multi depot vehicle routing problem with time windows were introduced.A modified variable neighborhood search was designed and implemented, integrating a hybrid local search opeartor, a post optimization procedure and the idea of simulaed annealing into the basic framework of the variable neighborhood search.Computational experiments were carried out on Cordeau benchmark instances, and serveal new best solutions were found. The computational results show that the proposed algorithm is effective in solving the multi depot vehicle routing problem with time windows.更多还原