车辆路径问题研究综述及展望.doc

车辆路径问题：研究综述及展望Vehicle Routing Problem: Research Status and Prospect摘要：车辆路径问题是物流系统优化中的关键内容之一，是现代物流管理研究中的重要内容。本文梳理分析了车辆路径问题 (VRP)的分类、模型及算法等，详细综述了多车型、多车场、时间窗车辆路径问题研究现状，指出联盟车辆调度问题、考虑车辆（供应）时间窗的车辆调度问题可能是VRP问题未来的新的研究趋势。关键词：车辆路径；多车型；多车场；时间窗中图分类号：F253.4 文献标识码：A 最后指出Abstract: Vehicle routing problem as a key content in the logistics system optimization, is an important component of modern logistics management study. This paper summarizes the classification, model and algorithm of the vehicle routing problems, and then detailed reviews the research status of the HVRP , MDVRP and VRPTW. The article finally points out that the AVRP and considering the vehicle (supply) time window of the VRP may be the new research trends of the future. Key words: vehicle routing; heterogeneous vehicle; multi-depot; time window车辆路径问题是运输组织优化中的核心问题，也是运筹学中的一类经典的组合优化问题，旨在借助构造适当的车辆行驶路线以实现运输成本的最优化。随着市场经济的发展和物流专业化水平的提高，车辆路径问题从提出之初就受到广泛关注。到目前为止，该问题的应用不仅仅局限在汽车交通运输领域，在航空、通讯、电力、工业管理和计算机应用等领域也有一定的应用。1 车辆路径问题车辆路径问题来源于交通运输，最早是由Dantzig和 Ramser Dantzig G, Ramser J. The truck dispatching problem. Management science,1959, (6): 80-91.于1959 年发表在Management Science上的文章The truck dispatching Problem中首次研究了亚特兰大炼油厂向各加油站发送汽油的运输路径优化问题，并提出了基于线性规划的求解过程。在随后的几十年里，VRP问题得到不断的扩充和发展。1.1 分类自车辆路径问题被提出后，Linus（1981），Bodin和Golden（1981），Assad（1988），Desrochers（1990）等许多学者从不同视角，按不同标准对该问题进行了分类 李军，郭耀煌. 物流配送车辆优化调度理论与方法.北京：中国物资出版社，2001,6.，例如：按车辆类型分，可分为单车型问题和多车型问题；按配送中心（车场）数目分，可分为单配送中心（车场）问题和多配送中心（车场）问题；按任务特征分，可分为纯送（取）货问题和装卸混合问题；按有无时间约束分，可分为无时间窗问题和有时间窗问题，另外可以按车辆装载情况、按优化目标数、按车辆对车场的所属关系、按已知信息的确定性分等不同分类标准进行分类。1.2 模型及算法车辆调度问题是一个较为复杂的组合优化问题, 可以从不同的角度进行建模。一般来说，车辆调度问题可以构造成整数规划模型，也可以构造成图论及其他模型，这些模型之间存在着某种联系，但从建立模型时的出发点考虑，大多数模型均可看作是几种模型的变形与组合。自车辆路径问题提出以来，国内外学者对于不同类型的车辆调度问题提出了许多不同的数学模型，并提出了许多获得问题最优解或次优解的算法。车辆路径问题的求解方法，基本上可分为精确算法、启发式算法和亚启发式算法三大类，具体分类情况如表2所示。表1 车辆路径问题的算法分类 唐连生,梁剑. 突发事件下的车辆路径问题研究综述J. 铁道运输与经济,2008,12:56-60.技术路线算法名称学者精确算法分支定界法Laporte1986)割平面法Kelley(1960)动态规划法Eilon (1971)网络流算法 XU和KELIY(1996)启发式算法节约法 Clarke和Wright (1964)两阶段法Lin(1965)扫描法 Gillett和Miller (1974)数学规划方法Kohld(1997)亚启发式算法遗传算法John Holland(1975)模拟退火算法Kirkpatrick (1983) 禁忌搜索算法Gendrean等(1994)蚁群算法Dorigo(1991)目前在车辆路径问题模型研究方面，都是从不同角度、不同方向开展，例如结合实际考虑时间窗、车场数、车型等要素，各有侧重。在算法研究中，国内外都进行了大量的算法研究，从六十年代的集中在各种形式的节约算法，到七、八十年代提出了各式各样的基于数学规划的算法，八十年代后期时至今日，各种智能算法和并行算法的广泛应用 Fisher M L, Vehicle routing problemJ, Operations Research and Management Science,1995(8),P1-33.。由于基本VRP问题属于NP-hard问题，使得各类VRP问题求解难度更加复杂，仍值得进一步研究。从现有研究文献看，围绕车辆路径问题的研究非常广泛，在此我们从多车场、多车型、有时间窗VRP问题三方向对现有研究文献进行综述，并结合社会经济发展所带来的新变化，对VRP问题未来研究趋势提出看法。2 多车型车辆路径问题综述多车型车辆路径问题是车辆路径问题的一种扩展。根据车辆的型号是否相同，可将车辆路径问题分为单车型问题(Homogeneous Vehicle Routing Problem, VRP)和多车型问题(Heterogeneous Vehicle Routing Problem, HVRP)。单车型问题假定车辆的型号相同，即具有相同的最大载重量与最大行驶距离以及相同的固定成本与变动成本，而多车型问题则不同，通常各车型的最大载重不同或使用成本不同。自1984年Golden等首先研究了多车型车辆路径问题以来，国内外学者针对多车型车辆路径问题的求解算法进行广泛探索。例如：Gendreau等 Gendreau M,Laporte G, Musaraganyi C,et al. A tabu search heuristic for the heterogenous fleet vehicle routing problem J. Computers & Operations Research, 1999,26(12):1153-1173.(1999)用禁忌搜索研究了每种车型的数量是无限的HVRP问题，即FSMVRP问题。Taillard等 Taillard E D. A heuristic column generation method for the heterogeneous fleetVRP. Report: Centre for research on transportation, University of Montreal.1999, 1-14.(1996) 提出了列产生启发式算法求解多车型的车辆路径问题。叶志坚，叶怀珍等叶志坚,叶怀珍,周道平,易海燕. 多车型车辆路径问题的算法J. 公路交通科技,2005,05:147-151. (2005)总结了国外五种求解多车型问题的启发式算法的优缺点，并提出了禁忌搜索算法和大旅程法相结合的混合启发式算法。3 多车场车辆路径问题综述多车场车辆路径问题(Multi-Depot Vehicle Routing Problem, MDVRP)是基本车辆路径问题的扩展，指的是有数个车场同时对多个用户进行服务，要求对各车场的车辆和行驶路线进行适当的安排，在保证满足各用户的需求的前提下，使总的运输成本最低。多车场车辆路径问题，实际上不仅是路径问题，它还涉及到了场站的选择和分配问题，一般可以分解为两个子问题：将顾客分派给场站；为每个场站优化线路。目前国内外关于多车场车辆调度问题的研究主要集中在算法的改进上，从传统的启发式算法的应用到现在集中于现代启发式算法的应用，同时注重结合实际运行情况，对多车场问题进行扩充。例如：Klots等 Klots B, Gal S, Harpaz A. Multi-depot and multi-product delivery optimization problem with time and service constraintsR.IBM Israel, Haifa,Israel, 1992.（1992）将线性规划和启发式算法结合起来求解MDVRP；Polacek等Polacek M, Hartl R F, Doerner K. A variable neighborhood search for the multi depot vehicle routing problem with time windowsJ.Journal of heuristics, 2004, 10(6):613-627.（2004）提出一种求解MDVRPTW的变邻域搜索算法算法；邹彤等邹彤,李宁,孙德宝,李菁.多车场车辆路径问题的遗传算法J.计算机工程与应用,2004(21):82-83.（2005）用遗传算法求解MDVRP问题。此外，在MDVRP基础上增添时间窗、路况情况、客户优先级等约束条件，使问题更具研究价值，例如：陈美军等陈美军,张志胜,史金飞.MDVRPMC问题的智能多态蚁群算法研究C/会议/论文集缺失,2007:621-628.（2007）在研究考虑了客户优先级、路况影响、时间窗等多约束情形下的MDVRP问题。4 带时间窗的车辆路径问题综述带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows, VRPTW)是基本车辆路径问题的扩展问题，即在VRP问题的基础上给每个客户加上服务所允许的时间窗约束。时间窗则是一个时间段，由客户要求的最早服务时间和最晚服务时间确定的一个服务时间区间。这里的时间窗是从客户角度出发，即可称为客户（需求）时间窗。因此考虑VRPTW问题，不仅需要在空间上进行车辆路径规划，而且还需要在时间上进行合理的安排。目前国内外学者对VRPTW问题的研究主要集中在算法研究上。Cordeau等 Cordeau J F, Laporte G, Mercier A. A unified tabu search heuristics for vehicle routing problems with time windows J. Journal of the Operational Research Society, 2001, 52(8):928-936.（2001）提出了求解VRPTW问题的通用的禁忌搜索算法；李宁，邹彤等李宁,邹彤,孙德宝. 带时间窗车辆路径问题的粒子群算法J. 系统工程理论与实践,2004,04:130-135.（2004）将粒子群算法(PSO)应用于带时间窗车辆路径问题(VRPTW)中。而且在研究VRPTW问题的过程中，同时也注重对VRPTW问题的扩充，例如结合多车场、满载、开放式、车辆租赁等因素，使研究点更具现实意义。例如：于滨，靳鹏欢等于滨,靳鹏欢,杨忠振. 两阶段启发式算法求解带时间窗的多中心车辆路径问题J. 系统工程理论与实践,2012,08:1793-1800.（2012）提出一个两阶段的启发式算法来求解MDVRPTW；孙国华（2012）孙国华. 带时间窗的开放式满载车辆路径问题建模及其求解算法J. 系统工程理论与实践,2012,08:1801-1807. 建立带时间窗的开放式满载车辆路径问题模型，并设计了改进的自适应遗传算法进行开环路径求解。 5 车辆路径问题研究趋势随着社会经济的快速发展，消费者对服务质量要求越来越高，物流作为生产性服务产业，作用日益凸显。车辆路径问题作为物流系统优化中的关键一环，也对之提出更高要求。然而市场竞争的日趋激烈，使得企业间的竞争更加白热化，企业与企业间的竞争，开始转变为联盟与联盟的竞争，企业面临更大的压力与挑战。随着信息技术与互联网技术的突飞猛进，特别是电子商务的快速发展，联盟车辆调度问题则会成为车辆路径问题的一个新的应用研究领域。例如：菜鸟网络科技有限公司、重庆市农业电子商务产业发展联盟的成立，都是通过组建联盟方式，利用互联网技术，有效整合