4节约里程法.pptx

节约里程法配送路线优化之配送路线优化之主讲人：王钢主讲人：王钢教学目标知识目标知识目标掌握节约里程法原理。掌握节约里程法原理。技能目标技能目标利用节约里程法完成实际配送路线优化利用节约里程法完成实际配送路线优化01Part原理篇问题的提出：喜羊羊送礼物的烦恼喜羊羊送礼物的烦恼方案一方案一方案二方案二新年到了！喜羊羊送礼物喽！怎么送？问题分析PAB方案一：方案一：S1=2PA+2PBS1=2PA+2PB总行驶里程计算总行驶里程计算方案二：方案二：S2=PA+PB+ABS2=PA+PB+AB根据三角形：根据三角形：两边之和两边之和大于大于第三边第三边所以，方案二所以，方案二优于优于方案一方案一节约里程节约里程=S1-S2=PA+PB-AB=S1-S2=PA+PB-AB问题的延展:给更多的朋友送礼物，怎么送？给更多的朋友送礼物，怎么送？求解的原理：复杂问题简单化复杂问题简单化一种可行的思路：一种可行的思路：节约节约越越多多，越靠近越靠近最优解最优解连接连接节约多的路线，就能够节约多的路线，就能够找到找到最优解。最优解。这就是：这就是：节约里程法节约里程法节约里程法节约里程法原理节约里程法原理B（客户）P PA（客户）B B（客户）（客户）(配送中心配送中心)P A A（客户）（客户）(配送中心配送中心)运行距离运行距离:S1=2PA+2PB:S1=2PA+2PB运行距离运行距离:S2=PA+PB+PC:S2=PA+PB+PC节约里程量节约里程量S=S1-S2=PA+PB-ABS=S1-S2=PA+PB-AB 节约里程法的设计路线思路：对所有配送点之节约里程法的设计路线思路：对所有配送点之间计算节约里程量，按照节约量的大小，进行制定间计算节约里程量，按照节约量的大小，进行制定配送线路。配送线路。单独送货单独送货巡回送货巡回送货02Part应用篇实际应用 已已知知配配送送中中心心P P0 0向向5 5个个用用户户P Pj j配配送送货货物物，其其配配送送路路线线网网络络、配配送送中中心心与与用用户户的的距距离离以以及及用用户户之之间间的的距距离离（单单位位：kmkm）如如下下图图所所示示，配配送送中中心心有有3 3辆辆2t 2t卡卡车车和和2 2辆辆4t 4t两两种种车车辆辆可可供供使使用用。车车辆辆一一次次行行走走路路线线不不能能超超过过40km40km。请请利用节约里程法制定最优的配送方案。利用节约里程法制定最优的配送方案。1.4tP0P2P3P4P5P1 12.4t 0.9t 1.7t1.5t 101275124136812168实际应用问题分析1.1.这是一个配送路线的设计问题。这是一个配送路线的设计问题。2.2.由一点向多点配送，而且需要返回。由一点向多点配送，而且需要返回。3.3.应该选择时间短、成本低的路径。应该选择时间短、成本低的路径。4.4.可以一次送一家，也可以一次送多家。可以一次送一家，也可以一次送多家。5.5.配送中心的车辆载重有限制，每次行驶的里程也有限制。配送中心的车辆载重有限制，每次行驶的里程也有限制。结结论论：我我们们需需要要在在不不超超载载、不不超超限限定定里里程程前前提提下下，设设计计一一条条最最优优配送路线。配送路线。单独送货方案：配送线路单独送货方案：配送线路5 5条，条，需要车需要车5 5辆辆 配送距离配送距离=392=78KM=392=78KM 1.4tP P0 0P2P3P4P5P P1 12.4t 0.9t 1.7t1.5t 107688实际应用实际应用实际应用实际应用单独送货方案单独送货方案第第1 1步：确定各地间最短距离。列出配送中心到用户及用户间的最短距离。步：确定各地间最短距离。列出配送中心到用户及用户间的最短距离。需求量需求量P P0 01.51.5P P1 1P P1 11.71.7P P2 2P P2 20.90.9P P3 3P P3 31.41.4P P4 4P P4 42.42.4P P5 5P P5 5实际应用实际应用步骤步骤节约里程法节约里程法(1.4)P0P2P3P4P5P P1 1(2.4)(1.7(1.7）1012751241368121689实际应用步骤第第1 1步：确定各地间最短距离。列出配送中心到用户及用户间的最短距离。步：确定各地间最短距离。列出配送中心到用户及用户间的最短距离。需求量需求量P P0 01.51.5P P1 18 8P P1 11.71.7P P2 28 81212P P2 20.90.9P P3 36 613134 4P P3 31.41.4P P4 47 715159 95 5P P4 42.42.4P P4 410101616181816161212P P5 5(0.9)(1.5(1.5)(1.4)P0P2P3P4P5P P1 1(2.4)(1.7(1.7）1012751241368121689实际应用步骤第第2 2步：求出各点间的节约里程量。按节约里程公式求得相应的节约里程数。步：求出各点间的节约里程量。按节约里程公式求得相应的节约里程数。需求量需求量（t t）P P0 01.51.58 8P P1 11.71.78 81212P P2 20.90.96 613134 4P P3 31.41.47 715159 95 5P P4 42.42.410101616181816161212P P5 5如：P0 P1+P0P2 -P1P2 =8+8-12 =4注意：红色数字为求得节约里程量！第第2 2步：求出各点间的节约里程量。按节约里程公式求得相应的节约里程数步：求出各点间的节约里程量。按节约里程公式求得相应的节约里程数。需求量需求量（t t）P P0 01.51.58 8P P1 11.71.78 81212P P2 24 40.90.96 613134 4P P3 31 110101.41.47 715159 95 5P P4 40 06 68 82.42.410101616181816161212P P5 52 20 00 05 5如：P0 P1+P0P2 -P1P2 =8+8-12 =4注意：红色数字为求得节约里程量！实际应用步骤第第 3 3 步：节约里程量排序。将节约里程按从大到小顺序排列。步：节约里程量排序。将节约里程按从大到小顺序排列。序号序号路线路线节约里程节约里程1 1P P2 2P P3 310102 2P P3 3P P4 48 83 3P P2 2P P4 46 64 4P P4 4P P5 55 55 5P P1 1P P2 24 46 6P P1 1P P5 52 27 7P P1 1P P3 31 18 8P P2 2P P5 50 09 9P P3 3P P5 50 01010P P1 1P P4 40 0实际应用步骤第第4 4步：作出配送路线。按节约里程量大小顺序，及步：作出配送路线。按节约里程量大小顺序，及车辆载重车辆载重和和路程限制路程限制形成配送路线形成配送路线。优先考虑节约里程最大的路线，优先考虑节约里程最大的路线，以此类推，如果前面涉及了某些路以此类推，如果前面涉及了某些路线，往后就考虑未涉及的路线。线，往后就考虑未涉及的路线。P P2 2P P3-3-P P3 3P P4 4 、P P1 1P P5 5序号路线节约里程1 1P P2 2P3P310102 2P3P4P3P48 83 3P2P4P2P46 64 4P4P5P4P55 55 5P1P2P1P24 46 6P1P5P1P52 27 7P1P3P1P31 12.4t 1.4tP0P2P3P4P5P1 1 0.9t 1.7t1.5t 1074688实际应用步骤1.5t 配送线路配送线路11.4tP0P2P3P4P5P1 12.4t 0.9t 1.7t1075488序号路线节约里程1 1P2P3P2P310102 2P3P4P3P48 83 3P2P4P2P46 64 4P4P5P4P55 55 5P1P2P1P24 46 6P1P5P1P52 27 7P1P3P1P31 1实际应用步骤 配送线路配送线路1：P0-P2-P3-P4-P0 运量运量=1.7+0.9+1.4=4t 运行距离运行距离845724km 用一辆用一辆 4t车运送车运送 配送线路配送线路2:P0-P1-P5-P0 运量运量=2.4+1.5=3.9t4t 运行距离运行距离8101634km 用一辆用一辆 4t车运送车运送 1.51.54配送路线21.41.4P0P2P3P4P5P12.42.40.91.71078 88 85配送线路11616序号路线节约里程1 1P P2 2P3P310102 2P3P4P3P48 83 3P2P4P2P46 64 4P4P5P4P55 55 5P1P2P1P24 46 6P1P5P1P52 27 7P1P3P1P31 1实际应用步骤初始方案：配送线路初始方案：配送线路5 5条，条，需要车需要车5 5辆辆 配送距离配送距离=392=78KM=392=78KM 1.4tP P0 0P2P3P4P5P P1 12.4t 0.9t 1.7t1.5t 107688实际应用步骤单独送货方案：单独送货方案：配送线路配送线路5 5条，条，需要车需要车5 5辆辆 配送距离：配送距离：392=78KM392=78KM使用节约里程法的方案：使用节约里程法的方案：2 2条配送线路，条配送线路，2 2辆辆4t4t车车 配送距离：配送距离：2424343458km58km 1.1.用户的需求量小，可以多个用户共同配送；用户的需求量小，可以多个用户共同配送；2.2.不使任何一辆车超载；不使任何一辆车超载；3.3.每辆车每天的总运行时间或行驶里程不超过规定的上限；每辆车每天的总运行时间或行驶里程不超过规定的上限；4.4.用户到货时间要求。不得超过规定时间。用户到货时间要求。不得超过规定时间。利用节约里程法注意事项：利用节约里程法注意事项：03Part实战篇实战篇节约里程法 鲁鲁商商集集团团银银座座超超市市配配送送中中心心位位于于省省会会济济南南，配配送送中中心心拥拥有有配配送送车车型型为为4T4T。主主要要为为山山东东省省内内各各地地级级市市的的银银座座超超市市进进行行配配送送,某某日日部部分分地地级级市市的的银银座座超超市市货货量量订订单单如如下下表表,各各地地之之间间的的里里程程如如里里程程表表（单单位位：kmkm）所所示示，请请利用节约里程法设计配送路线？利用节约里程法设计配送路线？银座超市银座超市淄淄博博店店 东营店东营店济宁店济宁店泰安店泰安店滨州店滨州店德州店德州店货运量(单位：t)0.51.81.72.21.63.8小提示：注意德州店的需求量小提示：注意德州店的需求量山东省地图注意：可以查里程表或通过地图软件确定距离 2.2t2.2t1.8t1.8t0.5t0.5t货运量货运量济南济南P0P0配送中心配送中心270270255255260260120120德州德州P6P6淄博淄博P1P1105105东营东营P2P2200200105105济宁济宁P3P3190190260260370370泰安泰安P4P49090140140250250120120滨州滨州P5P514014080807070340340220220淄博淄博P1P1东营东营P2P2济宁济宁P3P3泰安泰安P4P4滨州滨州P5P5德州德州店店P6P61.7t1.7t1.6t1.6t3.8t3.8t205205180180各地间里程表（单位：各地间里程表（单位：km）2.2t2.2t1.8t1.8t0.5t0.5t270270255255260260120120德州店德州店淄博店淄博店105105东营店东营店200200105105(200)(200)济宁店济宁店190190260260（3535）370370（2020）泰安店泰安店9090140140（5555）250250（4040）120120（160160）滨州店滨州店1401408080（165165）7070（270270）340340（-1010）220220（1010）货运量货运量济南济南配送中心配送中心淄博店淄博店东营店东营店济宁店济宁店泰安店泰安店滨州店滨州店德州德州店店1.7t1.7t1.6t1.6t3.8t3.8t205205180180节约里程排序表（从大从小）节约里程排序表（从大从小）序号序号连接点连接点节约节约里程里程序号序号连接点连接点节约节约里程里程1东营东营滨州滨州2709泰安泰安滨州滨州102淄博淄博东营东营20010济宁济宁滨州滨州-103淄博淄博滨州滨州165114济宁济宁泰安泰安160125淄博淄博泰安泰安556东营东营泰安泰安407淄博淄博济宁济宁358东营东营济宁济宁20方案：方案：第第一一条条路路线线：济济南南淄淄博博东东营营滨滨州州济济南南 共共3.9t3.9t，使使用用一一辆辆4t 4t车，全长共车，全长共430km430km。第第二二条条路路线线：济济南南泰泰安安济济宁宁济济南南 共共3.9t3.9t，使使用用一一辆辆4t 4t车车，全全长共长共400km400km。第第三三条条路路线线：济济南南德德州州济济南南 共共3.2t3.2t，使使用用一一辆辆4t 4t车车，全全程程共共240km240km。小结：四步走四步走收集收集计算计算排序排序绘制绘制最短里程最短里程节约里程节约里程从大到小从大到小优化线路图优化线路图小结需求量小需求量小节约里程法节约里程法拼装送货拼装送货配送效果：配送效果：1.1.缩短配送距离缩短配送距离 2.2.提高车辆利用率提高车辆利用率管理目标：降低配送成本，提高配送效率。管理目标：降低配送成本，提高配送效率。看观谢谢