第15章选址问题ppt课件.pptVIP

第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 找满足累积需求量 69101320 由计算结果可知计算编号s 3 若 则选址的x坐标即为对应的需求点s的x坐标 若 则选址的x坐标即为对应原需求点s和需求点s 1的x坐标范围内任一点 所以 本题选址点的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中位模型 其中覆盖模型常用的是集合覆盖模型和最大覆盖模型 覆盖模型 是对于需求已知的一些需求点 如何确定一组服务设施来满足这些需求点的需求 在这个模型中 需要确定服务设施的最小数量和合适位置 覆盖模型适用于商业物流系统 如零售点的选址 加油站的选址 配送中心的选址等 公用事业系统 如急救中心 消防中心等 以及计算机与通信系统 集合覆盖模型 用最小数量的设施去覆盖所有的需求点 最大覆盖模型 在给定数量的设施下 覆盖尽可能多的需求点 集合覆盖模型 定义 xi 需求点cj 覆盖成本sj 覆盖集合子集 取1时表示该子集启用 取0时表示该子集未启用 A 覆盖关系矩阵aij 覆盖关系矩阵中的元素 取1时表示集合sj可以把需求点xi覆盖进去 取0时表示集合sj不可以把需求点xi覆盖进去 数学模型 目标函数 约束条件 aij和sj为0 1变量 矩阵简化法求解第一步 若A中行i只有一个非0元素 例如aij 则记J j 即sj在最优解中 对A删除列j以及该列中aij 1的行 第二步 若A中存在行i和i 若对所有列有aij ai j 则删除行i 第三步 若A中存在列j和j 若对所有行有aij aij 则删除列j 第四步 反复进行前三步 直至矩阵A中不再包含任何元素 或不存在行或列可以删除 例2 有7个航线需要安排乘务员 有五组乘务组可选 请尽量安排最小的乘务组 且保证每条航线都至少有一个乘务组服务 解 1 在矩阵A中找出行中只有一个非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 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个地方建立仓库 从候选地址到不同的仓库的运输成本 各个超市的需求量都已确定 如表所示 用贪婪取走启发式算法 第一步 初始化 令循环参数k m 将所有的m个候选位置全选中 然后将每个客户指派给离其距离最近的一个候选位置 6 总成本费用为 2480 第二步 选择并取走一个位置点 满足以下条件 取走它并将客户重新指派后 总费用增加量最小 然后令k k 1 第三步 重复第二步 直到k 2 取走1后 总费用为3200 增加720 取走2后 总费用为2620 增加140 取走3后 总费用为3620 增加1140 取走4后 总费用为3520 增加1040