节约里程法课件.ppt

《节约里程法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、节约里程法一、配送线路的优化方法㈠一对一配送的最短路线问题示例：求1-6的最短距离。供应商客户配送线路的优化首先求出从1出发的一条最短路径（1-2：4），求次短路径（2-5：2），依次类推：（5-6：8），（5-4-6：7），（5-4-3-6：6），最短距离求得的最短路径是：1-2-5-4-3-6距离是：4+2+6=12㈡一对多配送的最短路线问题一、配送线路的优化方法配送线路的优化节约里程法原理：三角形一边之长必定小于另外两边之和。在汽车载重量允许的情况下，采用巡回发货比采用往返发货可节约汽车走行里程为：∆L=[2(L1+L2)]-(L1+

2、L2+L3)=L1+L2-L3节约里程法的基本规定利用里程节约法确定配送路线的主要出发点是，根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离来制定使配送车辆总的周转量达到或接近最小的配送方案。节约里程法应用案例某连锁零售店，下设有一个配送中心P和10个连锁分店A～J，配送中心和各连锁分店及各连锁分店之间的位置关系如下图1所示，两点间连线上的数字为两点间的路线长度（单位：公里）。各连锁分店对某种商品的需求量见表1，该商品由配送中心统一采购并进行配送。配送中心备用2t和4t的货车，限定送货车辆一次巡回距离不超过35公里，设送到时间均符合用户

3、要求，求配送中心的最优送货方案。图1配送网络图表1各连锁分店需求量重量单位：吨用节约里程法进行求解，其步骤如下：第一步：从配送网络图中计算出配送中心至各连锁分店及各连锁分店之间的最短距离，并做出最短距离表（见表2）。表2最短距离表第二步：由最短距离表，利用“节约里程”法计算出各连锁分店之间的节约里程，做出节约里程表（见表3），计算结果有正有负，节约里程为负数时，无实际意义，在表内写0。表3节约里程表第三步：将节约里程由大到小顺序排列，列出节约里程排序表（见表4），以便尽量使节约里程最多的点组合装车配送。第四步：根据节约里程排序表和配送车辆载重及行驶里

4、程等约束条件，渐近绘出如图2所示的配送路线图。图2配送路线图从配送路线图可看出，依次确定的三条配送路线均符合配送中心的约束条件，需要2t货车3辆，总走行里程为70km，若简单地每个连锁分店送货，需要2t货车10辆，走行总里程148km。案例分析例：某一配送中心p0向10个客户pj(j=1,2,…,10)配送货物，其配送网络如图11-9所示。图中括号内的数字表示客户的需求量（T），线路上的数字表示两节点之间的距离。配送中心有2t和4t两种车辆可供使用，试制定最优的配送方案。第一步：计算最短距离。根据配送网络中的已知条件，计算配送中心与客户及客户之间的最

5、短距离，结果见表11-11。第二步：计算节约里程sij,结果见表11-12。第三步：将节约sij,进行分类，按从大到小的顺序排列，得表11-13第四步：确定配送线路。从分类表中，按节约里程大小顺序，组成线路图（1）初始方案：对每一客户分别单独派车送货，结果如图11-10。修正方案4第四节配送路线设计一、配送路线选择问题物流中心在组织货物配送时，有n个客户，处在同一城市不同地区，如何取定最佳的配送路线？例题：如图8-1所示的运输网络，试求出最优路线。V1V2V7V4V3V6V55712481296910109图8-1V1V2V7V4V3V6V55712

6、481296910109图8-2解：图中顶点V2，V4，V5，V7为奇数顶点，要使它成为欧拉图，需用加重复边的方法使这四个顶点变为偶次顶点。选择在（V2，V5）（V4，V7）上加重复边，得到的初始方案示于图8-2中，圈（V2,V5,V4,V7,V2）中，重复边总权为9+4=13，非重复边总权为5+7=12，所以此方案不满足最优条件，需继续调整。调整时在不满足条件的圈中，将重复边与非重复边对换，即将重复边由（V2，V5）（V4，V7）换成（V2，V7）（V4，V5），得到图8-3。经检验所有圈均满足最优条件，即得最优路线。V1V2V7V4V3V6V55

7、712481296910109图8-3二、简单配送路线设计例题：在一个配送中心P有一辆载重量为Q的货车，现有N个客户需要配送，已知用户i的需求量是Gi（i=1,2,3……,n），且≤Q，求在满足各个用户需求的条件下，总运送路程最短的路线，即为简单配送路线问题。其求解思路是把配送中心也作为一个用户点，这样就把问题转化为n+1个点的旅行商问题。例表8-4给出了配送中心P（标记为中心0）和7个用户之间的距离，求最短配送路线？此类问题的解法是运用节约算法求解最优路线，节约算法又称C-W算法，是由Clarke和Wright在1964年提出的。它的基本思想是首先

8、把各用户单独与配送中心相连，构成一条仅含以各点的线路。此时线路距离Z为：然后计算将点i和j到同一条线路上得到