第三章选址模型及应用精选文档.ppt

第三章选址模型及应用第三章选址模型及应用本讲稿第一页，共六十二页3.1 3.1 选址的意义选址的意义选址在整个物流系统中占有非常重要的地位，主要属于物流选址在整个物流系统中占有非常重要的地位，主要属于物流管理战略层的研究问题。管理战略层的研究问题。选址决策就是要确定所要分配的设施的数量、位置以及分配选址决策就是要确定所要分配的设施的数量、位置以及分配方案。这些设施主要指物流系统中的节点，如制造商、供应商、方案。这些设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售商网点等。仓库、配送中心、零售商网点等。本讲稿第二页，共六十二页3.1 3.1 选址的意义选址的意义设施数量与客户响应时间设施数量与客户响应时间快速响应客户需求是竞争因素之一快速响应客户需求与节点设施设置的数量有关期望的期望的响应时间响应时间设施设施数量数量本讲稿第三页，共六十二页3.1 3.1 选址的意义选址的意义选址与库存、运输成本存在密切联系，选址就是要在设施数量和成本中求得选址与库存、运输成本存在密切联系，选址就是要在设施数量和成本中求得最佳。最佳。设施数量设施数量库库存存成成本本设施数量设施数量运运输输成成本本设施数量设施数量设设施施成成本本设施数量设施数量总成总成本本响应时间响应时间本讲稿第四页，共六十二页3.1 3.1 选址的意义选址的意义就供应链系统而言，核心企业的选址决策会影响所有供应商物流系统的选址决就供应链系统而言，核心企业的选址决策会影响所有供应商物流系统的选址决策。策。本讲稿第五页，共六十二页3.2 3.2 选址的影响因素选址的影响因素选址决策影响因素大致可分为外部因素及内部因素两大类选址决策影响因素大致可分为外部因素及内部因素两大类u宏观政治因素宏观政治因素政权、法制、政策等政权、法制、政策等u宏观经济因素宏观经济因素税收、关税、汇率等税收、关税、汇率等u基础设施基础设施交通设施、通信设施交通设施、通信设施u自然环境与社会环境自然环境与社会环境如劳动力成本与质量如劳动力成本与质量u市场环境市场环境竞争对手、供应商、客竞争对手、供应商、客户等户等u企业发展战略企业发展战略如制造业企业选择劳动如制造业企业选择劳动密集密集/技术密集发展战略；技术密集发展战略；如商业服务业选择连锁如商业服务业选择连锁便利店便利店/超市的发展战略超市的发展战略本讲稿第六页，共六十二页3.2 3.2 选址的影响因素选址的影响因素选址决策包括地区选择和地点选择，二者需要考虑的因素有所不同。地区选择要考虑的选址决策包括地区选择和地点选择，二者需要考虑的因素有所不同。地区选择要考虑的是宏观因素；地点选择要考虑的是微观因素。是宏观因素；地点选择要考虑的是微观因素。（1 1）政策导向）政策导向（2 2）市场情况）市场情况（3 3）社会环境）社会环境（4 4）资源条件）资源条件（5 5）基础设施和配套）基础设施和配套供应供应（6 6）上下游企业关系）上下游企业关系（1 1）区域规划）区域规划 （2 2）地形地貌）地形地貌（3 3）面积与外形）面积与外形（4 4）外部衔接）外部衔接（5 5）地质条件）地质条件（6 6）气象及辐射）气象及辐射（7 7）地下水与洪水）地下水与洪水（8 8）地震）地震本讲稿第七页，共六十二页3.2 3.2 选址的影响因素选址的影响因素按照影响因素的性质的不同，可把影响因素分成两大类：即成本因素和非成本因素。还可以根按照影响因素的性质的不同，可把影响因素分成两大类：即成本因素和非成本因素。还可以根据因素对设施选址的重要性，分为：关键因素、重要因素、次要因素等据因素对设施选址的重要性，分为：关键因素、重要因素、次要因素等。本讲稿第八页，共六十二页3.3 3.3 选址模型的分类选址模型的分类在建立一个选址模型之前，我们需要清楚以下问题：在建立一个选址模型之前，我们需要清楚以下问题：（1）选址的对象是什么？（）选址的对象是什么？（2）选址的目标区域是怎样的？）选址的目标区域是怎样的？（3）选址目标和成本函数是什么？（）选址目标和成本函数是什么？（4）有什么样的一些约束？）有什么样的一些约束？体选址面选址线选址高维选址单一设施选址多设施选址连续选址网络选址离散选址可行性/最优性Minisum/MinimaxMaximin高次目标函数确定性与随机性静态与动态有能力约束无能力约束有不可行区域无不可行区域设施维度及数量选址目标区域选址成本选址约束固定权重/可变权重本讲稿第九页，共六十二页3.4 3.4 选址问题中的距离计算选址问题中的距离计算在选址问题模型中，最基本的一个参数是各个节点之间的距离。在选址问题模型中，最基本的一个参数是各个节点之间的距离。有两种方法计算节点之间的距离：有两种方法计算节点之间的距离：直线距离，也叫欧几里德距离（直线距离，也叫欧几里德距离（Euclidean Metric）；）；折线距离（折线距离（Rectilinear Metric），也叫城市距离（），也叫城市距离（Metropolitan Metric）。）。本讲稿第十页，共六十二页3.5 3.5 选址模型选址模型I.简单模型：简单模型：在一条直线上（街道）选择一个有效位置（商店），即一种设施，让这条在一条直线上（街道）选择一个有效位置（商店），即一种设施，让这条街道上的所有顾客到达商店的平均距离最短。街道上的所有顾客到达商店的平均距离最短。假设街道上顾客分布的概率（密度）为假设街道上顾客分布的概率（密度）为则目标函数为：则目标函数为：简单模型简单模型大街上第大街上第i i个位置到所选地址的距离个位置到所选地址的距离选择投资的位置选择投资的位置本讲稿第十一页，共六十二页3.5 3.5 选址模型选址模型定积分求导：定积分求导：定积分求导定积分求导（1）其中，其中，被假设为在时间区间被假设为在时间区间 中具有连续导数中具有连续导数 。莱布尼兹法则莱布尼兹法则关于一个变量（它既不是积分变量，也不进入积分上下限）求导定积关于一个变量（它既不是积分变量，也不进入积分上下限）求导定积分，可以简单地穿过积分符号直接关于该变量求导被积函数。分，可以简单地穿过积分符号直接关于该变量求导被积函数。本讲稿第十二页，共六十二页3.5 3.5 选址模型选址模型定积分求导：定积分求导：定积分求导定积分求导（2）有微商公式：有微商公式：定积分关于积分上限定积分关于积分上限b的导数等于被积函数在的导数等于被积函数在t=b处的取值；处的取值；定积分关于积分下限定积分关于积分下限a的导数等于被积函数在的导数等于被积函数在t=a处的取值的负数；处的取值的负数；本讲稿第十三页，共六十二页3.5 3.5 选址模型选址模型定积分求导：定积分求导：定积分求导定积分求导（3）有微商公式：有微商公式：右边第一项来自对被积函数中变量的求导，右边第二项来自对积分上限的求导，而且右边第一项来自对被积函数中变量的求导，右边第二项来自对积分上限的求导，而且基于下列链式求导：基于下列链式求导：其中其中x不仅进入被积函数，而且影响积分上限不仅进入被积函数，而且影响积分上限对以下函数求导对以下函数求导本讲稿第十四页，共六十二页3.5 3.5 选址模型选址模型对目标函数求导，对目标函数求导，令一阶导数为零，得：令一阶导数为零，得：简单模型简单模型求解结果表明，所开设的新店面需要设置在权重的中点，即两求解结果表明，所开设的新店面需要设置在权重的中点，即两面的权重都是面的权重都是50%50%。本讲稿第十五页，共六十二页3.5 3.5 选址模型选址模型连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。为选址的问题。II.交叉中值模型（交叉中值模型（Cross Median）通过交叉中值的方法对单一设施平面选址问题的加权城市距离进行最小化。通过交叉中值的方法对单一设施平面选址问题的加权城市距离进行最小化。其目标函数为：其目标函数为：交叉中值模型交叉中值模型第第i i个点对应的权重，例如需求；个点对应的权重，例如需求；需求点的总数目需求点的总数目第第i i个需求点的坐标；个需求点的坐标；服务设施的坐标；服务设施的坐标；本讲稿第十六页，共六十二页3.5 3.5 选址模型选址模型交叉中值模型的目标函数可以用两个互不相干的部分来表达：交叉中值模型的目标函数可以用两个互不相干的部分来表达：交叉中值模型交叉中值模型是是x x方向所有权重的中值点；方向所有权重的中值点；是是y y方向所有权重的中值点；方向所有权重的中值点；惟一值惟一值某一范围某一范围惟一值惟一值点点线段线段某一范围某一范围线段线段区域区域本讲稿第十七页，共六十二页3.5 3.5 选址模型选址模型例例1 报刊亭选址报刊亭选址一个报刊连锁公司想在一个地区开设一个新的报刊亭零售点，主要的服务对象是附近的一个报刊连锁公司想在一个地区开设一个新的报刊亭零售点，主要的服务对象是附近的5个住宿小区个住宿小区的居民，他们是新开设报刊亭零售点的主要顾客源。下图坐标系中确切地表达了这些需求点的位置，下表的居民，他们是新开设报刊亭零售点的主要顾客源。下图坐标系中确切地表达了这些需求点的位置，下表为各个需求点对应的权重。权重代表每个月潜在的顾客需求总量，基本可以用小区中总的居民数量来近似。为各个需求点对应的权重。权重代表每个月潜在的顾客需求总量，基本可以用小区中总的居民数量来近似。经理希望通过这些信息来确定一个合适的报刊零售点的经理希望通过这些信息来确定一个合适的报刊零售点的 位置，要求每个月顾客到报刊零售点所行走的距离位置，要求每个月顾客到报刊零售点所行走的距离总和最小。总和最小。交叉中值模型交叉中值模型需求点需求点x坐标坐标y坐标坐标权重权重13112527343342435156本讲稿第十八页，共六十二页3.5 3.5 选址模型选址模型首先，确定中值，首先，确定中值，需求点需求点沿沿x轴的位置轴的位置w从左到右从左到右516426+3=9136+3+1=103425从右到左从右到左257347+3=10134251交叉中值模型交叉中值模型需求点需求点沿沿y轴的位置轴的位置w从上到下从上到下556446+3=9336+3+3=122211从下到上从下到上111221+7=8331+7+3=114455本讲稿第十九页，共六十二页3.5 3.5 选址模型选址模型选址结果：选址结果：交叉中值模型交叉中值模型位置位置A（3，3）位置位置B（4，3）需求点需求点距离距离权重权重总和总和需求点需求点距离距离权重权重总和总和121213132372122714313330304236433954624556305656本讲稿第二十页，共六十二页3.5 3.5 选址模型选址模型连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。III.精确重心法（精确重心法（Exact Gravity）交叉中值模型使用城市距离，适合小范围城市内选址问题；交叉中值模型使用城市距离，适合小范围城市内选址问题；精确重心法使用直线距离，适合大范围城市间选址问题，目标函数为，精确重心法使用直线距离，适合大范围城市间选址问题，目标函数为，精确重心法精确重心法与第与第i i个点对应的权重，例如需求；个点对应的权重，例如需求；需求点的总数目需求点的总数目第第i i个需求点的坐标；个需求点的坐标；服务设施的坐标；服务设施的坐标；本讲稿第二十一页，共六十二页3.5 3.5 选址模型选址模型精确重心法目标函数为双变量系统，分别对精确重心法目标函数为双变量系统，分别对xs和和ys求偏导，并令导数为零，求得求偏导，并令导数为零，求得隐含最优解的等式，隐含最优解的等式，精确重心法精确重心法本讲稿第二十二页，共六十二页3.5 3.5 选址模型选址模型迭代法：迭代法：利用已知的点（利用已知的点（xs(k-1),ys(k-1)）,求出求出dis(k-1)，再求出新的点，再求出新的点（xs(k),ys(k)）,依次求解，直到求得符合要求的解。依次求解，直到求得符合要求的解。精确重心法精确重心法迭代公式：迭代公式：(1)其中：其中：(2)本讲稿第二十三页，共六十二页3.5 3.5 选址模型选址模型精确重心法精确重心法迭代法步骤：迭代法步骤：（1）初始值的确定；）初始值的确定；（2）迭代；）迭代；（3）中止准则；）中止准则；初始值的确定：初始值的确定：a、任意选择一个点作为初始值；、任意选择一个点作为初始值；b、按照、按照简化公式简化公式选择初始值；选择初始值；本讲稿第二十四页，共六十二页3.5 3.5 选址模型选址模型中止准则的确定：中止准则的确定：a、直接设置一个确定的迭代次数、直接设置一个确定的迭代次数N；b、判断两次迭代的差值是否小于设定的阈值；、判断两次迭代的差值是否小于设定的阈值；C、判断总费用是否减小或两次迭代差值小于设定值、判断总费用是否减小或两次迭代差值小于设定值精确重心法精确重心法本讲稿第二十五页，共六十二页3.5 3.5 选址模型选址模型精确重心法应用于报刊亭选址问题：精确重心法应用于报刊亭选址问题：精确重心法精确重心法第第一一次次迭迭代代初始位置初始位置(x(x0 0,y,y0 0)3 33 3需求点需求点1 12 23 34 45 5(x(xi i,y,yi i)3 31 15 52 24 43 32 24 41 15 5权重权重w wi i1 17 73 33 36 6距离距离d disis(0)(0)2 22.2360679772.2360679771 11.4142135621.4142135622.8284271252.828427125w wi ix xi i/d/disis(0)(0)；w wi iy yi i/d/disis(0)(0)1.51.50.50.5 15.6524815.652486.260996.2609912129 94.24264.2426 8.48528.4852 2.12132.1213 10.60610.606w wi i/d/disis(0)(0)；w wi i/d/disis(0)(0)0.50.53.1304951683.1304951683 32.1213203442.1213203442.1213203442.121320344迭代位置迭代位置(x(x1 1,y,y1 1)3.2664391713.2664391713.2054113823.205411382中止判断（中止判断（Z Z1 1）41.8656792841.86567928本讲稿第二十六页，共六十二页3.5 3.5 选址模型选址模型精确重心法应用于报刊亭选址问题：精确重心法应用于报刊亭选址问题：精确重心法精确重心法第第二二次次迭迭代代初始位置初始位置(x(x1 1,y,y1 1)3.2664391713.2664391713.2054113823.205411382需求点需求点1 12 23 34 45 5(x(xi i,y,yi i)3 31 15 52 24 43 32 24 41 15 5权重权重w wi i1 17 73 33 36 6距离距离d disis(1)(1)2.2214475452.2214475452.1114567832.1114567830.76177770.76177774 41.4950716531.4950716532.8908986192.890898619w wi ix xi i/d/disis(1)(1)；w wi iy yi i/d/disis(1)(1)1.35041.35040.4500.4501 116.57616.5766.63046.630415.7515.752 211.811.81414 4.01314.0131 8.02638.0263 2.07542.0754 10.3710.37w wi i/d/disis(1)(1)；w wi i/d/disis(1)(1)0.4501569270.4501569273.3152466373.3152466373.93815653.938156554542.0065927912.0065927912.0754792162.075479216迭代位置迭代位置(x(x2 2,y,y2 2)3.3742776423.3742776423.164776123.16477612中止判断（中止判断（Z Z2 2）41.1175849241.11758492本讲稿第二十七页，共六十二页3.5 3.5 选址模型选址模型精确重心法应用于报刊亭选址问题：精确重心法应用于报刊亭选址问题：精确重心法精确重心法第第三三次次迭迭代代初始位置初始位置(x(x2 2,y,y2 2)3.3742776423.3742776423.164776123.16477612需求点需求点1 12 23 34 45 5(x(xi i,y,yi i)3 31 15 52 24 43 32 24 41 15 5权重权重w wi i1 17 73 33 36 6距离距离d disis(2)(2)2.1968931252.1968931251.9999191471.9999191470.64705450.647054587871.6081784631.6081784633.0008733753.000873375w wi ix xi i/d/disis(2)(2)；w wi iy yi i/d/disis(2)(2)1.36551.36550.4550.4551 117.50017.5007.00027.000218.5418.545 513.913.90909 3.73093.7309 7.46187.4618 1.99941.9994 9.9979.997w wi i/d/disis(2)(2)；w wi i/d/disis(2)(2)0.4551882790.4551882793.5001414993.5001414994.63639394.636393993931.8654646041.8654646041.9994179191.999417919迭代位置迭代位置(x(x3 3,y,y3 3)3.4633988113.4633988113.1167077413.116707741中止判断（中止判断（Z Z3 3）40.9672665540.96726655本讲稿第二十八页，共六十二页3.5 3.5 选址模型选址模型中止准则的使用：中止准则的使用：若（若（1）N=2；（；（2）坐标值阈值为）坐标值阈值为0.2；坐标值变化幅度小于；坐标值变化幅度小于4%；（；（3）总）总费用阈值为费用阈值为0.2；总费用相对变化幅度小于；总费用相对变化幅度小于1%。精确重心法精确重心法总费用总费用2.64%2.64%，-1.52%-1.52%3.30%3.30%，-1.27%-1.27%8.88%8.88%，6.85%6.85%相对差值相对差值40.843840.843840.967340.967341.117641.117641.865741.86570.08910.0891，-0.0481-0.04810.10780.1078，-0.0406-0.04060.26640.2664，0.20540.2054绝对差值绝对差值坐标点迭代差值坐标点迭代差值总费用迭代差值总费用迭代差值坐标点坐标点迭代迭代次数次数3.11673.11673.16483.16483.20543.2054y y3.46343.46343.37433.37433.26643.2664x x0.12350.12350.15030.15030.74810.7481绝对差值绝对差值1.79%1.79%1 10.37%0.37%2 20.30%0.30%3 3相对差值相对差值本讲稿第二十九页，共六十二页3.5 3.5 选址模型选址模型补充例题：有四个零售点，其坐标、物资需求量及运输费用如下表所示，请用补充例题：有四个零售点，其坐标、物资需求量及运输费用如下表所示，请用重心法为配送中心选址。重心法为配送中心选址。零售点零售点物资需物资需求量求量qi运输费运输费用用ri坐标坐标xiyi1252223511332.5510841549精确重心法精确重心法第一步，按照简化公式确定第一步，按照简化公式确定初始值，初始值，本讲稿第三十页，共六十二页3.5 3.5 选址模型选址模型 精确重心法精确重心法第二步，以点（第二步，以点（7.8，4.9）作为配送中心，计算距离与总费用，）作为配送中心，计算距离与总费用，第三步，计算改善的配送中心选址，第三步，计算改善的配送中心选址，本讲稿第三十一页，共六十二页3.5 3.5 选址模型选址模型 精确重心法精确重心法第四步，以点（第四步，以点（8.6，5.1）作为配送中心，计算距离与总费用，）作为配送中心，计算距离与总费用，第五步，计算改善的配送中心选址，第五步，计算改善的配送中心选址，本讲稿第三十二页，共六十二页3.5 3.5 选址模型选址模型 精确重心法精确重心法第六步，以点（第六步，以点（9.0，5.2）作为配送中心，计算距离与总费用，）作为配送中心，计算距离与总费用，此时，此时，Z(2)=Z(1)=191，虽然结果是取小数而得，但二者已经非常接近，所以可认为最佳点为（，虽然结果是取小数而得，但二者已经非常接近，所以可认为最佳点为（9.0，5.2）或（）或（8.6，5.1）。）。本讲稿第三十三页，共六十二页3.5 3.5 选址模型选址模型交叉中值模型与精确重心法交叉中值模型与精确重心法城市距离（折线距离）；城市距离（折线距离）；适合于小范围的城市内选址问题；适合于小范围的城市内选址问题；目标使对加权的城市距离最小化；目标使对加权的城市距离最小化；属于单一设施连续点选址问题。属于单一设施连续点选址问题。欧几米德距离（直线距离）；欧几米德距离（直线距离）；适合于大范围城市间选址问题；适合于大范围城市间选址问题；目标是使加权的直线距离最小化；目标是使加权的直线距离最小化；属于单一设施的连续点选址问题。属于单一设施的连续点选址问题。本讲稿第三十四页，共六十二页3.5 3.5 选址模型选址模型离散点选址问题指的是在有限的候选位置里面，选取最为合离散点选址问题指的是在有限的候选位置里面，选取最为合适的一个或一组位置为最优方案，相应的模型称为离散点选址适的一个或一组位置为最优方案，相应的模型称为离散点选址模型。模型。离散点选址模型与连续点选址模型的区别在于：它所拥有的离散点选址模型与连续点选址模型的区别在于：它所拥有的候选方案只有有限个元素。候选方案只有有限个元素。对于离散点选址问题，目前主要有两种模型，分别是覆盖模对于离散点选址问题，目前主要有两种模型，分别是覆盖模型和型和P-中值模型。覆盖模型常用的又有集合覆盖模型和最大覆中值模型。覆盖模型常用的又有集合覆盖模型和最大覆盖模型两种。盖模型两种。覆盖模型（覆盖模型（Covering）覆盖模型，是对于需求已知的一些需求点，确定一组服务设覆盖模型，是对于需求已知的一些需求点，确定一组服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适的位置。该模型适用于商业物流系统，如施的最小数量和合适的位置。该模型适用于商业物流系统，如零售点的选择问题、加油站的选址、配送中心的选址问题等。零售点的选择问题、加油站的选址、配送中心的选址问题等。离散点选址问题离散点选址问题本讲稿第三十五页，共六十二页3.5 3.5 选址模型选址模型根据解决问题的方法的不同，覆盖模型可以分为两种不同的主要模型：根据解决问题的方法的不同，覆盖模型可以分为两种不同的主要模型：集合覆盖模型，用最小数量的设施去覆盖所有的需求点；集合覆盖模型，用最小数量的设施去覆盖所有的需求点；最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求或需求点。最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求或需求点。覆盖模型覆盖模型本讲稿第三十六页，共六十二页3.5 3.5 选址模型选址模型IV.集合覆盖模型集合覆盖模型集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求点。集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求点。数学模型为：数学模型为：集合覆盖模型集合覆盖模型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 3.5 选址模型选址模型集合覆盖模型启发式算法：集合覆盖模型启发式算法：第一步：初始化。令所有的第一步：初始化。令所有的x xj j0 0，y yi i0 0，（已分配的需求），并（已分配的需求），并确定集合确定集合A(i)A(i)和集合和集合B(j)B(j)；第二步：选择下一个设施点。在第二步：选择下一个设施点。在M M中选择中选择y yi i0 0，且，且A(i)A(i)的规模为最大的点的规模为最大的点ii为设施点，为设施点，即即 ，令，令 ，并在，并在M M集合中剔除节点集合中剔除节点ii，即，即第三步：确定节点第三步：确定节点ii的覆盖范围。将的覆盖范围。将A(i)A(i)中的元素按中的元素按B(j)B(j)的规模从小到大的顺序的规模从小到大的顺序指派给指派给ii，直至，直至ii的容量为的容量为C Cii0 0或或A(i)A(i)为空。其中对于为空。其中对于jA(i)jA(i)且，且，x xj jDDj j，将，将j j支配给支配给ii的方法为：若的方法为：若 ，则令，则令x xijij=D=Dj jx xj j，C Cii=C=Cii-(D-(Dj j-x-xj j)，x xj j1 1，在，在A(i)A(i)和和N N中剔除需求点中剔除需求点j j。若。若 ，则令，则令第四步：若第四步：若N N或或M M为空，停止；否则，更新集合为空，停止；否则，更新集合A(i)A(i)和集合和集合B(j)B(j)，转第二步。，转第二步。集合覆盖模型启发式算法集合覆盖模型启发式算法本讲稿第三十八页，共六十二页3.5 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)。如下表。如下表所示，值得指出的是本问题没有需求量和容量，故无需考虑服务能力约束式。所示，值得指出的是本问题没有需求量和容量，故无需考虑服务能力约束式。集合覆盖模型启发式算法集合覆盖模型启发式算法17849256322434143233211 图图 小区居民点位置图小区居民点位置图3本讲稿第三十九页，共六十二页3.5 3.5 选址模型选址模型 集合覆盖模型启发式算法集合覆盖模型启发式算法第一步，初始化第一步，初始化居民点号居民点号A(i)B(j)11,2,3,41,2,3,421,2,31,2,331,2,3,4,5,61,2,3,4,541,3,4,5,6,71,3,4,5,753,4,5,63,4,563,4,5,7,874,6,7,84,7,886,7,8,97,8,998,98,9 第二步，确定一个设施点。因为第二步，确定一个设施点。因为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 3.5 选址模型选址模型 集合覆盖模型启发式算法集合覆盖模型启发式算法居民点号居民点号A(i)B(j)121,2,3221,2,3321,2,3,541,3,5,753,563,5,7,8787,888,97,8,998,98,9 第四步，确定一个设施点。因为第四步，确定一个设施点。因为A(8)8,9，|A(8)|2为最大，故首先选取为最大，故首先选取i8，并，并且且8，9两点归节点两点归节点8服务。服务。第五步，更新。此时，第五步，更新。此时，N2,M1,2,3,5,7,9,更新集合更新集合A(i)和集合和集合B(j)后如下表所示。后如下表所示。本讲稿第四十一页，共六十二页3.5 3.5 选址模型选址模型 集合覆盖模型启发式算法集合覆盖模型启发式算法 第六步，确定一个设施点。第六步，确定一个设施点。因为因为A(2)2，|A(2)|1为最大，故首先选取为最大，故首先选取i2，并且，并且2点点归节点归节点2服务服务。第七步，更新。此时，第七步，更新。此时，N,M1,3,5,7,9,结束。结束。因此，计算结果为（因此，计算结果为（4,8,2）。）。居民点号居民点号A(i)B(j)121,2,3221,2,3321,2,3,541,3,5,753,563,5,777879本讲稿第四十二页，共六十二页3.5 3.5 选址模型选址模型集合覆盖模型整数规划集合覆盖模型整数规划yi为0-1变量，yi=1,在i点建立设施；yi=0,不在i点建立设施，iMxij节点i供给量中被分配给需求点j的部分。居民点号居民点号A(i)B(j)11,2,3,41,2,3,421,2,31,2,331,2,3,4,5,61,2,3,4,541,3,4,5,6,71,3,4,5,753,4,5,63,4,563,4,5,7,874,6,7,84,7,886,7,8,97,8,998,98,9本讲稿第四十三页，共六十二页3.5 3.5 选址模型选址模型 集合覆盖模型整数规划集合覆盖模型整数规划整数规划模型：整数规划模型：本讲稿第四十四页，共六十二页3.5 3.5 选址模型选址模型 集合覆盖模型整数规划集合覆盖模型整数规划Lingo软件求解：软件求解：本讲稿第四十五页，共六十二页3.5 3.5 选址模型选址模型V.最大覆盖模型最大覆盖模型已知若干个需求点（客户）的位置和需求量，需从一组候选的地点中选择已知若干个需求点（客户）的位置和需求量，需从一组候选的地点中选择p个位置作为物流设个位置作为物流设施网点（如配送中心、仓库等），使得尽可能多地满足需求点的服务。施网点（如配送中心、仓库等），使得尽可能多地满足需求点的服务。最大覆盖模型的目标是对有限的服务网点进行选址，为尽可能多的对象提供服务，最大覆盖模型的目标是对有限的服务网点进行选址，为尽可能多的对象提供服务，如下图所示。如下图所示。最大覆盖模型最大覆盖模型最大覆盖模型最大覆盖模型本讲稿第四十六页，共六十二页3.5 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 3.5 选址模型选址模型 最大覆盖模型整数规划最大覆盖模型整数规划本讲稿第四十九页，共六十二页3.5 3.5 选址模型选址模型 集合覆盖模型整数规划集合覆盖模型整数规划Lingo软件求解：软件求解：本讲稿第五十页，共六十二页3.5 3.5 选址模型选址模型VI.P中值模型中值模型P中值模型是指在一个给定数量和位置的需求集合和一个给数量和候选位置的设施集合中值模型是指在一个给定数量和位置的需求集合和一个给数量和候选位置的设施集合的前提下，分别为的前提下，分别为P个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在设施与需求点之间的运输费用最低。设施与需求点之间的运输费用最低。如下图所示。如下图所示。P中值模型中值模型本讲稿第五十一页，共六十二页3.5 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.5 选址模型选址模型例例3：某饲料公司的仓库选址问题：某饲料公司的仓库选址问题某饲料公司在某新地区经过一段时间的宣传广告后，得到了某饲料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的定单，个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建由于该新地区离总部较远，该公司拟在该地区新建2个仓库，用最低的运输成本个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地调查之后，已有来满足该地区的需求。经过一段时间的实地调查之后，已有4个候选地址，如下个候选地址，如下图所示；各候选地址到不同超市的运输成本、各个超市的需求量如下表所示。图所示；各候选地址到不同超市的运输成本、各个超市的需求量如下表所示。P中值模型中值模型123456781234ijdi1234cij141220610022102510503341614120465928051812732006142 24970720302116082412622100本讲稿第五十三页，共六十二页3.5 3.5 选址模型选址模型P中值中值贪婪取走启发式算法贪婪取走启发式算法（Greedy Dropping Heuristic Algorithm）:P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法第一步，初始化，令循环数第一步，初始化，令循环数k=mk=m，将所有，将所有m m个候选位置都选中，然后将每个个候选位置都选中，然后将每个需求点分配给离其最近的一个侯选位置。需求点分配给离其最近的一个侯选位置。123456781234400100360600160140120600设施点设施点费用费用1860214037204760总费用总费用2480本讲稿第五十四页，共六十二页3.5 3.5 选址模型选址模型 P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客第二步，选择并取走一个位置点，满足以下条件：假如将它取走并