第7章配送路线优化设计全书电子课件完整版电子教案课件电子教案幻灯片.pptx

配送中心路线优化设计第 七 章目录Contents7.1配送运输的方式7.2配送路线类型分析7.3配送路线优化方法配送中心路线优化设计第 七 章知识目标了解配送运输的常见方法1 1熟悉配送路线的类型2 2了解配送路线优化的约束条件3 3配送中心路线优化设计第七章能力目标掌握配送运输的常见方法1掌握直送式配送最短路线和分送式配送最短路线设计方法2掌握配送路线优化方法3配送中心路线优化设计第七章素质目标培养重科学、懂技术、会创新的驱动意识1树立法制意识、成本意识、效率意识2配送中心路线优化设计第七章工作任务工作任务 工作要求 能掌握配送运输的方式掌握配送运输的概念掌握配送运输常见的方法学会确定配送路线的约束条件掌握一般配送约束条件掌握配送路线的三种类型学会配送路线优化方法掌握直送式配送最短路线计算方法掌握分送式配送最短路线方法“节约里程法”配送中心路线优化设计第七章 引导案例菜鸟研发全球60年来车辆路径规划最领先技术 截止至北京时间2018年10月9日，菜鸟在全球最权威的车辆路径（VRP）问题评测系统中创造了26项世界纪录。菜鸟车辆路径规划算法已经应用于多项业务中。在车辆配送环节，车辆路径规划算法可以有效降低车辆使用数量和车辆行驶距离；在仓库内部拣选作业中，车辆路径规划算法可以降低拣选人员的行走距离。此外，车辆路径规划算法还可以帮助外卖配送员规划配送路线，从而提升客户体验、大幅度降低配送成本。 车辆路径规划问题是运筹优化领域最经典的问题之一。以一家物流公司需要向1000个网点进行配送为例，其配送路径不计其数，如果能找到一条最高效的配送路径，将会大为提高物流效率降低成本。 中国有全球最大的物流市场，涉及到大量的车辆、人员的配送拣选路径优化，随着新物流时代的到来，即时送达需求旺盛，其中也涉及到大量外卖员的配送路径优化，我们如果能在路径规划中取得突破，将会在带来非常大的社会效应。目前通过在零售通城配业务中应用车辆路径规划算法，订单配送成本已经降低了10.3%，并推动仓库货物流转效率的提升，仓库集货周转时间降低了57%。 思考：1.配送中心优化配送路线后可以取得哪些经济效益？2.配送路线优化的方法有哪些？第七章一、配送运输的概念配送运输通常是一种短距离、小批量、高频率的运输形式，应尽可能满足客户要求为目标。如果单从运输的角度看，它是对干线运输的一种补充和完善，属于末端运输、支线运输，主要由汽车运输进行。具有城市轨道货运条件的可以采用轨道运输，对于跨城市的地区配送可以采用铁路运输进行，或者在河道水域通过船舶进行。 影响配送运输的因素很多，动态因素，如车流量变化道路施工、配送客户的变动、可供调动的车辆变动等；静态因素，如配送客户的分布区域道路交通网络、车辆运行限制等。各种因素互相影响，很容易造成配送运输不及时、配送路径选择不当，贻误交货时间等问题。7.1配送运输的方式第七章二、配送运输的常见方法汽车整车运输是指同一收货人一次性需要到达同一点，且适合配送装运3吨以上的货物运输，或者货物质量在3吨以下，但其性质、体积、形状需要一辆3吨以上车辆一次或一批运输到目的地的运输。7.1配送运输的方式1 1汽车整车运输1整车运输的特点2整车运输基本流程3整车运输作业过程第七章一、配送运输的概念多点分运即在多地点、多仓库集运货物。配送中心在保证满足客户要求的前提下，集多个客户的配送货物进行搭配装载，以充分利用运能、运力，降低配送成本，提高配送效率。7.1配送运输的方式2 2多点分运1往复式行驶路线2环形行驶路线3汇集式行驶路线4星形行驶路线7.1配送运输的方式第七章（三）快运根据道路货物运输管理办法的有关规定，快货应做到从接受委托的当天15时起算，300千米运距内，24小时内送达；1000千米运距内，48小时内送达；2000千米运距内，72小时内送达。1快运的特点2快运业务操作流程3快运基本形式定点运输。定时运输。特快运输。联合快运。送达速度快。配装手续简捷。实行承诺制服务。可随时进行信息查询。通过电话、传真、电子邮件接受客户的委托快速通道备货分拣包装发货装车快速运送货到分发送货上门信息查询费用结算。7.2 配送路线的类型分析第七章一、确定配送路线的约束条件一般配送约束条件有以下几项：1路线允许通行的时间限制2运输工具载重的限制3配送中心的配送能力4自然因素的通行限制5不可抗力因素的限制某些路段在一定的时间范围内，不允许某种类型的车辆通行。运输工具载重的限制是指每辆车、船、飞机都有一定额定载重量，如果超重就会影响安全运输。配送中心的配送能力同时包括运输和服务这两个方面的能力。7.2 配送路线的类型分析第七章二、配送路线的类型配送路线的选择影响到运输设备和人员的利用，正确地确定合理的配送路线可以降低配送成本。尽管路线选择问题种类繁多，但可以将其归纳为以下几个基本类型。1起讫点不同的单一问题对分离的、单个始发点和终点的物流网络的配送路线选择问题，最简单和直观的方法是最短路线法。物流网络由物流节点和运输路线组成，点与点之间由线连接，线代表节点之间的运输距离（或时间）。除起点外，所有节点都被认为是未解的，即均未确定是否在选定的配送路线上。始发点作为已解的点，计算从原点开始。一般采用迭代的方法计算数值。7.2 配送路线的类型分析第七章二、配送路线的类型如果有多个货源地可以服务于多个目的地时，如何选择为各目的地服务的供货地、目的地之间的最佳路径。该问题经常发生在多个供应商、工厂或仓库需服务于多个客户的情况下。如果各供货地能够满足需求的数量有限，则问题会变得更复杂。解决这类问题常常可以运用特殊的线性规划方法计算，即运输方法问题求解。2配送路线有多起讫点问题3配送路线起讫点重合问题我们经常遇到一个路线问题是，始发点就是终点的路线选择。这类问题通常在运输工具归属于同一部门情况下发生。始发点与终点相重合的路线选择通常被称为“旅行推销员问题”或“货郎担问题”。对这类问题应用经验探试法比较有效。一般地，当运行路线不发生交叉时，经过各停留点的次序是合理的。应根据运行路线不发生交叉为原则设计配送路线。7.3 配送路线的优化方法第七章一、配送路线优化的约束条件配送线路优化的目标与送货作业的目标是一致的，都是让客户满意和成本尽可能降低。 无论选择哪个目标或实现哪个目标，都是有一定的约束条件，只有在满足这些约束条件的前提下才能实现这些目标。一般在进行配送路线的选择时，有以下几个约束条件：1.满足所有收货人对货物品种、规格以及数量的要求；2.满足收货人对货物到达时间范围的要求； 3.在允许通行的时间内进行配送，各配送路线的货物量不得超过车辆容积和载重量的限制；4.在已有送货运力资源允许的范围内。7.3 配送路线的优化方法第七章一、配送路线优化的约束条件疫情期间社区商超物资配送路径优化【前沿技术】【前沿技术】2020年春节伊始，新型冠状病毒疫情首先在武汉出现，随后迅速笼罩到全国。疫情防控当前，确保社区居民生活物资的供应与配送成为政府工作的重中之重。无接触式配送响应疫情态势，各地社区推广生活物资统一购办方式，创新“商超十社区”配送模式确保居民生活用品配送，是打赢疫情防控攻坚战的关键所在。 以湖北省黄石港区社区物资配送路径为例，利用车辆路径规划中优化算法可更快地搜寻到最佳的物资配送路径，得到较好的物资配送方案。配送路径优化既能减少人员流动，又能使商超在疫情期间快速得到配送方案，提高配送效率，缓解因疫情为居民生活带来的众多不便，保障社区居民基本生活需求，推动疫情态势不断朝着好的方向发展。7.3 配送路线的优化方法第七章二、配送路线最短设计从客户满意角度，就是在路上送货的时间尽可能短，以便尽快地交付到客户手中。要想时间短则可以从两个方面实现，即送货速度快或送货路程短。速度快往往意味着费用高，成本控制方面压力较大；而路程短则可以在同等的时间内以相对经济的速度满足客户的要求，且路程短可以使各项送货成本均得到一定程度的降低，因此通常配送路线的优化选择都是以路程最短为原则来进行的。根据配送运输的实际情况，送货业务中出现最多的是以下两种情况：从单个配送中心向单个客户往返送货及从单个配送中心向多个客户循环送货后返回。这两种情况的配送线路最短路线设计实际可以归结为两类，即两点间最短路线（直送式配送最短路线）和单起点多回路最短路线（分送式配送最短路线）。7.3 配送路线的优化方法第七章二、配送路线最短设计在配送线路设计中，当配送的起点和终点都只有一个，即由一个配送中心向一个特定的客户进行专门送货时，这种情况一般是针对优质的主要客户，客户的送货需求量大且对到达时间准确性要求较高，需专门派一辆或多辆车一次或多次送货。这样配送的重点在于节省时间、多装快跑，提高送货的时间准确性。也就是说，直送式配送的路线优化，主要问题是寻找物流网络中的最短路线。1直送式配送最短路线7.3 配送路线的优化方法第七章二、配送路线最短设计已知物流网络如图7-1所示，各节点分别表示为A、B、C、D、E、F、G、H、I、J、K，各节点之间的距离见图7-1所示，试确定各节点间的最短路线。例题857264810910KCDBAHJ8FGEI1211141011613寻找最短路线的步骤如下。第一步：选择货物供应点为初始节点，并取其位势值为0，即Vi0。第二步：考虑与i点直接相连的所有路线节点。设其初始节点的位势值为Vi，则其终止节点j的位势值可按下式确定： Vj = Vi+ Lij式中，Lij i点与j点之间的距离。第三步：从所得到的所有位势值中选出最小者，此值即为从初始节点到该点的最短距离，将其标在该节点旁的方框内，并用箭头标出该连线IJ，以此表示从点I到J点的最短路线。第四步：重复以上步骤，直到物流网络中所有节点的位势值均达到最小为止。最后，各节点的位势值表示从初始节点到该点的最短距离。带箭头的各条连线则组成了从初始节点到其余节点的最短路线。分别以各点为初始节点，重复上述步骤，即可得各节点之间的最短距离。7.3 配送路线的优化方法第七章二、配送路线最短设计分送式配送是指由一个配送中心向多个客户进行共同送货，送货车辆送完货后再返回配送中心。由于受送货时间及送货线路里程的制约，通常不可能用一条线路为所有客户送货，而是设计数条送货线路，每条线路为某几个客户送货。同一条线路上由一辆配装着这条线路上所有客户需求货物的车，按照预先设计好的最佳线路依次将货物送达该线路上的每一个客户并最终返回配送中心。 解决分送式配送最短路线问题最常用的方法是“节约里程法”，它是形成人工和计算机计算单起点多回路最短路线的基础。2分送式配送最短路线7.3 配送路线的优化方法第七章二、配送路线最短设计利用节约里程法确定配送线路的主要出发点是根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离来确定使配送车辆总的周转量达到或接近最小的配送方案。为便于理解，假设：（1）配送的是同一种或相类似的货物；（2）各用户的位置及需求量已知；（3）配送方有足够的运输能力；（4）设状态参数为Tij。利用节约里程法制定出的配送方案除了使总的周转量最小外，还应满足以下要求：（1）方案能满足所有用户的到货时间要求；（2）不使车辆超载；（3）每辆车每天的总运行时间及里程满足规定的要求。1 1节约里程法的基本规定7.3 配送路线的优化方法第七章二、配送路线最短设计节约里程法的基本思想如图7-3所示，设P0为配送中心，分别向客户Pi和Pj送货。P0到Pi和Pj的距离分别为D0i和D0j，两个客户Pi和Pj之间的距离为Dij，送货方案只有两种配送中心P0向客户Pi、Pj分别送货和配送中心P0向客户Pi、Pj同时送货，如图7-3a)、b）所示。比较以下两种配送方案。方案a）的配送路线P0PiP0PjP0，配送距离Da2Doi2Doj方案b）的配送路线P0PiPjP0，配送距离DbDoiDijDoj显然，Da不等于Db，我们用Sij表示里程节约量，即方案b）比方案a）节约的配送里程为: Sij DoiDojDij 2 2节约里程法的基本思想PiPjP0a)PiPjP0b)7.3 配送路线的优化方法第七章二、配送路线最短设计根据节约里程法的基本思想，如果一个配送中心P0分别向n个客户Pj（j1，2，n）配送货物，在汽车载重能力允许的前提下，每辆汽车的配送路线上经过的客户个数越多，里程节约量越大，配送路线越合理。 在实际情况下，如果给数个客户进行配送，应首先计算平时中心与每个客户之间的最短距离及两两客户之间的最短距离，然后计算各客户之间的可节约的运行距离，按照节约运行距离的大小顺序连接各配送地并设计出配送路线。7.3 配送路线的优化方法第七章二、配送路线最短设计某一配送中心P0向10个客户Pj（j1，2，10）配送货物，其配送网络如图7-4所示。图中括号内的数字表示客户的需求量（吨），路线上的数字表示两个节点之间的距离。该配送中心有载重量为2吨和4吨两种车辆可供使用，试制定最优配送方案。例题39464352（0.6）（0.5）9（0.7）（1.4）（1.5）610647P0P1P9P10P4P5P8P7P3P2P6475745（0.4）（08）（1.5）（0.6）（0.8）1011885627.3 配送路线的优化方法第七章二、配送路线最短设计第一步，计算最短距离。根据图7-4提供的已知条件，计算配送中心与客户之间的最短距离，结果见表7-2。解题P010P1 94P2 795P3 814105P4 8181496P5 8181715137P6 313121011106P7 4141311121282P8 10111517181817119P9 7481315151510118P10 表7-2 配送中心与客户及客户之间的最短距离7.3 配送路线的优化方法第七章二、配送路线最短设计第二步，计算节约里程Sij，结果见表7-3。解题P115P2 811P3 4710P4 03610P5 00039P6 000015P7 0000045P8 94000125P9 1381000009P10表7-3节约里程量7.3 配送路线的优化方法第七章二、配送路线最短设计第三步，将节约里程Sij进行分类，按从大到小的顺序排列，得表7-4。解题序号序号路线路线节约里程节约里程序号序号路线路线节约里程节约里程1P1P2 1513P6 P752P1P101313P7 P853P2 P31113P8 P954P3 P41016P1 P444P4 P51016P2 P946P1 P9916P6 P846P5 P6919P2 P5 36P9 P10919P4 P639P1 P3821P7 P929P2 P10822P3 P10111P2 P4722P5 P7112P3 P6622P6 P91 表7-4 节约里程项目分类7.3 配送路线的优化方法第七章二、配送路线最短设计第四步，确定配送路线。从分类表中，按节约里程大小顺序，组成路线图。1）初始方案：对每一客户分别单独派车送货，结果如图7-5所示。初始方案：配送路线:10条。配送距离:S0为148千米。配送车辆:2吨10辆。解题7.3 配送路线的优化方法第七章二、配送路线最短设计2）修正方案1:按节约里程Sij由大到小的顺序连接P1和P2，P1和P10，P2和P3，得修正方案1，如图7-6所示。修正方案1：配送路线：7条。配送距离：S1为109千米。配送车辆：2吨6辆4吨1辆。解题7.3 配送路线的优化方法第七章二、配送路线最短设计3）修正方案2：在剩余的Sij中，最大的是S3，4和S4，5，此时P4和P5都有可能并入路线A中，但考虑到车辆的载质量及路线均衡问题，连接P4和P5形成一个新的路线B得修正方案2，如图7-7所示。修正方案2：配送路线：6条。配送距离：S2为99千米。配送车辆：2吨5辆4吨1辆解题7.3 配送路线的优化方法第七章二、配送路线最短设计4）修正方案3：接下来最大的Sij是S1，9和S5，6，由于此时P1已属于路线A，若将P9并入路线A，车辆会超载，故只将P6并入路线B，得修正方案3，如图7-8所示。修正方案3：配送路线：5条。配送距离：S3为90千米。配送车辆：2吨3辆4吨2辆解题7.3 配送路线的优化方法第七章二、配送路线最短设计5）修正方案4:再继续按Sij由大到小排出S9,10，S1,3、S2, 10，S2,4、S3,6，由于与其相应的用户均已包含在已完成的线路里，故不予考虑。把S6,7对应P7点并入线路B中，得修正方案4，如图7-9所示。修正方案4：配送路线：4条。配送距离：S4为85千米。配送车辆：2吨2辆4吨2辆。解题7.3 配送路线的优化方法第七章二、配送路线最短设计6）最终方案：剩下的是S7，8，考虑到配送距离的平衡和载重量的限制，不将P8并入到路线B中，而是连接P8和P9组成新的路线C，得到最终方案，如图7-10所示。这样配送方案已确定：共存在3条配送路线，总的配送距离为80千米，需要的配送车辆为2吨车1辆，4吨车2辆。3条配送路线分别为：第一条配送路线A：P0P3P2P1P10P0，使用1辆4吨车。第二条配送路线B：P0P4P5P6P7P0，使用1辆4吨车。第三条配送路线C：P0P8P9P0，使用1辆2吨车。最终方案：配送线路：3条。配送距离：S4为80千米。配送车辆：2吨1辆4吨2辆。例题7.3 配送路线的优化方法第七章综合实训实训目的01实训组织02实训要求031. 通过校园配送，学会进行直送式、分送式配送线路选择，同时保证物品配送质量。2. 能够利用节约里程法进行配送线路优化计算。1.校园快递点。送货出发地。2.周边大学里学生宿舍。客户网点（选择8-10个宿舍）。3.运输设施。自行车或助力车（有载重限制）。4.交通图。用GPS定位，计算送货距离，设定每辆车的单次送货距离。5.工作时间安排为4课时（半天）。1. 选择不同楼栋中810个客户，能够进行直送式、分送式配送线路选择，同时保证物品配送质量。2. 根据客户分布，画出配送网络图，能够利用节约法进行配送线路选择。7.3 配送路线的优化方法第七章综合实训大家练一练大家练一练