配送路线优化

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,项目三 配送服务,教学任务：,1,.进货入库作业、储存作业、盘点作业、返品处理作业,2,.订单处理与补货、拣货作业,3,.出货作业,上,车辆配装、货品装箱,、,装卸工安排,4,.,出货,作业下配送线路优化,项目三 配送服务,小组PPT介绍,互动：提问+分享,内容补充+总结,任务3,出货作业之,配送线路优化,一、最短路径法,二、节约法,任务3,配送线路优化方法,之1：最短路径法,一、最短路径法,所谓,最短路径法,，是指要从网络图中某顶点出发，经过图中路径到达另一顶点，而这些路径不止一条，如何找到一条路径使各边的权值之和为最小。,任务3,配送线路优化方法,之1：最短路径法,最短路径法示例1,：,新加坡某配送中心签订了一项配送运输合同，要从配送中心A配送一批货物到销售地F,两点之间可选择的行车路线如图所示，求从配送中心A到销售地F的最短路径。,D,E,B,A,C,F,1,1,4,2,8,7,4,1,8,2,3,任务3,配送线路优化方法,之1：最短路径法,最短路径法示例2,：,从V,0,到V,6,找出最短路径？,任务3,配送线路优化方法,之1：最短路径法,最短路径法计算,3,任务3,配送线路优化方法,之1：最短路径法,最短路径法计算3参考答案：,2的最短距离100路径1-2,3的最短距离175路径1-3,4的最短距离150路径1-4,5的最短距离325路径1-4-5,6的最短距离359路径1-4-6,7的最短距离425路径1-4-7,8的最短距离550路径1-4-7-8,9的最短距离550路径1-4-6-9,10的最短距离575路径,1-4-6-9-10,任务3,配送线路优化方法,之1：最短路径法,最短路径法,练习题：,某配送公司要将客户急需的商品从配送中心P运送到商场Q，图1表示由起点P到终点Q的路线图，各条弧所对应的数字表示通过该段路线所需时间。试求所需时间最短路线。,任务3,配送线路优化方法,之2：节约法,（,起止点重合的配送路线选择,）,任务导入1：,某车一天的货运任务如下图：求最佳行车路线。,注：方框为供货点，椭圆为需求点。,K=4吨,A=2吨,B=1吨,C=1吨,12,11,16,6,7,8,解：分析：从供货点到需求点再返回供货点的线路共4条，距离计算如下：,1：K-A-B-C-K,L1=12+6+7+11=36,2：K-C-B-A-K,L2=11+7+6+12=36,3：K-A-C-B-K,L3=12+8+7+16=43,4：K-C-A-B-K,L4=11+8+6+16=41,5：K-B-A-C-K,L5=16+6+8+11=41,6：K-B-C-A-K,L6=16+7+8+12=43,分析各线路的货运周转量大小并排序,Z1=4*12+2*6+1*7+11*0=48+12+7=67,Z2=4*11+3*7+2*6+0*12=44+21+12=77,Z3=4*12+2*8+1*7+0*16=48+,16,+7=7,1,Z4=4*11+3*8+1*6+0*16=44+24+6=74,Z5=4*16+3*6+1*8+0*11=64+18+8=90,Z6=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,，如同71所示。,图,7-1,路线图,O,从仓库,O,要运送货物给客户,A,和,B,第一条路线是从,O,到,A,，再返回，然后再从,O,到,B,，再返回,O,，总距离为,aabb2a2b,外一种路线，从,O到A,到B，再到,O,。总距离为：,abx,。将客户结合考虑，在第二种方案下走行路线的节约里程数是,：,（2a2b）（abx）,即：,abx,它从不为负。因为三角形的第三条边总是小于其他两条边之和，因此，它最小为零。,将客户连接起来，增加了节约。,客户之间的距离越近，而且它们距离仓库越远，那么节约就会越大。,这个方法也可以用时间来代替距离计算。,2,3,1,4,关于这个公式，注意：,二、节约法的基本原理,为了描述这个方法的使用，考虑下例。,例：如图,7-2,所示，需要安排从仓库,O,送货给四个客户,A、B、C、D,。任何路程不得超过,75,千米。,图,7-2,配送路线图,三、节约法示例1,解：,第一步：计算任一对客户的节约里程值，见表,2-10,：,表,2-10,节约值计算表,第二步：,从最大的节约值开始，将客户连接在一起，直到达到一个限制。,三、节约法示例1,第三步：,因此选择第一条路线,OCDO。,从最大节约值,27,开始，连接客户,C,和,D,。距离,OCDO,，和为,63,千米，没有超过限制。,选择下一个最大的节约值，为,20,，将,A、B、C,和,D,连在一起，距离,OABCDO,，超过了,75,千米，不予采纳。,选择另一个最大的节约值,10,，将,B、C,和,D,连接在一起，距离,OBCDO,，超过了,75,千米，仍然不采纳。,选择另一个最大的节约值,5,，将,A、C,和,D,连接在一起，距离,OACDO,，大于,75,千米，不采纳。,表,2-11,计算结果,第五步：,重新进行刚才的程序，从最大的,20,开始，将,A,和,B,连接在一起，距离,OABO,是,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.9t4t,用一辆 4t车运送,节约距离,SB=2km,第6步：与初始单独送货方案相比，计算总节约里程与节约时间,总节约里程：S=SA+SB=20 km,与初始单独送货方案相比，可节约时间：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,为配送中心所在地，,AJ,为客户所在地，括号内的数字为配送量，单位为吨,（t），,线路上的数字为道路的距离，单位为公里,（km）,。现有可以利用的车辆是最大装载量为,2,吨和,4,吨的两种厢式货车，并限制车辆一次运行距离在,30,公里以内。现求最佳配送路线。,第一步：首先计算相互之间最短距离，根据上图中配送中心至各用户之间，用户与用户之间的距离，得出配送路线最短的距离矩阵，如图：,第二步：从最短距离矩阵中计算出各用户之间的节约行程见下图。例如，计算AB的节约距离：,PA,的距离：,a=10,，,PB,的距离：,b=9，AB,的距离：,c=4，,a+b-c,=15,配送路线节约里程图,第三步：对节约行程按大小顺序排列，见下表。,配送线路节约里程排序表,第四步：按照节约行程排列顺序表，组合成配送路线图,依据配送中心约束条件和节约里程顺序表，首先选择最节约里程路段，依次安排，最后形成,3,条配送路线，运行距离为,80,公里。需要,2,吨汽车,1,辆，,4,吨汽车,2,辆。,其中配送路线,：,4,吨汽车,1,辆，运行距离,27,公里，装载量为,3.6,吨；配送路线,：,4,吨车,1,辆，运行距离,30,公里，装载量为,3.9,吨；配送路线,：,2,吨车,1,辆，运行距离,23,公里，装载量为,1.3,吨。,