《第15章选址问题课件.ppt》由会员分享，可在线阅读，更多相关《第15章选址问题课件.ppt（42页珍藏版）》请在三一办公上搜索。
1、第15章 选址问题,15.1 概述,选址理论：是关于选址问题模型和算法的理论。 选址在整个物流系统中占有非常重要的地位，主要属于物流管理战略层的研究问题。选址决策就是要确定所要分配的设施的数量、位置以及分配方案。这些设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售网点等。,1、选址问题设计算法和模型时要考虑：（1）被定位的对象具有什么特性（2）目标选址地区的结构特点是什么（3）目标和成本参数是什么（4）其他限制条件是什么,2、选址问题的分类（1）按被定位的对象的空间维数分为：立体选址、平面选址、线选址、点选址。 立体选址：集装箱装箱问题 平面选址：工厂或货运站的设施布局 线选
2、址：巷道内划出拣选带 点选址：制造或配送系统的选址,（2）按照目标区域的结构来划分：连续选址、网格选址、网络选址和离散点选址。连续选址：候选区域是一个平面或球面，任意点都可作为选址点。网格选址：目标区域被划分成多个单元，要求为对象分配其中若干单元。网络选址：目标选址区是一个网络，即节点和边的集合。离散点选址：候选点数量有限且较少。,（3）从目标函数来分类：中位问题、中心问题，反中心问题 中位问题：总成本最小为目标。 中心问题：服务于每个客户的最大成本最小化为目标。 反中心问题：服务于每个客户的最小成本最大化为目标。,（4）根据问题中的参数是否与解存在关联：纯选址问题和选址分配问题。 纯选址问题
3、：其中的参数或结构不依赖新建设施而改变，是事先确定的。 选址分配问题：其中的参数或结构依赖新建设施而改变。（5）根据问题中的参数是否随时间而改变，分为静态选址和动态选址。（6）根据参数是确定性的还是随机性的，分为确定性选址问题和随机选址问题。（7）根据候选点是否存在服务能力约束，可以分为无限能力选址和有限能力选址。,15.2 连续点选址问题,连续点选址问题中，点到点的距离计算标准有两种。设平面上的点坐标分别为（xi,yi），（xj,yj） 直线距离dijE： 折线距离dijR ：,1、直线距离准则下的选址,用直线距离准则进行选址，则目标函数为：,2、折线距离准则下的选址,重心法，用于以总和最小
4、为目标函数的单一设施选址问题。此时目标函数为：,可见，原问题可以被拆成两个独立的问题，即：,例1：报刊亭选址。有一个报刊连锁公司想在一个地区设一个新的报刊零售点，主要的服务对象为附近的五个居民小区。表中数字分别为各个小区的x坐标和y坐标，以及需求量。,用坐标图来表示五个小区的位置,解：先求x坐标的解（1）按坐标从小到大的顺序排列需求点（2）计算总权重（需求量）W，计算累积权重（需求量）（3）找满足累积需求量,69101320,由计算结果可知计算编号s3,若 ，则选址的x坐标即为对应的需求点s的x坐标。若 ，则选址的x坐标即为对应原需求点s和需求点s+1的x坐标范围内任一点。 所以，本题选址点的
5、x坐标是编号为3和编号为4的需求点的x坐标之间的任意值，即为3，4之间的任意值。 再求解y坐标的解。,（1）按坐标从小到大的顺序排列需求点（2）计算总权重（需求量）W，计算累积权重（需求量）,18111420,（3）y坐标为编号为3的需求点对应的y坐标，即y坐标为3。,x坐标为3，4之间的任意值，y坐标为3，说明新的报刊零售点的位置可以是PQ线段上的任意一点。,15.3 离散点选址问题,离散点选址指的是在有限的候选位置里，选取最为合适的一个或者一组位置为最优方案，相应的模型称为离散点选址模型。 离散点选址问题，目前主要有两种模型可供选择，分别是覆盖模型和k中位模型。其中覆盖模型常用的是集合覆盖
6、模型和最大覆盖模型。 覆盖模型，是对于需求已知的一些需求点，如何确定一组服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适位置。,覆盖模型适用于商业物流系统，如零售点的选址，加油站的选址、配送中心的选址等，公用事业系统，如急救中心、消防中心等，以及计算机与通信系统。 集合覆盖模型：用最小数量的设施去覆盖所有的需求点。,最大覆盖模型：在给定数量的设施下，覆盖尽可能多的需求点。,集合覆盖模型：定义：xi需求点 cj覆盖成本 sj覆盖集合子集，取1时表示该子集启用，取0时表示该子集未启用。 A覆盖关系矩阵 aij覆盖关系矩阵中的元素，取1时表示集合sj可以把需求点xi覆盖
7、进去，取0时表示集合sj不可以把需求点xi覆盖进去。,数学模型：目标函数：,约束条件：,aij和sj为0，1变量。,矩阵简化法求解第一步：若A中行i只有一个非0元素，例如aij，则记J=j，即sj在最优解中。对A删除列j以及该列中aij1的行。第二步：若A中存在行i和i，若对所有列有aijaij，则删除行i。第三步：若A中存在列j和j，若对所有行有aijaij，则删除列j。第四步：反复进行前三步，直至矩阵A中不再包含任何元素，或不存在行或列可以删除。,例2：有7个航线需要安排乘务员，有五组乘务组可选，请尽量安排最小的乘务组，且保证每条航线都至少有一个乘务组服务。,解：（1）在矩阵A中找出行中只
8、有一个非0元素的行。,记J=s3,（2）删除行x3，因为x3包含x2。,（3）删除列s5，因为s1包含s5。删除列s2，因为s4包含s2。,（4）记J=s3,s1,（5）记J=s3,s1,s4,例3：某物流企业要建设一些配送中心，为九个城市的客户服务，配送中心最远的服务距离为300km，即任何一个城市的周边300km处至少有一个配送中心。不考虑配送中心的服务能力，物流企业要确定需要多少个配送中心以及这些配送中心的位置。其中第6个城市由于缺乏建立配送中心的必要条件，不可以建立配送中心。图表示各个城市的相对位置和距离。,解：第一步是要建立覆盖矩阵。,1,1,1,0,1,0000,1,0,00000
9、,1,1,1,1,0000,1,0,1,1,1,1,00,00,1,1,1,000,000,1,0,1,1,0,00000,1,1,1,0000000,1,第二步进行计算。（1）找出行中只有一个非0元素的行。（2）简化矩阵,简化矩阵后得,记J=s3,记J=s3 ，s8,k中位模型： 设在某一地区要建立若干的配送中心，给其客户配送商品，配送中心有N个候选地址。现要求设立的配送中心到所有客户的总运输成本最小。,例4：某公司准备在8个客户的附近建立2个仓库，用最低的运输成本来满足客户的需求。现计划从4个候选地址选择2个地方建立仓库。从候选地址到不同的仓库的运输成本、各个超市的需求量都已确定，如表所示
10、：,用贪婪取走启发式算法：第一步：初始化，令循环参数k=m，将所有的m个候选位置全选中，然后将每个客户指派给离其距离最近的一个候选位置。,6,总成本费用为：2480,第二步：选择并取走一个位置点，满足以下条件：取走它并将客户重新指派后，总费用增加量最小，然后令k=k-1。第三步：重复第二步，直到k=2。,取走1后，总费用为3200，增加720。,取走2后，总费用为2620，增加140。,取走3后，总费用为3620，增加1140。,取走4后，总费用为3520，增加1040。,此时应取走2，总费用为2620，如图所示：,取走1后，总费用为4540，增加1920。,取走3后，总费用为5100，增加2490。,取走4后，总费用为3740，增加1120。,此时应取走4，最优解即为选择1和3两个候选点。,作业：P459 1，2,
