车辆路径问题的发展及其应用

卞晨++赵建东

摘要：车辆路径问题作为运筹学和组合优化领域的热点问题，与现实生活息息相关。随着对车辆路径问题的不断深入研究，各类新型的启发式算法被运用到解决这类问题之中。文对具有各类约束条件的车辆路径问题进行了调查、分析和总结，并对国内外相关研究成果进行了提炼，在该基础之上，阐述了车辆路径问题的研究综述。基于当前多样的分类标准，讨论并分析了经典车辆路径问题，并在此基础之上综述了求解各类型车辆路径问题的基本方法和现代启发式算法。

关键词：车辆路径问题；启发式算法；多配送中心；带时间窗；集送货一体化

中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2016）26-0079-02

Development and Application of Vehicle Routing Problem

BIAN Chen， ZHAO Jian-dong

（School of Computer Science and Engineering， Anhui University of Science & Technology， Huainan 232001， China）

Abstract： As a hotspot in the field of operational research and combinatorial optimization， vehicle routing problem is closely related to real life.As long as the deepening study of vehicle routing problem， various kinds of new types of heuristic algorithm is applied to solve such problems.The vehicle routing problem with various constraint were investigated， analysis and summary in this paper， and the related domestic and foreign research results were reviewed and refined， on this basis， this paper summarizes the research of vehicle routing problem. Based on the current various standard of classification， this paper discusses and analyzes the classical vehicle routing problem firstly， and summarized the basic methods and modern heuristic algorithm on this basis.

Key words： vehicle routing problem； heuristic algorithm； hybrid；multi-depots； time window； pickup and delivery

1 背景

车辆路径问题（Vehicle Routing Problem，VRP ）是由 Dantzig等人在1959 年提出的一个经典的NP-hard问题[1]。是指对于一系列的装货点及卸货点，规划合理的配送路径，在满足了约束条件之下，载货车辆按照规划的路线依次访问，能够满足一定的需求或达到某些目标。其研究成果已广泛地应用于各个学科之中。VRP已经不止是单纯的理论研究，现实世界中，国内外学者的研究经历了其从最早期无车辆约束的TSP问题发展为对车辆运载能力、车辆行驶里程、客户服务数量进行限制的经典VRP，而后依据客户需求的改变和客户对配送要求的提高，从服务无时限向有时限（也称为时间窗问题）以及从纯送货问题或者纯取货问题向混合取送问题（也称为集货送货一体化）的变化的VRP问题。为了不断满足现实要求，当前针对VRP的大部分研究，集中在对其动态性的讨论上，即从配送过程中信息的确定性向动态接受客户需求（也称为不确定性）的变化。

随着现代物流行业的崛起，企业为了降低运输成本，越来越重视对VRP问题的探究，新型的VRP不断地涌现，使得其更有研究价值和现实意义。

2车辆路径问题研究现状及评述

本文根据现有对VRP问题研究的成果，从综合的角度分析车辆路径路径问题，目前国内外针对车辆路径问题的研究主要集中在其扩展问题上。

2.1 多配送中心的车辆路径问题

根据配送中心数目的多少，配送车辆调度问题可以分为单配送中心车辆调度问题和多中心车辆调度问题，在整个物流管理的体系中，配送地一般都存在多个中心，因此对多配送中心车辆调度问题的研究更加具有现实意义。目前国内对于多配送中心车辆调度问题的研究还是处于一个有限的阶段。

在多配中心车辆路径问题中，车辆路径的安排需要满足以下四点条件：

1）每一辆车都从一个配送中心驶出，并在服务了一定数量的客户后返回初始的配送中心；

2）每一个客户每次只能被一辆车服务；

3）车辆不能够在两个配送中心之间进行运输，并且行驶路径不能够出现回路；

4）车辆的运载量不能够超出容量限制，并且每一个配送中心提供的客户服务数量是有限的。

对配送中心的车辆路径问题一般可以如下的描述：在整个物流配送系统中，存在着多个服务中心为多个客户进行服务，需要制定一条配送行车路径使得所有客户的需求被满足的前提之下，配送成本降至最低。多配送中心的VRP是一个NP难度组合优化问题，因此一般求解是很难得到最优解的。当前，国内外学者普遍采用多阶段的办法来解决此类问题，一般先将多配送中心问题转化为单配送中心问题，再利用启发式算法进行求解。崔文[2]通过多阶段的启发式算法，将此类问题通过聚合—求解—优化的步骤逐步求解出最优路径，提出了通过启发式算法在短时间生成最初的有效路径来代替Lin-Kemighan算法中采用的随机路径作为初始路径。

2.2 开放式车辆路径问题

开放式车辆路径问题（OVRP）是现代运输运筹学中的一个新型研究课题，与经典VRP问题相比较，他的一个显著特点是车辆在完成运输服务后可以将其他的配送中心点选为终点。OVRP一般可以简化为忽视了回程约束的带容量约束车辆路径问题（CVRP），其求解目标是构建一个哈密顿通路以满足所有顾客的需求。在现实中，物流公司可能通过雇佣车辆来完成配送任务，那么车辆是否回到出发点并不受到关注，这段路程的费用也将不计。

OVRP是配送运输管理中广泛存在的问题，在现实生活中有很多应用，特别是在具有外包业务特点的配送服务中具有较大的应用价值，例如校园班车问题、牛奶配送、报纸配送等，在这类问题中，由于企业没有自己的车辆，所以将其配送业务外包给其他的车辆或车队，而且企业并不要求车辆在服务完客户后回到车场点。OVRP问题的首要优化目标一般都是最少车辆数，在此基础上优化行驶距离。在过去的十几年里，尽管学者们通过禁忌搜索，确定性退火技术，大规模领域搜索方法，分枝切面法等多种方法为OVRP问题提供了基本的解决办法，但面对大规模的数据处理，OVRP问题仍然存在着一定的求解难度。Sariklis[6]等人通过两阶段启发式算法来进行求解，第一阶段是先生成客户群，然后在每一个客户群中安排路线，进行局部优化，第二阶段将OVRP问题转化为最小生成树问题并求解。Brandao[7]在求解时，通过最近邻居法和最小K度生成树来划分客户群，并最终用禁忌搜索法优化路径。

2.3 时间窗口约束的车辆路径问题

带时间窗车辆路径问题（Vehicle Routing Problem with Time Windows，VRPTW）作为物流管理问题中一个重要的分支，他基于以下假设：1.需要必不可少的通信设备，使得顾客和服务中心之间，服务中心和货运车辆之间的信息能够快速便捷的传递；2.配送的计划中，存在预约服务的客户。服务车辆必须在客户规定的时间窗[[Ai，Bi]]对其进行服务，其中[Ai]是客户[i]的允许最早开始时间，[Bi]是其所允许的最迟开始时间。如果车辆到达客户的时间早于[Ai]，那么车辆只得等待直至到达服务的最早时间点，其系统优化目标是最小化客户的平均等待时间。

近年来，对于求解带时间窗车辆路径问题取得较好效果的是启发式算法。Gold等人最早综述了VRPTW的研究状况。上世纪80-90年代，对VRPTW的研究开展综述的是Solomon等人[10]。随后Braysy等人[11]综述了经典启发式、智能启发式算法并提出了展望。最近，Raúl Ba?os[12]等人提出了一种针对多目标VRPTW问题的混合现代启发式算法，得到优化解决方案。

2.4 带集货送货需求的车辆路径问题

车辆调度领域之内的问题一般可以按如下区分为两大类：一种是纯装货或者纯卸货问题，另一种是带装货卸货一体化的车辆调度问题（VRPSPD），而后者更是包括了先送货后取货的车辆路径问题，同时集货送货的车辆路径问题以及混合集货送货的车辆路径问题。

VRPSPD的提出最早可以追溯到1989年，由Min提出的在解决了车辆数量一定并且车辆运载能力有限的情况下，一个中心配送点和22个地方图书馆之间的书籍配送问题。VRPSPD问题可描述为：某一个仓库为其用户群体进行货运服务，任意用户可能同时需要送货和集货服务，并且某一客户的送取货的需求之和不能大于车辆总运载能力Q。

VRPSDP的难点在于服务车辆的装载量难以控制易发生溢出。当每一个客户的送货需求是已知的时候，依据车辆的剩余装载能力来定义插入准则，。

2.5 动态车辆路径问题

依据物流信息在配送之前是否完全可知，VRP按新的分类方式分为静态VRP和动态VRP。动态车辆路径问题的首次完全提出要归功于Wilson和Colvin[13]，当时他们研究的单一车辆问题描述了客户旅程的需求，从始发地到目的地的旅程是动态变化，并通过启发式算法来提升计算效率。车辆路径问题中动态信息最常见的来源就是客户需求的在线到达。具体来说，需求可以是针对货物的调整也可以是是服务需求的变化。

一般认为动态车辆路径问题和静态车辆路径问题的区别在于信息的确定性与未知性，而前者在配送服务过程中，会出现不同类型的动态信息。

动态车辆路径问题一般具有的特征如下：

1）安排配送路径和车辆执行计划的过程中新客户信息能够实时的传达。

2）任何新传达的信息都允许是不精确的。

3）新信息需要被快速的响应。

4）与静态VRP问题相比求解的目标函数更为繁杂。

任何动态车辆路径问题仍是基于静态车辆路径问题提出的，目前针对动态车辆路径问题的求解办法，仍然需要借鉴处理静态车辆路径问题的各类算法，其中大部分算法为元启发算法。

动态车辆路径问题首先要明确需要响应哪些动态信息，并以客户需求变化为依据，选择需要优化的目标函数，例如将配送车辆的总行程作为目标函数进行优化，然后再设置额外的约束条件，例如设定单车最大行程为约束条件。借助各类启发式算法如蚁群优化算法等进行优化，在整个配送过程中，不再是单一直接地插入顾客需求，通过最大熵法分布估计算法计算出具有发展潜力的客户群体和区域。在=当需求发生冲突时衡量各个客户需求的利益，通过惩罚措施来降低费用。

3 结束语

车辆路径问题因其不可预估的经济效益和其在现代物流中的所占据的重要地位已经引起了国内外学者的高度关注，并依据实际需求不断引入新的约束。在理论与应用上，各类精确算法、启发式算法被广泛地应用于解决车辆路径问题，并已经取得了长足的进步。然而，同样被关注的是，从现有的各类研究成果看来，虽然新型约束条件下的VRP模型更加完善也更符合现代物流实际需求，但实际求解算法却很难在精度和效率上做到两全，简化算法测率需要得到更多的重视，特别是，各类启发式算法在求解时的弊端也愈加明显，需要取长补短发挥其他算法的优势。

参考文献：

[1] Dantzing G，Ramser J. The truck dispatching problem[J]. Management Science， 1959， 10（6）： 80-91.

[2]崔西.大规模多配送中心车辆路径问题研究[D]. 济南： 山东大学， 2009.

[3]Sariklis D， Powell S.A heuristic method for the open vehicle routing problem[J].Journal of the Operational ResearchSociety，2000，51： 564-573.

[4] Branda～o J.A tabu search algorithm for the open vehicle routing problem[J].European Journal of Operational Research， 2004，157：552-564.

[5] Desrochers M， Lenstra J K， Savelsbergh M W，et al. Vehicle Routing With Time Windows： Optimization and Approximation[M]. Amsterdam， The Netherlands： Elsevier Science Publishers， 1988.

[6] Braysy， Gendreau. Vehicle Routing Problem With Time Windows，Part I：Route Construction and Local Search Algorithms[J]. Transportation Science， 2005（39）： 104-118.

[7] Raul Banos， Julio Ortega， Consolacion Gil， et al. A Hybrid Meta-heuristic for Multi objective Vehicle Routing Problems with Time Windows[J]. Computers & Industrial Engineering， 2013， 65： 286-296.

[8] Wilson N，Colvin N.Computer control of the Rochester dial-a-ride system[Z]. Cambridge，Massachusetts，1977.