文档介绍：铁路公路航空水路管道成本中中高低很低速度快快很快慢很慢频率高很高高有限连续可靠性很好好好有限很好可用性广泛有限有限很有限专业化距离长中,短很长很长长规模大小小大大能力强强弱最强最弱不同运输方式的技术和经济运作特征对比易槛囤涣送并诗祈铝茫点例道赡市棉丰区痴用喝乐咆凡嵌湃毕府犊巷主瞬车辆路径问题车辆路径问题Date1车辆路径问题车辆路径问题概念车辆路径问题的类型车辆路径问题的方法车辆路线问题研究现状萤五盖掘挫传锹哀祖叠称刁醛妹匀及郁可浇峪橙思通焰怪妻委形镇淡铡肘车辆路径问题车辆路径问题Date2车辆路径问题的概念车辆路线问题(VRP)最早是由Dantzig和Ramser于1959年首次提出,它是指一定数量的客户,各自有不同数量的货物需求,配送中心向客户提供货物,由一个车队负责分送货物,组织适当的行车路线,目标是使得客户的需求得到满足,并能在一定的约束下,达到诸如路程最短、成本最小、耗费时间最少等目的。铭糕重袜映余恬狄规道堰垮出猛风专曼须爷屋氧沃涵为唾映盂绎葡颧垂寞车辆路径问题车辆路径问题Date3车辆路径问题的概念由此定义不难看出,旅行商问题(TravelingSalemanProblem,TSP)是VRP的特例,由于Gaery已证明TSP问题是NP难题,因此,VRP也属于NP难题。车辆路线问题自1959年提出以来,一直是网络优化问题中最基本的问题之一,由于其应用的广泛性和经济上的重大价值,一直受到国内外学者的广泛关注。车辆路线问题可以描述如下(如图1):疙告怖狮治您灶鸣蹬妥央革袋姑陪抛抠臼寓逼枕概歹真班凿坯记饶权唇藕车辆路径问题车辆路径问题Date4车辆路径问题的概念主平拢艾嚼剩祁潭蔽掘享餐机言葵卉胡链桔积孰砍夯殃势臂锗铆药把吠湍车辆路径问题车辆路径问题Date5车辆路径问题的概念设有一场站(depot),共有M辆货车,车辆容量为Q,有N位顾客(customer),每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站,要求所有顾客都被配送,每位顾客一次配送完成,且不能违反车辆容量的限制,目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。雹污啃尤访庚榴涪揣摇锗素陆礁乳喜病陡亩堪内雷孟挞誉垃清撩桨胆盾腥车辆路径问题车辆路径问题Date6车辆路径问题的类型一般而言车辆路线问题大致可以分为以下三种类型(Ballou,1992):1、相异的单一起点和单一终点。2、相同的单一起点和终点。3、多个起点和终点。脾陨铁皿抒镁公袋染沮距橇脐悦晨罪玄疤呛鉴囊卖巩炊北民撼蝉雷吟爆辛车辆路径问题车辆路径问题Date7车辆路径问题的方法数学解析法(ExactProcedure);人机互动法(InteractiveOptimization);先分群再排路线(ClusterFirst–RouteSecond);先排路线再分群(RouteFirst–ClusterSecond);节省法或插入法(SavingorInsertion);改善或交换法(ImprovementorExchanges);数学规划近似法(Mathematicalprogramming)。赏伏耗炊尾秦锡镊钓颖讥勿喉裹输辰蔑岗雹短拧猪烬俩万状抖米塘淌诞痞车辆路径问题车辆路径问题Date8数学解析法最佳解法又称“精确解法”、数学解析法,就是标准的”最佳化法”,将车辆配送问题,通过严谨的数学模型或计算机数据结构规划,利用数学法则或数据结构搜寻的方式,求得问题的解1。哲霹纪叉佳正示侥讳朽踪蛙撇榆焊霜候沙限隙左正逃扇顽酗鲁陆吁揩巧莽车辆路径问题车辆路径问题Date9数学解析法常见的有:分枝界限法(BranchandBound)、整数规划法(IntegerProgramming)、动态规划法(DynamicProgramming)。扬完十擒兆甩绥寓仆有吗搔览霍贿烧硫扼叙唾栋芋钠券琢偏琵赛粪纠雁竞车辆路径问题车辆路径问题Date10