车辆路径问题及其优化算法研究综述.doc

车辆路径问题及其优化算法研究综述 　　摘 要：车辆路径问题是物流管理与运输组织优化中的核心问题，是运筹学中一类经典的组合优化问题。文章比较系统地总结了常见的VRP问题的分类和基本的数学模型，并通过查阅学者们的研究状况，总结了求解VRP问题常用和高效的启发式算法及相应的研究现状；最后总结了研究存在的问题，并对今后VRP问题的研究和求解方法进行了展望。 　　关键词：车辆路径问题；启发式算法；优化 　　中图分类号：U116.2 文献标识码：A 　　Abstract： Vehicle routing problem is the core problem in logistics management and in the organization and optimization of transportation， and is a classic combinatorial optimization problem in operations research. This article systematically summarized the common classifications and the basic model of VRP problems. And through referring to scholars research situation， summarized the commonly used and efficient heuristic algorithms of solving VRP problems and the present situation of the corresponding research. Finally， summarized the problems in the research of VRP problems and discussed the future research and the solving methods for VRP problems. 　　Key words： vehicle routing problem； heuristic algorithm； optimization 　　0 引 言 　　随着科技的进步和电子商务的飞速发展，作为国民经济中一个重要行业的物流产业已成为拉动国家经济发展与提高居民生活水平的重要动力源泉，而物流行业中的车辆路径问题（Vehicle Routing Problem， VRP）是制约物流行业发展的一个关键要素，其研究也受到人们的广泛关注。车辆路径问题是物流管理与运输组织优化中的核心问题之一，是指在满足一定的约束条件（如时间限制、车载容量限制、交通限制等）下，通过对一系列收货点与发货点客户合理安排行车路线，在客户的需求得到满足的前提下，达到配送车辆最少、配送时间最短、配送成本最低、配送路程最短等目标。该问题由Dantzig和Ramser[1]于1959年在优化亚特兰大炼油厂的运输路径问题时首次提出，现已成为运筹学中一类经典的组合优化问题，是典型的NP-难题。 　　企业通过选取恰当的配送路径，对运输车辆进行优化调度，可以明显提高配送效率，有效减少车辆的空驶率和行驶距离，降低运输成本，加快响应客户的速度从而提高客户服务质量，提高企业的核心竞争力。VRP作为物流系统优化环节中关键的一环，其研究成果已经应用到快递和报纸配送连锁商店线路优化以及城市绿化车线路优化等社会实际问题中，因而车辆路径问题的优化研究具有很好的现实意义。 　　1 车辆路径问题的分类与基本模型 　　VRP的构成要素通常包括车辆、客户点、货物、配送中心（车场）、道路网络、目标函数和约束条件等，根据侧重点的不同，VRP可以分为不同的类型。根据运输车辆载货状况分类可分为非满载车辆路径问题和满载车辆路径问题；根据任务特征可分为仅装货、仅卸货和装卸混合的车辆路径问题；根据优化目标的数量可分为单目标车辆路径问题和多目标车辆路径问题；根据配送车辆是否相同可分为同型车辆路径问题和异型车辆路径问题；根据客户对货物接收与发送有无时间窗约束可分为不带时间窗的车辆路径问题和带时间窗的车辆路径问题；根据客户需求是否可拆分可分为需求可拆分车辆路径问题和需求不可拆分车辆路径问题；根据客户是否优先可分为优先约束车辆路径问题和无优先约束车辆路径问题；根据配送与取货完成后车辆是否需要返回出发点可分为开放式车辆路径问题和闭合式车辆路径问题；还可以将上述两个或更多约束条件结合起来，构成一些更复杂的车辆路径问题。 　　由于VRP的约束条件不同引起了其分类多种多样，而不同类型的VRP其模型构造及求解算法有很大差别。VRP的一般数学模型为： 　　在上述模型中，