第15章选址问题.ppt

第15章 选址问题 15.1 概述 选址理论：是关于选址问题模型和算法的理论。 选址在整个物流系统中占有非常重要的地位，主要属于物流管理战略层的研究问题。选址决策就是要确定所要分配的设施的数量、位置以及分配方案。这些设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售网点等。 1、选址问题设计算法和模型时要考虑： （1）被定位的对象具有什么特性 （2）目标选址地区的结构特点是什么 （3）目标和成本参数是什么 （4）其他限制条件是什么 2、选址问题的分类 （1）按被定位的对象的空间维数分为：立体选址、平面选址、线选址、点选址。 立体选址：集装箱装箱问题 平面选址：工厂或货运站的设施布局 线选址：巷道内划出拣选带 点选址：制造或配送系统的选址 （2）按照目标区域的结构来划分：连续选址、网格选址、网络选址和离散点选址。 连续选址：候选区域是一个平面或球面，任意点都可作为选址点。 网格选址：目标区域被划分成多个单元，要求为对象分配其中若干单元。 网络选址：目标选址区是一个网络，即节点和边的集合。 离散点选址：候选点数量有限且较少。 （3）从目标函数来分类：中位问题、中心问题，反中心问题 中位问题：总成本最小为目标。 中心问题：服务于每个客户的最大成本最小化为目标。 反中心问题：服务于每个客户的最小成本最大化为目标。 （4）根据问题中的参数是否与解存在关联：纯选址问题和选址分配问题。 纯选址问题：其中的参数或结构不依赖新建设施而改变，是事先确定的。 选址分配问题：其中的参数或结构依赖新建设施而改变。 （5）根据问题中的参数是否随时间而改变，分为静态选址和动态选址。 （6）根据参数是确定性的还是随机性的，分为确定性选址问题和随机选址问题。 （7）根据候选点是否存在服务能力约束，可以分为无限能力选址和有限能力选址。 15.2 连续点选址问题 连续点选址问题中，点到点的距离计算标准有两种。设平面上的点坐标分别为（xi,yi），（xj,yj） 直线距离dijE： 折线距离dijR ： 1、直线距离准则下的选址 用直线距离准则进行选址，则目标函数为： 2、折线距离准则下的选址 重心法，用于以总和最小为目标函数的单一设施选址问题。此时目标函数为： 可见，原问题可以被拆成两个独立的问题，即： 例1：报刊亭选址。有一个报刊连锁公司想在一个地区设一个新的报刊零售点，主要的服务对象为附近的五个居民小区。表中数字分别为各个小区的x坐标和y坐标，以及需求量。 用坐标图来表示五个小区的位置 解：先求x坐标的解 （1）按坐标从小到大的顺序排列需求点 （2）计算总权重（需求量）W，计算累积权重（需求量） （3）找满足累积需求量 若 ，则选址的x坐标即为对应的需求点s 的x坐标。 若 ，则选址的x坐标即为对应原需求点s 和需求点s+1的x坐标范围内任一点。 所以，本题选址点的x坐标是编号为3和编号为4的需求点的x坐标之间的任意值，即为[3，4]之间的任意值。 再求解y坐标的解。 （1）按坐标从小到大的顺序排列需求点 （2）计算总权重（需求量）W，计算累积权重（需求量） x坐标为[3，4]之间的任意值，y坐标为3，说明新的报刊零售点的位置可以是PQ线段上的任意一点。 15.3 离散点选址问题 离散点选址指的是在有限的候选位置里，选取最为合适的一个或者一组位置为最优方案，相应的模型称为离散点选址模型。 离散点选址问题，目前主要有两种模型可供选择，分别是覆盖模型和k中位模型。其中覆盖模型常用的是集合覆盖模型和最大覆盖模型。 覆盖模型，是对于需求已知的一些需求点，如何确定一组服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适位置。 覆盖模型适用于商业物流系统，如零售点的选址，加油站的选址、配送中心的选址等，公用事业系统，如急救中心、消防中心等，以及计算机与通信系统。 集合覆盖模型：用最小数量的设施去覆盖所有的需求点。 最大覆盖模型：在给定数量的设施下，覆盖尽可能多的需求点。 集合覆盖模型： 定义：xi——需求点 cj——覆盖成本 sj——覆盖集合子集，取1时表示该子集启用，取0时表示该子集未启用。 A——覆盖关系矩阵 aij