车辆路径问题：研究综述及展望VehicleRoutingProblem:ResearchStatusandProspect摘要：车辆路径问题是物流系统优化中的关键内容之一，是现代物流管理研究中的重要内容。本文梳理分析了车辆路径问题(VRP)的分类、模型及算法等，详细综述了多车型、多车场、时间窗车辆路径问题研究现状，指出联盟车辆调度问题、考虑车辆（供应）时间窗的车辆调度问题可能是VRP问题未来的新的研究趋势。关键词：车辆路径；多车型；多车场；时间窗中图分类号：F253.4文献标识码：A最后指出Abstract:Vehicleroutingproblemasakeycontentinthelogisticssystemoptimization,isanimportantcomponentofmodernlogisticsmanagementstudy.Thispapersummarizestheclassification,modelandalgorithmofthevehicleroutingproblems,andthendetailedreviewstheresearchstatusoftheHVRP,MDVRPandVRPTW.ThearticlefinallypointsoutthattheAVRPandconsideringthevehicle(supply)timewindowoftheVRPmaybethenewresearchtrendsofthefuture.Keywords:vehiclerouting;heterogeneousvehicle;multi-depot;timewindow车辆路径问题是运输组织优化中的核心问题，也是运筹学中的一类经典的组合优化问题，旨在借助构造适当的车辆行驶路线以实现运输成本的最优化。随着市场经济的发展和物流专业化水平的提高，车辆路径问题从提出之初就受到广泛关注。到目前为止，该问题的应用不仅仅局限在汽车交通运输领域，在航空、通讯、电力、工业管理和计算机应用等领域也有一定的应用。1车辆路径问题车辆路径问题来源于交通运输，最早是由Dantzig和Ramser[1]于1959年发表在《ManagementScience》上的文章《ThetruckdispatchingProblem》中首次研究了亚特兰大炼油厂向各加油站发送汽油的运输路径优化问题，并提出了基于线性规划的求解过程。在随后的几十年里，VRP问题得到不断的扩充和发展。1.1分类自车辆路径问题被提出后，Linus（1981），Bodin和Golden（1981），Assad（1988），Desrochers（1990）等许多学者从不同视角，按不同标准对该问题进行了分类[2]，例如：按车辆类型分，可分为单车型问题和多车型问题；按配送中心（车场）数目分，可分为单配送中心（车场）问题和多配送中心（车场）问题；按任务特征分，可分为纯送（取）货问题和装卸混合问题；按有无时间约束分，可分为无时间窗问题和有时间窗问题，另外可以按车辆装载情况、按优化目标数、按车辆对车场的所属关系、按已知信息的确定性分等不同分类标准进行分类。1.2模型及算法车辆调度问题是一个较为复杂的组合优化问题,可以从不同的角度进行建模。一般来说，车辆调度问题可以构造成整数规划模型，也可以构造成图论及其他模型，这些模型之间存在着某种联系，但从建立模型时的出发点考虑，大多数模型均可看作是几种模型的变形与组合。自车辆路径问题提出以来，国内外学者对于不同类型的车辆调度问题提出了许多不同的数学模型，并提出了许多获得问题最优解或次优解的算法。车辆路径问题的求解方法，基本上可分为精确算法、启发式算法和亚启发式算法三大类，具体分类情况如表2所示。表1车辆路径问题的算法分类[3]技术路线算法名称学者精确算法分支定界法Laporte1986)割平面法Kelley(1960)动态规划法Eilon(1971)网络流算法XU和KELIY(1996)启发式算法节约法Clarke和Wright(1964)两阶段法Lin(1965)扫描法Gillett和Miller(1974)数学规划方法Kohld(1997)亚启发式算法遗传算法JohnHolland(1975)模拟退火算法Kirkpatrick(1983)禁忌搜索算法Gendrean等(1994)蚁群算法Dorigo(1991)目前在车辆路径问题模型研究方面，都是从不同角度、不同方向开展，例如结合实际考虑时间窗、车场数、车型等要素，各有侧重。在算法研究中，国内外都进行了大量的算法研究，从六十年代的集中在各种形式的节约算法，到七、八十年代提出了各式各样的基于数学规划的算法，八十年代后期时至今日，各种智能算法和并行算法的广泛应用[4]。由于基本VRP问题属于NP-hard问题，使得各类VRP问题求解难度更加复杂，仍值得进一步研究。从现有研究文献看，围绕车辆路径问题的研究非常广泛，在此我们从多车场、多车型、有时间窗VRP问...