车辆调度算法研究及其应用【文献综述】.doc

1、 毕业设计文献综述 计算机科学与技术 车辆调度算法研究及其应用 一、 前言部分 车辆调度问题是现代物流系统优化中关键的一环，也是开展电子商务不可缺少的内容。 对车辆调度优化理论与算法进行系统研究是构建综合物流系统、建立现代调度指挥系统、发 展智能交通运输系统和开展电子商务的基础 1。 车辆调度问题是运筹学与组合优化领域的研究热点。有效的调度车辆，不仅可以提高物 流工作效率，而且能够为及时生产模式的企业提供运输上的保障，从而实现物流管理科学化。 由于该问题的理论涉及很多学科，很多实际问题的理论抽象都可归结为这一类问 题，研究该 问题具有很重要的理论意义和实际意义。 1 . VRP（ Vehicl

2、e Routing Problem）问题描述及其分类 VRP 问题一般可定义为：对一系列的装货点或卸货点，组织适当的行车路线，使车辆 有序地通过它们，在满足一定的约束条件 (货物需求量、发送量、车辆容量限制、行驶里程 限制、时间限制 )下，达到一定的目标 (路程最短、时间最小、费用最省、车辆数目最少等 )。 由于该问题研究范围非常广，根据其网络性能大致可以分为两类：一类为静态 VRP (StaticVRP, SVRP)，一类为动态 VRP (dynamic VRP, DVRP)。 (1) 静态 VRP问题描述 SVRP 问题是 VRP 中较简单的一类问题，是大部分研究者研究的热点。该问题具有一

3、 个很重要的特征：在安排初始路线时，和路线相关的所有信息已知，并且在安排路线以后其 相关信息始终保持改变 2。以下列举了一些常见的 SVRP 问题 :仅考虑车辆容量限制的VRP(CVRP)、带时间窗的 VRP(VRPTW)、带有回收的 VRP(VRP with backhauls)、带有集派的VRP(VRPPD)。除此以外，还有许多其它 CVRP 的延伸问题，如顾客 有优先权，考虑卸货时间、装卸时间、等待时间等，甚至综合了以上不同的特征。这些问题的相关信息均已知且保持不变 3。 (2) 动态 VRP问题描述 所谓 DVRP，是指在安排初始路线时，并不是和路线相关的所有信息都为已知，并且初始路线

4、安排以后，其相关信息可能发生改变。 DVRP 研究范围较广，需求不确定、动态网络、服务车辆不确定、提供数据有偏差等都属于 DVRP 的研究范畴。从网络性能角度， DVRP 可以分为以下三种类型： 1)时间依赖型 VRP (TDVRP)。 2)概率 VRP (PVRP)。车辆运行时间以离散或连续概率 发生变化。在这种网络中可用期望运行时间代替路径运行时间，再进行问题的求解。目前对该问题在最短路中研究比较多，一般是求得存在长度不超过给定值的路线概率及所给出路线为最短路的概率等 4。 3)时间依赖且概率变化的 VRP。 2. VRP问题算法描述 (1) 插入算法 插入算法是指通过 k 步迭代时，将第

5、 k 个节点插入到路线中。算法的关键在于确定在第 k+1 步可以被插入到路线中的点以及该点的最佳插入位置。因此，该算法由两个关键的部分组成。第一部分是节点选择阶段，即确定下一步被插入到路线中的顾客节点；第二部分是路径插 入阶段，即确定所选择的顾客节点在路线中的最佳插入位置 5。 (2) 节约算法 节约算法是一类最为经典的构造型启发式算法之一，该算法最早由 Clark 和 Wright 于1964 年提出 6，通常被简称为 C-W 算法。该算法的思想是：根据顾客点之间连接可以节省的距离（节约值）最大的原则，将不在线路上的顾客点依次插入到路线中，直到所有的点都被安排进路线为止。 (3) 最短路径算

6、法 用于解决最短路径问题的算法被称做 “ 最短路径算法 ” ， 有时被简称作 “ 路径算法 ” 。 最常用的路径算法有： Dijkstra算法 、 A*算法、 Bellman-Ford算法、 Floyd-Warshall算法、Johnson算法 7。 迪杰斯特拉提出的 Dijkstra算法 是最典型的最短路径算法 8。 (4) 遗传算法 遗传算法（ Genetic Algorithm，简称 GA）是美国 J.Holland 和他的学生于 1975 年受生物进化论的启发而提出并建立发展起来的。其基本思想是借鉴大自然生物进化中“适者生存”的规律，通过对产生的解（“父代”）不断操作（包括复制、交叉、

7、变异和竞争）以产生新的解（“子代”），如此反复迭代，最终收敛到“最适应环 境”的个体，从而得到相对比较好的解 9。 综上所述，各种优化方法在一定情况下都有各自的优点，都有解决某一问题的优越性。最优化算法有一个共同的特点就是可以求得最优解，但不适应现在的复杂的车辆优化问题，尤其是对多配送点的大型配送服务，相对求得最优解比较费时费力，且难以实现；而传统的启发式算法比最优化算法相对好些，但仍有不太适用于现在于现在实际遇到的问题，和现代启发式算法相比有些不足，但可以将各种算法结合使用，这样就更方便使用解决实际当中遇到的各种问题。 求解 VRP 问题时，我们旨在得到一系列路线，车辆 按照该路线来服务顾客

8、，在满足顾客需求的同时，使得总的运输费用最小。在设计这些路线时，还要根据不同问题考虑不同约束，设计的路线不能够违背相应的约束。 二、主题部分 1. VRP 问题研究的历史背景 1959 年， Dantzig 等人首先从旅行商问题（ Traveling Salesman Problem，简称 TSP 问题，）得到启发，提出了车辆分配问题 TDP（ Truck Dispatching Problem）。这是一类具有重要研究价值的问题。一方面，它代表了一类典型的组合优化问题，具有深远的理论意义；另一方面 ，它是一类重要的物流运输问题，直接影响着相关企业的运转效率，具有广泛的实践意义。半个世纪以来，许

9、多的专家学者对该问题进行了广泛而深入的研究，并将这类问题统称为车辆路径调度问题（ Vehicle Routing Problem，简称为 VRP 问题）。他们从基本问题出发，根据不同的约束和目标，构建了不同的模型，并有针对性地开发出了有效的算法 5。 2. VRP 问题 算法的发展现状 随着定位导航技术、数据通讯技术、自动控制技术、图像分析技术以及计算机网络和信息处理技术的快速发展，车辆优化调度问题作为智能交通系统的 一个重要组成部分，在很多国家受到关注。 80年代以来，随着 ITS研究领域和内容的不断深入发展，逐渐形成了美国、欧洲和日本三大智能交通体系，且三大体系研究方面各有侧重。目前，某些

10、常用且较成熟的算法并已被人们运用的有实际的动态车辆调度系统，美国利用最短路径算法、启发式算法开发计算机配送调度系统用来解决货运汽车作业计划路线优化选择和车辆分配等问题，使汽车里程利用率提高 5%-15%，运输成本和运输时间也有了明显下降。目前已经开发并应用于实践的动态车辆调度系统有美国 IBM公司开发的 VIIPX系统，其核心算法为最短路径算 法和启发式算法；日本富士通公司开发的 VSS系统，以节约为核心算法；美国美孚公司开发的 HOCAD系统，以扫描为核心算法 10。 由于该问题在交通运输、工业生产管理等领域具有广泛而重要的应用，因此近年来引起了人们极大的兴趣，运筹学、应用数学、组合数学、网

11、络分析、图论、计算机应用等学科的专家与运输计算制定者和管理者进行了大量的理论研究及实验析，取得了很大的进展。运用这些研究成果，车辆优化调度问题已被成功运用到邮件速递、出租车服务、奶品配送、生产计划、紧急服务等业务之中。车辆的优化调度问题是一种具有相当广泛实用价 值的学术研究问题，在理论上属于复杂的组合优化问题 11。 当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径。配送是物流系统中的一个重要环节，它是指按客户的订货要求，在物流中心进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。在配送业

12、务中，配送车辆调度问题的涉及面较广，需要考虑的因素较多，对配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大。该问题包括集货线路优化、货物配装及送货线路优化等，是 配送系统优化的关键。 3. VRP 问题算法的发展方向 相对于精确算法，启发式算法具有更好的工程实际应用价值。因为它既能够在合理的时间内得到问题的较优解，又能够使得到的较 优解的精度满足工程要求。从总结可以看到，启发式算法是一类基于直观或者经验设计而成的算法，因而算法设计具有较高的灵活性和较大的自由度 12。 另外，随着人们对 VRP问题研究的深入以及对 VRP问题解的质量要求的提高，人们开始 研究如何在算法中加进人的主观

13、判断以提高解的质量，比如如何在行驶过程中判断到仓库补 货的时机，这归结为补货策略问题；另外 ，人们也开始研究如何结合顾客库存的情况来制定 运输策略的问题，这归结为库存运输问题；诸如此类的研究尚处于起步阶段，因此具有很大的研究潜力和意义。 4. VRP 问题算法的主要应用 随着定位导航技术、数据通讯技术、自动控制技术、图像分析技术以及计算机网络和信息处理技术的快速发展，该问题在交通运输、工业生产管理等领域具有广泛而重要的应用。 (1) 智能交通系统车辆调度中的应用 13。 在智能交通系统 (ITS,Intellignet Transportation Systems)的各个子系统中 ,先进的公共

14、交通系统 (APTS,Advanced Public Transportation System)具有重要地位和作用 ,其中车辆调度问题是 APTS 的关键 .为了提高车辆调度的智能化 ,提出了一种基于遗传算法(GA,Genetic Algorithm)的公交车辆智能调度方法 ,采用最小费用作为目标函数 ,考虑了车辆配置、时间、运营效率及资源利用等方面因素 ,通过选择、交叉及变异等遗传操作 ,得到了最优的调度排序方案 ,并对 2种交叉方式进行了比较 ,仿真结果表明 ,利用 GA解决车辆调度问题具有可行性、先进性和快速性 . (2) 物 流管理 14。 车辆 调度 问题是物流管理研究中的一项重要

15、内容。选取恰当的车辆路径 ,可以加快对客户需求的响应速度 ,提高服务质量 ,增强客户对物流环节的满意度 ,降低服务商运作成本。 (3) 动态车队管理 15。 开展货物运输作业的优化组织工作是降低运输成本、提高运输效率的重要手段和关键。货运车辆作为货物运输的直接载体，同时也是货物运输作业过程中最重要的可支配资源。运用所掌握的车辆资源合理安排组织运输任务，消除对流、迂回、重复等不合理现象，实现车辆的优化组合与配置，并达到以最少的资源投入获得最优经济效益的 目的，是整个货物运输优化组织工作的核心内容。车队管理问题的研究就是在这种背景与需求下提出的，通过对货运车辆的科学有效管理，可以大大提高车辆利用率

16、，实现货物运输科学化。同时，对车队管理问题展开系统化地研究工作也是构建高效的货物运输组织体系、建立现代调度指挥系统、实现物流集约化和科学化、发展智能交通运输系统的基础与关键。 三、总结部分 VRP 问题自从被提出来以后就受到了广泛的关注，不少学者对求解该问题的算法进行了研究，并取得了不少成果。 VRP模型方面虽有许多研究，但缺少综合方面的研究。现代物流中，要求尽量减 少库存，及时配送变得越来越重要，所以今后满足客户的时间窗口是制定车辆路线优先考虑的重点。还有现有的配送路线的研究多为开发静态的模型，很少分析参数随时间变化的特性，而在现代物流日趋快速化、信息化、实时化的情况下已经有些不适应。例如，

17、仓库位置的成本将随时间变化；在一定的时间范围内，公司需要根据情况的变化来重新决策配送中心及销售网点的分布。因此，在配送路线模型中加入动态特性，实现实时或在线物流管理，会极大地提高与现实接近的程度。 目前对 VRP 问题的研究，大部分还停留在 SVRP 问题上。从近几年的文献可以发现， 已经有一些关于 TDVRP 的模型及算法的研究。 SVRP 问题研究为 DVRP 问题研究奠定了理 论基础， DVRP 问题更贴近实际，随着研究的不断深入，其理论成果不仅可以在物流、供应链优化、通信线路设计等相关领域得到广泛应用，还可以促进智能交通系统的发展，有助于物流配送与发达的交通系统相结合，对于节约能源、提

18、高物流工作效率、优化交通资源、改善城市交通状况也将起到十分重要的作用。这将是 VRP领域未来研究的热点。 本课题研究的研究旨在通过应用动态规划思想，改进求解 VRP问题的节约法，建立不断增加节约量的动 态规划数学模型，使其能够得到全局最优解，并将此算法应用于一种实际中。 四、参考文献 1 贾永基 .车辆调度问题优化算法研究 D;上海交通大学 ;2004. 2 Larsen A.The dynamic vehicle routing problemD. Dept. of Mathematical Modelling, Technical University ofDenmark, 2000. 3

19、 李妍峰 ,李军 ,赵达 .车辆调度问题研究现状及展望 D.四川成都， 2005. 4 Ali Haghani, Jung Soojung. A genetic algorithm for vehicle routing problem with time dependent travel timesJ. Computers and Operations Research, 2005, 32: 29592986. 5 杨燕旋 ,宋士吉 .车辆调度问题的启发式算法综述 D.北京：清华大学自动化系， 2007. 6 Clarke G, Wright JW. Scheduling of vehicl

20、es from a central depot to a number of delivery points. Operations Research 1964;12(4):68-81. 7 彭立云 .最短路径 算法 Dijkstra 算法 EB/OL;http:/ 2009/09/23/1572509.html:2009-09-23/13:05. 8 严蔚敏 ,吴伟民 .数据结构（ C 语言版） M.北京：清华大学出版社， 2007. 9 蔡自兴 ,徐光佑 .人工智能及其应用 M.北京 :清华大学出版社， 2003. 10 张艳 .基于动态规划改进求解 VRP问题的节约法的研究 D.大连 :

21、大连海事大学交通工程与物流学院 ,2006. 11 张丹羽 .现代物流配送中心车辆线路优化方案研究与应用 D.山东 :山东大学， 2005. 12 赵振华 ,王杰 ,娄春 .基于物流配送中车辆路径问题的模型及算法的研究 EB/OL.http:/ www.lunwentianxia. free.10001560.3/:2009-2-19. 13 范秋生，潘纹 .遗传算法在智能交通系统车辆调度中的应用 EB/OL; Article/CJFDTotal-JSSG200705010.htm; 2007-05-010. 14 刘云忠 ,宣慧玉 ;车辆路径问题的模型 及算法研究综述 J;管理工程学报 ;2005 年 01 期 . 15 李冰 ;动态车队管理问题的模型及算法研究 D;西南交通大学 ;2003.