第三章选址模型及应用ppt课件.ppt

3.1 选址的意义,选址在整个物流系统中占有非常重要的地位，主要属于物流管理战略层的研究问题。选址决策就是要确定所要分配的设施的数量、位置以及分配方案。这些设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售商网点等。,3.1 选址的意义,设施数量与客户响应时间快速响应客户需求是竞争因素之一快速响应客户需求与节点设施设置的数量有关,3.1 选址的意义,选址与库存、运输成本存在密切联系，选址就是要在设施数量和成本中求得最佳。,3.1 选址的意义,就供应链系统而言，核心企业的选址决策会影响所有供应商物流系统的选址决策。,3.2 选址的影响因素,选址决策影响因素大致可分为外部因素及内部因素两大类,3.2 选址的影响因素,选址决策包括地区选择和地点选择，二者需要考虑的因素有所不同。地区选择要考虑的是宏观因素；地点选择要考虑的是微观因素。,3.2 选址的影响因素,按照影响因素的性质的不同，可把影响因素分成两大类：即成本因素和非成本因素。还可以根据因素对设施选址的重要性，分为：关键因素、重要因素、次要因素等。,3.3 选址模型的分类,在建立一个选址模型之前，我们需要清楚以下问题：（1）选址的对象是什么？（2）选址的目标区域是怎样的？（3）选址目标和成本函数是什么？（4）有什么样的一些约束？,3.4 选址问题中的距离计算,在选址问题模型中，最基本的一个参数是各个节点之间的距离。有两种方法计算节点之间的距离：直线距离，也叫欧几里德距离（Euclidean Metric）；折线距离（Rectilinear Metric），也叫城市距离（Metropolitan Metric）。,3.5 选址模型,简单模型：在一条直线上（街道）选择一个有效位置（商店），即一种设施，让这条街道上的所有顾客到达商店的平均距离最短。假设街道上顾客分布的概率（密度）为则目标函数为：,简单模型,大街上第i个位置到所选地址的距离,选择投资的位置,3.5 选址模型,定积分求导：,定积分求导,（1）,其中， 被假设为在时间区间 中具有连续导数 。,莱布尼兹法则,关于一个变量（它既不是积分变量，也不进入积分上下限）求导定积分，可以简单地穿过积分符号直接关于该变量求导被积函数。,3.5 选址模型,定积分求导：,定积分求导,（2）,有微商公式：,定积分关于积分上限b的导数等于被积函数在t=b处的取值；定积分关于积分下限a的导数等于被积函数在t=a处的取值的负数；,3.5 选址模型,定积分求导：,定积分求导,（3）,有微商公式：,右边第一项来自对被积函数中变量的求导，右边第二项来自对积分上限的求导，而且基于下列链式求导：,其中x不仅进入被积函数，而且影响积分上限,对以下函数求导,3.5 选址模型,对目标函数求导，令一阶导数为零，得：,简单模型,求解结果表明，所开设的新店面需要设置在权重的中点，即两面的权重都是50%。,3.5 选址模型,连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。交叉中值模型（Cross Median）通过交叉中值的方法对单一设施平面选址问题的加权城市距离进行最小化。其目标函数为：,交叉中值模型,第i个点对应的权重，例如需求；,需求点的总数目,第i个需求点的坐标；,服务设施的坐标；,3.5 选址模型,交叉中值模型的目标函数可以用两个互不相干的部分来表达：,交叉中值模型,是x方向所有权重的中值点；,是y方向所有权重的中值点；,3.5 选址模型,例1 报刊亭选址一个报刊连锁公司想在一个地区开设一个新的报刊亭零售点，主要的服务对象是附近的5个住宿小区的居民，他们是新开设报刊亭零售点的主要顾客源。下图坐标系中确切地表达了这些需求点的位置，下表为各个需求点对应的权重。权重代表每个月潜在的顾客需求总量，基本可以用小区中总的居民数量来近似。经理希望通过这些信息来确定一个合适的报刊零售点的 位置，要求每个月顾客到报刊零售点所行走的距离总和最小。,交叉中值模型,3.5 选址模型,首先，确定中值，,交叉中值模型,3.5 选址模型,选址结果：,交叉中值模型,3.5 选址模型,连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。精确重心法（Exact Gravity）交叉中值模型使用城市距离，适合小范围城市内选址问题；精确重心法使用直线距离，适合大范围城市间选址问题，目标函数为，,精确重心法,与第i个点对应的权重，例如需求；,需求点的总数目,第i个需求点的坐标；,服务设施的坐标；,3.5 选址模型,精确重心法目标函数为双变量系统，分别对xs和ys求偏导，并令导数为零，求得隐含最优解的等式，,精确重心法,3.5 选址模型,迭代法：利用已知的点（xs(k-1), ys(k-1)）,求出dis(k-1)，再求出新的点（xs(k), ys(k)）,依次求解，直到求得符合要求的解。,精确重心法,3.5 选址模型,精确重心法,迭代法步骤：（1）初始值的确定；（2）迭代；（3）中止准则；,初始值的确定：a、任意选择一个点作为初始值；b、按照简化公式选择初始值；,3.5 选址模型,中止准则的确定：a、直接设置一个确定的迭代次数N；b、判断两次迭代的差值是否小于设定的阈值；C、判断总费用是否减小或两次迭代差值小于设定值,精确重心法,3.5 选址模型,精确重心法应用于报刊亭选址问题：,精确重心法,3.5 选址模型,精确重心法应用于报刊亭选址问题：,精确重心法,3.5 选址模型,精确重心法应用于报刊亭选址问题：,精确重心法,3.5 选址模型,中止准则的使用：若（1）N=2；（2）坐标值阈值为0.2；坐标值变化幅度小于4%；（3）总费用阈值为0.2；总费用相对变化幅度小于1%。,精确重心法,3.5 选址模型,补充例题：有四个零售点，其坐标、物资需求量及运输费用如下表所示，请用重心法为配送中心选址。,精确重心法,第一步，按照简化公式确定初始值，,3.5 选址模型,精确重心法,第二步，以点（7.8，4.9）作为配送中心，计算距离与总费用，,第三步，计算改善的配送中心选址，,3.5 选址模型,精确重心法,第四步，以点（8.6，5.1）作为配送中心，计算距离与总费用，,第五步，计算改善的配送中心选址，,3.5 选址模型,精确重心法,第六步，以点（9.0，5.2）作为配送中心，计算距离与总费用，,此时，Z(2)=Z(1)=191，虽然结果是取小数而得，但二者已经非常接近，所以可认为最佳点为（9.0，5.2）或（8.6，5.1）。,3.5 选址模型,交叉中值模型与精确重心法,3.5 选址模型,离散点选址问题指的是在有限的候选位置里面，选取最为合适的一个或一组位置为最优方案，相应的模型称为离散点选址模型。离散点选址模型与连续点选址模型的区别在于：它所拥有的候选方案只有有限个元素。对于离散点选址问题，目前主要有两种模型，分别是覆盖模型和P-中值模型。覆盖模型常用的又有集合覆盖模型和最大覆盖模型两种。覆盖模型（Covering） 覆盖模型，是对于需求已知的一些需求点，确定一组服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适的位置。该模型适用于商业物流系统，如零售点的选择问题、加油站的选址、配送中心的选址问题等。,离散点选址问题,3.5 选址模型,根据解决问题的方法的不同，覆盖模型可以分为两种不同的主要模型：集合覆盖模型，用最小数量的设施去覆盖所有的需求点；最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求或需求点。,覆盖模型,3.5 选址模型,集合覆盖模型集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求点。数学模型为：,集合覆盖模型,N区域中的需求点（客户）集合，N=1,2,n；M区域中可建设设施的候选点集合，M=1,2,m；Dj第i个需求点的需求量；Ci设施点j的服务能力；A(i)设施节点i可以覆盖的需求点j的集合；B(j)可以覆盖需求节点j的设施节点i的集合；,yi为0-1变量，yi=1,在i点建立设施；yi=0,不在i点建立设施，iMxij节点j需求中被分配给设施点i的部分。,3.5 选址模型,集合覆盖模型启发式算法：第一步：初始化。令所有的xj0，yi0， （已分配的需求），并确定集合A(i)和集合B(j)；第二步：选择下一个设施点。在M中选择yi0，且A(i)的规模为最大的点i为设施点，即 ，令 ，并在M集合中剔除节点i，即第三步：确定节点i的覆盖范围。将A(i)中的元素按B(j)的规模从小到大的顺序指派给i，直至i的容量为Ci0或A(i)为空。其中对于jA(i)且，xjDj，将j支配给i的方法为：若 ，则令xij=Djxj，Ci=Ci-(Dj-xj)，xj1，在A(i)和N中剔除需求点j。若 ，则令第四步：若N或M为空，停止；否则，更新集合A(i)和集合B(j)，转第二步。,集合覆盖模型启发式算法,3.5 选址模型,例：在某区域需规划建设若干个农贸市场为将来该区9个主要居民点提供服务，除第6居民点外，其他各点均有建设市场的条件，如下图所示。已知市场的最大服务直径为3km，为保护该区域的环境，希望尽可能少地建造农贸市场。问应如何规划？解：N1,2,3,4,5,6,7,8,9，M1,2,3,4,5, 7,8,9，由图两点间的最短距离，根据最大服务半径为3km的约束及第6居民点不适合建市场的要求，可确定集合A(j)和B(i)。如下表所示，值得指出的是本问题没有需求量和容量，故无需考虑服务能力约束式。,集合覆盖模型启发式算法,3.5 选址模型,集合覆盖模型启发式算法,第一步，初始化,第二步，确定一个设施点。因为A(4)=1,3,4,5,6,7，|A(4)|=6为最大，故首先选取i4。由于无容量约束故依次指派5,7,1,6,3,4点归节点4服务。 第三步，更新。此时，N2,8,9,M1,2,3,5,7,8,9,更新集合A(i)和集合B(j)后如下表所示。,3.5 选址模型,集合覆盖模型启发式算法,第四步，确定一个设施点。因为A(8)8,9，|A(8)|2为最大，故首先选取i8，并且8，9两点归节点8服务。 第五步，更新。此时，N2,M1,2,3,5,7,9,更新集合A(i)和集合B(j)后如下表所示。,3.5 选址模型,集合覆盖模型启发式算法,第六步，确定一个设施点。因为A(2)2，|A(2)|1为最大，故首先选取i2，并且2点归节点2服务。 第七步，更新。此时，N,M1,3,5,7,9,结束。 因此，计算结果为（4,8,2）。,3.5 选址模型,集合覆盖模型整数规划,yi为0-1变量，yi=1,在i点建立设施；yi=0,不在i点建立设施，iMxij节点i供给量中被分配给需求点j的部分。,3.5 选址模型,集合覆盖模型整数规划,整数规划模型：,3.5 选址模型,集合覆盖模型整数规划,Lingo软件求解：,3.5 选址模型,最大覆盖模型已知若干个需求点（客户）的位置和需求量，需从一组候选的地点中选择p个位置作为物流设施网点（如配送中心、仓库等），使得尽可能多地满足需求点的服务。最大覆盖模型的目标是对有限的服务网点进行选址，为尽可能多的对象提供服务，如下图所示。,最大覆盖模型,3.5 选址模型,最大覆盖数学模型为：,最大覆盖模型,N区域中的需求点（客户）集合，N=1,2,n；M区域中可建设设施的候选点集合，M=1,2,m；di第i个需求点的需求量；Dj设施点j的服务能力；p 允许建设的设施的数目；A(j)设施节点j可以覆盖的需求点i的集合；B(i)可以覆盖需求节点i的设施节点j的集合；Xj为0-1变量，xj=1,在j点建立设施；xj=0,不在j点建立设施，jMyij节点i需求中被分配给设施点j的部分(比例)。,3.5 选址模型,集合覆盖模型与最大覆盖模型数学模型比较,最大覆盖模型,3.5 选址模型,最大覆盖模型整数规划,3.5 选址模型,集合覆盖模型整数规划,Lingo软件求解：,3.5 选址模型,P中值模型P中值模型是指在一个给定数量和位置的需求集合和一个给数量和候选位置的设施集合的前提下，分别为P个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在设施与需求点之间的运输费用最低。如下图所示。,P中值模型,3.5 选址模型,P中值数学模型为：,P中值模型,N区域中的需求点（客户）集合，N=1,2,n；M区域中可建设设施的候选点集合，M=1,2,m；di第i个需求点的需求量；cij从需求点i到设施点j的单位运输费用；p 允许建设的设施的数目，pm；xj为0-1变量，xj=1,在j点建立设施；xj=0,不在j点建立设施，jMyij为0-1变量，yij=1,表示需求点i由节点j提供服务；yij=0,表示需求点i不由节点j提供服务； 。,3.5 选址模型,例3：某饲料公司的仓库选址问题某饲料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建2个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地调查之后，已有4个候选地址，如下图所示；各候选地址到不同超市的运输成本、各个超市的需求量如下表所示。,P中值模型,3.5 选址模型,P中值贪婪取走启发式算法（Greedy Dropping Heuristic Algorithm）:,P中值模型贪婪取走启发式算法,第一步，初始化，令循环数k=m，将所有m个候选位置都选中，然后将每个需求点分配给离其最近的一个侯选位置。,3.5 选址模型,P中值模型贪婪取走启发式算法,第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客户重新指派后，总费用增加量最小，然后令k=k-1。,1,2,3,4,5,6,7,8,2,3,4,600,160,140,120,600,600,500,480,3.5 选址模型,P中值模型贪婪取走启发式算法,1,2,3,4,5,6,7,8,1,3,4,400,100,360,600,160,280,120,600,移走位置2：,3.5 选址模型,P中值模型贪婪取走启发式算法,移走位置3：,1,2,3,4,5,6,7,8,1,2,4,400,100,360,600,160,140,660,1200,3.5 选址模型,P中值模型贪婪取走启发式算法,移走位置4：,1,2,3,4,5,6,7,8,1,2,3,400,100,360,1400,400,140,120,600,因此，移走位置2，总费用为2620，令k=k-1=3.,3.5 选址模型,P中值模型贪婪取走启发式算法,1,2,3,4,5,6,7,8,3,4,600,500,1680,600,160,280,120,600,第三步，重复步骤二。移走位置1：,3.5 选址模型,P中值模型贪婪取走启发式算法,1,2,3,4,5,6,7,8,1,4,400,100,360,600,160,630,2200,660,移走位置3：,3.5 选址模型,P中值模型贪婪取走启发式算法,移走位置4：,1,2,3,4,5,6,7,8,1,3,400,100,360,1400,480,280,120,600,因此，移走位置4，总费用为3740，令k=k-1=2.此时k=p，计算结束。,3.5 选址模型,P中值模型贪婪取走启发式算法,Lingo软件求解：,