资源描述
配送线路优化方法配送线路优化方法优选1配送线路优化方法优选1（一）直送式配送运输（一）直送式配送运输适用方法适用方法最短路径法最短路径法适用条件：适用条件：1 1、由配送中心向每一位客户开展专门送货；、由配送中心向每一位客户开展专门送货；2 2、该客户的送货量一般必须满足配送车辆满载。、该客户的送货量一般必须满足配送车辆满载。配送效果：配送效果：1.1.配送车辆满载运输；配送车辆满载运输；2.2.配送运输路线距离最短。配送运输路线距离最短。标点法设计标点法设计标点法设计标点法设计最短线路最短线路最短线路最短线路一对一配送的最短路线问题一对一配送的最短路线问题优选2（一）直送式配送运输适用方法最短路径法标点法设计最短线路【例】求1-6的最短距离。供应商客户优选3供应商客户优选3首先求出从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优选4首先求出从1出发的一条最短路径（1-2：4），求次短路径（2（二）分送式配送运输（二）分送式配送运输适用方法适用方法节约里程法节约里程法适用条件：适用条件：1 1、由配送中心向多位客户开展拼装送货；、由配送中心向多位客户开展拼装送货；2 2、每位客户的送货量都不能满足配送车辆、每位客户的送货量都不能满足配送车辆满载。满载。配送效果：配送效果：1.1.配送车辆满载运输；配送车辆满载运输；2.2.配送运输路线距离最短。配送运输路线距离最短。一对多配送的最短路线问题一对多配送的最短路线问题供应商客户优选5（二）分送式配送运输适用方法节约里程法一对多配送的最短路节约里程法的意义节约里程法的意义 送送货货时时，由由一一辆辆车车装装载载所所有有客客户户的的货货物物，沿沿着着一一条条精精心心设设计计的的最最佳佳路路线线依依次次将将货货物物送送到到各各位位客客户户手手中中，这这样样既既保保证证按按时时按按量量将将用用户户需需要要的的货货物物及及时时送送达达，又又节节约约了了车车辆辆，节节省省了了费费用用，缓缓解解了了交交通通紧紧张张的的压压力力，并并减减少少了了运运输输对对环环境境造造成成的的污染。污染。1.1.满足客户配送需要满足客户配送需要2.2.减少配送车辆使用减少配送车辆使用3.3.缓解交通紧张压力缓解交通紧张压力优选6节约里程法的意义 送货时，由一辆车装载所有客户的货节约里程法(Saving Algorithm)车辆调度程序法(Vehicle Scheduling Program:VSP)又称节约算法，是指用来解决运输车辆数目不确定的问题的最有名的启发式算法。核心思想:节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。优选7节约里程法(Saving Algorithm)车辆调度程序法节约里程法利用节约法制定出的配送方案除了使配送总吨公里数最小外，还应满足以下条件：满足所有用户的需求不使任何一辆车超载每辆车每天的总运行时间或行驶里程不超过规定的上限；用户到货时间要求。不得超过规定时间。优选8节约里程法利用节约法制定出的配送方案除了使配送总吨公里数最小节约里程法PA（客户）B（客户）ab(配送中心)P A（客户）B（客户）(配送中心)bac运行距离为：2a+2b运行距离为：a+b+c节约行程：节约行程：a+bc优选9节约里程法PA（客户）B（客户）ab(配送中心)P A（客户节约里程法例题：已知配送中心P0向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示，配送中心有3台2t卡车和2台4t两种车辆可供使用。利用节约里程法制定最优的配送方案。优选10节约里程法例题：已知配送中心P0向5个用户Pj配送货物，其配(1.4)P0P2P3P4P5P1(2.4)(0.9)(1.7）(1.5)10127594136812168优选11(1.4)P0P2P3P4P5P1(2.4)(0.9 节约里程法第第1 1 步：作运输里程表，列出配送中心到用户步：作运输里程表，列出配送中心到用户及用户间的最短距离。及用户间的最短距离。优选12节约里程法第1 步：作运输里程表，列出配送中心到用户及用户间节约里程法第第2 2步：按节约里程公式求得相应的节约里程数步：按节约里程公式求得相应的节约里程数优选13节约里程法第2步：按节约里程公式求得相应的节约里程数优选13节约里程法第第 3 步：将节约里程按从大到小顺序排列步：将节约里程按从大到小顺序排列优选14节约里程法第 3 步：将节约里程按从大到小顺序排列优选14节约里程法第第4 4步：根据载重量约束与节约里程大小，顺步：根据载重量约束与节约里程大小，顺序连接各客户结点序连接各客户结点,形成二个配送路线形成二个配送路线 .P2P3 P3P4P2P4P4P5 P1P2 P1P5 P1P3 P2P5 P3P5 P1P4（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）(1.5)10768845优选15节约里程法第4步：根据载重量约束与节约里程大小，顺序连接各客节约里程法（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）(1.5)1078845配送线路1优选16节约里程法（1.4）P0P2P3P4P5P1（2.4）（0.节约里程法（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）(1.5)1078845配送线路1配送线路1：运量=1.7+0.9+1.4=4t 运行距离845724km 用一辆 4t车运送节约距离=18km 配送线路2:运量=2.4+1.5=3.9t4t 运行距离8101634km 用一辆 4t车运送 节约距离=2km优选17节约里程法（1.4）P0P2P3P4P5P1（2.4）（0.节约里程法（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）(1.5)107688初始方案：配送线路5条，需要车5辆 配送距离=392=78KM 优选18节约里程法（1.4）P0P2P3P4P5P1（2.4）（0.节约里程法初始方案：初始方案：配送线路配送线路5 5条，条，需要车需要车5 5辆辆配送距离：配送距离：392=78KM392=78KM优化后的方案：优化后的方案：2 2条配送线路，条配送线路，2 2辆辆4t4t车车配送距离：配送距离：2424343458km58km优选19节约里程法初始方案：优选19练习练习位于牡丹江市内的百家姓配送中心（位于牡丹江市内的百家姓配送中心（P P0 0）向）向它旗下的它旗下的1010家连锁商店家连锁商店p pi i(i=1,2,(i=1,2,10),10)配配送商品，其配送网络如下图所示。送商品，其配送网络如下图所示。图中括号内的数字表示每一家连锁店的需图中括号内的数字表示每一家连锁店的需求量（求量（t t），线路上的数字表示两节点之间），线路上的数字表示两节点之间的距离（的距离（kmkm）。配送中心现有）。配送中心现有2t2t和和4t4t车辆车辆可供使用，并且每辆车配送距离不得超过可供使用，并且每辆车配送距离不得超过30km30km。请为百家姓配送中心制定最优的配送方案。请为百家姓配送中心制定最优的配送方案。优选20练习位于牡丹江市内的百家姓配送中心（P0）向它旗下的10家连优选21优选21第一步：计算最短距离。根据配送网络中的已知条件，计算配送中心与客户及客户之间的最短距离，结果见表11-11。第二步：计算节约里程sij,结果见表11-12。优选22第一步：计算最短距离。根据配送网络中的已知条件，计算配送中心l第三步：将节约sij,进行分类，按从大到小的顺序排列，得表11-13 优选23第三步：将节约sij,进行分类，按从大到小的顺序排列，得表1l第四步：确定配送线路。从分类表中，按节约里程大小顺序，组成线路图 优选24第四步：确定配送线路。从分类表中，按节约里程大小顺序，组成线（1）初始方案：对每一客户分别单独派车送货，结果如图11-10。优选25（1）初始方案：对每一客户分别单独派车送货，结果如图11-1修正方案4 优选26修正方案4 优选26
展开阅读全文