基于矩阵算法的区位模型的应用研究.doc

基于矩阵算法的区位配置模型研究徐向平(兰州交通大学数理与软件工程学院，甘肃兰州730070)摘 要：区位配置模型主要是针对区位寻找问题，为设施布局提供解决方案木文运用图论中的矩阵算法， 结合实例，探讨了在网络环境中如何确定服务设施的具体位置关键词：区位配置模型；最短路径；矩阵算法寻找最优区位是城市各类基础设施(如医院、学校、消防站、公园、社区服务)规划和 布局时经常遇到的问题区位配置模型(Location-Allocation Model),简称区位模型，是针 对这类问题发展起来的，主要是优化某种设施在空间上的配置自20世纪60年代以来，区 位模型得到了广泛的研究，并在多个政府部门或私有企业的设施布局或项目评价中得到应用 和推广随着可用土地的日益短缺，科学确定设施的空间位置显得越来越重要基于此，本 文运用图论中的矩阵算法，结合实例，探讨了在网络环境中如何确定服务设施的具体位置1区位配置模型的概念与类型区位配置模型(Location-Allocation Model),简称区位模型，是城市与区域规划中应用 非常广泛的一种数学模型区位模型的主要用途是从一批候选位置或(区域)中选取一定的 位置，建设公共设施(供应点)，为本区域中的其它区域(需求点)提供服务。

区位模型的 基本原理是要使设施位于可达性最佳的区位基于不同的准则，区位模型可以有多种不同形 式Church (1999)对区位模型进行了归纳，分为4类：(1) 中值模型(medianmodel)在一定地域范围内为固定数量的设施选址，其基本原 则是：任何一个需求点到距其最近的设施之间的平均距离最小2) 覆盖模型(covering model)□在一定地域范围内对设施布局，使设施在最大服务 距离内能覆盖区内所有(或绝大多数的)需求点其思路是，某一设施所能就近服务的用户 越多，服务效果就越好3) 容量限制模型(capacitated model)o上述两个模型都是基于这样一种假设，即每 个设施的服务能力或容量是没有限制的，需求点的位置只要是在该设施的有效距离范围内， 其需求都可以得到满足而容量限制模型则不同，设施所能提供的产品容量或服务能力是有 限制的，如垃圾站每天所能处理的垃圾量不能超出上限4) 竞争模型(competition model)在有竞争的条件下，模拟某投资者针对其他竞争 对手做出选址决定或服务对策例如，当一个投资者在其竞争对手经营较为薄弱的市场服务 区开设一个分支机构的时候，对于可能会重新调整其策略，不久也在同一地区设置同类型的 机构，以争夺失去的市场份额。

因而，投资者作区位决策时，必须要考虑竞争对手对其决策 会做出什么反应中值、覆盖以及容量限制三种模型通常被看作是传统的优化模型，而竞争模型则要通过 博弈论及模拟来解决通常情况下，一个区位问题适用于什么模型，一般由供需规律所决定, 也取决于决策者的倾向、喜好具体应用都需要考虑到上述四种情况，但是在实践中最常用 的还是最优化模型，主要是多设施中值模型(p-median)和最大覆盖模型(maximal covering)□ 容量限制模型，目前还不成熟，竞争模型更具有特殊性2矩阵算法区位模型根据设施点是在一个连续平面上随机分布,还是只能分布在网络上的固定位置 (网络顶点)可以分为平面区位模型和网络区位模型，前者设施点的位置在平面上不受任何 限制网络区位模型是平面区位模型的扩展，更具有实用性网络由结点、连接和连接长度 表示，结点就是网络上的端点，连接就是两个网络结点之间的连线网络区位模型的需求点 分布在结点上，可以证明，满足总距离最短的设施点必定在网络结点上，这就要首先计算各 结点之间的最短距离，以便应用距离最短原则确定设施结点从算法研究的角度考虑最短路径问题通常可归纳为两大类:一类是所有点对之间的最短 路径，另一类是单源点间的最短路径问题。

Dijkstra算法是解决单源点间最短路径问题比较 经典而且有效的算法，但在网络模型中往往要求任意两点之间的最短距离，这时采用矩阵算 法比较简单有效矩阵算法是利用矩阵来求出网络的最短距离矩阵假设D=(d”是带权无向图的邻 接矩阵，定义心为图中两相邻点的距离，若j与/不相邻，令di} = 00 ,则矩阵D表明从7点 到j点的直接最短距离但从i点到j点的最短路不一定是i- j，可能是i-l-j, i-l 7-j,或7 - / — k - j o先考虑i与j之间有一个中间点的情况，则%的最短距 离应为min{d,]+〃]厂％2+厶厂…，4*+爲}，这里厶+“”表示从结点7经过中间点1到结 点j的路径长度，di2+d2j表示从结点7经过中间点2到结点j的路径长度，其余各项的意 义与此相同，都表示从结点i经过一个中间点到结点/的路径长度，心取它们中的最小值， 为此可以构造一个新的矩阵Dm,令D⑴中每个心⑴=min{dik+dkj],贝U矩阵D⑴给出了 网络中任意两点之间直接到达和包括经一个中间点时的最短距离再构造矩阵D⑵，令贝U D⑵给出网络中任意两点直接到 达，及包括经过一至三个中间点时的最短距离。

一般地有给⑴=min{d「i+dji},矩阵D⑷给出网络中任意两点直接到达，经 过一个、两个、…、至ij(2-l)个中间点时比较得到的最短距离设网络图有卩个点，则一般计算到不超过D⑹，k的值按下式计算：2*7-1< p-2<2k-1即 斤_]<晅(匕-1)“lg2如果计算中出现D(m+1)=D(m)时，计算也可结束，矩阵中的各个元素值即为各点间最 短距离3应用实例案例网络中的服务及设施布局长虹街道近年新建了 11个居民小区，各小区的大致位置及相互间的道路距离(单位： 100m)如图1所示各居民小区居民数为：①3000,②3500,③3700,④5000,⑤ 3000,⑥2500,⑦2800,⑧4500,⑨3300,⑩4000,⑪3500试帮助决策：在11个 小区内准备共建一套医务所、邮局、综合超市等服务设施，应建于哪一居民小区，使对居民 总体来说感到方便邻点的距离，若i与j不相邻，令血~Q400407oo706500oo006D =oo00580000oo0000oo0000oo0000oo0000_04114071170651111106D(i) =oo12581200121114oo0012130000oo0000解：(1 )用矩阵算法求各点之间的最短距离。

定义Q为图1的邻接矩阵,仃为图中两相8,由此6oo008oooo00005oo0000oooo00GOoo6500oooo00000500006oo000050400860000oo4000oo70000oooo0004oo5006800404005oo670040006oooo005oooo06oooo00005660_611008120013oo5101212110000oo1165oo141200oo05910610001150412860012940oo1170013101200048596811404951067840126oooo0059120611121395660d(2> =04116111581216131740751012121115171611701165181412231865110591061015111110650412861712151259401511719138121810121504859121114681140495161512106784012613172315171959120617161811121395660D⑶=D⑵D⑵中的元素给⑵表明网络图中从,点到八点的最短距离。

2 ）将计算得到的D⑵的第一行数字乘以居民小区①的居民数，则乘积数字为假定服务 设施建于各小区时，小区①居民获取服务时单程所走路程将D⑵中第二行数字乘以小区 ②的居民数，得服务设施建于各小区时，小区②居民获取服务时单程所走路程依次类推 可计算得到表1表1最下面一行为各列累加数字，表示若服务设施建于第/个小区时，11 个小区居民累计的获取一次服务单程所走路程表1设施建丁各小区时居民获取服务所疋路程Table 1 The path that the residents get services when the facilities are built in each location①②③④⑤⑥⑦@⑪①012000330001800033000450002400036000480003900051000140000245001750035000420004200038500525005950056000③407002590004070022200185006660051800444008510066600④300002500055000025000450005000030000500007500055000⑤330003000018000150000120003600024000180005100036000⑥375003000012500225001000003750027500175004750032500⑦224003360050400280003360042000011200224001400025200。