基于物流配送中车辆路径问题的模型及算法的研究

　　　　
　　论文关键词：车辆路径问题；精确算法；启发式算法

　　论文摘要：本文介绍了车辆路径问题的分类及限制条件，重点论述了国内外关于车辆路径问题的模型及算法研究现状，分析了各种算法的优缺点和适用范围，并指出了车辆路径问题的研究前景。

　　
　　Abstract: This paper presents the classifications and constraint conditions about the Vehicle Routing Problem, and discourses emphases upon achievements of models and algorithms for vehicle routing problem at homeland and abroad, and analyzes advantage or disadvantage and its applicable cope of these algorithms. Then it prospects future research orientations of it.
　　Key words: vehicle routing problem; accurate algorithm; heuristic algorithm
　　
　　配送中心作为物流活动中专职从事配送工作的组织者，具有规模大、配送能力强的特点，从而使得由配送中心对用户进行需求物品配送成为物流配送的主要形式，而其中配送车辆的路径合理与否，对于配送速度、配送费用、运力配备以及配送与效益的影响均很大，采用科学合理的方法来确定车辆路径便成为配送中心进行配送活动的一项重要工作。车辆路径问题（Vehicle Routing Problem，VRP）是由G．Dantzig和 J．Ramser[1]于1959年首先提出来的，很快引起运筹学、管、应用、组合、图论等学科的专家学者的高度重视。他们对此问题进行了大量的理论研究和实验分析，取得了很大进展。其研究结果在系统、物流配送系统、快递收发系统中都已得到广泛应用。现在，对车辆路径问题的研究仍然相当活跃。车辆路径问题一般定义为：对一系列发货点和／或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆尽量少等）。由此定义不难看出，旅行商问题（Traveling Salesman Problem，TSP）是VRP的一个特例：由于Gaery已证明TSP问题是NP难题，因此，VRP也是NP难题。
　　
　　1车辆路径问题的分类
　　
　　在经典VRP的基础上，车辆路径问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括TSP（当VRP只包括一条路径，且没有能力约束时就成为TSP）、带能力约束的车辆路径问题（CVRP）、带时间窗的车辆路径问题（VRPTW）、追求最佳服务时间的车辆路径问题（VRPDT）、多车种车辆路径问题（FSVRP）、车辆多次使用的车辆路径问题（VRPM）、考虑收集的车辆路径问题（VRPB）、随机需求车辆路径问题（VRPSD）、动态车辆路径问题（DVRP）、满载/非满载VRP、双向VRP等。虽然VRP具有多种变化型态，事实上，根据研究重点的不同，VRP存在多种分类方式，但总的来说，在VRP中，最常见的附加条件有：
　　（1）能力约束。与每个客户或城市对应的需求是个非负的值，任意车辆路径的总重量不能超过该车辆的能力负荷。
　　（2）任意路径所含城市数的上界为q。
　　（3）总时间约束。任意路径的长度不能超过预先给定的界L；该长度由车辆在城市间的旅行时间和在该路径里的每个城市i的停留时间所构成。
　　（4）时间窗口。必须在时间区间,里访问城市i，并允许在城市i等待。
　　（5）多个城市间存在优先级关系，必须在访问城市i之前访问城市j。
　　基于此，文献[2]按已知信息的特征将VRP分为确定性VRP和非确定性VRP，其中非确定性VRP可进一步分为随机VRP（SVRP）和模糊VRP（FVRP）；按约束条件可分为CVRP（带能力约束）、DVRP（带时间距离约束）、VRPTW（带时间窗口）；按需求是否可切分，又可分为可切分的VRP和不可切分的VRP。
　　
　　2车辆路径问题的算法
　　
　　在VRP中，问题的算法与所建立的模型密切相关。由于在现有的文献中，大部分文献是研究确定性VRP和非确定性VRP的，因此，下文将对确定性VRP和非确定性VRP的算法作详细介绍。
　　2.1确定性VRP
　　确定性VRP是现实中最常见的类型。它指的是这样一类VRP：（1）在路径规划开始之前，规划人员对有关路径规划的所有信息都是清楚的；（2）在路径构建以后，与路径规划有关的信息不再变化。所谓相关信息，包括顾客的所有特征，如顾客的位置、所需服务时间、每个顾客的需求量等。解决这类问题的方法一般分为精确算法和启发式算法两类。
　　2.1.1精确算法
　　精确算法指可求出最优解的算法。到目前为止，已提出的精确算法种类较多，有分支定界法、割平面法、整数规划算法和动态规划算法等。
　　Laporte等用VRP与多重旅行商之间的关系，将VRP变形为旅行商问题后，再用分枝定界法求得问题最优解。随后，Laporte等又将该方法拓展到具有其他边约束的问题中。与这种方法略有不同，Christofides等先将问题转化为“K-度中心树”后，再采用分枝定界法进行求解。
　　求解确定性VRP的动态规划算法最早由Eilon等提出。但由于他们提出的动态规划方法需要考虑相当庞大的状态数，故只能精确求解规模非常小的问题。Christofides等通过运用状态空间松弛技术大大减少了状态数，使动态规划算法的性能得到了很大程度上的改善。他们的实验表明，该方法可有效求解顶点数不超过50的有容量约束VRP。
　　确定性VRP也可以表示为整数线性规划模型，主要有三种：集分割模型、货物流模型和车辆流模型。Balinsk等最早利用集分割模型来研究VRP。然而，这个模型与一般的动态规划模型有着相同的缺点，即使对于规模较小的问题，模型的变量数在大多数情况下亦是天文数字，比如问题的规模若为10，那么模型中出现的变量数最多可达到1010。除此之外，确定目标函数中的值往往先要求解大量的NP难题（如旅行商问题），这也给问题精确求解带来困难。采用列生成技术可部分解决这些困难，如Agarwal等，Desrosiers等采用列生成技术求解了规模较小有容量和时间窗约束的确定性VRP。