配送路径优化-PPT

1、配送线路优化1配送线路优化配送线路优化配送线路优化2什么是什么是“配送配送”？ 1. 配送是从物流据点至用户的特殊的送货形式。 2. 配送是短距离的末端运输。 3. 配送是一种以供给者送货到用户的服务式商品供应制 配送线路优化3案例案例1（枚举法）（枚举法） 如图所示：数码电子如图所示：数码电子器材配送中心器材配送中心(P1)需需将一批个人电脑送往将一批个人电脑送往某数码城某数码城(P7) ,连线上连线上方数字表示线路长度方数字表示线路长度(km)，送货人员应如，送货人员应如何选择路线，才能将何选择路线，才能将货物最快送达？货物最快送达？配送线路优化4枚举法枚举法即例举出所有可能的线路和里程，

2、选择即例举出所有可能的线路和里程，选择其中最小者。其中最小者。 路径里程（km）1-2-5-7151-2-7191-2-4-6-7151-2-4-6-5-7131-3-6-7121-3-6-5-7101-3-6-4-2-5-720配送线路优化5案例案例2（枚举法尝试）（枚举法尝试） 问：问： 对图对图1做如做如下变化，下变化，还能用刚还能用刚才的方法才的方法求出最短求出最短路径吗？路径吗？配送线路优化6案例（枚举法尝试）案例（枚举法尝试）路径里程（km）1-2-5-7151-2-4-5-7191-2-4-6-7151-2-4-6-5-7131-3-6-712配送线路优化7 枚举法的局限性枚举法

3、的局限性 枚举法是一种直接简单的搜寻方法，当配送路线网简单时运用该方法能够快速找出最短路径。 当配送网络结构复杂，特别是出现多个环路时，枚举法不再是最为有效的搜寻方法。因为枚举法的关键是例举出集合中的全部元素（所有可能的路径），在复杂网络中，例举出所有路径本身是一件很困难的事情。配送线路优化8我们该用何种方法解决这个问题呢？ ？ ？ ？ 破圈法配送线路优化9什么是破圈法呢？什么是破圈法呢？ 破圈法任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。配送线路优化10案例3（

4、破圈法）（破圈法） 一个乡有9个自然村，其间道路如图5-26（a）所示，要以村为中心建有线广播网络，如要求沿道路架设广播线，应如何架设？Ki配送线路优化11解：本问题用上述“破圈法”，任取一圈从中去掉边，再选圈，去掉边，以同样方法进行，直到无圈。图5-26（b）就是一种方案。配送线路优化12案例4 （破圈法） 如图如图1所示，数码电所示，数码电子器材配送中心子器材配送中心(P1)需将一批个人电脑需将一批个人电脑送往某数码城送往某数码城(P7) ,连线上方数字表示连线上方数字表示线路长度线路长度(km)，如，如何将货物最快送达？何将货物最快送达？配送线路优化13案例案例5（破圈法）（破圈法） 问

5、：问： 如果运用如果运用破圈法，破圈法，这个案例这个案例又如何解又如何解答呢？答呢？ 配送线路优化14案例案例6 已知配送中心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（单位：公里） 各客户的

6、需求量为Q1=2、Q2=1.5（单位：吨） 配送中心有3台2t卡车和2台4t两种车辆可供使用 PAB配送中心用户l1l2PAB配送中心(q1)l1l2l3(q2)配送线路优化16方案和方案有什么区别？ 方案 配送距离2(1+2) =5*2+7*2=24 方案 =Q1Q2=2+1.5=3.54T 配送距离 (l1+l2+l3 ) =5+9+7=2124 或7+9+5=2124PAB配送中心用户l1l2PAB配送中心(q1)l1l2l3(q2)配送线路优化17方案和方案有什么区别？ 往返发货与巡回发货车辆行走距离往返发货与巡回发货车辆行走距离 l=2(l1+l2)-(l1+l2+l3)=l1+l2

7、-l3方案中的两种算法有什么区别？方案中的两种算法有什么区别？是应该先送还是先送呢？是应该先送还是先送呢？ 提示：Q1=2、Q2=1.5配送线路优化18配送路线的确定的基本条件配送路线的确定的基本条件 1满足所有收货人对货物品种、规格、数量的要求。 2满足收货人对货物发到时间范围的要求。 3在交通管制允许通行的时间中进行配送。 4各配送路线的货物量不得超过车辆容积及载重辆的限制。配送线路优化19案例案例 （节约里程法） 已知配送中心PO向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图与表所示：图中括号内的数字表示客户的需求量（单位：吨），线路上的数字表示两结

8、点之间的距离，配送中心有3台2t卡车和2台4t两种车辆可供使用， 1、试利用节约里程法制定最优的配送方案？ 2、设卡车行驶的速度平均为40公里/小时，试比较优化后的方案比单独向各用户分送可节约多少时间？（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）（1.5）101275124136812168配送线路优化20案例案例 （节约里程法）解：第（1）步：作运输里程表，列出配送中心到用户及用户间的最短距离。最短距离表（单位：公里）需求量需求量P0 1.58P1-1.7812P20.96134P31.471595P42.41016181612P5配送线路优化21案例案例 （节约里程法）

9、第（2）步：由运输里程表、按节约里程公式，求得相应的节约里程数，如上表（ ）内。需求量需求量P0 1.58P1-1.7812（）（）P20.9613（）（）4（）（）P31.4715（）（）9（）（）5（）（）P42.41016（）（）18（）（）16（）（）12（）（）P5配送线路优化22案例案例 （节约里程法） 第（3）步：将节约里程sij进行分类，按从大到小顺序排列序序号号路线路线节约节约里里程程序序号号路线路线节约节约里里程程1 1P P2 2P P3 310106 6P P1 1P P5 52 22 2P P3 3P P4 48 87 7P P1 1P P3 31 13 3P P2

10、2P P4 46 68 8P P2 2P P5 50 04 4P P4 4P P5 55 59 9P P3 3P P5 50 05 5P P1 1P P2 24 41010P P1 1P P4 40 0配送线路优化23案例案例 （节约里程法） 第（）步：根据载重量约束与节约里程大小，将各客户结点连接起来，形成二个配送路线。即A、B两配送方案。（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）（1.5）107548168A：（24KM，4T）B：（34KM，3.9T）配送线路优化24案例案例 （节约里程法） 配送线路A： P0-P2-P3-P4- P0 运量qA= q2+q3+q4

11、 = 1.7+0.9+1.4 = 4t 用一辆 4t车运送 节约距离 SA =10 +8 = 18km 配送线路B: P0-P5-P1-P0 运量qB =q5+q1=2.4+1.5 =3.9t4t车 用一辆 4t车运送 节约距离 SB=2km配送线路优化25案例案例 （节约里程法） 第（）步：确定单独送货的配送线路 初始方案配送距离=392=78KM（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）（1.5）107688配送线路优化26案例案例 （节约里程法） 第（6）步：与初始单独送货方案相比，计算总节约里程与节约时间 总节约里程： S= SA+ SB= 20 km 与初始单独

12、送货方案相比，可节约时间：T =S/V=20/40=0.5小时（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）（1.5）107548168A：（：（24KM，4T）B：（：（34KM，3.9.9T）配送线路优化27节约里程法小结节约里程法小结关键：求出各配送点组合的节约量并排序。关键：求出各配送点组合的节约量并排序。必须：满足运输车辆的载重要求。必须：满足运输车辆的载重要求。最佳路线：环路。最佳路线：环路。 配送线路优化28想一想：1.本次课共运用了几种方法来设计运输线路？ 答：枚举法、破圈法 和 节约里程法。2.枚举法的缺点是什么? 答：当配送网络结构复杂时难以运用。3.破圈法和节约里程法的应用区别在哪? 答：破圈法不要求有回路, 但节约里程法的最佳路线是环路。配送线路优化2