配送线路优化.ppt

配送线路优化 直送式配送运输——最短路径问题 分送式配送运输——节约历程问题 * 一、线路优化设计的意义 1、适时适当地利用现有的运输工具和道路状况，及时、安全、方便、经济地将客户所需商品准确地送达客户手中； 2、在配送运输线路设计中，需根据不同客户群的特点和要求，选择不同的线路设计方法； 3、最终达到节省时间、运距和降低配送运输成本的目的。 二、配送线路优化方法 （一）直送式配送运输 适用条件： 1、由配送中心向每一位客户开展专门送货； 2、该客户的送货量一般必须满足配送车辆满载。 适用方法——最短路径法 （二）分送式配送运输 适用条件： 1、由配送中心向多位客户开展拼装送货； 2、每位客户的送货量都不能满足配送车辆满载。 适用方法——节约里程法 2 3 7 1 8 4 5 6 2 4 2 11 8 2 1 5 1 12 4 8 2 9 现问从u1到u8,的各条路线中,哪一条的总长度最短? 最短路问题 （0） 8 2 11 （2） 现问从u1到u8,的各条路线中,哪一条的总长度最短? （0） 2 3 7 1 8 4 5 6 2 4 2 11 8 2 1 5 1 12 4 8 2 9 8 2 11 （2） 6 7 （6） 最短路问题 现问从u1到u8,的各条路线中,哪一条的总长度最短? （0） 2 3 7 1 8 4 5 6 2 4 2 11 8 2 1 5 1 12 4 8 2 9 8 2 11 （2） 6 7 （6） 15 （7） 最短路问题 现问从u1到u8,的各条路线中,哪一条的总长度最短? （0） 2 3 7 1 8 4 5 6 2 4 2 11 8 2 1 5 1 12 4 8 2 9 8 2 11 （2） 6 7 （6） 15 （7） 8 11 （8） 15 最短路问题 现问从u1到u8,的各条路线中,哪一条的总长度最短? （0） 2 3 7 1 8 4 5 6 2 4 2 11 8 2 1 5 1 12 4 8 2 9 8 2 11 （2） 6 7 （6） 15 （7） 8 11 （8） 15 20 （11） 最短路问题 现问从u1到u8,的各条路线中,哪一条的总长度? （0） 2 3 7 1 8 4 5 6 2 4 2 11 8 2 1 5 1 12 4 8 2 9 8 2 11 （2） 6 7 （6） 15 （7） 8 11 （8） 15 20 （11） 13 （13） 从u1到u8,的最短路为13,路径为1-3-6-7-8 最短路问题 为实现配送所节约里程。可根据用户要求、道路条件等设计几种巡回配送方案，再计算节约里程，VSP方法可对所有配送地点计算其节约里程，按节约量的大小顺序，优选确定配送路线。 原 现 节约里程（VSP）法原理 提 出 任 务 位于牡丹江市内的百家姓配送中心（P0）向它旗下的10家连锁商店pi(i=1,2,…,10)配送商品，其配送网络如下图所示。 图中括号内的数字表示每一家连锁店的需求量（t），线路上的数字表示两节点之间的距离（km）。配送中心现有2t和4t车辆可供使用，并且每辆车配送距离不得超过30km。 请为百家姓配送中心制定最优的配送方案。 配送网络图 P0 9 e 1.4 8 6 10 7 6 f 1.5 8 g 0.6 3 2 9 h 0.8 4 i 0.5 10 j 0.6 7 a 0.7 10 b 1.5 9 c 0.8 7 d 0.4 8 5 5 4 4 11 8 百家姓配送中心交通图 配送网络图 P0 e 1.4 8 f 1.5 8 g 0.6 3 h 0.8 4 i 0.5 10 j 0.6 7 a 0.7 10 b 1.5 9 c 0.8 7 d 0.4 8 初始方案：从P点向各点分别派车送货。 初始方案运行结果： 1、从百家姓配送中心出发，需要设计10条配送线路，分别向10家连锁店配送商品； 2、需要10辆2t的配送车辆（每家连锁店的需要量都低于2t），总配送距离为148km。 P 10 9 4 7 9 5 8 14 10 5 8 18 14 9 6 8 18 17 15 13 7 3 13 12 10 11 10 6 4 14 13 11 12 12 8 2 10 11 15 17 18 18 17 11 9 a b c d e f g h i j 7