第8章_物流配送问题

第8章物流配送问题8.1.1配送模式1.自营配送模式2.共同配送模式3.互用配送模式4.第三方配送模式8.1配送模式及其选择8.1.2现代配送模式的选择1.矩阵图决策法重要不重要配送对企业的重要性企业配送能力高低IIIIIIⅣ图8-5矩阵图决策法8.1.2现代配送模式的选择2.比较选择法(1)确定型决策例8-1，某企业在选择配送模式时主要考虑了四个方面的目标，如表8-2所示。根据以上资料计算各模式的综合价值系数。解：V自营=5/10×0.1+220/220×0.3+25/25×0.4+98/99×0.22=0.95V互用=5/8×0.1+180/220×0.3+17/25×0.4+97/99×0.2=0.76V第三方=5/5×0.1+140/220×0.3+15/25×0.4+99/99×0.2=0.73结论：自营配送模式的综合价值系数最大，是企业所要选择的配送模式。8.1.2现代配送模式的选择2.比较选择法(2)非确定型决策例8-2，某企业计划通过提高配送效率，满足客户对配送的要求，来扩大经营规模。现可供选择的配送模式有三种，由于在未来几年内，企业对用户要求配送的程度无法做出准确的预测，只能大体估计为三种情况，且估算出三种模式在未来几年内三种自然状态下的成本费用(见表8-3)，但不知道这三种情况的发生概率，问如何决策？8.1.2现代配送模式的选择2.比较选择法(2)非确定型决策解：第一种方法：按乐观准则来决策第二种方法：按悲观准则来决策第三种方法：按折衷准则或赫维斯准则来决策第四种方法：按等概率准则或拉普拉斯准则来决策第五种方法：按最小后悔值准则来决策8.1.2现代配送模式的选择2.比较选择法(3)风险型决策例8-3，某企业计划通过加强配送效率，提高客户满意度来扩大产品的销售量，现有三种配送模式可供企业选择，各种资料如表8-5所示，问企业应选择哪种配送模式。解：自营模式销售额：1000×0.5+800×0.3+500×0.2=840(万元)互用模式销售额：1200×0.5+700×0.3+400×0.2=890(万元)第三方模式销售额：1500×0.5+1000×0.3+300×0.2=1110(万元)结论：第三方配送模式的期望值最大为1110万元，故该模式可作为企业比较满意的模式。8.2配送线路优化问题8.2.1单回路运输——TSP模型及求解单回路运输问题是指在路线优化中，设存在节点集合D，选择一条合适的路径遍历所有的节点，并且要求闭合。因此，单回路运输问题的两个显著特点是：（1）单一性（只有一个回路）；（2）遍历性（不可遗漏）。8.2.1单回路运输——TSP模型及求解旅行商问题（TravelingSalesmanProblem，TSP），也称货郎担问题，是单回路运输问题的典型问题，对于大规模的线路优化问题，无法获得最优解，只有通过启发式算法获得近似最优解。TSP问题描述：一个货郎担着商品去他所在的区域内的所有村镇进行推销，他应怎样选择一条总路程最短的行走路线使每个村镇恰好去一次或者至少去一次？或一个推销员要到若干个城市推销产品，然后回到出发点，已知每两个城市之间的距离，他应如何选择其旅行路线，使每个城市经过一次且仅仅一次或者至少经过一次，并且总的行程最短？TSP问题的图论语言描述：在给定的连通加权无向图（G,w）中找出一条最小权的Hamilton圈或者找出一条经过G中每个顶点并且有最小权的闭链。前者称为最优圈（OptimalCycle），后者称为最优链（OptimalChain）。一般来说，货郎担问题的这两种定义会产生不同的解。TSP模型8.2.1单回路运输——TSP模型及求解TSP模型的数学描述为：连通图H，其顶点集为顶点间的距离为TSP模型VjVixVSSxVjxVixtsxczijSiSjijniijnjijninjijij,},1,0{)3(,1)2(,1)1(,1..min1111属于最优路径到从不属于最优路径到从jijixij,1,0VjicccccCiijiijijnnij,,,,0,][},,2,1{nV约束式（1）和（2）意味着对每个点来说，仅有一条边进和一条边出；约束式（3）则保证了没有任何子回路的产生。8.2.1单回路运输——TSP模型及求解TSP模型的求解方法：（1）枚举法→n!或(n-1)!（2）整数规划（分枝定界法、割平面法等）→小规模TSP问题（3）启发式算法→适各种规模的TSP问题TSP模型8.2.1单回路运输——TSP模型及求解最近邻点法1最近邻点法是由RosenKrantz和Stearns等人在1977年提出的一种用于解决TSP问题的算法。该算法十分简单，但是它得到的解并不十分理想，有很大的改善余地。由于该算法计算快捷，但精度低，可以作为进一步优化的初始解。最近邻点法包括四个步骤：（1）从零点开始，作为整个回路的起点。（2）找到离刚刚加入到回路的上一个顶点最近的一个顶点，并将其加入到回路中。（3）重复步骤（2），直到V中所有顶点都加入到回路中。（4）最后，将最后一个加入的顶点和起点连接起来。8.2.1单回路运输——TSP模型及求解例4现有一个连通图，|V|=6，各个顶点之间的距离矩阵如下表所示，假设i和j两点之间的距离是对称的。最近邻点法8.2.1单回路运输——TSP模型及求解最近邻点法求解：最近邻点法123456总距离f=6+5+15+4+12+15=578.2.1单回路运输——TSP模型及求解最近插入法2最近插入法是由RosenKrantz和Stearns等人在1977年提出的另外一种用于解决TSP问题的算法。最近插入法比最近邻点法复杂，但是可以得到相对比较满意的解。最近插入法也包括四个步骤：（1）找到c1k最小的节点vk，形成一个子回路（subtour），T={v1,vk,v1}.（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点vk。（3）在子回路中找到一条弧(i,j)，使得cik+ckj-cij最小，然后将节点插入到vi和vj之间，用两条新的弧(i,k)和(k,j)代替原来的弧(i,j)，并将节点vk加入到子回路中。（4）重复步骤（2）和（3），直到所有的节点都加入到子回路中。8.2.1单回路运输——TSP模型及求解最近插入法求解：123456假如将V5插入V1和V3之间：cik+ckj-cij=c15+c53-c13=7+7-6=8假如将V5插入V3和V2之间：cik+ckj-cij=c35+c52-c32=7+15-5=17假如将V5插入V1和V2之间：cik+ckj-cij=c15+c52-c12=7+15-10=12所以选最小的8，即应将V5插入V1和V3之间，其他点的插入法以此类推。8.2.2多回路运输——VRP模型及求解多回路运输问题，也称车辆路径问题（VehicleRoutingProblem，VRP），是现实中十分普遍的一种调配问题，特别是对于有大量服务对象的实体。解决此类问题时，核心问题是如何对车辆进行调度。车辆路径问题最早是由Dantzig和Ramser于1959年首次提出的。该问题的研究目标是对一系列的顾客需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，达到一定的优化目标。约束条件：如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等。优化目标：如里程最短、费用最少、时间尽量少、车队规模尽量小、车辆利用率尽量高等。8.2.2多回路运输——VRP模型及求解8.2.2多回路运输——VRP模型及求解物流配送车辆路径问题的描述：从某物流中心用多台配送车辆向多个客户送货，每个客户的位置和货物需求量一定，每台配送车辆的载重量一定，每台车的一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足以下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量限制；（2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；（3）所用车辆路线均起始并终止于配送中心，每个客户的需求必须满足，且只能由一台配送车辆送货；（4）车辆的行车路线的总耗时不超过一个事先定下的数值，以满足客户对供货时间的要求；（5）对某个客户点，车辆到达时间限制在某一时间段内（软限制），如果此约束不满足，则引入惩罚函数。综合考虑运输路径最短、总运费最少、总运输时间最短、空载车总运行时间最少、完成任务所需的车辆最少这五个目标时，总运费就不应单单是距离的函数，而要考虑到即时配送、车辆成本、人员成本的问题。8.2.2多回路运输——VRP模型及求解扫描算法（SweepAlgorithm）是Gillett和Miller在1974年提出的，也是解决车辆数目不限制的VRP问题的一种启发式算法。扫描算法的4个步骤：（1）以起始点0作为极坐标系统的原点，并以连通图中的任意一顾客点和原点的连线定义为角度零。然后对所有的客户所有的位置进行坐标系的变换，全部转换为极坐标系。（2）分组。从最小角度的客户开始，建立一个组，按逆时针方向，将客户逐渐加入到组中，直到客户的需求问题超出了负载限制（或超过其他约束条件的限制）。然后建立一个新组，继续按逆进针方向将客户加入到组中。（3）重复（2）的过程，直到所有的客户都被分组。（4）路径优化。对各个分组内的客户点，进行单独的TSP问题优化。扫描算法222019年9月6日星期五例子：现有一个仓库，需要对9个客户提供货物，它们的需求量及极坐标值见下表，它们的位置关系如下图所示。设每个车辆的运输能力是12个单位的货物，并现有足够多的车辆。试用扫描算法对该运输问题进行求解。0v需求表和极坐标的解坐标值232019年9月6日星期五图顾客和仓库的位置图图扫描算法求解过程242019年9月6日星期五解：（1）建立极坐标系由于题中已经直接给出了极坐标，本步可以省略。（2）分组过程从角度为零向逆时针方向进行扫描，第一个被分组的是顾客2，送货量是3;继续转动，下一个被分组的是顾客1，送货量是5,合计3+5=8;如前图所示。由于负载还没有超过限制12，继续转动。下一个被分组的是顾客3，送货量是6,如果继续分到一组，3+5+6=14,则超限制了。按照分组规则，需要一个新的组，这样在第一个组里面只有顾客1和2。在第2组中有顾客3，继续上面步骤，直到所有的顾客都被分配完毕。这时，可以得到如下图所求的分组结果。（3）组内的线路优化对上面的4个组，都已经是一个单回路运输问题，根据前面的介绍，分别用TSP模型（见单回路运输问题）进行路径优化。值得注意的是，虽然供应点0没有被任何一个组包含，但它是任何一个组的TSP问题的起点和终点。8531LoaditLoadLoadlim1121465362Load252019年9月6日星期五图扫描算法求解结果8.3配送需求计划1．DRP的概念DRP是配送需求计划（distributionrequirementplanning）的简称,它是流通领域中的一种物流技术，是MRP在流通领域应用的直接结果。它主要解决分销物资的供应计划和高度问题，达到保证有效地满足市场需要又使得配置费用最省的目的。2．DRP的适用对象DRP主要适用于流通企业和自己具有销售网络和储运设施的生产企业。这两类企业共同的基本特征是：以满足自身的需求为宗旨；都依靠一定的物流能力，包括仓储、运输、包装、装卸、搬运等功能；以物流活动作为基本手段来满足社会的商品需求；都要从商品生产企业或商品资源市场组织商品资源。图1仓库、物流中心业务模式仓库、物流中心生产企业1用户需求下属物流中心需求生产企业1生产企业1即含有物流业务的企业，如储运、配送、商贸连锁企业等这些企业涉及到储存和运输的业务，即进货与送货的业务DRP可以使企业商品流通中的总费用最省，资源（车辆、仓库等）利用率最高。3.DRP与MRP的联系DRP和MRP一样都是需求管理（demandmanagement)的一部分；DRP是由顾客的需求所决定，企业无法或