车辆路径优化文献综述

车辆路径优化文献综述肖建辉（广东女子职业技术学院，广东广州511450）摘要：车辆调度问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 （VRP，VehicleRoutingProblem)是现代物流系统研究中的一项重要内容.选取合适的运输路线，可以加快对客户需求的响应速度，提高服务质量，降低服务商的运营成本.本文就车辆路径问题的模型和求解方法对前人的研究成果进行回顾与梳理.关键词：车辆调度问题；现代物流；优化中图分类号：U9文献标识码：A文章编号：1672-402X（2010）02-0031-07收稿日期：2010-04-03作者简介：肖建辉（1975-），女，湖南长沙人，广东女子职业技术学院经济师，高级物流师，北京交通大学物流工程硕士。研究方向：物流技术。车辆路径问题（VehicleRoutingProblem，简称VRP）［1］，又称为车辆调度问题，通常可以描述为：对一系列装货点和卸货点，组织适当的行车路线，使车辆有序地通过他们，在满足一定的约束条件(如货物需求量、发送量、交货时间、车辆容量限制、行使里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)，并返回车辆停放场地.车辆调度问题VRP(VehicleRoutingProblem)是现代物流系统研究中的一项重要内容.选取合适的运输路线，可以加快对客户需求的响应速度，提高服务质量，降低服务商的运营成本.下面，本文就从车辆路径问题的模型和求解方法对前人的研究成果进行回顾与梳理.1车辆路径问题的模型车辆路径问题涉及到的各因素是车辆路径问题分类的依据.Bodin(1983)等人将影响车辆路径问题的主要因素整理如表1所示［2］.目前已知的研究模型是对这些因素中的一种或几种的组 合同 劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载 时忽略其他因素建立的.车辆路径问题的主要模型如下［3］：（1）按起讫点划分为：一是起讫点不同的单一车辆路径问题；二是多个起讫点的车辆路径问题；三是起讫点相同的车辆路径问题.（2）按照有无车辆容量限制分为：有能力约束的车辆路径问题(CapacitatedVehicleRoutingProblem，CVRP)和没有能力约束的车辆路径问题.CVRP是指任意车辆路径的总重量不能超过该车辆的重量或体积的能力负荷.（3）有时间窗约束和无时间窗约束的车辆路径的问题.包括硬时间窗(HardTimewindows)和软时间窗(SoftTimewindows)约束.引出带时间窗(包括硬时间窗和软时间窗)的车辆路径问题(VehicleRoutingProblemwithTimewindows，VRPTW).如果到达任务点的时间是事先规定的，则称该问题是带时间窗要求的车辆优化调度问题；若到达和离开时间没有规定，则称该问题就是一个直接的线路安排问题.带时间窗的VRP又可分为硬时间窗VRP和软时间窗VRP.硬时间窗VRP指每项任务必须在要求的时间内完成，软时间窗VRP指如果某项任务不能在要求广东技术师范学院学报（自然科学）2010年第2期JournalofGuangdongPolytechnicNormalUniversityNo.2，2010第2期肖建辉：车辆路径优化文献综述的时间范围内完成，则给予一定的惩罚.（4）满载和非满载的车辆路径问题.当每个客户需求量小于车辆容量时，用一辆车执行一项任务就存在不满载运行情况，调度时可安排一辆车执行多项任务，即在一辆车上装载不同货主的货物，这类问题称为非满载VRP.当然，这类问题有一个前提条件，即不同货主的货物允许混装.当每个客户需求量大于车辆容量时，用一辆车执行一项任务就不能满足客户的需求，此时需要一辆以上的车对其进行送货，车辆能够满载，该问题称为满载VRP.（5）单车场和多车场的车辆路径问题(SingleandMulti-DepotVehicleRoutingProblem).单车场车辆路径问题是指所有的车辆均从一个配送中心发出，完成各自的任务后都返回该配送中心.多车场车辆路径问题是指，存在着多个配送中心，车辆可以从任何一个配送中心派出，完成任务后，车辆也可以返回其中的任何一个配送中心，随着供应链的集成一体化，多车场的车辆路径问题将越来越多、越来越重要.对于这类问题可以通过一定的方法将其转化为单车场的车辆路径问题.（6）按车辆类型数量分为：单车型问题(所有配送车辆的载重量相同)和多车型问题(配送车辆的载重量不完全相同)(Mixed/HeterogeneousFleetVehicleRoutingProblem.MFVRP/HFVRP).（7）按车辆对车场的所属关系分为：开路车辆路径问题(OpenVehicleRoutingProblem)（即车辆完成配送任务后可以不返回其发出车场)和封闭车辆路径问题(即车辆完成配送任务后必须返回其发出车场).（8）按配送任务特征分：纯送货问题、纯取货问题、取送混合问题(VehicleRoutingProblemwithPick-upandDelivery,VRPPD).纯送货问题仅考虑从物流中心向客户送货，也称为纯卸问题；纯取货问题仅考虑把各客户供应的货物取到物流中心，也称为纯装问题；VRPPD既考虑将客户需求的货物从配送中心送到各个客户，同时考虑将客户供应的货物从客户取到物流中心，也称为装卸混合问题或集货和送货一体化问题.（9）确定型需求车辆路径问题、模糊需求车辆路径问题(FuzzVehicleRoutingProblem,FVRP)、随机需求车辆路径问题(VehicleRoutingProblemwithStochasticDemand，VRPSD).随机需求车辆路径问题目前主要研究的是随机客户、随机需求、随机时间这三方面的内容.随机客户问题在物流领域经常会出现.随机需求车辆路径问题(VRPSD)，虽然知道确切的客户，却无法知道客户的准确需求量.模糊需求车辆路径问题FVRP：在实际的车辆调度中，某些待服务客户的需求信息没有或无法给出准确的描述，所以就需要将模糊概念引入模型和算法来解决这类问题；另一种形式是将模糊概念引入时间窗，通常客户需要服务的时间虽然有一个范围，但是一个模糊量.车辆在客户要求的范围内到达都是可行的，但到达的时间不同，客户的满意度可能不同，这类问题同时是多目标优化的问题.（10）周期性的车辆路径问题(PeriodicVehicleRoutingProblem,PVRP).周期性车辆路径问题是对VRP的扩展，VRP研究的是对车辆的日安排，而PVRP是对车辆的一个周期内多日的安排.在一个周期内，每个客户在满足需求的前提下，最少被服务一次，也可以是多次.（11）非对称网络车辆路径问题(AsymmetricNetworkVehicleRoutingProblem,AVRP).非对称网络车辆路径问题在现实生活中比较常见，如单行道或禁止左转等交通标识的存在，使得从甲地到乙地，和从乙地到甲地的距离(或时间)并不相同.由于非对称网络的这个特性，使得许多在VRP中成功应用的算法不能直接用于非对称网络的求解，目前的许多求解算法都是基于非对称TSP问题的算法而来的［4］.（12）按目标多少分为：单目标车辆路径问题和多目标车辆路径问题.单目标车辆路径问题仅考虑一个配送目标；多目标车辆路径问题同时考虑多个配送目标，比如说同时考虑里程最短、费用最少、时间最短等.另外还有相容性约束车辆路径问题(VehicleR-outingProblemwithCompatibilityConstraints,VR-PCC)，优先约束车辆路径问题(VehicleRoutingProb-lemwithprecedenceConstraints,VRPPC)，带回程运输的车辆路径问题(VehicleRoutingProblemwithBackhauls,VRPB)，分散配送车辆路径问题(SplitDe-liveryVehicleRoutingProblem,SDVRP).SDVRP与一般车辆路径问题的不同在于允许一个客户被两辆或者多辆车配送，该问题是Dro和Trudeau在1989年提出的，该问题的求解算法多用启发式算法［5-6］.随着社会的发展，VRP也在不断的发展变化，一些新要素也出现了并对研究起着至关重要的作用，如仓储配送一体化优化的库存路径问题(Inventory32··第2期RoutingProblem，IRP)等［7］.VRP的主要优化目标有：①配送总里程最短.配送里程与配送车辆的耗油量、磨损程度以及司机疲劳程度等直接相关，它直接决定配送的成本，对配送业务的经济效益有很大影响.由于配送里程计算简便，它是选择配送路线时用得最多的指标.②配送总费用最低.降低综合费用是实现配送业务经济效益的基本要求.在配送中，与取送货有关的费用包括：车辆维护和行驶费用、路桥费、车队管理费用、货物装卸费用、有关人员工资费用等.③配送总时间最短.配送总时间是在一定配送任务下，各条配送线路配送时间之和.配送时间的长短衡量企业对客户需求响应速度的快慢，同时也反映了车辆使用的周转速度，影响车辆的利用率，它是选择配送线路的一个重要指标之一.④配送车辆的吨公里数最少.该目标将配送距离与车辆的载重量结合起来考虑，即以所有配送车辆的吨位数(最大载重吨)与其行驶距离的乘积的总和最少为目标.⑤准时性最高.由于客户对交货时间有较严格的要求，为提高配送服务质量，有时需要将准时性最高作为确定配送路线的目标.⑥运力利用最合理.该目标要求使用的较少的车辆完成配送任务，并使车辆的装载率最高，以充分利用车辆的装载能力.常见的模型有运筹学模型、图论模型、EXCEL模型，罗晓玲（2006）在《公司物流输配送系统的优化建模及求解》一文中建立VRP问题的EXCEL模型并求解.2车辆路径问题的求解方法配送车辆路径问题是世界公认的NP难题.国外不少学者对其计算的复杂性进行了研究.Lenstra和RinnooyKan［3］在文献中，对VRP求解的复杂性进行了综述和 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ；Dantzig和Fuikerson（1954）分析了有确定开始时间的配送车辆路径问题的复杂性；Savelsbergh(1985)和Solomon(1986)提出有时限的物流配送车辆调度问题比一般的物流配送车辆调度问题更复杂；Savelsbergh(1985)提出有时限的物流配送车辆调度问题不仅问题本身是NP难题，甚至在车队大小固定时，找一个可行解也是NP难题；Lenstra和RinnoopyKan还证明了几乎所有类型的物流配送车辆调度问题均为NP难题.配送车辆路径问题作为一个NP难题，随着客户数量的增加，可选的配送路径数量将以指数速度急剧增长，即出现组合爆炸现象.据计算，对于一个有20个顶点的TPS(TravelingSalesmanProblem，即旅行商问题)，其可能的路径数为20！/（2*20）≈6.08*1016，即使用每秒一亿次的计算机按穷举搜索法求解，也需要计算350年［8］.配送车辆路径问题是一个约束性多路旅行商问题，与TSP相比，不仅约束条件更复杂，而且存在多条配送路径，因此计算量将比TSP大得多.配送路径问题的复杂性使许多专家学者转向对VRP问题的求解方法的研究，概括如下：国外研究情况.1983年Bodin.Golden等人在他们的综述文章中列举有700余篇有关文献.在Christofides(1985)，Golden和Assad(1988)编辑的 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 集中，以及Altinkeme和Gavish(1991)，Laporte(1992)，Salhi(1993)等的综述文章中都对该领域的研究成果进行了详尽的阐述.近年来，有很多国外学者利用多种算法对物流配送车辆调度问题进行了求解.该研究领域的代表人物主要有：Bodin，Christofides，Golden，Assad，Ball，Laporte，RinnooyKan，Lenstra，Desrosiers和Desrochers等［3］.其中Bodin（1983）等人将VRP求解方法划分为七种，分别是：（1）先分群再派路线(clusterfirstroutesecond)：先将需求点分成几组群落，然后在依各个群落寻找最佳车辆路径.Gillett和Miller(1974)所提出的Sweep算法则是属于这种方式，其利用极坐标的方式表示各个需求点的位置，取任一点为起始位置，命其角度为零，以顺时针和逆时针分割车辆服务区域，而每个区块再依旅行商问题的演算法求解.（2）先排路线再分群(routefirstclustersecond)：首先为所有需求点建立一条经济路线(可为非可行解)，再依车辆的容量限制，拆成多个适合的路线.如Golden等人(1974)所提出的巨网分割法(GiantTourAlgorithm).（3）节省法或插入法(SavingsorInsertionProce-dure)：此法针对现有路径做连接(new-join)、并入(at-tach)、合并(merge)等三种方式结合路径.如ClarkeandWright(1964)的节省法［9］.（4）改善与交换法(ImprovementorExchangePro-cedure)：此法为改善现有的可行解，将某路线中的连线与另一路线的连线相互交换，以得到较佳解，如Lin(1973)的2-opt法，ChristofidesandEilon(1969)的肖建辉：车辆路径优化文献综述33··第2期3-opt法、Or-opt法等.（5）数学 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 法(MathematicalProgrammingAp-proaches)：如FisherandJaikumar(1981)利用数学规划法，将VRP分解成一般指派问题和TSP问题，先解决指派问题，再针对每辆车作TSP问题求解.（6）人机互动法(InteractiveOptimization)：决策者可以透过人机互动详细了解实际状况，并根据以往经验及相关知识等进行各项设定与修订，以做出最佳决策.（7）最佳解法(ExactProcedure)：如分支界限法(BranchandBound)，动态规划法(DynamicProgram-ming)，切平面法(CuttingPlane).国内也有一些对配送车辆路径问题的研究.袁庆达等［10］用GENIUS(GENeralizedInsertion,UnstringandString)算法和TabuSearch相结合的混合策略优化配送线路.肖鹏等［11］利用单亲遗传算法解决车辆调度问题.张涛［12］等用禁忌搜索算法和遗传算法相结合的混合算法求解了不确定车辆数的VRP.方跃建等［13］针对非满载车辆调度问题，提出了自适应遗传算法.孙华丽等［14］用暂态混沌神经网络启发式算法解决了带容量约束的多车调度问题.丰伟等［15］用粒子群算法(PSO)求解了带时间约束的多目标车辆调度问题.王海星等［16］提出了一种重新设定转移规则和轨迹更新规则、改进算法转移策略和信息素更新策略的求解有时间窗约束VRP的改进的蚁群算法.宋康等［17］等针对多目标车辆路径问题，提出了改进的遗传算法.吕雄伟［18］等采用遗传算法求解了随机需求下带时间窗的库存-运输一体化问题.黄敏芳［19］等提出了将模糊聚类分析法和带控制策略的深度优先搜索算法相结合的车辆路径问题三阶段算法.张海刚［20］针对带时间窗约束的车辆调度问题，提出了多相粒子群优化算法(Multi-pha-sesParticleSwarmOptimization,MPSO).霍佳震［21］等提出了基于节约值比较的解决带有时间窗的满载车辆调度问题的节约法.刘浩［22］等用两阶段的模拟退火算法求解了两种车型随机需求的车辆路径问题.王志坚［23］针对一体化集货和配送车辆路径问题，提出了采用自然数编码、用改进的顺序交叉算子、对混合遗传算法求得的精英种群进行禁忌搜索求解的混合遗传启发式算法.张景玲［24］等用量子进化算法和改进的蚁群算法、两阶段算法相结合的混合策略对动态车辆路径问题进行了求解.袁健［25］等用神经网络法求解了随机需求的车辆路径问题.袁庆达、杜文、雷邦军等［26-28］针对随机需求的库存-运输联合优化问题提出了求解算法.彭北青、张建勇、张海刚、谢小良等［29-32］对模糊需求车辆路径问题进行了研究.近年来，郭耀煌、李军、谢秉磊、周双贵［33-44］等对车辆调度问题进行了较为深入的研究，提出了多种求解方法.求解VRP问题的方法很多，实质上可分为三大类：精确算法、纯启发式算法和智能算法.2.1精确算法精确算法是求出最优解的算法，主要有：分枝定界法、割平面法、网络流算法、动态规划法等.由于精确算法的计算量一般会随着问题规模的增大呈指数增长，只有在客户数量较少、运输网络较简单时，才能求得物流配送车辆调度问题的精确最优解，在实际中其应用范围很有限，所以专家学者们主要把精力花在构造高质量的启发式算法和智能算法上.2.2启发式算法（1）节约法(SavingMethod)节约法的理论依据是数学定理：三角形的两边之和大于第三边.该方法的思想是将每个配送点作为一条线路，全部线路构成的集合作为初始解.将一个点与另个点相连合并成一条新的线路.如果合并的线路能满足约束条件，则合并是可行的，并将合并的节约参数值（如里程、时间等）定义为连接这两条线路的节约值.从所有合并线路中选择节约值最大的边进行一次线路合并，当合并不可行，算法结束.节约法可以得到满意解，但不一定能保证为最优解.此方法的优点是思路简单、清晰；计算步骤简单，计算速度快；易于考虑各种实际问题；有利于提高车辆装载率.（2）邻接法(Nearest-Neighbor)邻接法是一种构造序列路线法.该算法的思路是从一条只含一个配送点的线路出发(通常取距离配送中心最近的点)，从未选择点中筛选出可加入点，并从可加入点中选取一个点作为当前线路的终点，使得线路的总成本最小.以此对线路不断进行扩充，直到线路没有可加入点为止.如果所有点均已选择，则算法结束；否则，另外生成一条新的初始线路，重复前面的线路扩充过程，直至所有点都已选择.（3）插入法插入法结合节约算法与邻接算法的思想，依序将配送点纳入路径中以制定配送线路.它的程序与邻接算法相似，也是从初始线路开始，构造序列线路，并在没有可行插入时新增一条线路.插入算法的肖建辉：车辆路径优化文献综述34··第2期关键是选择最合适的未分配点在线路中的最佳位置进行插入.（4）扫描法扫描法属于“先分组后线路”的算法.所谓分组就是指分派给每辆车一组配送点.一种简单的分组方法是将以配送据点为原点的坐标平面划分为多个扇形区域，并初步为每个扇形区域的点指派一辆车.而所谓的“线路”就是指在每个区域内，先采用扫描法选择未分配点，然后采用插入算法扩充线路.如果在进行了一次“分组与线路”的路线构造后，还存在未分配点，则继续进入“分组与路线”程序.如此反复，直到所有的点均己分配完毕为止.2.3智能算法（1）禁忌搜索算法(TabuSearch，TB)该算法通过设置禁忌表记录局部最优点，并在后面的循环搜索中，根据某种限制规则和禁忌表中已记录的信息在当前搜索邻域中取一个合适的解.该算法对初始解有很强的依赖性，多数学者采用插入法产生初始解，也有不少学者采用扫描法、下届算法、K-tree算法产生初始解.为了降低搜索的复杂性，一方面，研究者提出了一些特殊策略来限制领域的范围，比如重心分组法.另一方面，为了加速搜索进程，可采用平行机计算技术.算法多以车辆数最少为优化的第一目标.禁忌搜索算法在开放式车辆路径问题、回程载货车辆路径问题、有时间窗约束的车辆路径问题、动态车辆路径问题中都有大量应用.（2）遗传算法(GeneticAlgorithms,GA)遗传算法是以适者生存规律为理论依据的随机搜索算法.该算法的思路是：从一组随机产生的初始解，称为“种群”开始搜索过程，种群中的每一个个体是问题的一个解，称为“染色体”，染色体通常是一串数据（或数组），用来作为优化问题的解的代码，染色体在后续迭代过程中不断进化，称为“遗传”，在每一代中用“适值”来测量染色体的好坏，生成的下一代染色体称为“后代”，该算法通过染色体的配对和变异过程实现种群的进化，每一次进化则对应解的一次迭代.当迭代次数达到最大次数限制或群体中的个体无显著差异时，迭代终止.（3）模拟退火算法(SimulatedAnnealing,SA)模拟退火算法模拟固体退火过程，1982年，Kirkpatrick等将退火思想引入车辆调度优化问题，提出了一种求解大规模车辆调度问题的有效近似算法，即模拟退火算法.该算法实际上是一种随机松弛技巧，它模拟了退火过程.在搜索的初始阶段，算法跳向远点，随着时间的延伸或“降温”，跳跃幅度逐渐减小，最终转向局部搜索下降方法.（4）蚁群算法(AntColonyOptimization,ACO)蚁群算法是受自然界中真是蚁群觅食行为的启发而提出的一种模拟进化算法.在寻找食物时，蚂蚁会在它所经过的路径通过排放一种外激素(pheromone，在算法中称为信息素)作出标记，排放的量则根据路径长度和食物的等级决定.这些外激素为其它蚂蚁提供信息，并吸引它们前去搬运食物.对于VRP问题，也可以根据蚂蚁觅食原理来进行搜索.该算法是一种应用与组合优化问题的启发式算法.另外一种解决车辆调度问题的方法是Excel建模求解法.国内主要利用Excel系统解决大型的车辆调度问题的还很少，但在国外有不少成功应用的案例.Excel软件提供了一个对管理问题进行描述和分析的环境，具有管理者需要得到的大量管理科学工具，使管理者能够自己进行分析和决策.Excel已经应用在诸多决策当中，创造出了非常大的经济效益.例如，联合航空公司，将Excel用来解决为满足乘客需求得以最低的成本进行订票和机场的工作班次排程，每年节支600万美元；AT&T公司将Excel用于为公司商业用户的电话销售中心的优化选址，每年节支4.06亿美元；Reynolds金属制品公司，利用Ex-cel对本公司的来自超过200个工厂、仓库和供应商的货物装载调度系统进行优化，每年节约开支700万等.Excel具有直观、透明、易于操作等特点，特别是在计算机能处理成千上万个约束条件和决策变量之后，Excel的适用范围更加广泛，被管理者广泛运用到了工业、农业、交通、商业、通信、政府机关等诸多部门和领域当中.它主要解决生产计划、最优分配、最佳设计、最优决策等最优化管理问题，是现代管理科学的重要手段之一.从上述分析可知，求解VRP问题的方法有很多，各种方法在一定时期、一定情况下都有各自的优点，都具有解决某一类问题的优越性.3总结与展望车辆路径问题由于在管理学和运筹学上非常重要而且求解有一定的难度，同时由于它具有很强的现实价值，可产生极其可观的经济效益，因而是理论界与企业界关注的一个极其具有魅力的优化问题.笔者就车辆路径问题的模型和求解方法对前人的研肖建辉：车辆路径优化文献综述35··第2期究成果进行回顾与梳理.随着社会的发展，VRP也在不断的发展变化，一些新要素也出现了并对研究起着至关重要的作用，如将配送中心选址考虑进来的库存-运输一体化优化的库存路径问题.车辆路径问题的求解算法包括精确算法、纯启发式算法和智能算法.由于精确算法的计算量一般会随着问题规模的增大呈指数增长，只有在客户数量较少、运输网络较简单时，才能求得物流配送车辆调度问题的精确最优解，在实际中其应用范围很有限，所以专家学者们主要把精力花在构造高质量的启发式算法和智能算法上.随着研究不断深入，学者门对启发式算法和智能算法进行了多形式、多角度的改进，出现了多种改进式的启发式算法和智能算法.随机需求车辆路径问题（VRPSD）、非对称网络车辆路径问题、仓储-配送一体化库存路径问题(IRP)等将是进一步研究的方向.随机需求车辆路径问题（VRPSD）在物流领域经常会出现，需求者、需求方向、需求时间、需求种类、需求数量等往往是随机的，但目前关于随机需求的车辆路径问题研究还很少.非对称网络车辆路径问题在现实生活中比较常见，例如单行道或禁止左转等交通标识的存在，使得从甲地到乙地，和从乙地到甲地的距离(或时间)并不相同.由于非对称网络的这个特性，使得许多在VRP中成功应用的算法不能直接用于非对称网络的求解，目前的许多求算法都是基于对称TSP问题的算法而来［4］，不能有效解决非对称网络车辆路径问题.另外仓储-配送一体化库存路径问题(IRP)将仓储点作为运输配送车辆路径选择的考虑因素，现代物流要求系统化的决策与运作，因而库存-运输一体化车辆路径问题是具有价值的.所以随机需求车辆路径问题（VRPSD）、非对称网络车辆路径问题、仓储-配送一体化库存路径问题(IRP)等将是进一步研究的方向.另外，随着连锁经营在我国快速发展，连锁配送活动越来越普遍.而配送恰恰具备了车辆调度问题的一般特征和优化调度条件.在车辆调度问题中，最短路径问题和起讫点重合的单车场、非满载、有时间窗约束的问题具有代表性，这类问题通常出现在自己经营配送业务的连锁经营企业.目前我国自营配送中心的比例70%以上，因而最短路径问题和起讫点重合的单车场、非满载、有时间窗约束的问题是众多连锁配送企业共同存在的问题，具有深入研究的价值.参考文献：［1］DantzingG,RamserJ.Thetruckdispatchingproblem［J］.ManagementScience,1959,10(6):80-91.［2］Bodin,L.B.,B.L.Golden,A.A.Assad,M.O.Ball.Routingandschedulingofvehiclesandcrews-Thestateoftheart［J］.Comput.Oper.Res,1983，10:63-211［3］郎茂祥，物流配送车辆调度问题的模型与算法研究［D］.北京:北方交通大学博士学位论文，2002:1-143.［4］JohanOpen,Arne.Arcroutinginanoderoutingenviron-ment［J］.Computers&OperationsResearch,2006,133(4):1033-1055.［5］MingzhouJin,KaiLiu,RoyceO.Bowden.Atwo-stagealgo-rithmwithvalidinequalitiesforthesplitdeliveryvehicleroutingproblem［J］.InternationalJournalofProductionE-conomics,2006,105(1):228-242.［6］ArchettiC,SperanzaM,HertzA.ATabuSearchAlgorithmfortheSplitDeliveryVehicleRoutingProblem［J］.Trans-portationScience,2006,40(1):64-73.［7］吴斌.车辆路径问题的粒子群算法研究与应用［D］.浙江工业大学信息工程学院博士学位论文.2007,(11):141.［8］胡小兵,吴树范,江驹.TSP的一种改进遗传算法［J］.计算技术与自动化,2000,(4).［9］郭耀煌,李军.车辆优化调度［M］.成都:成都科技大学出版社.1994:44-60.［10］袁庆达,闫昱,周再玲．TabuSearch算法在优化配送路线问题中的应用［J］.计算机工程，2001，(11):86-89．［11］肖鹏,李茂军,张军平，叶涛.单亲遗传算法及其在物流配送系统中的应用［J］．系统工程，2000，(1):64-66．［12］张涛,王梦光,杨建夏.不确定计划数的轧制批量计划的模型和算法［J］.系统工程学报,2000,15(1):54-60.［13］方跃建,杨春节,李平,曹柬.一种新的非满载车辆调度的遗传算法［J］.江南大学学报(自然科学版),2007,(2):136-139.［14］孙华丽,谢剑英,薛耀锋.带容量约束的多车调度暂态混沌神经网络算法［J］.上海交通大学学报,2006,40(7):1148-1151.［15］丰伟,李雪芹.基于粒子群算法的多目标车辆调度模型求解［J］.系统工程,2007,25(4):15-19.［16］王海星,王德占,申金升.蚁群算法解决有时间窗的车辆优化调度问题研究［J］.物流技术,2006,(11):37-40.［17］宋康，蔡延光张敏捷等．多目标车辆路径的遗传算法［J］．微计算机信息,2010,26（4-1）：221-223.［18］吕雄伟,孙斌峰,李军.随机需求下带时间窗IRP问题的遗传算法研究［J］.商业研究,2008,(9):8-10.［19］黄敏芳,胡祥培,王征等.车辆路径问题的三阶段求解方法研究［J］.管理科学,2009,22(3)）:37-46.肖建辉：车辆路径优化文献综述36··第2期［20］张海刚,顾幸生,吴燕翔.改进的粒子群算法及其在带软时间窗车辆调度问题中的应用［J］.华东理工大学学报(自然科学版),2009,35(5):774-778.［21］霍佳震,张磊.用节约法解决带有时间窗的满载车辆调度问题［J］.工业工程与管理,2006,(4):38-42［22］刘浩,袁健,卢厚清.两种类型车辆随机需求路由问题［J］.南京肮空航天大学学报,2001,33(2):155-158.［23］王志坚,王晓博,李一军.一体化集货和配送车辆路径问题的混合遗传启发式算法［J］.系统管理学报,2009,18(3):339-343.［24］张景玲,赵燕伟,王海燕等.多车型动态需求车辆路径问题建模及优化［J］.计算机集成制造系统,2010,16(3):543-550.［25］袁健,刘晋.随机需求情形VRP的Hopfield神经网络解法［J］.南京航空航天大学学报,2000,32(5):579-585.［26］袁庆达.随机库存—运输联合优化问题研究［D］.成都:西南交通大学,2002:1-123.［27］杜文,袁庆达,周再玲.一类随机库存/运输联合优化问题求解过程分析［J］.中国公路学报,2004,17(1):114-118.［28］雷邦军,钟波.模糊环境下库存与运输整合优化问题研究［J］.北京工商大学学报(自然科学版),2008,26(6):63-67.［29］彭北青.开放式模糊需求车辆路径问题的差分进化算法［J］.武汉理工大学学报,2009,31(9):75-83.［30］张建勇,李军.模糊车辆路径问题的一种混合遗传算法［J］.管理工程学报,2005,19(2):23-26.［31］谢小良,符卓,杨芳.模糊需求车辆路径问题的模型与算法［J］.计算机系统应用,2009,(10):65-143.［32］顾幸生,吴燕翔,甘世红.基于免疫算法的不确定条件下车辆调度问题［J］.华东理工大学学报(自然科学版),2009,35(3):452-456.［33］李军，郭耀煌.物流配送车辆优化调度理论与方法［M］.北京.中国物资出版社.2001:1-26.［34］郭耀煌,李军,詹昭铭.货车调度的一种序列优化算法［J］.汽车运输研究,1994,11(3):26-32.［35］郭耀煌.安排城市卡车行车路线的一种新算法［J］.系统工程学报,1989,7(1):47-53.［36］郭耀煌.复杂道路网上货运卡车的优化调度［J］.西南交通大学学报,1988,(4):67-75.［37］郭耀煌,钟小鹏.动态车辆路径问题排队模型分析［J］.管理科学学报,2006,9(1):33-37［38］谢秉磊,安实,郭耀煌.随机车辆路径问题的多回路优化策略［J］.系统工程理论与实践,2007,(2):167-171.［39］张建勇,李军,郭耀煌.带模糊预约时间的动态VRP的插入启发式算法［J］.西南交通大学学报,2008,43(1):107-113.［40］张建勇,李军.具有同时配送和回收需求的车辆路径问题的混合遗传算法［J］.中国公路学报,2006,7(4):118-122.［41］张建勇,李军,郭耀煌.模糊需求信息条件下的实时动态车辆调度问题研究［J］.管理工程学报,2004,18(4):69-72.［42］张建勇,李军.模糊车辆路径问题的一种混合遗传算法［J］.管理工程学报,2005,19(2):23-26.［43］张建勇,李军,郭耀煌.具有模糊预约时间的VRP混合遗传算法［J］.管理科学学报,2005,8(3):64-71.［44］张建勇,郭耀煌,李军.一种具有模糊费用系数的VSP的修正C-W节约算法［J］.西南交通大学学报,2004,39(3):281-284.ReviewonVehicleRoutingOptimizationsXIAOJianhui（GuangdongWomen’sPolytechnicCollege,Guangzhou511450,China）Abstract:VehicleroutingProblem（VRP）isanimportantsubjectinthestudyofthemodernlogisticssys-tem.Selectingthepropertransportationroutecanimprovetheresponsetimetotheclients'requirementsandtheservicequality,andlowertheoperatingcostoftheserviceprovider.Ttherefore,thisarticlewillhaveareviewonthestudiesbyotherscholarsofboththemodeloftransportationroutingproblemanditssolutionsKeywords:VRPproblem;modernlogistics;optimizing肖建辉：车辆路径优化文献综述37··