第15章选址问题课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第15章 选址问题,第15章 选址问题,1,15.1 概述,选址理论：是关于选址问题模型和算法的理论。,选址在整个物流系统中占有非常重要的地位，主要属于物流管理战略层的研究问题。选址决策就是要确定所要分配的设施的数量、位置以及分配方案。这些设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售网点等。,15.1 概述 选址理论：是关于选址问题模型,2,1、选址问题设计算法和模型时要考虑：,（1）被定位的对象具有什么特性,（2）目标选址地区的结构特点是什么,（3）目标和成本参数是什么,（4）其他限制条件是什么,1、选址问题设计算法和模型时要考虑：,3,2、选址问题的分类,（1）按被定位的对象的空间维数分为：立体选址、平面选址、线选址、点选址。,立体选址：集装箱装箱问题,平面选址：工厂或货运站的设施布局,线选址：巷道内划出拣选带,点选址：制造或配送系统的选址,2、选址问题的分类,4,（2）按照目标区域的结构来划分：连续选址、网格选址、网络选址和离散点选址。,连续选址：候选区域是一个平面或球面，任意点都可作为选址点。,网格选址：目标区域被划分成多个单元，要求为对象分配其中若干单元。,网络选址：目标选址区是一个网络，即节点和边的集合。,离散点选址：候选点数量有限且较少。,（2）按照目标区域的结构来划分：连续选址、网格选址、网络选址,5,（3）从目标函数来分类：中位问题、中心问题，反中心问题,中位问题：总成本最小为目标。,中心问题：服务于每个客户的最大成本最小化为目标。,反中心问题：服务于每个客户的最小成本最大化为目标。,（3）从目标函数来分类：中位问题、中心问题，反中心问题,6,0,5,6,7,中位点,中心点3.5,反中心点2.5,0567中位点中心点3.5反中心点2.5,7,（4）根据问题中的参数是否与解存在关联：纯选址问题和选址分配问题。,纯选址问题：其中的参数或结构不依赖新建设施而改变，是事先确定的。,选址分配问题：其中的参数或结构依赖新建设施而改变。,（5）根据问题中的参数是否随时间而改变，分为静态选址和动态选址。,（6）根据参数是确定性的还是随机性的，分为确定性选址问题和随机选址问题。,（7）根据候选点是否存在服务能力约束，可以分为无限能力选址和有限能力选址。,（4）根据问题中的参数是否与解存在关联：纯选址问题和选址分配,8,15.2 连续点选址问题,连续点选址问题中，点到点的距离计算标准有两种。设平面上的点坐标分别为（x,i,y,i,），（x,j,y,j,）,直线距离d,ij,E,：,折线距离d,ij,R,：,y,x,i,j,15.2 连续点选址问题 连续点选址问题中，点,9,1、直线距离准则下的选址,用直线距离准则进行选址，则目标函数为：,1、直线距离准则下的选址 用直线距离准则进行选,10,2、折线距离准则下的选址,重心法，用于以总和最小为目标函数的单一设施选址问题。此时目标函数为：,2、折线距离准则下的选址 重心法，用于以总和最,11,可见，原问题可以被拆成两个独立的问题，即：,可见，原问题可以被拆成两个独立的问题，即：,12,例1：报刊亭选址。有一个报刊连锁公司想在一个地区设一个新的报刊零售点，主要的服务对象为附近的五个居民小区。表中数字分别为各个小区的x坐标和y坐标，以及需求量。,小区,x坐标,y坐标,需求量w,i,A,3,1,1,B,5,2,7,C,4,3,3,D,2,4,3,E,1,5,6,例1：报刊亭选址。有一个报刊连锁公司想在一个地区设一个新的报,13,用坐标图来表示五个小区的位置,小区,x坐标,y坐标,需求量w,i,A,3,1,1,B,5,2,7,C,4,3,3,D,2,4,3,E,1,5,6,x,y,0,1 2 3 4 5,5,4,3,2,1,1,2,3,4,5,用坐标图来表示五个小区的位置小区x坐标y坐标需求量wiA31,14,解：先求x坐标的解,（1）按坐标从小到大的顺序排列需求点,（2）计算总权重（需求量）W，计算累积权重（需求量）,（3）找满足累积需求量,计算编号,小区名称,x坐标,累积需求量,1,E,1,2,D,2,3,A,3,4,C,4,5,B,5,6,9,10,13,20,由计算结果可知计算编号s3,解：先求x坐标的解计算编号小区名称x坐标累积需求量1E12D,15,若 ，则选址的x坐标即为对应的需求点s,的x坐标。,若 ，则选址的x坐标即为对应原需求点s,和需求点s+1的x坐标范围内任一点。,所以，本题选址点的x坐标是编号为3和编号为4的需求点的x坐标之间的任意值，即为3，4之间的任意值。,再求解y坐标的解。,若 ，则选址的,16,（1）按坐标从小到大的顺序排列需求点,（2）计算总权重（需求量）W，计算累积权重（需求量）,计算编号,小区名称,y坐标,累积需求量,1,A,1,2,B,2,3,C,3,4,D,4,5,E,5,1,8,11,14,20,（3）y坐标为编号为3的需求点对应的y坐标，即y坐标为3。,（1）按坐标从小到大的顺序排列需求点计算编号小区名称y坐标累,17,x坐标为3，4之间的任意值，,y坐标为3，说明,新的报刊零售点的位置可以是PQ线段上的任意一点。,x,y,0,1 2 3 4 5,5,4,3,2,1,1,2,3,4,5,P,Q,x坐标为3，4之间的任意值，y坐标为3，说明新的报刊零售,18,15.3 离散点选址问题,离散点选址指的是在有限的候选位置里，选取最为合适的一个或者一组位置为最优方案，相应的模型称为离散点选址模型。,离散点选址问题，目前主要有两种模型可供选择，分别是覆盖模型和k中位模型。其中覆盖模型常用的是集合覆盖模型和最大覆盖模型。,覆盖模型，是对于需求已知的一些需求点，如何确定一组服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适位置。,15.3 离散点选址问题 离散点选址指的是在有,19,覆盖模型适用于商业物流系统，如零售点的选址，加油站的选址、配送中心的选址等，公用事业系统，如急救中心、消防中心等，以及计算机与通信系统。,集合覆盖模型：用最小数量的设施去覆盖所有的需求点。,覆盖模型适用于商业物流系统，如零售点的选址，,20,最大覆盖模型：在给定数量的设施下，覆盖尽可能多的需求点。,最大覆盖模型：在给定数量的设施下，覆盖尽可能,21,集合覆盖模型：,定义：x,i,需求点 c,j,覆盖成本,s,j,覆盖集合子集，取1时表示该子集启用，取0时表示该子集未启用。 A覆盖关系矩阵,a,ij,覆盖关系矩阵中的元素，取1时表示集合s,j,可以把需求点x,i,覆盖进去，取0时表示集合s,j,不可以把需求点x,i,覆盖进去。,数学模型：,目标函数：,约束条件：,a,ij,和s,j,为0，1变量。,集合覆盖模型：数学模型：约束条件：aij和sj为0，1变量。,22,矩阵简化法求解,第一步：若A中行i只有一个非0元素，例如a,ij,，则记J=j，即s,j,在最优解中。对A删除列j以及该列中a,ij,1的行。,第二步：若A中存在行i和i，若对所有列有a,ij,a,ij,，则删除行i。,第三步：若A中存在列j和j，若对所有行有,a,ij,a,ij,，则删除列j。,第四步：反复进行前三步，直至矩阵A中不再包含任何元素，或不存在行或列可以删除。,矩阵简化法求解,23,例2：有7个航线需要安排乘务员，有五组乘务组可选，请尽量安排最小的乘务组，且保证每条航线都至少有一个乘务组服务。,乘务组,航线,s,1,s,2,s,3,s,4,s,5,x,1,1,0,1,1,0,x,2,1,0,0,1,0,x,3,1,1,0,1,0,x,4,0,1,1,1,0,x,5,1,0,0,0,1,x,6,0,0,1,0,0,x,7,0,1,0,1,0,例2：有7个航线需要安排乘务员，有五组乘务组可选，请尽量安排,24,解：（1）在矩阵A中找出行中只有一个非0元素的行。,x,1,x,2,x,3,x,4,x,5,x,6,x,7,s,1,s,2,s,3,s,4,s,5,记J=s,3,（2）删除行x,3,，因为x,3,包含x,2,。,（3）删除列s,5,，因为s,1,包含s,5,。删除列s,2,，因为s,4,包含s,2,。,x,2,x,3,x,5,x,7,s,1,s,2,s,4,s,5,x,2,x,5,x,7,s,1,s,4,（4）记J=s,3,s,1,（5）记J=s,3,s,1,s,4,解：（1）在矩阵A中找出行中只有一个非0元素的行。x1s1,25,例3：某物流企业要建设一些配送中心，为九个城市的客户服务，配送中心最远的服务距离为300km，即任何一个城市的周边300km处至少有一个配送中心。不考虑配送中心的服务能力，物流企业要确定需要多少个配送中心以及这些配送中心的位置。其中第6个城市由于缺乏建立配送中心的必要条件，不可以建立配送中心。图表示各个城市的相对位置和距离。,2,400,1,3,4,5,6,7,8,9,200,300,200,100,350,300,250,150,150,300,400,300,200,300,例3：某物流企业要建设一些配送中心，为九个城市的客户服务，配,26,解：第一步是要建立覆盖矩阵。,2,400,1,3,4,5,6,7,8,9,200,300,200,100,350,300,250,150,150,300,400,300,200,300,s1,s2,s3,s4,s5,s7,s8,s9,c1,1,c2,1,c3,1,c4,1,c5,1,c6,c7,1,c8,1,c9,1,1,1,1,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,解：第一步是要建立覆盖矩阵。2400134567892003,27,第二步进行计算。,（1）找出行中只有一个非0元素的行。,（2）简化矩阵,第二步进行计算。,28,简化矩阵后得,记J=s,3,记J=s,3,，s,8,简化矩阵后得记J=s3记J=s3 ，s8,29,k中位模型：,设在某一地区要建立若干的配送中心，给其客户配送商品，配送中心有N个候选地址。现要求设立的配送中心到所有客户的总运输成本最小。,k中位模型：,30,例4：某公司准备在8个客户的附近建立2个仓库，用最低的运输成本来满足客户的需求。现计划从4个候选地址选择2个地方建立仓库。从候选地址到不同的仓库的运输成本、各个超市的需求量都已确定，如表所示：,p1,p2,p3,p4,需求量,x1,4,12,20,6,100,x2,2,10,25,10,50,x3,3,4,16,14,120,x4,6,5,9,2,80,x5,18,12,7,3,200,x6,14,2,4,9,70,x7,20,30,2,11,60,x8,24,12,6,22,100,例4：某公司准备在8个客户的附近建立2个仓库，用最低的运输成,31,用贪婪取走启发式算法：,第一步：初始化，令循环参数k=m，将所有的m个候选位置全选中，然后将每个客户指派给离其距离最近的一个候选位置。,1,2,3,4,5,6,7,8,1,4,2,3,400,100,360,160,600,140,120,600,总成本费用为：2480,用贪婪取走启发式算法：1234567814234001003,32,第二步：选择并取走一个位置点，满足以下条件：取走它并将客户重新指派后，总费用增加量最小，然后令k=k-1。,第三步：重复第二步，直到k=2。,1,2,3,600,500,480,4,5,6,7,8,1,4,2,3,160,600,140,120,600,取走1后，总费用为3200，增加720。,第二步：选择并取走一个位置点，满足以下条件：取走它并将客户重,33,取走2后，总费用为2620，增加140。,6,280,1,2,3,4,5,7,8,1,4,2,3,400,100,360,160,600,120,600,取走2后，总费用为2620，增加140。6280123457,34,取走3后，总费用为3620，增加1140。,1,2,3,4,5,6,1,4,2,3,400,100,360,160,600,140,7,8,660,1200,取走3后，总费用为3620，增加1140。123456142,35,取走4后，总费用为3520，增加1040。,4,5,400,1400,7,8,1,2,3,6,1,4,2,3,400,100,360,140,120,600,取走4后，总费用为3520，增加1040。454001400,36,此时应取走2，总费用为2620，如图所示：,6,280,1,2,3,4,5,7,8,1,4,2,3,400,100,360,160,600,120,600,此时应取走2，总费用为2620，如图所示：628012345,37,6,280,4,5,7,8,1,4,2,3,160,600,120,600,取走1后，总费用为4540，增加1920。,1,2,3,600,500,1680,628045781423160600120600取走1后，总,38,取走3后，总费用为5100，增加2490。,1,2,3,4,5,1,4,2,3,400,100,360,160,600,6,630,7,8,660,2200,取走3后，总费用为5100，增加2490。123451423,39,取走4后，总费用为3740，增加1120。,4,5,480,1400,6,280,1,2,3,7,8,1,4,2,3,400,100,360,120,600,取走4后，总费用为3740，增加1120。454801400,40,此时应取走4，最优解即为选择1和3两个候选点。,4,5,480,1400,6,280,1,2,3,7,8,1,4,2,3,400,100,360,120,600,此时应取走4，最优解即为选择1和3两个候选点。4548014,41,作业：P459 1，2,作业：P459 1，2,42,