·论文·车辆路径调度问题的启发式算法综述1杨燕旋1，宋士吉1(1.清华大学自动化系，北京 100084)摘要：车辆路径调度问题是一类具有重大研究意义及广泛应用价值的NP难优化问题。
本文给出了该问题的定义和基本描述，并将目前为止被应用于求解VRP问题的启发式算法分为构造型启发式算法、改进型启发式算法和人工智能算法这三大类，接着介绍了各类中比较典型的算法，并对算法的应用和研究情况进行了分析和总结，最后对进一步的研究做出了展望。
关键词：物流；车辆路径问题；调度；启发式算法中图分类号：F252A Survey on the Heuristic Algorithms for the Vehicle RoutingProblemYANG Yan-Xuan,1 SONG Shi-Ji,1(1.Department of Automation, Tsinghua University, Beijing 100084, China)Abstract：Vehicle Routing Problem is an NP-hard problem with great research and application significance. In this research, we first present the definition of the problem and give a classification to the existed heuristic algorithms for the problem. Then typical algorithms are introduced and research on the algorithms are investigated and summarized. Finally, further research directions are given.Key words：Logistics; Vehicle Routing Problem; Scheduling; Heuristic Algorithm 1959年，Dantzig等人首先从旅行商问题（Traveling Salesman Problem，简称TSP问题，）得到启发，提出了车辆分配问题TDP（Truck Dispatching Problem）。
这是一类具有重要研究价值的问题。
一方面，它代表了一类典型的组合优化问题，具有深远的理论意义；另一方面，它是一类重要的物流运输问题，直接影响着相关企业的运转效率，具有广泛的实践意义。
半个世纪以来，许多的专家学者对该问题进行了广泛而深入的研究，并将这类问题统称为车辆路径调度问题（Vehicle Routing Problem，简称为VRP问题）。
他们从基本问题出发，根据1基金项目：自然科学基金（编号：60574077）、国家“八六三”高技术项目（编号：2007AA04Z102）作者简介：杨燕旋（1983-），女，汉族，广东，清华大学硕士研究生，从事车辆路径调度方向的研究，E-mail: yyx02@. 宋士吉（1965-），男，汉族，黑龙江，清华大学教授，博导，从事供应链管理等方向的研究，E-mail: shijis@不同的约束和目标，构建了不同的模型，并有针对性地开发出了有效的算法。
从大的框架上讲，用于求解VRP 问题的算法可以分为两类，一类是精确算法；一类是启发式算法。
精确算法主要是基于对具体的问题建立具体的数学模型，并利用数学方法进行求解；启发式算法主要是基于直观或者凭借经验，开发出能够朝着最优解的方向搜索或靠近的一类算法。
精确算法以时间和空间的复杂度为代价，换取了解的质量，但往往只能应用于小规模的问题中，这是由VRP 是NP 难问题的属性所决定的；启发式算法通常能够在时间和空间复杂度以及解的质量中获得一个平衡，因此，该类算法被越来越多的学者所采用和研究，在实际应用中，它们也显示出了它们的优势。
本文对目前被应用得比较多且相对较为成熟的启发式算法进行一个综述。
启发式算法可以分为三大类：（一）构造型启发式算法；（二）改进型启发式算法；（三）人工智能算法。
本文在总结时，将对各类算法中比较经典和基本的算法（见表1）进行描述，并对相关的研究进行总结。
表1 启发式算法分支图 三大类经典算法 插入算法节约算法先聚类后路线算法构造型启发式算法 先路线后分割算法Petal 算法Sweep 算法改进型启发式算法 Or-opt 算法禁忌搜索算法遗传算法蚁群算法启发式算法 人工智能算法模拟退火算法1 车辆路径问题的定义和描述车辆路径调度问题的一般定义[1]为：对一系列发货点和收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。
在基本定义中，可以总结出VRP 问题中涉及到的能够影响问题模型的变量有：1） 仓库（v o ）：就数目来讲，有两种组合，即单仓库和多仓库，一般只考虑单仓库问题，因为多仓库问题可以通过区域划分简化为单仓库问题；另外，现实中，通常仓库会有固定的服务对象，因此算法只考虑单仓库问题；2）车辆（k i）：就数目来讲，有两种组合，即单车辆和多车辆；就容量来讲，可以有容量限制和无容量限制两类，也可以有同容量车辆和不同容量车辆两类；可以有运输路线长度限制和无运输路线长度限制两类；就车辆是否需要返回仓库来讲，有封闭式（车辆需要回到车场）和开放式（车辆不需要回到车场）两类；就车辆在固定路段的运行时间来讲，可以分为固定旅行时间、模糊旅行时间和随机旅行时间三类；3）客户（v i）：就数目来讲，可以分为有固定客户数目和随机客户数目两类；就客户需求来讲，可以有多维度的考虑，可以分为有时间窗要求和无时间要求两类；可以有固定客户需求、模糊客户需求和随机客户需求三类。
根据这些主体变量取值的不同可以将VRP问题分为很多种类型，由于本文旨在对算法进行综述，不涉及针对某种类型的算法的讨论，因此这里就不再对各种类型的VRP问题进行一一列举了。
求解VRP问题时，我们旨在得到一系列路线，车辆按照该路线来服务顾客，在满足顾客需求的同时，使得总的运输费用最小。
在设计这些路线时，还要根据不同问题考虑不同约束，设计的路线不能够违背相应的约束。
下面介绍一些经典的求解该问题的启发式算法。
而值得说明的是，下边介绍的算法无论对于求解哪一种VRP问题都是会有启发的，因为这些算法都能够帮助读者从不同的角度或程度去思考求解某一种具体VRP问题，只是由于问题特点的不同，有些算法对于辅助解决某一类型的问题显得更好，对其他类型则可能略显不足。
2构造型启发式算法构造型启发式算法是一类基于直观或者经验来构造相对有效解的算法。
这类算法的共同特点是：根据某些降低耗费的规则或者标准，每一次将不在线路上的点增加进已经构造的路线中去，直到所有的点都被安排进线路为止。
2.1插入算法插入算法是指通过k步迭代时，将第k个节点插入到路线中。
算法的关键在于确定在第k+1步可以被插入到路线中的点以及该点的最佳插入位置。
因此，该算法由两个关键的部分组成。
第一部分是节点选择阶段，即确定下一步被插入到路线中的顾客节点；第二部分是路径插入阶段，即确定所选择的顾客节点在路线中的最佳插入位置。
根据不同的节点选择规则，可以得到不同的插入算法。
比如，最短距离插入算法（Nearest Insertion）选择离路线中的任意一点距离最短的点插入到路线中；最低耗费插入算法（Cheapest Insertion）选择插入后子路线费用最低的点插入到路线中。
更多的插入算法可以参考Bodin等[2]的研究，他们总结了八种插入算法，并逐个分析了它们在最坏情况下的解的情况，这些统称为基本插入算法，除了上述的几种算法外，还包括凸包插入、最大角插入、最远距离插入、任意插入、快速插入、差值比率插入，关于这一类算法，读者可以参阅参考文献[2]。
不少学者借鉴基本插入算法的思想，针对不同问题开发了新的插入算法。
Renaud和Boctor等[3]借鉴凸包插入算法的思想，开发了CLOCK插入算法，作为初始解的构造方法。
该算法从一个节点出发，顺时针或者逆时针地将其他相关节点插入到路线中，这样形成的初始路线不一定会包括所有的节点，算法允许在下一步将剩余的节点插入到路线中，形成完整的路线。
2.2节约算法节约算法是一类最为经典的构造型启发式算法之一，该算法最早由Clark和Wright于1964年提出[4]，通常被简称为C-W算法。
该算法的思想是：根据顾客点之间连接可以节省的距离（节约值）最大的原则，将不在线路上的顾客点依次插入到路线中，直到所有的点都被安排进路线为止。
根据不同的模型可以对节约值进行不同的定义，以辅助求得相应模型的较优解。
C-W 算法中对节约值的定义为：s(i,j)=c i0+c0j-c ij，即依次服务i和j比分开单独服务i和j可以节省的值，其中c ij表示从顾客i到顾客j的运输总费用。
算法开始时，计算所有的节约值s ij= c i0 +c0j-c ij，并将它们由从大到小进行排列，同时生成n-1条独立的路线(1,i,1)；之后分别考虑包含弧(i,1)和(1,j)的两条路线，如果将他们合成后对应的节约值大于0，则在满足容量或时间等其他约束的条件下将这两条路线合二为一。
重复这个步骤直到没有路线可进一步合并为止。
节约算法根据特定规则一次性地生成了可行解，并把它当成问题的解。
该算法是很经典的构造型启发式算法，在提出之后被许多学者所借鉴和研究引用[2, 5]。
但是实际应用中，更多的算法则是将整个构造的过程分为两大步，现在用得最多的有即先聚类后安排路线的算法和先安排路线后分割的算法。
2.3先聚类后路线算法在对实际的大规模VRP问题设计算法时，往往会因为节点数目的增大而使得求解的难度变大，因此，可以考虑先根据一些原则（如距离或服务时间的相近、需求的合适组合等），采用合适的操作，对节点进行分区或者聚类，由同一辆车服务同一分区或者同一类中的顾客节点；然后再对分区里的节点进行排序，确定车辆在分区内的行车路线。
由于车辆通常有容量限制，因此安排到每个车辆的顾客节点的数目是有限的，因此在步骤2可以采取精确算法来求得一条最优的路线。
因此，本算法的关键在于步骤1，即如何进行聚类才能够使得解较优的问题。
截至目前，不少学者应用该算法的思想求解了VRP问题。
Karp等[6]利用该算法解决了大规模TSP问题，他们还分析这种方法在最坏情况下的表现；Fisher和Jaikumar[7]开发了用于求解VRP问题的广义分配启发式算法，他们将聚类问题看成一个广义分配或匹配问题并加以求解；不少学者通过设定规则逐步进行寻优聚类，比如按照服务时刻、顾客需求量、地理位置相近度等规则进行聚类，Gillett和Miller[8]在地理平面上建立极坐标系，按照顾客极坐标角大小依次对顾客编号，然后基于车辆容量约束依次将顾客安排到车辆中，完成了顾客到车辆的分配，即顾客聚类（Lin的文章称为生成Petal集，具体参见下文叙述的Petal算法）；Yang等[9]在进行顾客节点分区时提出另一种更为有效的聚类方法，即先选择种子顾客节点，再根据种子顾客节点对其他节点进行吸收，最后完成聚类。