物流工程与管理学：选址问题

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

2、出拣选带 点选址：制造或配送系统的选址（2）按照目标区域的结构来划分：连续选址、网格选址、网络选址和离散点选址。连续选址：候选区域是一个平面或球面，任意点都可作为选址点。网格选址：目标区域被划分成多个单元，要求为对象分配其中若干单元。网络选址：目标选址区是一个网络，即节点和边的集合。离散点选址：候选点数量有限且较少。（3）从目标函数来分类：中位问题、中心问题、反中心问题。 中位问题：总成本最小为目标。 中心问题：服务于每个客户的最大成本最小化为目标。 反中心问题：服务于每个客户的最小成本最大化为目标。 0567中位点中心点3.5反中心点2.5（4）根据问题中的参数是否与解存在关联：纯选址问题和

3、选址分配问题。纯选址问题：其中的参数或结构不依赖新建设施而改变，是事先确定的。选址分配问题：其中的参数或结构依赖新建设施而改变。（5）根据问题中的参数是否随时间而改变，分为静态选址和动态选址。（6）根据参数是确定性的还是随机性的，分为确定性选址问题和随机选址问题。（7）根据候选点是否存在服务能力约束，可以分为无限能力选址和有限能力选址。15.2 连续点选址问题 连续点选址问题中，点到点的距离计算标准有两种。设平面上的点坐标分别为（xi,yi），（xj,yj） 直线距离dijE： 折线距离dijR ：yxij1. 直线距离准则下的选址 用直线距离准则进行选址，则目标函数为：2. 折线距离准则下的

4、选址 重心法用于以总和最小为目标函数的单一设施选址问题。此时目标函数为：可见，原问题可以被拆成两个独立的问题，即：例1：报刊亭选址。有一个报刊连锁公司想在一个地区设一个新的报刊零售点，主要的服务对象为附近的五个居民小区。表中数字分别为各个小区的x坐标和y坐标，以及需求量。小区x坐标y坐标需求量wiA311B527C433D243E156用坐标图来表示五个小区的位置小区x坐标y坐标需求量wiA311B527C433D243E156xy0 1 2 3 4 55432112345解：先求x坐标的解（1）按坐标从小到大的顺序排列需求点。（2）计算总权重（需求量）W，计算累积权重（需求量）。（3）找满足

5、累积需求量。 计算编号小区名称x坐标累积需求量1E12D23A34C45B569101320由计算结果可知计算编号s3若 ，则选址的x坐标即为对应的需求点s的x坐标。若 ，则选址的x坐标即为对应原需求点s和需求点s+1的x坐标范围内任一点。 所以，本题选址点的x坐标是编号为3和编号为4的需求点的x坐标之间的任意值，即为3，4之间的任意值。 再求解y坐标的解。（1）按坐标从小到大的顺序排列需求点。（2）计算总权重（需求量）W，计算累积权重（需求量）。计算编号小区名称y坐标累积需求量1A12B23C34D45E518111420（3）y坐标为编号为3的需求点对应的y坐标，即y坐标为3。x坐标为3，

6、4之间的任意值，y坐标为3，说明新的报刊零售点的位置可以是PQ线段上的任意一点。xy0 1 2 3 4 55432112345PQ15.3 离散点选址问题 离散点选址指的是在有限的候选位置里，选取最为合适的一个或者一组位置为最优方案，相应的模型称为离散点选址模型。 离散点选址问题，目前主要有两种模型可供选择，分别是覆盖模型和k中位模型。其中覆盖模型常用的是集合覆盖模型和最大覆盖模型。 覆盖模型，是对于需求已知的一些需求点，如何确定一组服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适位置。 覆盖模型适用于商业物流系统，如零售点的选址，加油站的选址、配送中心的选址等，

7、公用事业系统，如急救中心、消防中心等，以及计算机与通信系统。 集合覆盖模型：用最小数量的设施去覆盖所有的需求点。 最大覆盖模型：在给定数量的设施下，覆盖尽可能多的需求点。集合覆盖模型：定义：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以及该列中aij1的行。

8、第二步：若A中存在行i和i，若对所有列有aijaij，则删除行i。第三步：若A中存在列j和j，若对所有行有aijaij，则删除列j。第四步：反复进行前三步，直至矩阵A中不再包含任何元素，或不存在行或列可以删除。例2：有7个航线需要安排乘务员，有五组乘务组可选，请尽量安排最小的乘务组，且保证每条航线都至少有一个乘务组服务。 乘务组航线s1s2s3s4s5x110110 x210010 x311010 x401110 x510001x600100 x701010解：（1）在矩阵A中找出行中只有一个非0元素的行。x1x2x3x4x5x6x7s1 s2 s3 s4 s5记J=s3x1x2x3x4x5x

9、6x7s1 s2 s3 s4 s5（2）删除行x3，因为x3包含x2。（3）删除列s5，因为s1包含s5。删除列s2，因为s4包含s2x2x3x5x7 s1 s2 s4 s5x2x5x7s1 s4 （4）记J=s3,s1（5）记J=s3,s1,s4例3：某物流企业要建设一些配送中心，为九个城市的客户服务，配送中心最远的服务距离为300km，即任何一个城市的周边300km处至少有一个配送中心。不考虑配送中心的服务能力，物流企业要确定需要多少个配送中心以及这些配送中心的位置。其中第6个城市由于缺乏建立配送中心的必要条件，不可以建立配送中心。图表示各个城市的相对位置和距离。2400134567892

10、00300200100350300250150150300400300200300解：第一步是要建立覆盖矩阵。240013456789200300200100350300250150150300400300200300s1s2s3s4s5s7s8s9c11c21c31c41c51c6c71c81c911110100001000000111100001011110000111000000101100000011100000001第二步进行计算。（1）找出行中只有一个非0元素的行。（2）简化矩阵简化矩阵后得记J=s3记J=s3 ，s8k中位模型： 设在某一地区要建立若干的配送中心，给其客户配送商品

11、，配送中心有N个候选地址。现要求设立的配送中心到所有客户的总运输成本最小。例4：某公司准备在8个客户的附近建立2个仓库，用最低的运输成本来满足客户的需求。现计划从4个候选地址选择2个地方建立仓库。从候选地址到不同的仓库的运输成本、各个超市的需求量都已确定，如表所示：p1p2p3p4需求量x1412206100 x2210251050 x3341614120 x4659280 x5181273200 x61424970 x7203021160 x82412622100用贪婪取走启发式算法：第一步：初始化，令循环参数k=m，将所有的m个候选位置全选中，然后将每个客户指派给离其距离最近的一个候选位置

12、。123456781423400100360160600140120600总成本费用为：2480第二步：选择并取走一个位置点，满足以下条件：取走它并将客户重新指派后，总费用增加量最小，然后令k=k-1。第三步：重复第二步，直到k=2。123600500480456781423160600140120600取走1后，总费用为3200，增加720。取走2后，总费用为2620，增加140。628012345781423400100360160600120600取走3后，总费用为3620，增加1140。1234561423400100360160600140786601200取走4后，总费用为3520，增加1040。4540014007812361423400100360140120600此时应取走2，总费用为2620，如图所示：628012345781423400100360160600120600628045781423160600120600取走1后，总费用为4540，