《配送路径优化-ppt》由会员分享,可在线阅读,更多相关《配送路径优化-ppt(30页珍藏版)》请在金锄头文库上搜索。
1、配送线路优化,1,配送线路优化,配送线路优化,2,什么是“配送”?,1. 配送是从物流据点至用户的特殊的送货形式。 2. 配送是短距离的末端运输。 3. 配送是一种以供给者送货到用户的服务式商品供应制,配送线路优化,3,案例1(枚举法),如图所示:数码电子器材配送中心(P1)需将一批个人电脑送往某数码城(P7) ,连线上方数字表示线路长度(km),送货人员应如何选择路线,才能将货物最快送达?,配送线路优化,4,枚举法 即例举出所有可能的线路和里程,选择其中最小者。,配送线路优化,5,案例2(枚举法尝试),问: 对图1做如下变化,还能用刚才的方法求出最短路径吗?,配送线路优化,6,案例(枚举法尝
2、试),配送线路优化,7,枚举法的局限性 枚举法是一种直接简单的搜寻方法,当配送路线网简单时运用该方法能够快速找出最短路径。 当配送网络结构复杂,特别是出现多个环路时,枚举法不再是最为有效的搜寻方法。因为枚举法的关键是例举出集合中的全部元素(所有可能的路径),在复杂网络中,例举出所有路径本身是一件很困难的事情。,配送线路优化,8,我们该用何种方法解决这个问题呢?,? ? ? 破圈法,配送线路优化,9,什么是破圈法呢?,破圈法任取一个圈,从圈中去掉一条权最大的边(如果有两条或两条以上的边都是权最大的边,则任意去掉其中一条)。在余下的图中,重复这个步骤,直到得到一个不含圈的图为止,这时的图便是最小树
3、。,配送线路优化,10,案例3(破圈法),一个乡有9个自然村,其间道路如图5-26(a)所示,要以村为中心建有线广播网络,如要求沿道路架设广播线,应如何架设?,K i,配送线路优化,11,解:本问题用上述“破圈法”,任取一圈从中去掉边,再选圈,去掉边,以同样方法进行,直到无圈。图5-26(b)就是一种方案。,配送线路优化,12,案例4 (破圈法),如图1所示,数码电子器材配送中心(P1)需将一批个人电脑送往某数码城(P7) ,连线上方数字表示线路长度(km),如何将货物最快送达?,配送线路优化,13,案例5(破圈法),问: 如果运用破圈法,这个案例又如何解答呢?,配送线路优化,14,案例6,已
4、知配送中心PO向2个用户和P2配送货物,其配送路线网络如下图与表所示:配送中心与用户的距离以及用户之间的距离为I1=5、I2=7、I3=9(单位:公里),各客户的需求量为Q1=2、Q2=1.5(单位:吨),线路上的数字表示两结点之间的距离,配送中心有3台2t卡车和2台4t两种车辆可供使用。 问:有几种配送方案?哪种为最优配送方案?为什么?,配送 中心,用户,用户,配送线路优化,15,案例6(节约里程法),配送中心与用户间的距离为=5、I2=7、I3=9(单位:公里) 各客户的需求量为Q1=2、Q2=1.5(单位:吨) 配送中心有3台2t卡车和2台4t两种车辆可供使用,配送线路优化,16,方案和
5、方案有什么区别?,方案 配送距离 2(1+2) =5*2+7*2=24,方案 =Q1Q2=2+1.5=3.54T 配送距离 (l1+l2+l3 ) =5+9+7=2124 或7+9+5=2124,配送线路优化,17,方案和方案有什么区别?,往返发货与巡回发货车辆行走距离 l=2(l1+l2)-(l1+l2+l3)=l1+l2-l3 方案中的两种算法有什么区别? 是应该先送还是先送呢? 提示:Q1=2、Q2=1.5,配送线路优化,18,配送路线的确定的基本条件,1满足所有收货人对货物品种、规格、数量的要求。 2满足收货人对货物发到时间范围的要求。 3在交通管制允许通行的时间中进行配送。 4各配送
6、路线的货物量不得超过车辆容积及载重辆的限制。,配送线路优化,19,案例 (节约里程法),已知配送中心PO向5个用户Pj配送货物,其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图与表所示:图中括号内的数字表示客户的需求量(单位:吨),线路上的数字表示两结点之间的距离,配送中心有3台2t卡车和2台4t两种车辆可供使用, 1、试利用节约里程法制定最优的配送方案? 2、设卡车行驶的速度平均为40公里/小时,试比较优化后的方案比单独向各用户分送可节约多少时间?,配送线路优化,20,案例 (节约里程法),解: 第(1)步:作运输里程表,列出配送中心到用户及用户间的最短距离。 最短距离表(单位:
7、公里),配送线路优化,21,案例 (节约里程法),第(2)步:由运输里程表、按节约里程公式,求得相应的节约里程数,如上表( )内。,配送线路优化,22,案例 (节约里程法),第(3)步:将节约里程sij进行分类,按从大到小顺序排列,配送线路优化,23,案例 (节约里程法),第()步:根据载重量约束与节约里程大小,将各客户结点连接起来,形成二个配送路线。即A、B两配送方案。,配送线路优化,24,案例 (节约里程法),配送线路A: P0-P2-P3-P4- P0 运量qA= q2+q3+q4 = 1.7+0.9+1.4 = 4t 用一辆 4t车运送 节约距离 SA =10 +8 = 18km,配送
8、线路B: P0-P5-P1-P0 运量qB =q5+q1=2.4+1.5 =3.9t4t车 用一辆 4t车运送 节约距离 SB=2km,配送线路优化,25,案例 (节约里程法),第()步:确定单独送货的配送线路 初始方案配送距离=392=78KM,配送线路优化,26,案例 (节约里程法),第(6)步:与初始单独送货方案相比,计算总节约里程与节约时间 总节约里程: S= SA+ SB= 20 km 与初始单独送货方案相比,可节约时间:T =S/V=20/40=0.5小时,配送线路优化,27,节约里程法小结,关键:求出各配送点组合的节约量并排序。 必须:满足运输车辆的载重要求。 最佳路线:环路。,配送线路优化,28,想一想:,1.本次课共运用了几种方法来设计运输线路? 答:枚举法、破圈法 和 节约里程法。 2.枚举法的缺点是什么? 答:当配送网络结构复杂时难以运用。 3.破圈法和节约里程法的应用区别在哪? 答:破圈法不要求有回路, 但节约里程法的最佳路线是环路。,配送线路优化,29,巩固练习(节约里程法),某配送中心A要向所在城市B、C、D、E、F、G共6个客户点配送货物,如图9所示,它们之间的距离(km)和每一处的配送货物量(t)见表2。运输车有2.5t和4t两种货车,试确定配送路线。,配送线路优化,30,希望各位老师指正 谢谢!,