若
W ，则选址的x坐标即为对应原需求点s wi 2 i 1
s
和需求点s+1的x坐标范围内任一点。 所以，本题选址点的x坐标是编号为3和编号为4 的需求点的x坐标之间的任意值，即为[3，4]之间的 任意值。 再求解y坐标的解。
（1）按坐标从小到大的顺序排列需求点 （2）计算总权重（需求量）W，计算累积权重（需坐标图来表示五个小区的位置
小区 A B C D E x坐 标 3 5 4 2 1 y坐 标 1 2 3 4 5 需求 量wi 1 7 3 3 6
y
5 4
5 4
3
2 1 0 1 2 3 1 4
3 2
5
x
解：先求x坐标的解 （1）按坐标从小到大的顺序排列需求点 （2）计算总权重（需求量）W，计算累积权重（需 求量） 计算 小区 x坐标 累积需 （3）找满足累积需求量
R min Z wi d is i 1 n
wi | xi xs | | yi ys |
i 1 n
n
wi | xi xs | wi | yi ys |
i 1 i 1
n
可见，原问题可以被拆成两个独立的问题，即：
min Z x wi | xi xs |
400 2 400 7 300 1 250 200 3 100 4 150 150 5 350 300 300 200 300
8 6
300
解：第一步是要建立覆盖矩阵。
9 2 400 400 7 200 350 300
1
300
200 3
300
300
250 6 150 5 300
8
100
4 150
s1 c1 c2 1 1 1 1 0 0
R ij
x
1、直线距离准则下的选址
用直线距离准则进行选址，则目标函数为：
min Z wi d
i 1 n
n
E is
wi ( xi xs ) 2 ( yi ys ) 2
i 1
2、折线距离准则下的选址
重心法，用于以总和最小为目标函数的单一设施 选址问题。此时目标函数为：
5
6
7
（4）根据问题中的参数是否与解存在关联：纯选址 问题和选址分配问题。
纯选址问题：其中的参数或结构不依赖新建设施而改变， 是事先确定的。 选址分配问题：其中的参数或结构依赖新建设施而改变。
（5）根据问题中的参数是否随时间而改变，分为静 态选址和动态选址。 （6）根据参数是确定性的还是随机性的，分为确定 性选址问题和随机选址问题。 （7）根据候选点是否存在服务能力约束，可以分为 无限能力选址和有限能力选址。
s2 1 1 1 0 0
s3 1 1
s4 1 0 1 1 1
s5
s7
s8
s9
0
0 1 1 1
0
0 0 1 0
0
0 0 0 0 1 1 1 1
0
0 0 0 0 0 0 1 1
c3
c4 c5 c6
1
1 1 0 0
0
0 0
1
1 0 0
1
0
1 1
1 0
c7
c8 c9
0
0 0
0
0
0
0
0
第二步进行计算。 （1）找出行中只有一个非0元素的行。 （2）简化矩阵 s1 s2 s3 s4 s5
0 1 0
0 0 1
1 0 0
解：（1）在矩阵A中找出行中只有一个非0元素的行。
s1 s 2 x1 x2 x3 x4 x5 s3 s4 s5
1 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1
记J={s3}
s1 s2 x2 x3 x5
s4
s5
x2 1
s1 s4
3 2
2
1 0 1
1
2
3
4
5
x
15.3 离散点选址问题
离散点选址指的是在有限的候选位置里，选取最 为合适的一个或者一组位置为最优方案，相应的模 型称为离散点选址模型。 离散点选址问题，目前主要有两种模型可供选择， 分别是覆盖模型和k中位模型。其中覆盖模型常用 的是集合覆盖模型和最大覆盖模型。 覆盖模型，是对于需求已知的一些需求点，如何 确定一组服务设施来满足这些需求点的需求。在这 个模型中，需要确定服务设施的最小数量和合适位 置。
计算编号 1 2 3 4 5 小区名称 A B C D E y坐标 1 2 3 4 5 累积需求量
1 8 11 14 20
（3）y坐标为编号为3的需求点对应的y坐标，即y 坐标为3。
x坐标为[3，4]之间的任意值，y坐标为3，说明新的 报刊零售点的位置可以是PQ线段上的任意一点。
y
5
4 3
5 4
P Q
4
5 1400 3 140 2 6
7 120
600 8
取走4后，总费用为3520，增加1040。
此时应取走2，总费用为2620，如图所示：
600 4 160 4 2 100 280 6 360 3 2 8 3 600 5
7
120
1
360 3
2
总成本费用为：2480
第二步：选择并取走一个位置点，满足以下条件：取走它并将 客户重新指派后，总费用增加量最小，然后令k=k-1。 第三步：重复第二步，直到k=2。
1 500 2 600 4 160 4 3 140 6 600 8 600 5
7
120
1 480
3
2
取走1后，总费用为3200，增加720。
j 1
min c j s j
j 1
n
a
j 1
n
ij
1
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中不再包含任 何元素，或不存在行或列可以删除。
i 1 n
n
min Z y wi | yi ys |
i 1
例1：报刊亭选址。有一个报刊连锁公司想在一个地 区设一个新的报刊零售点，主要的服务对象为附近 的五个居民小区。表中数字分别为各个小区的x坐 标和y坐标，以及需求量。
小区 A B C D x坐标 3 5 4 2 y坐标 1 2 3 4 需求量wi 1 7 3 3
（2）按照目标区域的结构来划分：连续选址、网格 选址、网络选址和离散点选址。
连续选址：候选区域是一个平面或球面，任意点都可作为选 址点。 网格选址：目标区域被划分成多个单元，要求为对象分配其 中若干单元。 网络选址：目标选址区是一个网络，即节点和边的集合。 离散点选址：候选点数量有限且较少。
（3）从目标函数来分类：中位问题、中心问题，反 中心问题
15.2 连续点选址问题
连续点选址问题中，点到点的距离计算标准有两 种。设平面上的点坐标分别为（xi,yi），（xj,yj） 直线距离dijE： y
E dij ( xi x j ) 2 ( yi y j ) 2
i
折线距离dijR ：
j
d | xi x j | | yi y j |
例4：某公司准备在8个客户的附近建立2个仓库，用最低的运 输成本来满足客户的需求。现计划从4个候选地址选择2个 地方建立仓库。从候选地址到不同的仓库的运输成本、各 个超市的需求量都已确定，如表所示： p1 p2 p3 p4 需求量 100 50 120 80 200 70 60 100
x1 x2 x3 x4 x5 x6 x7 x8
s7 0 0 0 1 0 1 1 1 0
s8 0 0 0 0 0 1 1 1 1
s9 0 0 0 0 0 0 0 1 1
c1 c2 c3 c4 c5 c6 c7 c8 c9
1 1 1 1 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0
1 0 1 1 1 1 1 0 0
1 400 2 100 160 4
600 4 5
7
120 280 3 600 8
1
360 3 2
6
取走2后，总费用为2620，增加140。
1 400 2 100 1 360 3 160 4
600
4
5 660 3 140 2 6 1200
7
8
取走3后，总费用为3620，增加1140。
1 400 2 100 4 1 360 3 400
例2：有7个航线需要安排乘务员，有五组乘务组可选， 请尽量安排最小的乘务组，且保证每条航线都至少 有一个乘务组服务。
乘务组 航线 x1 x2 x3 x4 s1 1 1 1 0 s2 0 0 1 1 s3 1 0 0 1 s4 1 1 1 1 s5 0 0 0 0
x5 x6 x7
1 0 0
0 0 1
W s 1 wi 2 i 1 s W wi i 1 2
编号 1 2 3 4 5
名称 E D A C B
求量
6 9 10 13 20
1 2
3 4 5
由计算结果可知计算编号s＝3
若
W ，则选址的x坐标即为对应的需求点s wi 2 i 1
s
的x坐标。
第15章 选址问题
15.1 概述
选址理论：是关于选址问题模型和算法 的理论。 选址在整个物流系统中占有非常重要的 地位，主要属于物流管理战略层的研究问 题。选址决策就是要确定所要分配的设施 的数量、位置以及分配方案。这些设施主 要指物流系统中的节点，如制造商、供应 商、仓库、配送中心、零售网点等。