第三章选址模型及应用

第三章选址模型及应用第1页，共62页，2023年，2月20日，星期三3.1选址的意义选址在整个物流系统中占有非常重要的地位，主要属于物流管理战略层的研究问题。选址决策就是要确定所要分配的设施的数量、位置以及分配方案。这些设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售商网点等。第2页，共62页，2023年，2月20日，星期三3.1选址的意义设施数量与客户响应时间快速响应客户需求是竞争因素之一快速响应客户需求与节点设施设置的数量有关期望的响应时间设施数量第3页，共62页，2023年，2月20日，星期三3.1选址的意义选址与库存、运输成本存在密切联系，选址就是要在设施数量和成本中求得最佳。设施数量库存成本设施数量运输成本设施数量设施成本设施数量总成本响应时间第4页，共62页，2023年，2月20日，星期三3.1选址的意义就供应链系统而言，核心企业的选址决策会影响所有供应商物流系统的选址决策。第5页，共62页，2023年，2月20日，星期三3.2选址的影响因素选址决策影响因素大致可分为外部因素及内部因素两大类选址决策影响因素外部因素宏观政治因素政权、法制、政策等宏观经济因素税收、关税、汇率等基础设施交通设施、通信设施自然环境与社会环境如劳动力成本与质量市场环境竞争对手、供应商、客户等内部因素企业发展战略如制造业企业选择劳动密集/技术密集发展战略；如商业服务业选择连锁便利店/超市的发展战略第6页，共62页，2023年，2月20日，星期三3.2选址的影响因素选址决策包括地区选择和地点选择，二者需要考虑的因素有所不同。地区选择要考虑的是宏观因素；地点选择要考虑的是微观因素。选址决策影响因素地区选择（1）政策导向（2）市场情况（3）社会环境（4）资源条件（5）基础设施和配套供应（6）上下游企业关系地点选择（1）区域规划（2）地形地貌（3）面积与外形（4）外部衔接（5）地质条件（6）气象及辐射（7）地下水与洪水（8）地震第7页，共62页，2023年，2月20日，星期三3.2选址的影响因素按照影响因素的性质的不同，可把影响因素分成两大类：即成本因素和非成本因素。还可以根据因素对设施选址的重要性，分为：关键因素、重要因素、次要因素等。第8页，共62页，2023年，2月20日，星期三3.3选址模型的分类在建立一个选址模型之前，我们需要清楚以下问题：（1）选址的对象是什么？（2）选址的目标区域是怎样的？（3）选址目标和成本函数是什么？（4）有什么样的一些约束？体选址面选址线选址高维选址单一设施选址多设施选址连续选址网络选址离散选址可行性/最优性Minisum/MinimaxMaximin高次目标函数确定性与随机性静态与动态有能力约束无能力约束有不可行区域无不可行区域设施维度及数量选址目标区域选址成本选址约束固定权重/可变权重第9页，共62页，2023年，2月20日，星期三3.4选址问题中的距离计算在选址问题模型中，最基本的一个参数是各个节点之间的距离。有两种方法计算节点之间的距离：直线距离，也叫欧几里德距离（EuclideanMetric）；折线距离（RectilinearMetric），也叫城市距离（MetropolitanMetric）。第10页，共62页，2023年，2月20日，星期三3.5选址模型简单模型：在一条直线上（街道）选择一个有效位置（商店），即一种设施，让这条街道上的所有顾客到达商店的平均距离最短。假设街道上顾客分布的概率（密度）为则目标函数为：简单模型——大街上第i个位置到所选地址的距离——选择投资的位置第11页，共62页，2023年，2月20日，星期三3.5选址模型定积分求导：定积分求导（1）其中，被假设为在时间区间中具有连续导数。莱布尼兹法则关于一个变量（它既不是积分变量，也不进入积分上下限）求导定积分，可以简单地穿过积分符号直接关于该变量求导被积函数。第12页，共62页，2023年，2月20日，星期三3.5选址模型定积分求导：定积分求导（2）有微商公式：定积分关于积分上限b的导数等于被积函数在t=b处的取值；定积分关于积分下限a的导数等于被积函数在t=a处的取值的负数；第13页，共62页，2023年，2月20日，星期三3.5选址模型定积分求导：定积分求导（3）有微商公式：右边第一项来自对被积函数中变量的求导，右边第二项来自对积分上限的求导，而且基于下列链式求导：其中x不仅进入被积函数，而且影响积分上限对以下函数求导第14页，共62页，2023年，2月20日，星期三3.5选址模型对目标函数求导，令一阶导数为零，得：简单模型求解结果表明，所开设的新店面需要设置在权重的中点，即两面的权重都是50%。第15页，共62页，2023年，2月20日，星期三3.5选址模型连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。交叉中值模型（CrossMedian）通过交叉中值的方法对单一设施平面选址问题的加权城市距离进行最小化。其目标函数为：交叉中值模型——第i个点对应的权重，例如需求；——需求点的总数目——第i个需求点的坐标；——服务设施的坐标；第16页，共62页，2023年，2月20日，星期三3.5选址模型交叉中值模型的目标函数可以用两个互不相干的部分来表达：交叉中值模型是x方向所有权重的中值点；是y方向所有权重的中值点；惟一值某一范围惟一值点线段某一范围线段区域第17页，共62页，2023年，2月20日，星期三3.5选址模型例1报刊亭选址一个报刊连锁公司想在一个地区开设一个新的报刊亭零售点，主要的服务对象是附近的5个住宿小区的居民，他们是新开设报刊亭零售点的主要顾客源。下图坐标系中确切地表达了这些需求点的位置，下表为各个需求点对应的权重。权重代表每个月潜在的顾客需求总量，基本可以用小区中总的居民数量来近似。经理希望通过这些信息来确定一个合适的报刊零售点的位置，要求每个月顾客到报刊零售点所行走的距离总和最小。交叉中值模型需求点x坐标y坐标权重13112527343342435156第18页，共62页，2023年，2月20日，星期三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第19页，共62页，2023年，2月20日，星期三3.5选址模型选址结果：交叉中值模型位置A（3，3）位置B（4，3）需求点距离权重总和需求点距离权重总和121213132372122714313330304236433954624556305656第20页，共62页，2023年，2月20日，星期三3.5选址模型连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。精确重心法（ExactGravity）交叉中值模型使用城市距离，适合小范围城市内选址问题；精确重心法使用直线距离，适合大范围城市间选址问题，目标函数为，精确重心法——与第i个点对应的权重，例如需求；——需求点的总数目——第i个需求点的坐标；——服务设施的坐标；第21页，共62页，2023年，2月20日，星期三3.5选址模型精确重心法目标函数为双变量系统，分别对xs和ys求偏导，并令导数为零，求得隐含最优解的等式，精确重心法第22页，共62页，2023年，2月20日，星期三3.5选址模型迭代法：利用已知的点（xs(k-1),ys(k-1)）,求出dis(k-1)，再求出新的点（xs(k),ys(k)）,依次求解，直到求得符合要求的解。精确重心法迭代公式：(1)其中：(2)第23页，共62页，2023年，2月20日，星期三3.5选址模型精确重心法迭代法步骤：（1）初始值的确定；（2）迭代；（3）中止准则；初始值的确定：a、任意选择一个点作为初始值；b、按照简化公式选择初始值；第24页，共62页，2023年，2月20日，星期三3.5选址模型中止准则的确定：a、直接设置一个确定的迭代次数N；b、判断两次迭代的差值是否小于设定的阈值；C、判断总费用是否减小或两次迭代差值小于设定值精确重心法第25页，共62页，2023年，2月20日，星期三3.5选址模型精确重心法应用于报刊亭选址问题：精确重心法第一次迭代初始位置(x0,y0)33需求点12345(xi,yi)3152432415权重wi17336距离dis(0)22.23606797711.4142135622.828427125wixi/dis(0)；wiyi/dis(0)1.50.515.652486.260991294.24268.48522.121310.606wi/dis(0)；wi/dis(0)0.531213203442.121320344迭代位置(x1,y1)3.2664391713.205411382中止判断（Z1）41.86567928第26页，共62页，2023年，2月20日，星期三3.5选址模型精确重心法应用于报刊亭选址问题：精确重心法第二次迭代初始位置(x1,y1)3.2664391713.205411382需求点12345(xi,yi)3152432415权重wi17336距离dis(1)2.2214475452.1114567830.761777741.4950716532.890898619wixi/dis(1)；wiyi/dis(1)1.35040.450116.5766.630415.75211.8144.01318.02632.075410.37wi/dis(1)；wi/dis(1)0.4501569273.3152466373.9381565542.0065927912.075479216迭代位置(x2,y2)3.3742776423.16477612中止判断（Z2）41.11758492第27页，共62页，2023年，2月20日，星期三3.5选址模型精确重心法应用于报刊亭选址问题：精确重心法第三次迭代初始位置(x2,y2)3.3742776423.16477612需求点12345(xi,yi)3152432415权重wi17336距离dis(2)2.1968931251.9999191470.6470545871.6081784633.000873375wixi/dis(2)；wiyi/dis(2)1.36550.455117.5007.000218.54513.9093.73097.46181.99949.997wi/dis(2)；wi/dis(2)0.4551882793.5001414994.6363939931.8654646041.999417919迭代位置(x3,y3)3.4633988113.116707741中止判断（Z3）40.96726655第28页，共62页，2023年，2月20日，星期三3.5选址模型中止准则的使用：若（1）N=2；（2）坐标值阈值为0.2；坐标值变化幅度小于4%；（3）总费用阈值为0.2；总费用相对变化幅度小于1%。精确重心法总费用2.64%，-1.52%3.30%，-1.27%8.88%，6.85%相对差值40.843840.967341.117641.86570.0891，-0.04810.1078，-0.04060.2664，0.2054绝对差值坐标点迭代差值总费用迭代差值坐标点迭代次数3.11673.16483.2054y3.46343.37433.2664x0.12350.15030.7481绝对差值1.79%10.37%20.30%3相对差值第29页，共62页，2023年，2月20日，星期三3.5选址模型补充例题：有四个零售点，其坐标、物资需求量及运输费用如下表所示，请用重心法为配送中心选址。零售点物资需求量qi运输费用ri坐标xiyi1252223511332.5510841549精确重心法第一步，按照简化公式确定初始值，第30页，共62页，2023年，2月20日，星期三3.5选址模型

精确重心法第二步，以点（7.8，4.9）作为配送中心，计算距离与总费用，第三步，计算改善的配送中心选址，第31页，共62页，2023年，2月20日，星期三3.5选址模型

精确重心法第四步，以点（8.6，5.1）作为配送中心，计算距离与总费用，第五步，计算改善的配送中心选址，第32页，共62页，2023年，2月20日，星期三3.5选址模型

精确重心法第六步，以点（9.0，5.2）作为配送中心，计算距离与总费用，此时，Z(2)=Z(1)=191，虽然结果是取小数而得，但二者已经非常接近，所以可认为最佳点为（9.0，5.2）或（8.6，5.1）。第33页，共62页，2023年，2月20日，星期三3.5选址模型交叉中值模型与精确重心法交叉中值模型精确重心法城市距离（折线距离）；适合于小范围的城市内选址问题；目标使对加权的城市距离最小化；属于单一设施连续点选址问题。欧几米德距离（直线距离）；适合于大范围城市间选址问题；目标是使加权的直线距离最小化；属于单一设施的连续点选址问题。第34页，共62页，2023年，2月20日，星期三3.5选址模型离散点选址问题指的是在有限的候选位置里面，选取最为合适的一个或一组位置为最优方案，相应的模型称为离散点选址模型。离散点选址模型与连续点选址模型的区别在于：它所拥有的候选方案只有有限个元素。对于离散点选址问题，目前主要有两种模型，分别是覆盖模型和P-中值模型。覆盖模型常用的又有集合覆盖模型和最大覆盖模型两种。覆盖模型（Covering）

覆盖模型，是对于需求已知的一些需求点，确定一组服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适的位置。该模型适用于商业物流系统，如零售点的选择问题、加油站的选址、配送中心的选址问题等。离散点选址问题第35页，共62页，2023年，2月20日，星期三3.5选址模型根据解决问题的方法的不同，覆盖模型可以分为两种不同的主要模型：①集合覆盖模型，用最小数量的设施去覆盖所有的需求点；②最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求或需求点。覆盖模型第36页，共62页，2023年，2月20日，星期三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点建立设施，i∈Mxij—节点j需求中被分配给设施点i的部分。第37页，共62页，2023年，2月20日，星期三3.5选址模型集合覆盖模型启发式算法：第一步：初始化。令所有的xj＝0，yi＝0，（已分配的需求），并确定集合A(i)和集合B(j)；第二步：选择下一个设施点。在M中选择yi＝0，且A(i)的规模为最大的点i’为设施点，即，令，并在M集合中剔除节点i’，即第三步：确定节点i’的覆盖范围。将A(i’)中的元素按B(j)的规模从小到大的顺序指派给i’，直至i’的容量为Ci’＝0或A(i’)为空。其中对于j∈A(i’)且，xj<Dj，将j支配给i’的方法为：若，则令xi’j=Dj－xj，Ci’=Ci’-(Dj-xj)，xj＝1，在A(i’)和N中剔除需求点j。若，则令第四步：若N或M为空，停止；否则，更新集合A(i)和集合B(j)，转第二步。集合覆盖模型启发式算法第38页，共62页，2023年，2月20日，星期三3.5选址模型例：在某区域需规划建设若干个农贸市场为将来该区9个主要居民点提供服务，除第6居民点外，其他各点均有建设市场的条件，如下图所示。已知市场的最大服务直径为3km，为保护该区域的环境，希望尽可能少地建造农贸市场。问应如何规划？解：N＝{1,2,3,4,5,6,7,8,9}，M＝{1,2,3,4,5,7,8,9}，由图两点间的最短距离，根据最大服务半径为3km的约束及第6居民点不适合建市场的要求，可确定集合A(j)和B(i)。如下表所示，值得指出的是本问题没有需求量和容量，故无需考虑服务能力约束式。

集合覆盖模型启发式算法1○7○8○4○9○2○5○6○3○22434143233211图小区居民点位置图3第39页，共62页，2023年，2月20日，星期三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为最大，故首先选取i’＝4。由于无容量约束故依次指派5,7,1,6,3,4点归节点4服务。第三步，更新。此时，N＝{2,8,9},M＝{1,2,3,5,7,8,9},更新集合A(i)和集合B(j)后如下表所示。第40页，共62页，2023年，2月20日，星期三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为最大，故首先选取i’＝8，并且8，9两点归节点8服务。第五步，更新。此时，N＝{2},M＝{1,2,3,5,7,9},更新集合A(i)和集合B(j)后如下表所示。第41页，共62页，2023年，2月20日，星期三3.5选址模型

集合覆盖模型启发式算法第六步，确定一个设施点。因为A(2)＝{2}，|A(2)|＝1为最大，故首先选取i’＝2，并且2点归节点2服务。第七步，更新。此时，N＝{},M＝{1,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第42页，共62页，2023年，2月20日，星期三3.5选址模型集合覆盖模型整数规划yi为0-1变量，yi=1,在i点建立设施；yi=0,不在i点建立设施，i∈Mxij—节点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第43页，共62页，2023年，2月20日，星期三3.5选址模型

集合覆盖模型整数规划整数规划模型：第44页，共62页，2023年，2月20日，星期三3.5选址模型

集合覆盖模型整数规划Lingo软件求解：第45页，共62页，2023年，2月20日，星期三3.5选址模型最大覆盖模型已知若干个需求点（客户）的位置和需求量，需从一组候选的地点中选择p个位置作为物流设施网点（如配送中心、仓库等），使得尽可能多地满足需求点的服务。最大覆盖模型的目标是对有限的服务网点进行选址，为尽可能多的对象提供服务，如下图所示。最大覆盖模型□□□□□□□□□○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○最大覆盖模型第46页，共62页，2023年，2月20日，星期三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点建立设施，j∈Myij—节点i需求中被分配给设施点j的部分(比例)。第47页，共62页，2023年，2月20日，星期三3.5选址模型集合覆盖模型与最大覆盖模型数学模型比较最大覆盖模型集合覆盖模型最大覆盖模型第48页，共62页，2023年，2月20日，星期三3.5选址模型

最大覆盖模型整数规划第49页，共62页，2023年，2月20日，星期三3.5选址模型

集合覆盖模型整数规划Lingo软件求解：第50页，共62页，2023年，2月20日，星期三3.5选址模型P—中值模型P—中值模型是指在一个给定数量和位置的需求集合和一个给数量和候选位置的设施集合的前提下，分别为P个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在设施与需求点之间的运输费用最低。如下图所示。P—中值模型第51页，共62页，2023年，2月20日，星期三3.5选址模型P—中值数学模型为：P—中值模型N－区域中的需求点（客户）集合，N={1,2,…,n}；M－区域中可建设设施的候选点集合，M={1,2,…,m}；di－第i个需求点的需求量；cij－从需求点i到设施点j的单位运输费用；p－允许建设的设施的数目，p<m；xj为0-1变量，xj=1,在j点建立设施；xj=0,不在j点建立设施，j∈Myij为0-1变量，yij=1,表示需求点i由节点j提供服务；yij=0,表示需求点i不由节点j提供服务；。第52页，共62页，2023年，2月20日，星期三3.5选址模型例3：某饲料公司的仓库选址问题某饲料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建2个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地调查之后，已有4个候选地址，如下图所示；各候选地址到不同超市的运输成本、各个超市的需求量如下表所示。P—中值模型123456781234ijdi1234cij1412206100221025105033416141204659280518127320061424970720302116082412622100第53页，共62页，2023年，2月20日，星期三3.5选址模型P—中值贪婪取走启发式算法（GreedyDroppingHeuristicAlgorithm）:P—中值模型贪婪取走启发式算法第一步，初始化，令循环数k=m，将所有m个候选位置都选中，然后将每个需求点分配给离其最近的一个侯选位置。123456781234400100360600160140120600设施点费用1860214037204760总费用2480第54页，共62页，2023年，2月20日，星期三3.5选址模型

P—中值模型贪婪取走启发式算法第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客户重新指派后，总费用增加量最小，然后令k=k-1。12345678234600160140120600需求点移走位置1后总费用增加量1+2002+4003+120总费用增加量+720600500480第55页，共62页，2023年，2月20日，星期三3.5选址模型

P—中值模型贪婪取走启发式算法12345678134400100360600160280120600需求点移走位置2后总费用增加量6+140总费用增加量+140移走位置2：第56页，共62页，2023年，2月20日，星期三3.5选址模型

P—中值模型贪婪取走启发式算法需求点移走位置2后总费用增加量7+5408+600总费用增加量+1140移走位置3：123456781244001003606001601406601200第57页，共62页，2023年，2月20日，星期三3.5选址模型

P—中值模型贪婪取走启发式算法需求点移走位置2后总费用增加量4