配送路线优化

项目三配送服务•教学任务：•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：最短路径法最短路径法练习题：•某配送公司要将客户急需的商品从配送中心P运送到商场Q，图1表示由起点P到终点Q的路线图，各条弧所对应的数字表示通过该段路线所需时间。试求所需时间最短路线。任务3配送线路优化方法之2：节约法（起止点重合的配送路线选择）任务导入1：某车一天的货运任务如下图：求最佳行车路线。注：方框为供货点，椭圆为需求点。K=4吨A=2吨B=1吨C=1吨121116678任务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步：作运输里程表，列出配送中心到用户及用户间的最短距离。三、节约法示例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公里以内。现求最佳配送路线。DBCHEGFAIPJ55411892676245867910710434564(0.4)(1.4)(0.8)(1.5)(0.7)(0.6)(1.5)(0.6)(0.8)(0.5)3配送中心的配送网络图•第一步：首先计算相互之间最短距离，根据上图中配送中心至各用户之间，用户与用户之间的距离，得出配送路线最短的距离矩阵，如图：•第二步：从最短距离矩阵中计算出各用户之间的节约行程见下图。例如，计算AB的节约距离：•PA的距离：a=10，PB的距离：b=9，AB的距离：c=4，a+b-c=15配送路线节约里程图•第三步：对节约行程按大小顺序排列，见下表。序号连接点节约里程序号连接点节约行程1A~B1513F~G52A~J1313G~H53B~C1113H~I54C~D1016A~D44D~E1016B~I46A~I916F~H46E~F919B~E36I~J919D~F39A~C821G~I29B~J822C~J111B~D722E~G112C~E622F~I1配送线路节约里程排序表第四步：按照节约行程排列顺序表，组合成配送路线图依据配送中心约束条件和节约里程顺序表，首先选择最节约里程路段，依次安排，最后形成3条配送路线，运行距离为80公里。需要2吨汽车1辆，4吨汽车2辆。其中配送路线Ⅰ：4吨汽车1辆，运行距离27公里，装载量为3.6吨；配送路线Ⅱ：4吨车1辆，运行距离30公里，装载量为3.9吨；配送路线Ⅲ：2吨车1辆，运行距离23公里，装载量为1.3吨。FJIHGDCABPE34778(0.8)(0.4)(0.6)(0.8)(0.5)(0.6)(0.7)(1.5)(1.4)(1.5)910676544配送线路Ⅰ配送线路Ⅲ配送线路Ⅱ最优配送路线