1、FP&D第三章第三章 选址模型及应用选址模型及应用3.1 选址的意义选址的意义3.2 选址决策的影响因素选址决策的影响因素3.3 选址模型的分类选址模型的分类3.4 选址中的距离计算选址中的距离计算3.5 选址模型选址模型3.6 实例分析实例分析FP&D3.1 3.1 选址的意义选址的意义选址在整个物流系统中占有非常重要的地位，主要属于物流选址在整个物流系统中占有非常重要的地位，主要属于物流管理战略层的研究问题。管理战略层的研究问题。选址决策就是要确定所要分配的设施的数量、位置以及分配选址决策就是要确定所要分配的设施的数量、位置以及分配方案。这些设施主要指物流系统中的节点，如制造商、供应商、方
2、案。这些设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售商网点等。仓库、配送中心、零售商网点等。FP&D3.1 3.1 选址的意义选址的意义设施数量与客户响应时间设施数量与客户响应时间 快速响应客户需求是竞争因素之一快速响应客户需求是竞争因素之一 快速响应客户需求与节点设施设置的数量有关快速响应客户需求与节点设施设置的数量有关期望的期望的响应时间响应时间设施设施数量数量FP&D3.1 3.1 选址的意义选址的意义选址与库存、运输成本存在密切联系，选址就是要在设施数量和成本中选址与库存、运输成本存在密切联系，选址就是要在设施数量和成本中求得最佳。求得最佳。设施数量设施数量库库存
3、存成成本本设施数量设施数量运运输输成成本本设施数量设施数量设设施施成成本本设施数量设施数量总成总成本本响应时间响应时间FP&D3.1 3.1 选址的意义选址的意义就供应链系统而言，核心企业的选址决策会影响所有供应商物流系统的就供应链系统而言，核心企业的选址决策会影响所有供应商物流系统的选址决策。选址决策。FP&D3.2 3.2 选址的影响因素选址的影响因素选址决策影响因素大致可分为外部因素及内部因素两大类选址决策影响因素大致可分为外部因素及内部因素两大类u宏观政治因素宏观政治因素政权、法制、政策等政权、法制、政策等u宏观经济因素宏观经济因素税收、关税、汇率等税收、关税、汇率等u基础设施基础设施
4、交通设施、通信设施交通设施、通信设施u自然环境与社会环境自然环境与社会环境如劳动力成本与质量如劳动力成本与质量u市场环境市场环境竞争对手、供应商、客竞争对手、供应商、客户等户等u企业发展战略企业发展战略如制造业企业选择劳动如制造业企业选择劳动密集密集/技术密集发展战略；技术密集发展战略；如商业服务业选择连锁如商业服务业选择连锁便利店便利店/超市的发展战略超市的发展战略FP&D3.2 3.2 选址的影响因素选址的影响因素选址决策包括地区选择和地点选择，二者需要考虑的因素有所不同。地选址决策包括地区选择和地点选择，二者需要考虑的因素有所不同。地区选择要考虑的是宏观因素；地点选择要考虑的是微观因素。
5、区选择要考虑的是宏观因素；地点选择要考虑的是微观因素。（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）地震）地震FP&D3.2 3.2 选址的影响因素选址的影响因素按照影响因素的性质的不同，可把影响因素分成两大类：即成本因素
6、和非成本按照影响因素的性质的不同，可把影响因素分成两大类：即成本因素和非成本因素。还可以根据因素对设施选址的重要性，分为：关键因素、重要因素、次要因因素。还可以根据因素对设施选址的重要性，分为：关键因素、重要因素、次要因素等素等。FP&D3.3 3.3 选址模型的分类选址模型的分类在建立一个选址模型之前，我们需要清楚以下问题：在建立一个选址模型之前，我们需要清楚以下问题：（1）选址的对象是什么？（）选址的对象是什么？（2）选址的目标区域是怎样的？）选址的目标区域是怎样的？（3）选址目标和成本函数是什么？（）选址目标和成本函数是什么？（4）有什么样的一些约束？）有什么样的一些约束？体选址面选址线
7、选址高维选址单一设施选址多设施选址连续选址网络选址离散选址可行性/最优性Minisum/MinimaxMaximin高次目标函数确定性与随机性静态与动态有能力约束无能力约束有不可行区域无不可行区域设施维度及数量选址目标区域选址成本选址约束固定权重/可变权重FP&D3.4 3.4 选址问题中的距离计算选址问题中的距离计算在选址问题模型中，最基本的一个参数是各个节点之间的距离。在选址问题模型中，最基本的一个参数是各个节点之间的距离。有两种方法计算节点之间的距离：有两种方法计算节点之间的距离：直线距离，也叫欧几里德距离（直线距离，也叫欧几里德距离（Euclidean Metric）；）；折线距离（折
8、线距离（Rectilinear Metric），也叫城市距离（），也叫城市距离（Metropolitan Metric）。）。FP&D3.5 3.5 选址模型选址模型I.简单模型：简单模型：在一条直线上（街道）选择一个有效位置（商店），即一种设施，让这在一条直线上（街道）选择一个有效位置（商店），即一种设施，让这条街道上的所有顾客到达商店的平均距离最短。条街道上的所有顾客到达商店的平均距离最短。假设街道上顾客分布的概率（密度）为假设街道上顾客分布的概率（密度）为则目标函数为：则目标函数为：简单模型简单模型)(xworwiLsxsxnsiiisiiidxsxxwdxxsxwZorsxwxswZ)
9、()(min)()(min00大街上第大街上第i i个位置到所选地址的距离个位置到所选地址的距离选择投资的位置选择投资的位置ixsFP&D3.5 3.5 选址模型选址模型定积分求导：定积分求导：定积分求导定积分求导badtxtFxI),()(（1）其中，其中，被假设为在时间区间被假设为在时间区间 中具有连续导数中具有连续导数 。),(xtFx),(xtF,babaxdtxtFdxdI),(莱布尼兹法则莱布尼兹法则关于一个变量（它既不是积分变量，也不进入积分上下限）求导关于一个变量（它既不是积分变量，也不进入积分上下限）求导定积分，可以简单地穿过积分符号直接关系该变量求导被积函数。定积分，可以简
10、单地穿过积分符号直接关系该变量求导被积函数。FP&D3.5 3.5 选址模型选址模型定积分求导：定积分求导：定积分求导定积分求导badtxtFbaJ),(),(（2）),(),(),(),(xaFxtFdadJxbFxtFdbdJatbt有微商公式：有微商公式：定积分关于积分上限定积分关于积分上限b的导数等于被积函数在的导数等于被积函数在t=b处的取值；处的取值；定积分关于积分下限定积分关于积分下限a的导数等于被积函数在的导数等于被积函数在t=a处的取值的负数；处的取值的负数；FP&D3.5 3.5 选址模型选址模型定积分求导：定积分求导：定积分求导定积分求导)(),()(xbadtxtFxK
11、（3）)(),(),()(xbxxbFdtxtFdxdKxbax有微商公式：有微商公式：右边第一项来自对被积函数中变量的求导，右边第二项来自对积分上右边第一项来自对被积函数中变量的求导，右边第二项来自对积分上限的求导，而且基于下列链式求导：限的求导，而且基于下列链式求导：其中其中x不仅进入被积函数，而且影响积分上限不仅进入被积函数，而且影响积分上限dxxdbxdbdK)()(dtedxdx20对以下函数求导对以下函数求导dtxdxdt32dttdxdx2023FP&D3.5 3.5 选址模型选址模型对目标函数求导，对目标函数求导，令一阶导数为零，得：令一阶导数为零，得：简单模型简单模型0)()
12、(000LsxsxnsiisiidxxwdxxwdsdZorwwdsdZ求解结果表明，所开设的新店面需要设置在权重的中点，求解结果表明，所开设的新店面需要设置在权重的中点，即两面的权重都是即两面的权重都是50%50%。LsxsxnsiiisiiidxsxxwdxxsxwZorsxwxswZ)()(min)()(min00FP&D3.5 3.5 选址模型选址模型连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。作为选址的问题。II.交叉中值模型（交叉中值模型（Cross Median）通过交叉中值的方法对单
13、一设施平面选址问题的加权城市距离进行最小通过交叉中值的方法对单一设施平面选址问题的加权城市距离进行最小化。其目标函数为：化。其目标函数为：交叉中值模型交叉中值模型1nisisiiyyxxwZ第第i i个点对应的权重，例如需求；个点对应的权重，例如需求；需求点的总数目需求点的总数目iwn第第i i个需求点的坐标；个需求点的坐标；iiyx,服务设施的坐标；服务设施的坐标；ssyx,FP&D3.5 3.5 选址模型选址模型交叉中值模型的目标函数可以用两个互不相干的部分来表达：交叉中值模型的目标函数可以用两个互不相干的部分来表达：交叉中值模型交叉中值模型nisiinisiiyywxxwZ11min是是
14、x x方向所有权重的中值点；方向所有权重的中值点；sx是是y y方向所有权重的中值点；方向所有权重的中值点；sy惟一值惟一值某一范围某一范围惟一值惟一值点点线段线段某一范围某一范围线段线段区域区域sxsyFP&D3.5 3.5 选址模型选址模型例例1 报刊亭选址报刊亭选址一个报刊连锁公司想在一个地区开设一个新的报刊亭零售点，主要的服务对象一个报刊连锁公司想在一个地区开设一个新的报刊亭零售点，主要的服务对象是附近的是附近的5个住宿小区的居民，他们是新开设报刊亭零售点的主要顾客源。下图坐标个住宿小区的居民，他们是新开设报刊亭零售点的主要顾客源。下图坐标系中确切地表达了这些需求点的位置，下表为各个需
15、求点对应的权重。权重代表每系中确切地表达了这些需求点的位置，下表为各个需求点对应的权重。权重代表每个月潜在的顾客需求总量，基本可以用小区中总的居民数量来近似。经理希望通过个月潜在的顾客需求总量，基本可以用小区中总的居民数量来近似。经理希望通过这些信息来确定一个合适的报刊零售点的这些信息来确定一个合适的报刊零售点的 位置，要求每个月顾客到报刊零售点所行位置，要求每个月顾客到报刊零售点所行走的距离总和最小。走的距离总和最小。交叉中值模型交叉中值模型需求点需求点x坐标坐标y坐标坐标权重权重13112527343342435156FP&D3.5 3.5 选址模型选址模型首先，确定中值，首先，确定中值，
16、需求点需求点沿沿x轴的位置轴的位置w从左到右从左到右516426+3=9136+3+1=103425从右到左从右到左257347+3=10134251交叉中值模型交叉中值模型10)63371(21211niiwW需求点需求点沿沿y轴的位置轴的位置w从上到下从上到下556446+3=9336+3+3=122211从下到上从下到上111221+7=8331+7+3=114455FP&D3.5 3.5 选址模型选址模型选址结果：选址结果：交叉中值模型交叉中值模型位置位置A（3，3）位置位置B（4，3）需求点需求点距离距离权重权重总和总和需求点需求点距离距离权重权重总和总和12121313237212
17、2714313330304236433954624556305656FP&D3.5 3.5 选址模型选址模型连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。作为选址的问题。III.精确重心法（精确重心法（Exact Gravity）交叉中值模型使用城市距离，适合小范围城市内选址问题；交叉中值模型使用城市距离，适合小范围城市内选址问题；精确重心法使用直线距离，适合大范围城市间选址问题，目标函数为，精确重心法使用直线距离，适合大范围城市间选址问题，目标函数为，精确重心法精确重心法nisisiiyyxxwZ1
18、2/122)()(min与第与第i i个点对应的权重，例如需求；个点对应的权重，例如需求；需求点的总数目需求点的总数目iwn第第i i个需求点的坐标；个需求点的坐标；iiyx,服务设施的坐标；服务设施的坐标；ssyx,FP&D3.5 3.5 选址模型选址模型精确重心法目标函数为双变量系统，分别对精确重心法目标函数为双变量系统，分别对xs和和ys求偏导，并令导数为求偏导，并令导数为零，求得隐含最优解的等式，零，求得隐含最优解的等式，精确重心法精确重心法221111)()(sisiisniisiniisiisniisiniisiisyyxxddwdywydwdxwxFP&D3.5 3.5 选址模型
19、选址模型迭代法：迭代法：利用已知的点（利用已知的点（xs(k-1),ys(k-1)）,求出求出dis(k-1)，再求出新的点，再求出新的点（xs(k),ys(k)）,依次求解，直到求得符合要求的解。依次求解，直到求得符合要求的解。精确重心法精确重心法迭代公式：迭代公式：niisiniisiisniisiniisiiskdwkdywkykdwkdxwkx1111)1()1()()1()1()(1)其中：其中：2122)1()1()1(kyykxxkdsisiis(2)FP&D3.5 3.5 选址模型选址模型精确重心法精确重心法迭代法步骤：迭代法步骤：（1）初始值的确定；）初始值的确定；（2）迭代
20、；）迭代；（3）中止准则；）中止准则；初始值的确定：初始值的确定：a、任意选择一个点作为初始值；、任意选择一个点作为初始值；b、按照、按照简化公式简化公式选择初始值；选择初始值；niisiniisiisniisiniisiiskdwkdywkykdwkdxwkx1111)1()1()()1()1()(niiniiisniiniiiswywywxwx1111)0()0(FP&D3.5 3.5 选址模型选址模型中止准则的确定：中止准则的确定：a、直接设置一个确定的迭代次数、直接设置一个确定的迭代次数N；b、判断两次迭代的差值是否小于设定的阈值；、判断两次迭代的差值是否小于设定的阈值；C、判断总费用
21、是否减小或两次迭代差值小于设定值、判断总费用是否减小或两次迭代差值小于设定值精确重心法精确重心法itssssitssssykykykyxkxkxkxlimlim)1()()()1()()(itniiiiZkZkZkZ或者kZkZkyykxxkZlim12122)1()()()1()()()()(FP&D3.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 4
22、3 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.515.652415.65248 86.260996.2609912129 94.24264.2426 8.48528.4852 2.12132.121310.60610.606w wi i/d/disis(0)(
23、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.86567928FP&D3.5 3.5 选址模型选址模型精确重心法应用于报刊亭选址问题：精确重心法应用于报刊亭选址问题：精确重心法精确重心法第第二二次次迭迭代代初始位置初始位置(x(x1 1,y,y1 1)3
24、.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/
25、d/disis(1)(1)1.3501.3504 40.4500.4501 116.57616.576 6.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
26、(x2 2,y,y2 2)3.3742776423.3742776423.164776123.16477612中止判断（中止判断（Z Z2 2）41.1175849241.11758492FP&D3.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权重权
27、重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.3651.3655 50.4550.4551 117.50017.500 7.00027.000218.5418.545 513.913.90909 3.73093.7309 7.46187.
28、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.96726655FP&D3.5 3.5 选址模
29、型选址模型中止准则的使用：中止准则的使用：若（若（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.10
30、780.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相对差值相对差值FP&D3.5 3.5 选址模型选址模型补充例题：有四个零售点，其
31、坐标、物资需求量及运输费用如下表所示，补充例题：有四个零售点，其坐标、物资需求量及运输费用如下表所示，请用重心法为配送中心选址。请用重心法为配送中心选址。零售点零售点物资需物资需求量求量qi运输费运输费用用ri坐标坐标xiyi1252223511332.5510841549精确重心法精确重心法第一步，按照简化公式确第一步，按照简化公式确定初始值，定初始值，9.415.2329185.23322)0(8.715.23241105.211322)0(11111111niiiniiiiniiniiisniiiniiiiniiniiisrqyrqwywyrqxrqwxwxFP&D3.5 3.5 选址模
32、型选址模型 精确重心法精确重心法第二步，以点（第二步，以点（7.8，4.9）作为配送中心，计算距离与总费用，）作为配送中心，计算距离与总费用，第三步，计算改善的配送中心选址，第三步，计算改善的配送中心选址，1.56.5/18.3/5.27.3/35.6/26.5/918.3/85.27.3/335.6/22)0()0()1(6.86.5/18.3/5.27.3/35.6/26.5/418.3/105.27.3/1135.6/22)0()0()1(41414141iisiiisiisiisiiisiisdwdywydwdxwx6.5)99.4()48.7()0(8.3)89.4()108.7()
33、0(7.3)39.4()118.7()0(5.6)29.4()28.7()0(2/12242/12232/12222/1221ssssdddd1965)6.518.35.27.335.62()0(ZFP&D3.5 3.5 选址模型选址模型 精确重心法精确重心法第四步，以点（第四步，以点（8.6，5.1）作为配送中心，计算距离与总费用，）作为配送中心，计算距离与总费用，第五步，计算改善的配送中心选址，第五步，计算改善的配送中心选址，2.56.5/18.3/5.27.3/35.6/26/910.3/85.22.3/333.7/22)1()1()2(0.96.5/18.3/5.27.3/35.6/2
34、6/410.3/105.22.3/1133.7/22)1()1()2(41414141iisiiisiisiisiiisiisdwdywydwdxwx6)91.5()46.8()1(0.3)81.5()106.8()1(2.3)31.5()116.8()1(3.7)21.5()26.8()1(2/12242/12232/12222/1221ssssdddd1915)610.35.22.333.72()1(ZFP&D3.5 3.5 选址模型选址模型 精确重心法精确重心法第六步，以点（第六步，以点（9.0，5.2）作为配送中心，计算距离与总费用，）作为配送中心，计算距离与总费用，此时，此时，Z(2
35、)=Z(1)=191，虽然结果是取小数而得，但二者已经非常接近，所以可认，虽然结果是取小数而得，但二者已经非常接近，所以可认为最佳点为（为最佳点为（9.0，5.2）或（）或（8.6，5.1）。）。3.6)92.5()40.9()1(0.3)82.5()100.9()1(0.3)32.5()110.9()1(7.7)22.5()20.9()1(2/12242/12232/12222/1221ssssdddd1915)3.610.35.20.330.72()2(ZFP&D3.5 3.5 选址模型选址模型交叉中值模型与精确重心法交叉中值模型与精确重心法 城市距离（折线距离）；城市距离（折线距离）；适
36、合于小范围的城市内选址问题；适合于小范围的城市内选址问题；目标使对加权的城市距离最小化；目标使对加权的城市距离最小化；属于单一设施连续点选址问题。属于单一设施连续点选址问题。欧几米德距离（直线距离）；欧几米德距离（直线距离）；适合于大范围城市间选址问题；适合于大范围城市间选址问题；目标是使加权的直线距离最小化；目标是使加权的直线距离最小化；属于单一设施的连续点选址问题。属于单一设施的连续点选址问题。FP&D3.5 3.5 选址模型选址模型离散点选址问题指的是在有限的候选位置里面，选取最为合离散点选址问题指的是在有限的候选位置里面，选取最为合适的一个或一组位置为最优方案，相应的模型称为离散点选址
37、适的一个或一组位置为最优方案，相应的模型称为离散点选址模型。模型。离散点选址模型与连续点选址模型的区别在于：它所拥有的离散点选址模型与连续点选址模型的区别在于：它所拥有的候选方案只有有限个元素。候选方案只有有限个元素。对于离散点选址问题，目前主要有两种模型，分别是覆盖模对于离散点选址问题，目前主要有两种模型，分别是覆盖模型和型和P-中值模型。覆盖模型常用的又有集合覆盖模型和最大覆中值模型。覆盖模型常用的又有集合覆盖模型和最大覆盖模型两种。盖模型两种。覆盖模型（覆盖模型（Covering）覆盖模型，是对于需求已知的一些需求点，确定一组服务覆盖模型，是对于需求已知的一些需求点，确定一组服务设施来满
38、足这些需求点的需求。在这个模型中，需要确定服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适的位置。该模型适用于商业物流系统，设施的最小数量和合适的位置。该模型适用于商业物流系统，如零售点的选择问题、加油站的选址、配送中心的选址问题等。如零售点的选择问题、加油站的选址、配送中心的选址问题等。离散点选址问题离散点选址问题FP&D3.5 3.5 选址模型选址模型根据解决问题的方法的不同，覆盖模型可以分为两种不同的主要模型：根据解决问题的方法的不同，覆盖模型可以分为两种不同的主要模型：集合覆盖模型，用最小数量的设施去覆盖所有的需求点；集合覆盖模型，用最小数量的设施去覆盖所
39、有的需求点；最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求点。最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求点。覆盖模型覆盖模型FP&D3.5 3.5 选址模型选址模型IV.集合覆盖模型集合覆盖模型集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求点。集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求点。数学模型为：数学模型为：集合覆盖模型集合覆盖模型MjNiyMjxMjxDydNiytsxijjjAijjijiiBjijMjj,0,1,0,1.min)()(N区域中的需求点（客户）集合，N=1,2,n；M区域中可建设设施的候选点集合，M=1,2,m；di第i个需求点的需求量；
40、Dj设施点j的服务能力；A(j)设施节点j可以覆盖的需求点i的集合；B(i)可以覆盖需求节点i的设施节点j的集合；Xj为0-1变量，xj=1,在j点建立设施；xj=0,不在j点建立设施，jMyij节点i需求中被分配给设施点j的部分(比例)。FP&D3.5 3.5 选址模型选址模型集合覆盖模型启发式算法：集合覆盖模型启发式算法：第一步：初始化。令所有的第一步：初始化。令所有的y yi i0 0，x xj j0 0，（已分配的需（已分配的需求），并确定集合求），并确定集合A(jA(j)和集合和集合B(iB(i)；第二步：选择下一个设施点。在第二步：选择下一个设施点。在M M中选择中选择x xj j
41、0 0，且，且A(jA(j)的规模为最大的的规模为最大的点点jj为设施点，即为设施点，即 ，令，令 ，并在，并在M M集合中剔除节点集合中剔除节点jj，即，即第三步：确定节点第三步：确定节点jj的覆盖范围。将的覆盖范围。将A(jA(j)中的元素按中的元素按B(iB(i)的规模从的规模从小到大的顺序指派给小到大的顺序指派给jj，直至，直至jj的容量为的容量为D Dj j0 0或或A(jA(j)为空。其中对于为空。其中对于i iA(jA(j)且，且，y yi i11，将，将i i支配给支配给jj的方法为：若的方法为：若 ，则令，则令y yijij=1=1y yi i，D Dj j=D=Djj-d-
42、di i(1-y(1-yi i)，y yi i1 1，在，在A(jA(j)和和N N中剔除需求点中剔除需求点i i。若若 ，则令，则令第四步：若第四步：若N N或或M M为空，停止；否则，更新集合为空，停止；否则，更新集合A(jA(j)和集合和集合B(iB(i)，转第二，转第二步。步。集合覆盖模型启发式算法集合覆盖模型启发式算法0Mjijiyy)(max)(jAjA1 jx jMMjiiDyd)1(jiiDyd)1(0,jijiiijijDyyydDyFP&D3.5 3.5 选址模型选址模型例：在某区域需规划建设若干个农贸市场为将来该区例：在某区域需规划建设若干个农贸市场为将来该区9个主要居民
43、点提供服务，个主要居民点提供服务，除第除第6居民点外，其他各点均有建设市场的条件，如下图所示。已知市场的最大服务居民点外，其他各点均有建设市场的条件，如下图所示。已知市场的最大服务直径为直径为3km，为保护该区域的环境，希望尽可能少地建造农贸市场。问应如何规划？，为保护该区域的环境，希望尽可能少地建造农贸市场。问应如何规划？解：解：N1,2,3,4,5,6,7,8,9，M1,2,3,4,5,7,8,9，由图两点间的最短距离，根，由图两点间的最短距离，根据最大服务半径为据最大服务半径为3km的约束及第的约束及第6居民点不适合建市场的要求，可确定集合居民点不适合建市场的要求，可确定集合A(j)和和
44、B(i)。如下表所示，值得指出的是本问题没有需求量和容量，故无需考虑服务能力约。如下表所示，值得指出的是本问题没有需求量和容量，故无需考虑服务能力约束式。束式。集合覆盖模型启发式算法集合覆盖模型启发式算法17849256322434143233211 图图 小区居民点位置图小区居民点位置图3FP&D3.5 3.5 选址模型选址模型 集合覆盖模型启发式算法集合覆盖模型启发式算法第一步，初始化第一步，初始化居民点号居民点号A(j)B(i)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,5
45、63,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为最大，故为最大，故首先选取首先选取j4。由于无容量约束故依次指派。由于无容量约束故依次指派5,7,1,6,3,4点归节点点归节点4服务。服务。第三步，更新。此时，第三步，更新。此时，N2,8,9,M1,2,3,5,7,8,9,更新集合更新集合A(j)和集合和集合B(i)后如下表所示。后如下表所示。FP&D3.5 3.5 选址模型选址模型 集合覆盖模型启发式算法集合覆盖模型启发式算法居民点号居民点号A(
46、j)B(i)12221,2,3324567888,97,8,998,98,9 第四步，确定一个设施点。第四步，确定一个设施点。因为因为A(8)8,9，|A(8)|2为最大，故首先选取为最大，故首先选取j8，并且，并且8，9两点归节点两点归节点8服务服务。第五步，更新。此时，第五步，更新。此时，N2,M1,2,3,5,7,9,更新集合更新集合A(j)和集合和集合B(i)后如下表所示。后如下表所示。FP&D3.5 3.5 选址模型选址模型 集合覆盖模型启发式算法集合覆盖模型启发式算法居民点号居民点号A(j)B(i)122223245679 第六步，确定一个设施点。第六步，确定一个设施点。因为因为A
47、(2)2，|A(2)|1为最大，故首先选取为最大，故首先选取j2，并且，并且2点归节点点归节点2服务服务。第七步，更新。此时，第七步，更新。此时，N,M1,3,5,7,9,结束。结束。因此，计算结果为（因此，计算结果为（4,8,2）。）。FP&D3.5 3.5 选址模型选址模型集合覆盖模型整数规划集合覆盖模型整数规划N区域中的需求点（客户）集合，N=1,2,n；M区域中可建设设施的候选点集合，M=1,2,m；di第i个需求点的需求量；Dj设施点j的服务能力；A(j)设施节点j可以覆盖的需求点i的集合；B(i)可以覆盖需求节点i的设施节点j的集合；Xj为0-1变量，xj=1,在j点建立设施；xj
48、=0,不在j点建立设施，jMyij节点i需求中被分配给设施点j的部分(比例)。居民居民点号点号A(j)B(i)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整数规划模型求解：整数规划模型求解：MjNiyMjxMjxDydNiytsxijjjAijjijiiBjijMjj,0,1,0,1.min)()(FP&D3.5 3.5 选址模型选址模型 集合覆盖模型整数规划集合覆盖模型整数规划整数规划模型：
49、整数规划模型：9,8,7,6,5,4,3,2,1,9,8,7,6,5,4,3,2,1,09,8,7,6,5,4,3,2,1,1,01111111110.min9998898887787774686765646355545347454443413534333231232221141312116987654321jiyjxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyxtsxxxxxxxxxzijj9998989888786878777674768676564636565554535474645444341436353433323132322212141312111999999
50、999.xyyxyyyyxyyyyxyyyyyxyyyyxyyyyyyxyyyyyyxyyyxyyyytsFP&D3.5 3.5 选址模型选址模型 集合覆盖模型整数规划集合覆盖模型整数规划Lingo软件求解：软件求解：FP&D3.5 3.5 选址模型选址模型V.最大覆盖模型最大覆盖模型已知若干个需求点（客户）的位置和需求量，需从一组候选的地点中选择已知若干个需求点（客户）的位置和需求量，需从一组候选的地点中选择p个位个位置作为物流设施网点（如配送中心、仓库等），使得尽可能多地满足需求点的服务。置作为物流设施网点（如配送中心、仓库等），使得尽可能多地满足需求点的服务。最大覆盖模型的目标是对有限的
