《物流配送中心的VPR问题的节约里程法课件》由会员分享，可在线阅读，更多相关《物流配送中心的VPR问题的节约里程法课件（26页珍藏版）》请在金锄头文库上搜索。
1、节约里程法节约里程法目录基本原理基本原理案例分析案例分析优缺点分析优缺点分析改进建议改进建议基本原理基本原理是几何学中三角形一边之长必定小于另外两边之和。节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。假如一家配送中心（DC）向两个用户A、B运货，配送中心到两用户的最短距离分别是La和Lb，A和B间的最短距离为Lab，A、B的货物需求量分别是Qa和Qb，且（Qa+Qb）小于运输装载量Q，如图所示，如果配送中心分别送货，那么需要两个车次，总路程为：L1=2（
2、La+Lb）。ABDCLaLbABDCLaLb Lab 如果改用一辆车对两客户进行巡回送货，则只需一个车次,行走的总路程为： L2=La+Lb+Lab 有三角形的性质我们知道： Lab（La+Lb） 所以第二次的配送方案明显优于第一种，且行走总路程节约： L=（La+Lb）Lab 如果配送中心的供货范围内还存在着：3,4,5，n个用户，在运载车辆载重和体积都允许的情况下，可将它们按着节约路程的大小依次连入巡回线路，直至满载为止，余下的用户可用同样方法确定巡回路线，另外派车。实例分析设一配送中心向13个客户配送商品，配送中心及客户间的最短距离如表1所示，如果配送的车辆载重为200吨，那么利用节约
3、法求解的配送路线的步骤如下：第一步，计算配送中心到库户间的最短距离，画出距离表。因为本例已给出，所以可以直接进行第二步。 表1 配送中心到客户间的最短距离表DCDC1 12 23 34 45 56 67 78 89 910101111121213131 112120 02 28 89 90 03 317178 810100 04 415159 98 84 40 05 5151517179 9141411110 06 6202023231515202016166 60 07 7171722221313202016165 54 40 08 88 817179 9191916161111141410
4、100 09 96 618181212222220201717202016166 60 01010161623231414222219199 98 84 48 814140 011112121282818182626222211117 76 6131319195 50 01212111122221414242421211414161612125 57 79 913130 013131515272720203030282822222323202012129 9161620208 80 0需求量需求量4848363643439292575716165656303057574747919155553
5、838 第二步，根据最短距离表，利用节约法计算出用户间的节约里程，并由大到小排列，编制节约里程顺序表，如表2所示。 L=（La+Lb）Lab12：L1+L2-L12=12+8-9=1113：L1+L3-L13=12+17-8=2114：L1+L4-L14=12+15-9=1815：L1+L5-L15=12+15-17=1016：L1+L6-L16=12+20-23=917：L1+L7-L17=12+17-22=718：L1+L8-L18=12+8-17=319：L1+L9-L19=12+6-18=0110：L1+L10-L1、10=12+16-23=7111：L1+L11-L1、12=12+2
6、1-28=5112：L1+L12-L1、12=12+11-22=1113：L1+L13-L1、13=12+15-27=023：L2+L3-L23=8+17-10=1524：L2+L4-L24=8+15-8=1525：L2+L5-L25=8+15-9=1426：L2+L6-L26=8+20-15=1327：L2+L7-L27=8+17-13=1228：L2+L8-L28=8+8-9=729：L2+L9-L29=8+6-12=2210：L2+L10-L2、10=8+16-14=10211：L2+L11-L2、11=8+21-18=11212：L2+L12-L2、12=8+11-14=5213：L2
7、+L13-L2、13=8+15-20=334：L3+L4-L34=17+15-4=2835：L3+L5-L35=17+15-14=1836：L3+L6-L36=17+20-20=17表表2 节约里程表节约里程表序序号号路程路程节约里程节约里程（La+Lb）Lab序号序号路程路程节约里程节约里程（La+Lb）Lab序号序号路程路程节约里程节约里程（La+Lb）Lab1 166113434111155102222212111111316162 26673333121211321212222881016163 37 71 113 32 2131311111219192323771216164 410
8、10113 32 214144451919242444716165 577102929151544619192525881116166 6556292916161141818262622315157 7334282817173351818272722415158 86610282818181212131818282877815159 955727271919101012181829296612151510105511252520203361717 第三步，根据节约里程顺序表和配送中心的约束条件，绘制配送路线。其具体步骤如下：首先选择最节约里程的路段（611），然后是（67），由于配送路线必须包
9、含DC，且每条循环路线上的客户需求量之和要小于200吨，在接下的选择中满足条件的只有路段（118），此时载重总量为193吨，因为在余下选择中没有满足条件的客户，所以，第一回合的配送路线为（DC76118DC）。按此方法类推，其余的配送路线分别是（DC134DC）、（DC5101213DC）、（DC29DC）。总路程为：（17+4+7+13+8）+（12+8+4+15）+(15+9+9+8+15)+(8+12+6)=170 原路程为：2（12+8+17+15+15+20+17+8+6+16+21+11+15） =362总共节约里程为：362170=192 或（33+34+16）+（28+21）+
10、（22+18+18）+2=192 例：由配送中心P向AI等9个用户配送货物。图中连线上的数字表示公路里程（km）。靠近各用户括号内的数字，表示各用户对货物的需求量（t）。配送中心备有2t和4t载重量的汽车，且汽车一次巡回走行里程不能超过35km，设送到时间均符合用户要求，求该配送中心的最优送货方案。计算配送中心至各用户以及各用户之间的最短距离，列表得最短距离表： P A B C D E F G H I PABCDEF GHI 11 10 9 6 7 10 10 8 7 5 10 14 18 21 21 13 6 5 9 15 20 20 18 11 4 10 19 19 17 16 6 15
11、16 14 13 9 17 15 14 14 18 17 12 17 7 由最短距离表，利用节约法计算出各用户之间的节约里程，编制节约里程表：AB:LA+LBLAB=11+10-5=16AC:LA+LCLAC=11+9-10=10AD:LA+LDLAD=11+6-14=3AE:LA+LELAE=11+7-18=0AF:LA+LFLAF=11+10-21=0AG:LA+LGLAG=11+10-21=0 A B C D E F G H I ABCDEF GHI 16 10 3 0 0 0 6 12 14 7 2 0 0 0 6 11 6 0 0 0 0 7 1 0 0 0 8 0 0 0 6 0
12、0 6 0 8 节约里程表节约里程表 根据节约里程表中节约里程多少的顺序，由大到小排列，编制节约里程顺序表，以便尽量使节约里程最多的点组合装车配送。顺位号里程节约里程顺位号里程节约里程顺位号里程节约里程1A-B166H-I810F-G62B-C148B-D710G-H63A-I128D-E715A-D34C-D1110A-H616B-E25A-C1010B-I617D-F16E-F810C-E6 根据节约里程排序表和配车（车辆的载重和容积因素）、车辆行驶里程等约束条件，渐进绘出配送路径：ABCDEFGHIP(0.9)(1.2)(1.6)(1.1)(0.9)(0.9)(0.6)(1.7)(0.5
13、)475586669101012路径A路径B路径C路径A：4t车，走行32km，载重量3.7t；路径B：4t车，走行31km，载重量3.9t；路径C：2t车，走行30km，载重量1.8t。 总共走行里程93km，共节约里程（16+14+12）+（8+7）+6=63km。优缺点分析优点： 节约法是一种简便、易行的方法，一方面体现出优化运输过程，与一般方法相比缩短了运输路程；另一方面，它也体现了物流配送网络的优势，实现了企业物流活动的整合，而且思路简单清晰、便于执行。缺点： 第一，利用节约法选择配送路线过于强调节约路程，而没考虑行程中的时间因素，在许多情况下，时间更能决定物流配送的成本与服务质量。
14、例如城市间配送时对高速公路的选择，城市内部上下班时间的道路拥挤，一个巡回配送过程中的时间长短，直接影响配送人员的精神状态，而人员的精神状态又与交通事故和配送错误相连等，所以时间对配送路线的选择有时更重要。 第二，利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。由于现代的消费者的需求倾向于个性化，引起企业的生产、销售和配送也愈来愈倾向于小批量，多品种，多批次。而节约法更适合需求稳定或是需求的时间不紧迫，这显然不能满足现代多变得市场环境。 最后值得一提的是，节约法计算的配送路线并不是总路程最短。由上面的案例可知,如若采用配送路线(DC - 1 - 3 - 4 - DC) ， (DC -
15、2 - 5 - 6 - DC)， (DC - 10 - 7 - 11 - DC) 和(DC - 8 - 12 - 13 - 9 -DC) ,总路程为165 km ,比采用节约法的计算结果少11 km. 原因是节约法一方面要缩短总路程,另一方面又要充分利用车辆的运输空间(载重 / 容积) ，减少配送车次，而且只要在前一条预设路线上运行的配送车辆的运输空间允许，就必须按着节约路程的大小顺序进行选择而不考虑其它的预设路线，在事实情况下选择的路线并不能“节约”路程和有效利用运输空间，而且运输的车次也不一定减少，对比上例中两种方案就会发现这一问题。节约法的改进建议 由以上的分析可知,节约法简便易行,同时也有一些弊端.是否可以通过改进使其成为一种最优的方法呢 ?在配送路线选择决策时,通常考虑较优的原则,而不是最优化原则.深入了解客户,加强与客户的信息交流。通过对客户需求的时间变化对其进行分类,以增加配送的灵活性。路线决策过程中实施多路线同步决策。节约法的实施过程,要综合考虑路程长短和时间因素。配送的总体过程实际上还会受商品分拣、装卸、搬运设备和货物组装的共同影响。The end,thank you!
