毕国通

摘 要：车辆路径问题是物流管理与运输组织优化中的核心问题，是运筹学中一类经典的组合优化问题。文章比较系统地总结了常见的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-难题。

企业通过选取恰当的配送路径，对运输车辆进行优化调度，可以明显提高配送效率，有效减少车辆的空驶率和行驶距离，降低运输成本，加快响应客户的速度从而提高客户服务质量，提高企业的核心竞争力。……