第2章选址模型及应用

1第二章选址模型及应用•选址的意义•选址决策的影响因素•选址模型的分类•选址问题中的距离计算•选址模型•实例分析22.1选址的意义•定义–选址决策就是确定所要分配的设施的数量、位置及分配方案。•意义–就单个企业而言，它决定了整个物流系统及其它层次的结构。–影响物流成本：库存、运输（图2.1,2.2）–核心企业的选址影响供应物流系统选址3452.2选址决策的影响因素•外部因素：宏观政治及经济因素、基础设施及环境、竞争对手等•内部因素：企业的发展战略、产品、技术或服务的特征62.2.1外部因素分析•宏观政治及经济因素–宏观政治因素包括：政权是否稳定、法制是否健全、是否存在贸易禁运政策等。–宏观经济因素包括：税收政策、关税、汇率等•基础设施及环境–基础设施包括交通设施、通信设施等–环境包括自然环境、社会环境（劳动力成本、素质）•竞争对手–远离还是靠近？72.2.2内部因素分析•选址决策要与企业的发展战略相适应–制造业•高技术→高素质•劳动力密集→低人力成本–商业及服务业•便利店：人口密集、面积小•超市、批发市场：不需要人口密集、面积大–成本–服务水平82.2.3案例分析•肯德基的选址秘笈–本案例中考虑了那些因素？这些因素和我们刚才讲过的因素怎样对应？–商圈的成熟度和稳定度、聚客点、人流的主要动线怎样影响肯德基的选址？–肯德基选址使用选址模型么？–如果要开一家中餐馆、物流中心、超市、银行等，你认为肯德基的方法、指标那些是可以借鉴的？哪些是不同的？92.3选址模型的分类•被定位设施的维度及数量•选址问题目标区域的特征•选址成本•选址约束102.3.1被定位设施的维度及数量•根据设施的维度–体选址–面选址–线选址–点选址–更高维度的选址•设施选址的数量–单一设施–多设施112.3.2选址问题目标区域的特征•连续选址•网格选址•离散选址122.3.3选址成本•Minisum目标函数–X：新的待定设施物体的坐标–j：已存在且位置固定的物体的编号–Cj(X)：j到X的成本•minmax目标函数•maxmin目标函数min()jxjCX13三种中心的例子0567minisumminmaxmaxmin2.53.55.5反中心点中心点中值142.3.3选址成本(续)•固定权重与可变权重•被定位设施间有无相互联系•确定性与随机性•静态与动态152.4选址问题中的距离计算•直线距离（欧几里得距离）•折线距离（城市距离）22()()Eijijijdxxyy||||Rijijijdxxyy16172.5选址模型•商店选址：在一条直线上（街道）选个商店的位置，使得所有顾客到商店的平均距离最短–是选在中间位置么？18例商店选址(续)•如果顾客只出现在n个点上，商店选在其中一个点上。假设：–xi：表示第i个点坐标；–Wi：一段时间内，第i个点上出现顾客数量的随机变量；–xs：表示所选择点的坐标（介于第s个点和第s+1个点之间）0min||(2.3)nisiizwxx19例商店选址(续)•如果顾客可以出现在这条街的任一个点x，且每个点x上出现顾客的随机变量是w(x)。假设街道长为L，商店选在s点。0min()()()()(2.4)sLszwxsxdswxsxds20例商店选址(续)•对上面两式微分，并令微分值等于零，可以得到解：0100(2.5)()()(2.6)sniiiissLxxsdZwwdsdZwxdxwxdxds212.5.1连续点选址模型2.5.1.1交叉中值型(CrossMedian)wi：与第i个点对应的权重（例如需求）；(xi,yi)：第i个点的坐标；(xs,ys)：设施服务点的坐标；n：需求点的总数目1||||(2.7)niisisizwxxyy22•本模型的解是：–xs是x方向的对所有权重wi的中值点；–ys是y方向的对所有权重wi的中值点；11||||(2.8)nniisiisiizwxxwyy23例2.1报刊亭选址•一个报刊连锁公司想在一个地区开设一个新的报刊零售点，主要的服务对象是附近的5个小区的居民。图2-6笛卡尔坐标系表示了这些小区的坐标。表2-1显示各点的坐标值和权重（根据各小区的人数确定）。要求确定报刊亭的位置，使得每个月顾客到报刊亭所行走的距离总和最小。2425表2-1需求点对应的权重需求点x坐标y坐标权重wi13112527343342435156112niiWw26表2｜2x轴方向的中值计算需求点x坐标从左到右516=6426+3=9136+3+1=103425从右到左257=7347+3=10134251iw27表2｜3y轴方向的中值计算需求点y坐标从上到下556=6446+3=9336+3+3=122211从上到下111=1221+7=8331＋7＋3＝114455iw28表2-4位置A、B间的加权距离比较位置A(3,3)位置B(4,3)需求点距离权重总和需求点距离权重总和12121313237212271431333030423643395462455630565629•最优解是点(3,3)到点(4,3)间的线段上任意点•讨论–经过10年后，在该地区又增加了2个小区，分别位于(3,7)和(1,6)，它们的人口权重wi分别是2，5。现在需要搬家，试确定新的最佳位置302.5.1.2精确重心法1/2221min()()(2.10)niisisizwxxyy1111(2-11)(2-12)niiiissniiisniiiissniiiswxdxwdwydywd311/222()()isisisdxxyy(1)(1)(1)1/222()()iiiisisisdxxyy32(1)(1)(1)(1)1111(2-11)(2-12)iiiiniiiissiniiisniiiissiniiiswxdxwdwydywd33•迭代终止规则–N步之后停止–迭代结果变化小于给定值之后(1)(1)limitlimit||(2-15)||(2-16)iiiissssssssxxxxyyyy34表2-5精确重心法计算•使用式2-13，2-14，带入初值(3,3)得到（3.26,3.20）。使用matlab编程，可以求得最优点是(3.9273,2.9793)。需求点(i)12345位置(xi,yi)(3,1)(5,2)(4,3)(2,4)(1,5)权重(wi)17336(dis(i-1))22.2411.412.82wi/dis(i-1)0.53.1332.132.13wixi/dis(i-1),wiyi/dis(i-1)1.5,0.515.63,6.2512,94.25,8.52.13,10.63352.5.2离散点选址模型•离散点选址模型是指在有限的候选位置里面，选取最为合适的一个或者一组位置为最优方案的模型。•分类：P集合覆盖模型覆盖模型最大覆盖模型中值模型362.5.2.1覆盖模型37382.5.2.1.1集合覆盖模型•用尽可能少的设施覆盖所有需求点–设施候选停放点为所有的需求点–N={1,2,…,n}，所有的需求点；–di：第i个节点的需求量；–Cj：设施节点j的容量；–A(j)：设施节点j所覆盖的需求点集合；–B(i)={j|iA(j)}：可以覆盖节点i的设施的集合；–yij：节点i需求中被分配给j点设施的百分比。1,0,jjxj节点有设施节点没有设施39模型()()min(2-17)..1,(2-18),(2-19){0,1},(2-20)0,jjNijjBiiijjjiAjjijxstyiNdyCxjNxiNy(2-21)jN40例2•卫生部门计划在某地区的9个村增加一系列诊所（图2-10）。它希望每个村周围30km范围内至少有一个诊所，而且不考虑诊所能力的限制。除了第6个村子外，其它的村子都可以建诊所。卫生部门要确定建多少诊所，分别建在哪里。4142•解题步骤–找到每个村子建立卫生所的覆盖集A(j)（如表2-6所示）；–在所有的A(j)中去掉一些被包含的子集；–在剩下的集合中确定最佳位置；43表2-6候选位置的服务范围村编号A(j)B(i)11,2,3,41,2,3,421,2,31,2,331,2,3,4,51,2,3,4,541,3,4,5,6,71,3,4,5,753,4,5,63,4,564,5,7,874,6,7,8,94,7,8,986,7,8,97,8,998,98,9A(j):每个村子可以提供的服务B（i）可以给该村提供服务的村子44•讨论–试对本例建立一个数学模型–表2-6中的B(i)有何作用？452.5.2.1.2最大覆盖模型•服务设施有限的前提下，最大化提供服务–设施候选停放点为所有的需求点–N={1,2,…,n}，所有的需求点；–di：第i个节点的需求量；–Cj：设施节点j的容量；–A(j)：设施节点j所覆盖的需求点集合；–B(i)={j|iA(j)}：可以覆盖节点i的设施的集合；–p：设施数目46–yij：节点i需求中被分配给j点设施的百分比。1,0,jjxj节点有设施节点没有设施47()()()max(2-22)..1,(2-23),(2-24)(2-25){0,1},iijjNiAjijjBiiijjjiAjjjNjdystyiNdyCxjNxpx(2-26)0,(2-27)ijiNyjN48•以例2的数据为例，假设只允许建立两个卫生所，怎样选址使得覆盖的村庄最多？•用贪婪算法求解–首先得到处理过的候选集A＝{3,4,8}，并且令S表示最后选定的位置，初始化S={Ф}；–第二步：找到一个点使得该点覆盖的村最多；然后从A中删除该点，在S中增加该点，删除该点所覆盖的村庄；重复第二步直到A为空集或者S中的个数满足了约束。49贪婪算法求解过程•A=｛3，4，8｝，S＝｛Ф｝村编号A(j)需要覆盖的村庄31,2,3,4,51,2,3,4,5,6,7,8,941,3,4,5,6,786,7,8,9初始化50•A=｛3，8｝，S＝｛4｝村编号A(j)需要覆盖的村庄31,2,3,4,52,8,986,7,8,9第一次循环51•A=｛3｝，S＝｛4，8｝•结束，村庄2未被满足村编号A(j)需要覆盖的村庄31,2,3,4,52第二次循环52•讨论–本例的贪婪算法显然没有达到最优值,算法有问题么?53一个复杂的例子•基于禁忌搜的救护车选址问题542.5.2.2P—中值模型•已知:–需求点的位置和需求量–设施数量p–候选位置•求:–p个合适的位置，使得设施和需求点间的运费最小。5556约定N={1,2,…,n}，所有的需求点；M={1,2,…,m}，所有的设施候选地点；di：第i个节点的需求量；cij：从点i到点j的单位运输费用；p：设施数目1,0,jjMxjM在节点建立设施不在节点建立设施1,0,ijiNjMy需求点由节点的设施提供服务其他情况57()min(2-28)..1,(2-29)(2-30),(2-31){0,1},iijijiNjMijjBijjMijjjdcystyiNxpyxiNjNx(2-32){0,1},(2-33)ijiNyjN58•思考–yij为什么是0-1变量，而不是像覆盖模型中那样取0～1之间的数？–如果设施的能力有限值，模型如何改进？–如果一个客户可以被多个设施服务，模型如何改进？59例3•某饮料公司在某新地区经过一段时间广告宣传之后，得到了8个超市的订单，由于该地区离总部教远，该饮料公司决定在该地区建立2个仓库，经过一段时间调查后，确定了4个候选位置。从这些位置到各超市的单位运输成本、各超市的需求都已确定，如图2-12所示。60616263646566•贪婪算法