文档介绍：空间网络分析方法
路径分析(path an alysis)
在空间网络分析中，路径问题占有重要位置。人们常想知道在地理空间网络的两指定结点间是否存在路径，如果有则特别希望找出其中的最短路径。这种路径问题对于交通、消防、信息传件代表了规划目标所必须满足的规划条件，例如，要求所有需求点都有相应的供给点等，作为问题解决的约束条件; 日标函数是给出极大值或极小值，例如规定所有设施和需求点之间的总加权距离为最小等，其意义是在于能获得一个明确的分析结果。
定位-配置分析的算法包括P一中心问题、中心服务范围的确定和中心资源的分配范围等，它们是定位—配置分析或规划的重要工具，以下分别予以介绍。
P 一中心问题。这一问题是要在m个候选点中，选择P个供应点，为 n 个需求点服务，并使得从服务中心到需求点之间的总距离(或时间、费用)为最小。P 一中心问题可以描述为：
，% = 1 22 y = F
并满足保证每个需求点i(i = 1,2，…，n)都被服务和将服
务中心的数量限定为P个。
上述两个约束条件是为了保证每个需求点仅受一个供应点服务，并且只有 P 个供应点。
式中：i、n分别为需求点的位置和数量；
j、 m 为候选点的位置和数量;
P 为要确定的服务中心的数量;
wi 为需求点 i 的需求量; dij为需求点i到服务点j的距离。
并且yinxij, B ,町，只有第j个中心被选中时，需求点i才能分配到该中心；
yj=0或1,巧任何一个候选点被选中时为l;否则为0;
xij = O, X,巧需求点有中心j服务时为I；否则为0。
P 一中心问题可以用线性规划方法求得全局性的最佳结果，但由于计算量及内存需求量巨大，在实际应用中常用一些启发式算法来逼近或求得最佳结果，其中著名的有Teitz-Bart算法。该算法的主要步骤如下：
先选P个候选点作为起始供应点集Pt:C1, C2,…,Cp。
将所有的需求点分配给它们最邻近的供应点，使其距离为最短。计算总的加权距离为 Bt。
从未被选取的候选点集中选一候选点Cb。
对Pt中的每个供应点Cj用Cb替换之，并计算其总加权距离的变化Abj。
如果用Cb替换某个Cj 后,可以使总加权距离减少，那么就替换总加权距离减少最多的供应点Ck，令Bt=Bt-Abk，并将Pt修改为也所在的供应点。
重复③-⑤步，直至未被选取的候选点集为空。
当所有不在Pt中的候选点都试过后，其结果记为，，，并取代Pt。继续重复②-⑦步，如果没有任何取代能减少总的加权距离，则停止。其最后的结果以,即为所求的P个中心的供应点。
中心服务范围的确定。中心服务范围是指一个服务设施在给定的时间或距离内，能够到达的区域。
设一个带中心的空间网络G = (V,E,C)，其中V表示空间网络结点的集合,E 表示边的集合，C为该网络的一个中心。若已知该中心的阻值为cw,网络边 eij的费用为wij, r表示空间网络上任何结点到中心的(vi,ve)间的一条路径， ric是该路径的费用，那么在不考虑货源量和需求量的情况下，中心的服务范围应为满足下列条件的网络边和结点的集合F：
F二伦1%螯嘲亡|
为确定该中心的服务范围，须依次求出到服务中心费用不超过中心最大阻值的