配送路线的优化

复习：6.2配送的方法1）配货2）车载货物的配装3）配送路线的确定目标：①以效益最高为目标；②以成本最低为目标；③以路程最短为目标；④以tkm最小为目标；⑤以准确性最高为目标。①满足所有人对货物品种、规格、数量的要求；②满足收货人对货物发到时间范围的要求；③在允许通行的时间内进行配送；④各配送路线的货物量不得超过车辆容积和载重量的限制；⑤在配送中心现有运力允许的范围内。约束条件：6.3配送路线的优化——节约法（节约里程法）一、节约法的基本规定利用节约法确定配送路线的主要出发点是，根据配送中心的运输能力（包括车辆的多少和载重量）和配送中心到各个用户以及各个用户之间的距离来制订使总的车辆运输的tkm数量最小的配送方案。假设条件：①配送的是同一种货物；②各用户的坐标及需求量均为已知；③配送中心有足够的运输能力。方案需要满足的条件：①方案能满足所有用户的需求；②不使任何一辆车超载；③每辆车每天的总运行时间或行使里程不超过规定的上限；④能满足用户到货时间要求。二、节约法的基本思想和求解步骤1、节约法的基本思想如图所示，设po点为配送中心，它分别向用户pi和pj送货，设po到pi和pj的距离为doi和doj，两个用户pi和pj之间的距离为dij。doidojdij是从配送中心po向用户pi、pj分别送货●pi●●popj（a）配送路线为：popidoipodoipjdoj●pi●●popjpodoj总的配送距离为Da=2doi+2doj方案a方案b是从配送中心po向用户pi、pj共同送货●pi●●popj配送路线为：popidoipjdijpodoj或popjdojpidijpodoi总的配送距离为Db=doi+doj+dij对比两个方案，哪个更合理呢？这就要看Da和Db哪个最小，配送距离越小则说明方案越合理：Da-Db=2doi+2doj-(doi+doj+dij)=doi+doj-dij●pi●●popj（b）把po、pi、pj看成是一个三角形的三个顶点，那么doi、doj、dij则是这个三角形三条边的长度。由三角形的几何性质可知，任意两条边之和均大于第三条边。doidojdij因此，可以认定的结果是：Da-Db0或DaDb由上可知，b方案优于a方案，这种分析方案优劣的思想就是节约法的基本思想。我们把Da-Db的值定义为“节约量”，用Sij表示，得下式：Sij=Da-Db=doi+doj-dij2、节约法的解题步骤例：设某配送中心p0向5个用户pj(j=1~5)配送货物。各用户的需求量用qj（吨）表示，从配送中心到各用户的距离为doj(公里，j=1~5)，各用户之间的距离dij（公里，i=1~5，j=1~5）；各参数的数值见下表，配送中心共有若干4吨车和6吨车，问如何制订出最优的配送方案。pj12345qj（吨）1.21.71.51.41.7doj（公里）914212322配送距离等相关参数各用户之间的距离关系dijp15p2127p3221710p421162119p5解：列出配送距离、需求量和各用户之间的距离关系表qjp01.29p11.7145p21.521127p31.423221710p41.72221162119p5（1）选择初始配送方案初始配送方案是分别向每个用户单独送货（方案a）。由于题中各用户的需求量qj均小于4吨，因此初始方案中车辆分派为用5量载重量为4吨的汽车分别完成送货任务。总配送距离S0=2doj=152*（9+14+21+23+22）=178km计算所有节约量Sij=doi+doj-dij，并把计算结果写到单元格左上角。qjp01.29p11.7145p21.521127p31.423221710p41.72221162119p5节约量公式Sij=doi+doj-dijqjp01.29p11.7145p21.521127p31.423221710p41.72221162119p5S12S13、S23S14、S24、S34S15、S25、S35、S45S12=9+14-5=18S13=9+21-12=18S23=14+21-7=28S14=S24=S34=S15=S25=S35=S45=9+23-22=1014+23-17=2021+23-10=349+22-21=1014+22-16=2021+22-21=2223+22-19=26计算：qjp01.29p1181.7145p218281.521127p31020341.423221710p4102022261.72221162119p5qjp01.29p1181.7145p218281.521127p31020341.423221710p4102022261.72221162119p5（2）修正方案③用户pi和pj的需求量qi和qj之和应小于现有车辆中某种型号的车辆的载重量（一般指小于最大载重车辆的载重量）。qjp01.29p1181.7145p218281.521127p31020341.423221710p4102022261.72221162119p5①Smaxij所对应的两个用户pi和pj有需求量存在；选出满足下列条件的最大节约量Smaxij②pi和pj不在同一配送路线上；qjp01.29p1181.7145p218281.521127p31020341.423221710p4102022261.72221162119p5qjp01.29p1181.7145p218281.521127p31020341.423221710p4102022261.72221162119p5p0p3p4p0节约数为34，送货量为2.9吨（1.5+1.4）。qjp01.29p1181.7145p218281.521127p31020341.423221710p4102022261.72221162119p5p0p2p3p4p0①Smaxij所对应的两个用户pi和pj有需求量存在；②pi和pj不在同一配送路线上；③用户pi和pj的需求量qi和qj之和应小于现有车辆中某种型号的车辆的载重量（一般指小于最大载重车辆的载重量）。三个条件：节约数为62(34+28)，送货量为4.6吨(2.9+1.7)。qjp01.29p1181.7145p218281.521127p31020341.423221710p4102022261.72221162119p5p0p2p3p4p5p0节约数为88(62+26)，送货量为6.3吨(4.6+1.7)，×p0p1p2p3p4p0节约数为80(62+18)，送货量为5.8吨(4.6+1.2)。路线一：路线二：qjp01.29p1181.7145p218281.521127p31020341.423221710p4102022261.72221162119p5p0p5p0送货量为1.7吨qjp01.29p1181.7145p218281.521127p31020341.423221710p4102022261.72221162119p56.3＞6，不符合条件三。归纳整理最优配送方案：路线一：p0p1p2p3p4p0节约数为80km，送货量为5.8吨，选用一辆载重量为6吨的车送货。路线二：p0p5p0送货量为1.7吨，选用一辆载重量为？吨的车送货。送货量为1.7吨，选用一辆载重量为4吨的车送货。总的配送距离=178-80=98km小结：1、节约法的基本规定——条件2、节约法的基本思想——公式Sij=Da-Db=doi+doj-dij3、节约法的步骤——Sij计算Smaxij选择载重车量的选择qjp01.29P11.7145P21.521127P31.423221710P41.72221162119P510161620381.425242330289P61020263044501.23231262725107P7102020244250581.93635303735161110P810161620385054681.838373643412213166P91020323644506472681.64241363129201710612P10102034414450647276841.7504944373128251814128P111.1525146392930272016201010P12设某配送中心p0向12个用户pj(j=1~12)配送货物。各用户的需求量用qj（吨）表示，从配送中心到各用户的距离为doj(公里，j=1~12)，各用户之间的距离dij（公里，i=1~12，j=1~12）；各参数的数值见左表，配送中心共有若干4吨车和6吨车，问如何制订出最优的配送方案。课后练习