配送路线优化

项目三配送服务教学任务：1.进货入库作业、储存作业、盘点作业、返品处理作业2.订单处理与补货、拣货作业3.出货作业上——车辆配装、货品装箱、装卸工安排4.出货作业下——配送线路优化项目三配送服务小组PPT介绍互动：提问+分享内容补充+总结任务3

出货作业之配送线路优化

一、最短路径法

二、节约法任务3

配送线路优化方法

之1：最短路径法一、最短路径法

所谓最短路径法，是指要从网络图中某顶点出发，经过图中路径到达另一顶点，而这些路径不止一条，如何找到一条路径使各边的权值之和为最小。

任务3配送线路优化方法

之1：最短路径法最短路径法示例1：

新加坡某配送中心签订了一项配送运输合同，要从配送中心A配送一批货物到销售地F,两点之间可选择的行车路线如图所示，求从配送中心A到销售地F的最短路径。

DEBACF11428741823任务3

配送线路优化方法

之1：最短路径法

最短路径法示例2：

从V0到V6找出最短路径？

任务3配送线路优化方法

之1：最短路径法

最短路径法计算3

任务3

配送线路优化方法

之1：最短路径法

最短路径法计算3参考答案：

2的最短距离100路径1-23的最短距离175路径1-34的最短距离150路径1-45的最短距离325路径1-4-56的最短距离359路径1-4-67的最短距离425路径1-4-78的最短距离550路径1-4-7-89的最短距离550路径1-4-6-910的最短距离575路径1-4-6-9-10任务3配送线路优化方法

之1：最短路径法

最短路径法练习题：

某配送公司要将客户急需的商品从配送中心P运送到商场Q，图1表示由起点P到终点Q的路线图，各条弧所对应的数字表示通过该段路线所需时间。试求所需时间最短路线。

任务3配送线路优化方法

之2：节约法（起止点重合的配送路线选择）

任务导入1：

某车一天的货运任务如下图：求最佳行车路线。注：方框为供货点，椭圆为需求点。K=4吨A=2吨B=1吨C=1吨121116678解：分析：从供货点到需求点再返回供货点的线路共4条，距离计算如下：1：K-A-B-C-K,L1=12+6+7+11=362：K-C-B-A-K,L2=11+7+6+12=363：K-A-C-B-K,L3=12+8+7+16=434：K-C-A-B-K,L4=11+8+6+16=415：K-B-A-C-K,L5=16+6+8+11=416：K-B-C-A-K,L6=16+7+8+12=43分析各线路的货运周转量大小并排序Z1=4*12+2*6+1*7+11*0=48+12+7=67Z2=4*11+3*7+2*6+0*12=44+21+12=77Z3=4*12+2*8+1*7+0*16=48+16+7=71Z4=4*11+3*8+1*6+0*16=44+24+6=74Z5=4*16+3*6+1*8+0*11=64+18+8=90Z6=4*16+3*7+2*8+0*12=64+21+16=101显然，第一条线路的货运周转量最小，故选择第一条线路。任务3配送线路优化方法

之2：节约法（起止点重合的配送路线选择）

任务导入2：

某配送配送中心A向全市4个商店B、C、D、E进行配送，各点相对位置见下图，运输距离见表1，求最佳配送路线。任务3配送线路优化方法

之2：节约法一、节约法的基本假定

前提假设：当从若干配送据点向众多的客户配送货物时，各用户的坐标及需求量均为已知，配送中心有足够的运输能力。利用节约法制定出的配送方案除了使配送里程最小外，还满足以下条件，方案能满足所有用户的要求，不使任何一辆车超载；每辆车每天的总运行时间或行驶里程不超过规定的上限，能满足用户到货时间要求。二、节约法的基本原理假如由一家配送中心O向两个用户A、B送货，配送中心到两客户的最短距离分别是a和b，A和B间的最短距离为x，AB的货物需求量分别是Q1和Q2，且Q1+Q2小于车辆装载量Q，如同7－1所示。图7-1路线图ＡＢO从仓库O要运送货物给客户A和B第一条路线是从O到A，再返回，然后再从O到B，再返回O，总距离为a＋a＋b＋b＝2a＋2b外一种路线，从O到A到B，再到O。总距离为：a＋b＋x。将客户结合考虑，在第二种方案下走行路线的节约里程数是：（2a＋2b）－（a＋b＋x）即：a＋b－x它从不为负。因为三角形的第三条边总是小于其他两条边之和，因此，它最小为零。将客户连接起来，增加了节约。客户之间的距离越近，而且它们距离仓库越远，那么节约就会越大。这个方法也可以用时间来代替距离计算。2314关于这个公式，注意：

二、节约法的基本原理为了描述这个方法的使用，考虑下例。例：如图7-2所示，需要安排从仓库O送货给四个客户A、B、C、D。任何路程不得超过75千米。图7-2配送路线图三、节约法示例1

解：第一步：计算任一对客户的节约里程值，见表2-10：表2-10节约值计算表第二步：从最大的节约值开始，将客户连接在一起，直到达到一个限制。三、节约法示例1

第三步：因此选择第一条路线O—C—D—O。

从最大节约值27开始，连接客户C和D。距离O—C—D—O，和为63千米，没有超过限制。选择下一个最大的节约值，为20，将A、B、C和D连在一起，距离O—A—B—C—D—O，超过了75千米，不予采纳。选择另一个最大的节约值10，将B、C和D连接在一起，距离O—B—C—D—O，超过了75千米，仍然不采纳。选择另一个最大的节约值5，将A、C和D连接在一起，距离O—A—C—D—O，大于75千米，不采纳。表2-11计算结果

第五步：重新进行刚才的程序，从最大的20开始，将A和B连接在一起，距离O—A—B—O是50千米，是第二条路线。第四步：划掉C和D之间的行和列，见表2-11。三、节约法示例1任务3配送线路优化方法

之2：节约法（起止点重合的配送路线选择）

任务导入：

某配送配送中心A向全市4个商店B、C、D、E进行配送，各点相对位置见下图，运输距离见表1，求最佳配送路线。现在能找到最佳配送路线吗？

三、节约法示例2已知配送中心P0向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图与表所示：图中括号内的数字表示客户的需求量（单位：吨），线路上的数字表示两结点之间的距离，配送中心有3台2t卡车和2台4t两种车辆可供使用。问题：1、试利用节约里程法制定最优的配送方案？2、设卡车行驶的速度平均为40公里/小时，试比较优化后的方案比单独向各用户分送可节约多少时间？

三、节约法示例2

三、节约法示例2第1步：作运输里程表，列出配送中心到用户及用户间的最短距离。

三、节约法示例2第1步：作运输里程表，列出配送中心到用户及用户间的最短距离。

三、节约法示例2第1步：作运输里程表，列出配送中心到用户及用户间的最短距离。

三、节约法示例2第2步：由运输里程表、按节约里程公式，求得相应的节约里程数，如下表（）内。

三、节约法示例2第2步：由运输里程表、按节约里程公式，求得相应的节约里程数，如下表（）内。

三、节约法示例2第3步：将节约里程按从大到小顺序排列

三、节约法示例2第3步：将节约里程按从大到小顺序排列

三、节约法示例2第4步：根据载重量约束与节约里程大小，将各客户结点连接起来，形成二个配送路线。即A、B两配送方案。

三、节约法示例2第5步：确定单独送货的配送线路

计算初始方案配送距离=?

三、节约法示例2①配送线路A：P0-P2-P3-P4-P0运量=q2+q3+q4=1.7+0.9+1.4=4t,用一辆4t车运送节约距离SA=10+8=18km②配送线路B:P0-P5-P1-P0运量=q5+q1=2.4+1.5=3.9t<4t,用一辆4t车运送节约距离SB=2km第6步：与初始单独送货方案相比，计算总节约里程与节约时间总节约里程：△S=SA+SB=20km与初始单独送货方案相比，可节约时间：△T=△S/V=20/40=0.5小时

三、节约法示例3练习：某连锁零售店，下设有一个配送P和9个连锁分店A-J,配送中心和各连锁分店及各连锁分店之间的位置关系如图所示。该商品由配送中心统一采购并进行配送运输，配送中心有最大装载量为2t和5t的货车，并限定车辆一次运行距离不超过35km，设送到时间均符合用户要求，求配送中心的最优配送运输方案。

三、节约法示例3练习：某连锁零售店，下设有一个配送P和9个连锁分店A-J,配送中心和各连锁分店及各连锁分店之间的位置关系如图所示。该商品由配送中心统一采购并进行配送运输，配送中心有最大装载量为2t和5t的货车，并限定车辆一次运行距离不超过35km，设送到时间均符合用户要求，求配送中心的最优配送运输方案。作业：节约法示例4

下图所示为一配送网络，P为配送中心所在地，A－J为客户所在地，括号内的数字为配送量，单位为吨（t），线路上的数字为道路的距离，单位为公里（km）。现有可以利用的车辆是最大装载量为2吨和4吨的两种厢式货车，并限制车辆一次运行距离在30公里以内。现求最佳配送路线。第一步：首先计算相互之间最短距离，根据上图中配送中心至各用户之间，用户与用户之间的距离，得出配送路线最短的距离矩阵，如图：第二步：从最短距离矩阵中计算出各用户之间的节约行程见下图。例如，计算AB的节约距离：PA的距离：a=10，PB的距离：b=9，AB的距离：c=4，a+b-c=15

配送路线节约里程图

第三步：对节约行程按大小顺序排列，见下表。

配送线路节约里程排序表