第15章选址问题课件

第15章选址问题第15章选址问题115.1概述选址理论：是关于选址问题模型和算法的理论。选址在整个物流系统中占有非常重要的地位，主要属于物流管理战略层的研究问题。选址决策就是要确定所要分配的设施的数量、位置以及分配方案。这些设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售网点等。15.1概述选址理论：是关于选址问题模型21、选址问题设计算法和模型时要考虑：（1）被定位的对象具有什么特性（2）目标选址地区的结构特点是什么（3）目标和成本参数是什么（4）其他限制条件是什么1、选址问题设计算法和模型时要考虑：32、选址问题的分类（1）按被定位的对象的空间维数分为：立体选址、平面选址、线选址、点选址。

立体选址：集装箱装箱问题平面选址：工厂或货运站的设施布局线选址：巷道内划出拣选带点选址：制造或配送系统的选址2、选址问题的分类4（2）按照目标区域的结构来划分：连续选址、网格选址、网络选址和离散点选址。连续选址：候选区域是一个平面或球面，任意点都可作为选址点。网格选址：目标区域被划分成多个单元，要求为对象分配其中若干单元。网络选址：目标选址区是一个网络，即节点和边的集合。离散点选址：候选点数量有限且较少。（2）按照目标区域的结构来划分：连续选址、网格选址、网络选址5（3）从目标函数来分类：中位问题、中心问题，反中心问题中位问题：总成本最小为目标。中心问题：服务于每个客户的最大成本最小化为目标。反中心问题：服务于每个客户的最小成本最大化为目标。（3）从目标函数来分类：中位问题、中心问题，反中心问题60567中位点中心点3.5反中心点2.50567中位点中心点3.5反中心点2.57（4）根据问题中的参数是否与解存在关联：纯选址问题和选址分配问题。纯选址问题：其中的参数或结构不依赖新建设施而改变，是事先确定的。选址分配问题：其中的参数或结构依赖新建设施而改变。（5）根据问题中的参数是否随时间而改变，分为静态选址和动态选址。（6）根据参数是确定性的还是随机性的，分为确定性选址问题和随机选址问题。（7）根据候选点是否存在服务能力约束，可以分为无限能力选址和有限能力选址。（4）根据问题中的参数是否与解存在关联：纯选址问题和选址分配815.2连续点选址问题连续点选址问题中，点到点的距离计算标准有两种。设平面上的点坐标分别为（xi,yi），（xj,yj）直线距离dijE：折线距离dijR：yxij15.2连续点选址问题连续点选址问题中，点91、直线距离准则下的选址用直线距离准则进行选址，则目标函数为：1、直线距离准则下的选址用直线距离准则进行选102、折线距离准则下的选址重心法，用于以总和最小为目标函数的单一设施选址问题。此时目标函数为：2、折线距离准则下的选址重心法，用于以总和最11可见，原问题可以被拆成两个独立的问题，即：可见，原问题可以被拆成两个独立的问题，即：12例1：报刊亭选址。有一个报刊连锁公司想在一个地区设一个新的报刊零售点，主要的服务对象为附近的五个居民小区。表中数字分别为各个小区的x坐标和y坐标，以及需求量。小区x坐标y坐标需求量wiA311B527C433D243E156例1：报刊亭选址。有一个报刊连锁公司想在一个地区设一个新的报13用坐标图来表示五个小区的位置小区x坐标y坐标需求量wiA311B527C433D243E156xy0123455432112345用坐标图来表示五个小区的位置小区x坐标y坐标需求量wiA3114解：先求x坐标的解（1）按坐标从小到大的顺序排列需求点（2）计算总权重（需求量）W，计算累积权重（需求量）（3）找满足累积需求量

计算编号小区名称x坐标累积需求量1E12D23A34C45B569101320由计算结果可知计算编号s＝3解：先求x坐标的解计算编号小区名称x坐标累积需求量1E12D15若，则选址的x坐标即为对应的需求点s的x坐标。若，则选址的x坐标即为对应原需求点s和需求点s+1的x坐标范围内任一点。所以，本题选址点的x坐标是编号为3和编号为4的需求点的x坐标之间的任意值，即为[3，4]之间的任意值。再求解y坐标的解。若，则选址的16（1）按坐标从小到大的顺序排列需求点（2）计算总权重（需求量）W，计算累积权重（需求量）计算编号小区名称y坐标累积需求量1A12B23C34D45E518111420（3）y坐标为编号为3的需求点对应的y坐标，即y坐标为3。（1）按坐标从小到大的顺序排列需求点计算编号小区名称y坐标累17x坐标为[3，4]之间的任意值，y坐标为3，说明新的报刊零售点的位置可以是PQ线段上的任意一点。xy0123455432112345PQx坐标为[3，4]之间的任意值，y坐标为3，说明新的报刊零售1815.3离散点选址问题离散点选址指的是在有限的候选位置里，选取最为合适的一个或者一组位置为最优方案，相应的模型称为离散点选址模型。离散点选址问题，目前主要有两种模型可供选择，分别是覆盖模型和k中位模型。其中覆盖模型常用的是集合覆盖模型和最大覆盖模型。覆盖模型，是对于需求已知的一些需求点，如何确定一组服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适位置。15.3离散点选址问题离散点选址指的是在有19覆盖模型适用于商业物流系统，如零售点的选址，加油站的选址、配送中心的选址等，公用事业系统，如急救中心、消防中心等，以及计算机与通信系统。集合覆盖模型：用最小数量的设施去覆盖所有的需求点。覆盖模型适用于商业物流系统，如零售点的选址，20最大覆盖模型：在给定数量的设施下，覆盖尽可能多的需求点。最大覆盖模型：在给定数量的设施下，覆盖尽可能21集合覆盖模型：定义：xi——需求点cj——覆盖成本sj——覆盖集合子集，取1时表示该子集启用，取0时表示该子集未启用。A——覆盖关系矩阵aij——覆盖关系矩阵中的元素，取1时表示集合sj可以把需求点xi覆盖进去，取0时表示集合sj不可以把需求点xi覆盖进去。数学模型：目标函数：约束条件：aij和sj为0，1变量。集合覆盖模型：数学模型：约束条件：aij和sj为0，1变量。22矩阵简化法求解第一步：若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中不再包含任何元素，或不存在行或列可以删除。矩阵简化法求解23例2：有7个航线需要安排乘务员，有五组乘务组可选，请尽量安排最小的乘务组，且保证每条航线都至少有一个乘务组服务。乘务组航线s1s2s3s4s5x110110x210010x311010x401110x510001x600100x701010例2：有7个航线需要安排乘务员，有五组乘务组可选，请尽量安排24解：（1）在矩阵A中找出行中只有一个非0元素的行。x1x2x3x4x5x6x7s1s2s3s4s5记J={s3}（2）删除行x3，因为x3包含x2。（3）删除列s5，因为s1包含s5。删除列s2，因为s4包含s2。x2x3x5x7s1s2s4s5x2x5x7s1s4

（4）记J={s3,s1}（5）记J={s3,s1,s4}解：（1）在矩阵A中找出行中只有一个非0元素的行。x1s125例3：某物流企业要建设一些配送中心，为九个城市的客户服务，配送中心最远的服务距离为300km，即任何一个城市的周边300km处至少有一个配送中心。不考虑配送中心的服务能力，物流企业要确定需要多少个配送中心以及这些配送中心的位置。其中第6个城市由于缺乏建立配送中心的必要条件，不可以建立配送中心。图表示各个城市的相对位置和距离。240013456789200300200100350300250150150300400300200300例3：某物流企业要建设一些配送中心，为九个城市的客户服务，配26解：第一步是要建立覆盖矩阵。240013456789200300200100350300250150150300400300200300s1s2s3s4s5s7s8s9c11c21c31c41c51c6c71c81c911110100001000000111100001011110000111000000101100000011100000001解：第一步是要建立覆盖矩阵。240013456789200327第二步进行计算。（1）找出行中只有一个非0元素的行。（2）简化矩阵第二步进行计算。28简化矩阵后得记J={s3}记J={s3，s8}简化矩阵后得记J={s3}记J={s3，s8}29k中位模型：设在某一地区要建立若干的配送中心，给其客户配送商品，配送中心有N个候选地址。现要求设立的配送中心到所有客户的总运输成本最小。k中位模型：30例4：某公司准备在8个客户的附近建立2个仓库，用最低的运输成本来满足客户的需求。现计划从4个候选地址选择2个地方建立仓库。从候选地址到不同的仓库的运输成本、各个超市的需求量都已确定，如表所示：p1p2p3p4需求量x1412206100x2210251050x3341614120x4659280x5181273200x61424970x7203021160x82412622100例4：某公司准备在8个客户的附近建立2个仓库，用最低的运输成31用贪婪取走启发式算法：第一步：初始化，令循环参数k=m，将所有的m个候选位置全选中，然后将每个客户指派给离其距离最近的一个候选位置。123456781423400100360160600140120600总成本费用为：2480用贪婪取走启发式算法：123456781423400100332第二步：选择并取走一个位置点，满足以下条件：取走它并将客户重新指派后，总费用增加量最小，然后令k=k-1。第三步：重复第二步，直到k=2。123600500480456781423160600140120600取走1后，总费用为3200，增加720。第二步：选择并取走一个位置点，满足以下条件：取走它并将客户重33取走2后，总费用为2620，增加140。628012345781423400100360160600120600取走2后，总费用为2620，增加140。628012345734取走3后，总费用为3620，增加1140。1234561423400100360160600140786601200取走3后，总费用为3620，增加1140。12345614235取走4后，总费用为3520，增加1040。4540014007812361423400100360140120