资源描述：
《车辆路径问题的模型及算法研究综述new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、管理工程学报Vol119,No11JournalofIndustrialEngineeringPEngineeringManagement2005年第1期外论评介车辆路径问题的模型及算法研究综述刘云忠,宣慧玉(西安交通大学管理学院,陕西西安710049)摘要:本文在文献[1,2,3,4]的基础上,首先,介绍了车辆路径问题的分类和限制条件;然后,全面综述了国内外关于车辆路径问题的模型及算法研究现状,重点探讨了车辆路径问题的模型构造、求解算法及其适用范围;最后,展望了其研究的前景。关键词:车辆路径问题;物流管理;遗传算法;启发式算法中图分类号:F57017文献标识码
2、:A文章编号:100426062(2005)01201242070引言(车辆必须返回车场);按已知信息的特征分类,有确定性车辆路径问题(VehicleRoutingProblem,VRP)是物流管理VRP和不确定性VRP,其中不确定性VRP可进一步分为随机研究中的一项重要内容。选取恰当的车辆路径,可以加快对VRP(SVRP)和模糊VRP(FVRP);按约束条件分类,有CVRP客户需求的响应速度,提高服务质量,增强客户对物流环节(带能力约束)、DVRP(带时间距离约束)和VRPTW(带时间窗的满意度,降低服务商运作成本。车辆路径问题是由口);按需求是否可切分分类,
3、又可分为可切分的VRP和不可G.Dantzig和J.Ramser[5]于1959年首先提出来的,很快引起运切分的VRP。按优化目标数来分类,有单目标问题和多目标问题。由于情况的不同,车辆路径问题的模型构造及算法有筹学、管理学、计算机应用、组合数学、图论等学科的专家学很大差别。者的高度重视。他们对此问题进行了大量的理论研究和实在VRP中,最常见的约束条件有:验分析,取得了很大的研究进展。其研究结果在运输系统、(1)容量约束。任意车辆路径的总重量不能超过该车辆物流配送系统、快递收发系统中都已得到广泛应用。现在,的能力负荷。引出带容量约束的车辆路径问题(Capacit
4、ated对车辆路径问题的研究仍然相当活跃。车辆路径问题一般VehicleRoutingProblem,CVRP)。定义为:对一系列发货点和/或收货点,组织适当的行车路(2)优先约束。引出优先约束车辆路径问题(Vehicle线,使车辆有序地通过它们,在满足一定的约束条件(如货物RoutingProblemwithprecedenceConstraints,VRPPC)。需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、(3)车型约束。引出多车型车辆路径问题(Mixed/时间限制等)下,达到一定的目标(如路程最短、费用最小、时HeterogeneousFlee
5、tVehicleRoutingProblem.MFVRP/HFVRP)。间尽量少、使用车辆尽量少等)。由此定义不难看出,旅行商(4)时间窗约束。包括硬时间窗(HardTimewindows)和软问题(TravelingsalesmanProblem,TSP)是VRP的一个特例。由时间窗(SoftTimewindows)约束。引出带时间窗(包括硬时间[2]于Gaery已证明TSP问题是NP难题,因此,VRP也是NP难窗和软时间窗)的车辆路径问题(VehicleRoutingProblemwith题。Timewindows,VRPTW)。(5)相容性约束。引出相容性
6、约束车辆路径问题(Vehicle1车辆路径问题的分类及约束条件RoutingProblemwithCompatibilityConstraints,VRPCC)。根据研究重点的不同,VRP有多种分类方式。如按任务(6)随机需求。引出随机需求车辆路径问题(Vehicle特征分类,有装货问题、卸货问题及装卸混合问题;按任务性RoutingProblemwithStochasticDemand,VRPSD)。质分类,有对弧服务问题(如中国邮递员问题)和对点服务问(7)开路。引出开路车辆路径问题(OpenVehicleRouting题(如旅行商问题)以及混合服务问题(如
7、校车路线安排问Problem)。题)。按车辆载货状况分类,有满载问题和非满载问题;按车(8)多运输中心。引出多运输中心的车辆路径问题场数目分类,有单车场问题和多车场问题;按车辆类型分类,(Multi2DepotVehicleRoutingProblem)。有单车型问题和多车型问题;按车辆对车场的所属关系分(9)回程运输。引出带回程运输的车辆路径问题(Vehicle类,有车辆开放问题(车辆可不返回车场)和车辆封闭问题RoutingProblemwithBackhauls)。收稿日期:2003205226修回日期:2003210208作者简介:刘云忠(1970—),
8、男,江西新干人,西安交通
