数学建模中的节约里程法.ppt

《数学建模中的节约里程法.ppt》由会员分享，可在线阅读，更多相关《数学建模中的节约里程法.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三节第三节 物流配送组织物流配送组织第三节 物流配送组织 配送路线合理与否对配送速度、车辆的合理利用和配送费用都有直接影响,因此配送路线的优化问题是配送工作的主要问题之一。采用科学的合理的方法制定配送路线,是配送活动中非常重要的一项工作。第三节 物流配送组织直送式配送运输，是指个供地点别一个客户的专门送货。从物流优化的角度看，直送式客户的基本条件是其需求量接近于或大于可用车辆的额定载质量，需专门派一辆或多辆车一次或多次送货。因此直送情况下，货物的配送要求是多装快跑，选择最短配送线路，以节约时间、费用，提高配送效率。即直送问题的物流优化，主要是寻找物流网络中的最短线路问题。位势法abcde43

2、6742第三节 物流配送组织分送式配送是指由一个供应点对多个客户的共同送货。其基本条件是所有客户的需求量总和不大于一辆车的额定载质量。送货时，由这一辆车装着所有客户的货物，沿着一条精心选择的最佳线路依次将货物送到各个客户手中，这样既保证按时按量将用户需要的货物及时送到，又节约了文辆，节省了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染。节约里程法基本原理基本原理是几何学中三角形一边之长必定小于另外两边之和。节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方

3、式两种。假如一家配送中心（DC）向两个用户A、B运货，配送中心到两用户的最短距离分别是La和Lb，A和B间的最短距离为Lab，A、B的货物需求量分别是Qa和Qb，且（Qa+Qb）小于运输装载量Q，如图所示，如果配送中心分别送货，那么需要两个车次，总路程为：L1=2（La+Lb）。ABDCLaLbABDCLaLb Lab 如果改用一辆车对两客户进行巡回送货，则只需一个车次,行走的总路程为：L2=La+Lb+Lab 有三角形的性质我们知道：Lab（La+Lb）所以第二次的配送方案明显优于第一种，且行走总路程节约：L=（La+Lb）Lab 如果配送中心的供货范围内还存在着：3,4,5，n个用户，在运

4、载车辆载重和体积都允许的情况下，可将它们按着节约路程的大小依次连入巡回线路，直至满载为止，余下的用户可用同样方法确定巡回路线，另外派车。实例分析设一配送中心向13个客户配送商品，配送中心及客户间的最短距离如表1所示，如果配送的车辆载重为200吨，那么利用节约法求解的配送路线的步骤如下：第一步，计算配送中心到库户间的最短距离，画出距离表。因为本例已给出，所以可以直接进行第二步。表1 配送中心到客户间的最短距离表DCDC1 12 23 34 45 56 67 78 89 910101111121213131 112120 02 28 89 90 03 317178 810100 04 415159

5、 98 84 40 05 5151517179 9141411110 06 6202023231515202016166 60 07 7171722221313202016165 54 40 08 88 817179 9191916161111141410100 09 96 618181212222220201717202016166 60 01010161623231414222219199 98 84 48 814140 011112121282818182626222211117 76 6131319195 50 0121211112222141424242121141416161212

6、5 57 79 913130 013131515272720203030282822222323202012129 9161620208 80 0需求量需求量4848363643439292575716165656303057574747919155553838 第二步，根据最短距离表，利用节约法计算出用户间的节约里程，并由大到小排列，编制节约里程顺序表，如表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-L1

7、6=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+21-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=12

8、28：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+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序号序号路程路程节约里程节约里程

9、（La+Lb）Lab1 166113434111155102222212111111316162 26673333121211321212222881016163 37 71 113 32 2131311111219192323771216164 41010113 32 214144451919242444716165 577102929151544619192525881116166 6556292916161141818262622315157 7334282817173351818272722415158 86610282818181212131818282877815159 95572

10、7271919101012181829296612151510105511252520203361717 第三步，根据节约里程顺序表和配送中心的约束条件，绘制配送路线。其具体步骤如下：首先选择最节约里程的路段（611），然后是（67），由于配送路线必须包含DC，且每条循环路线上的客户需求量之和要小于200吨，在接下的选择中满足条件的只有路段（118），此时载重总量为193吨，因为在余下选择中没有满足条件的客户，所以，第一回合的配送路线为（DC76118DC）。按此方法类推，其余的配送路线分别是（DC134DC）、（DC5101213DC）、（DC29DC）。总路程为：（17+4+7+13+8）

11、+（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）+（22+18+18）+2=192 例：由配送中心P向AI等9个用户配送货物。图中连线上的数字表示公路里程（km）。靠近各用户括号内的数字，表示各用户对货物的需求量（t）。配送中心备有2t和4t载重量的汽车，且汽车一次巡回走行里程不能超过35km，设送到时间均符合用户要求，求该配送中心的最优送货方案。计算配送中心至各用户以及各用户之间的最短距离，列

12、表得最短距离表：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 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-

13、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 0 6 0 8 节约里程表节约里程表 根据节约里程表中节约里程多少的顺序，由大到小排列，编制节约里程顺序表，以便尽量使节约里程最多的点组合装车配送。顺位号里程节约里程顺位号里程节约里程顺位号里程节约里程1A-B166H-I810F-G62B-C148B-D710G-H63A-I128D-E715A-D34C-D1110A-H616B-E25A-C1

14、010B-I617D-F16E-F810C-E6 根据节约里程排序表和配车（车辆的载重和容积因素）、车辆行驶里程等约束条件，渐进绘出配送路径：ABCDEFGHIP(0.9)(1.2)(1.6)(1.1)(0.9)(0.9)(0.6)(1.7)(0.5)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。优缺点分析优点：节约法是一种简便、易行的方法，一方面体现出优化运输过程，与一般方法

15、相比缩短了运输路程；另一方面，它也体现了物流配送网络的优势，实现了企业物流活动的整合，而且思路简单清晰、便于执行。缺点：第一，利用节约法选择配送路线过于强调节约路程，而没考虑行程中的时间因素，在许多情况下，时间更能决定物流配送的成本与服务质量。例如城市间配送时对高速公路的选择，城市内部上下班时间的道路拥挤，一个巡回配送过程中的时间长短，直接影响配送人员的精神状态，而人员的精神状态又与交通事故和配送错误相连等，所以时间对配送路线的选择有时更重要。第二，利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。由于现代的消费者的需求倾向于个性化，引起企业的生产、销售和配送也愈来愈倾向于小批量，多品

16、种，多批次。而节约法更适合需求稳定或是需求的时间不紧迫，这显然不能满足现代多变得市场环境。最后值得一提的是，节约法计算的配送路线并不是总路程最短。由上面的案例可知,如若采用配送路线(DC-1-3-4-DC)，(DC-2-5-6-DC)，(DC-10-7-11-DC)和(DC-8-12-13-9-DC),总路程为165 km,比采用节约法的计算结果少11 km.原因是节约法一方面要缩短总路程,另一方面又要充分利用车辆的运输空间(载重/容积)，减少配送车次，而且只要在前一条预设路线上运行的配送车辆的运输空间允许，就必须按着节约路程的大小顺序进行选择而不考虑其它的预设路线，在事实情况下选择的路线并不

17、能“节约”路程和有效利用运输空间，而且运输的车次也不一定减少，对比上例中两种方案就会发现这一问题。节约法的改进建议 由以上的分析可知,节约法简便易行,同时也有一些弊端.是否可以通过改进使其成为一种最优的方法呢?在配送路线选择决策时,通常考虑较优的原则,而不是最优化原则.深入了解客户,加强与客户的信息交流。通过对客户需求的时间变化对其进行分类,以增加配送的灵活性。路线决策过程中实施多路线同步决策。节约法的实施过程,要综合考虑路程长短和时间因素。配送的总体过程实际上还会受商品分拣、装卸、搬运设备和货物组装的共同影响。题目例：有一配送中心P，其配送网络如图所示，A-D为各收货点，括号内的数字为各收货

18、点的需求量（吨），两点间连线上的数字是距离（公里）。运输货车有最大为2吨和4吨，试确定配送路线。PABCD87910554(0.6)(0.7)(1.7)(0.8)解：1 计算配送中心与各收货点及各收货点相互之间的最短距离PABCDP10978A4914B510C5D2 计算各收货点间的节约里程数，并将其进行排序序号123456组合ABBCCDACBDAD节约里程 1511108743 按节约里程大小组合顺序组合，安排配送路线由表可以看出AB节约里程最大，已知A、B的配送货物量是：0.7+1.7=2.4吨，在货车载重限制内，可以入选，BC节约里程次之，C的配送货物数量是0.8吨，2.4+0.8=3.2吨，未超出货车载重量。CD再次之，D的配送量是0.6吨，3.2+0.6=3.8吨，可以拼装一辆4吨货车，因此配送线路一条，即PABCDP,全程为：10+4+5+5+8=32The end,thank you!