2012年6月28日星期四
5

4、选址问题中的距离计算
选址问题模型中，最基本的一个参数是各个节
点之间的距离。 一般采用两种方法来计算节点之间的距离：一 种是直线距离，也叫欧几里得距离（Euclidean Metric）；另一种是折线距离（Rectilinear Metric），也叫城市距离（Metropolitan Metric）。
min Z

n i 1
wi xi x s yi y s
2
2 1/ 2


这是一个双变量系统，分别对xs和ys进行求偏微分，并且 令其为零，这样就可以得到两个微分等式。应用这两个等 式分别对xs和ys进行求解，即可以求出下面的一对隐含有 最优解的等式：
2012年6月28日星期四
2012年6月28日星期四
11
其相应的目标函数为：
Z
w x
i i 1
n
i
xs yi ys

式中：
——与第i个点对应的权重（例如需求）； wi x i ，y i ——第i个需求点的坐标； x s ，y s ——服务设施点的坐标；
n
——需求点的总数目。
在这个问题里面，最优位置也就是由如下坐标组成的点： x s 是在x方向的对所有的权重的中值点； y s 是在y方向的对所有的权重的中值点。 考虑到 x s ，y s 两者可能同时是惟一值或某一范围，最优的 位置也相应的可能是一个点，或者是线，或者是一个区域。
2012年6月28日星期四 12


例子：报刊亭选址 一个报刊连锁公司想在一个地区开设一个新的报刊零售点， 主要的服务对象是附近的5个住宿小区的居民，他们是新 开设报刊零售点的主要顾客源。下图笛卡儿坐标系中确切 地表达了这些需求点的位置，下表是各个需求点对应的权 重。这里，权重代表每个月潜在的顾客需求总量，基本可 以用每个小区中的总的居民数量来近似。经理希望通过这 些信息来确定一个合适的报刊零售点的位置，要求每个月 顾客到报刊零售点所行走的距离总和为最小。 解： 由于考虑的问题是在一个城市中的选址问题，评价是，使 用城市距离是合适的，交叉中值选址方法将会用来解决这 个问题。
20

xs
n
wi xi d is wi d is
ys

n
wi yi d is wi d is
2 1/ 2
i 1
i 1

n

n
i 1
i 1
上式中， d is
x
i
xs yi y s
2

该微分议程组不能直接求解，可以通过迭代的方法进行求解， 这需要提供一组初始值xs0和ys0 。然后利用xs(i-1)和ys(i-1)求出 dis(i-1)，再用它去求出xsi和ysi ，迭代公式如下：

xs0
n
wi xi
i 1 n

ys0
n
wi yi

x si
n
wi xi d is ( i 1 ) wi d is ( i 1 )
2

y si
n
wi yi d is ( i 1 ) wi d is ( i 1 )
2 1/ 2
i 1 n
i 1 n
w
i 1
i 1 n
25
2012年6月28日星期四





1、覆盖模型 所谓覆盖模型，就是对于需求已知的一些需求点，如何确定 一组服务设施来满足这些需求点的需求。在这个模型中，需 要确定服务设施的最小数量和合适的位置。 该模型适用于商业物流系统，如零售点的选址问题、加油站 的选址、配送中心的选址等，公用事业系统，如急救中心、 消防中心等，以及计算机与通信系统，如有线电视网的基站、 无线通信网络基站、计算机网络中的集线器设置等。 根据解决问题的方法的不同，可以分为两种不同的主要模型： （1）集合覆盖模型，用最小数量的设施去覆盖所有的需求 点。 （2）最大覆盖模型，在给定数量的设施下，覆盖尽可能多 的需求点。 两类模型的区别：集合覆盖模型要满足所有的需求点，而最 大覆盖模型则只覆盖有限的需求点，两种模型的应用情况取 决于服务设施的资源充足与否。
i
w
i 1
i


i 1
i 1
上式中， d is ( i 1 )
2012年6月28日星期四
x
i
x s ( i 1 ) y i y s ( i 1 )

21


如果该迭代过程具有收敛性，那么经过无限次的迭代之后， 可以得到一个最优解xs*和ys *。但是在实际中，可以迭代的 次数是有限的，所以在迭代过程中需要确定一个中止准则。 设置中止准则有两个方法：（1）根据经验和以前的试验结 果，直接设置一个确定的迭代次数N；（2）将每一次得到的 迭代结果xsi和ysi 跟前面一次的迭代结果xs（i-1）和ys（i-1） 比较， x s lim it y s lim it 当两次的迭代结果变化小于某一个阈值 、 时，迭 代过程结束。
26
2012年6月28日星期四


（1）集合覆盖模型 集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求 点，相应的目标函数可以表达为：
min

xj

约束条件为：
j B ( i )
j N
——最小化设施的数目

y ij 1，i N
——保证每个需求点的需求得到完全的满足
i
i A (
d


离散点选址指的是在有限的候选位置里面，选取最为合适 的一个或者一组位置为最优方案，相应的模型就叫做离散 点选址模型。它与连续点选址模型的区别在于：它所拥有 的候选方案只有有限个元素，我们考虑问题的时候，只需 要在这几个有限的位置进行分析。 对于离散点选址问题。目前主要有两种模型可供选择，分 别是覆盖模型（Covering）和P—中值模型。其中覆盖模 型常用的有集合覆盖模型（Set Covering Location Problem）和最大覆盖模型（Maximum Covering Location）。
2012年6月28日星期四
23
然后根据前面的公式，即可得到迭代结果：
x si 1 . 5 15 . 65 12 4 . 25 2 . 13 0 . 5 3 . 13 3 2 . 13 2 . 13
0 . 5 6 . 25 9 8 . 5 10 . 63 0 . 5 3 . 13 3 2 . 13 2 . 13
3 . 26
y si
3 . 20
然后进行中止准则的判断，确定是否继续进行迭代。

注意：用精确重心法得到的最优解只有一个点，而不会是一 条线段或者一个区域。而且只有在十分偶然的情况下，才会 出现用交叉中值法和精确重心法得到的最优优地址一致的情 况。
2012年6月28日星期四
24
三、离散点选址模型
2012年6月28日星期四
4

（2）选址目标区域的特征
根据选址目标区域的特征：连续选址、网格选址、离
散选址。

（3）选址成本
可行性与最优性 Minisum/Minimax目标函数 固定权重与可变权重 被定位设施间有无相互联系
确定性与随机性
静态与动态

（4）选址约束
有/无能力约束 不可行区域约束

2012年6月28日星期四
3


1、选址的意义 2、选址决策的影响因素
外部因素 宏观政治、经济因素 基础设施及环境 竞争对手 内部因素


3、选址模型的分类 （1）被定位设施的维数及数量
根据被定位设施的维数：体选址、面选址、线选址、
点选址； 根据选址设施的数量：单一设施选址、多设施选址；
j)
y ij C j x j , j N
——是对每个提供服务的服务网点的服务能力的限制
x j 0 ,1, i N
——保证一个地方最多只能投建一个设施
y ij 0 , i , j N
2012年6月28日星期四
——允许一个设施只提供部分的需求
27

对于此类带有约束条件的极值问题，有两大类方法可以进行 分解：一是精确的算法，应用分枝定界求解的方法，能够找 到小规模问题的最优解，由于运算量方面的限制，一般也只 适用于小规模问题的求解；二是启发式方法，所得到的结果 不能保证是最优解，但是可以保证是可行解，可以对大型问 题进行有效的分析、求解。
2012年6月28日星期四
19



2、精确重心法（Exact Gravity） 前面介绍的交叉中值模型由于其本身的局限性，例如使用 的是城市距离，只适合于解决一些小范围的城市内的选址 问题。精确重心法在评价的过程中使用的是欧几米德距离， 即直线距离，它使选址问题变得复杂，但是有着更为广阔 的应用范围。 在使用了欧几米德距离之后，目标函数变成了：
dZ ds

w
i 1
s
i

w
i s
n
i
0
dZ dss源自x0w x dx

L
xs
w x dx 0
计算结果表明：所开设的新店面需要设置在权重的中点，即两边的 权重相等。
2012年6月28日星期四
10

连续点选址问题指的是在一条路径或者一个区域 里面的任何位置都可以作为选址的一个选择。 1、交叉中值模型（Cross Median） 交叉中值模型是用来解决连续点选址问题的一种 十分有效的模型，它是利用城市距离进行计算， 通过交叉中值的方法可以对单一的选址问题在一 个平面上的加权的城市距离进行最小化。