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

基于矩阵算法的区位配置模型研究徐向平（兰州交通大学数理与软件工程学院，甘肃兰州730070）摘要：区位配置模型主要是针对区位寻找问题，为设施布局提供解决方案。本文运用图论中的矩阵算法，结合实例，探讨了在网络环境中如何确定服务设施的具体位置。关键词：区位配置模型；最短路径；矩阵算法寻找最优区位是城市各类基础设施（如医院、学校、消防站、公园、社区服务）规划和布局时经常遇到的问题。区位配置模型（Location-AllocationModel），简称区位模型，是针对这类问题发展起来的，主要是优化某种设施在空间上的配置。自20世纪60年代以来，区位模型得到了广泛的研究，并在多个政府部门或私有企业的设施布局或项目评价中得到应用和推广。随着可用土地的日益短缺，科学确定设施的空间位置显得越来越重要。基于此，本文运用图论中的矩阵算法，结合实例，探讨了在网络环境中如何确定服务设施的具体位置。1区位配置模型的概念与类型区位配置模型（Location-AllocationModel），简称区位模型，是城市与区域规划中应用非常广泛的一种数学模型。区位模型的主要用途是从一批候选位置或（区域）中选取一定的位置，建设公共设施（供应点），为本区域中的其它区域（需求点）提供服务。区位模型的基本原理是要使设施位于可达性最佳的区位。基于不同的准则，区位模型可以有多种不同形式。Church（1999）对区位模型进行了归纳，分为4类：（1）中值模型（medianmodel）。在一定地域范围内为固定数量的设施选址，其基本原则是：任何一个需求点到距其最近的设施之间的平均距离最小。（2）覆盖模型（coveringmodel）。在一定地域范围内对设施布局，使设施在最大服务距离内能覆盖区内所有（或绝大多数的）需求点。其思路是，某一设施所能就近服务的用户越多，服务效果就越好。（3）容量限制模型（capacitatedmodel）。上述两个模型都是基于这样一种假设，即每个设施的服务能力或容量是没有限制的，需求点的位置只要是在该设施的有效距离范围内，其需求都可以得到满足。而容量限制模型则不同，设施所能提供的产品容量或服务能力是有限制的，如垃圾站每天所能处理的垃圾量不能超出上限。（4）竞争模型（competitionmodel）。在有竞争的条件下，模拟某投资者针对其他竞争对手做出选址决定或服务对策。例如，当一个投资者在其竞争对手经营较为薄弱的市场服务区开设一个分支机构的时候，对手可能会重新调整其策略，不久也在同一地区设置同类型的机构，以争夺失去的市场份额。因而，投资者作区位决策时，必须要考虑竞争对手对其决策会做出什么反应。中值、覆盖以及容量限制三种模型通常被看作是传统的优化模型，而竞争模型则要通过博弈论及模拟来解决。通常情况下，一个区位问题适用于什么模型，一般由供需规律所决定，也取决于决策者的倾向、喜好。具体应用都需要考虑到上述四种情况，但是在实践中最常用的还是最优化模型，主要是多设施中值模型（p-median）和最大覆盖模型（maximalcovering）。容量限制模型，目前还不成熟，竞争模型更具有特殊性。2矩阵算法区位模型根据设施点是在一个连续平面上随机分布，还是只能分布在网络上的固定位置（网络顶点）可以分为平面区位模型和网络区位模型，前者设施点的位置在平面上不受任何限制。网络区位模型是平面区位模型的扩展，更具有实用性。网络由结点、连接和连接长度表示，结点就是网络上的端点，连接就是两个网络结点之间的连线。网络区位模型的需求点分布在结点上，可以证明，满足总距离最短的设施点必定在网络结点上，这就要首先计算各结点之间的最短距离，以便应用距离最短原则确定设施结点。从算法研究的角度考虑最短路径问题通常可归纳为两大类：一类是所有点对之间的最短路径，另一类是单源点间的最短路径问题。Dijkstra算法是解决单源点间最短路径问题比较经典而且有效的算法，但在网络模型中往往要求任意两点之间的最短距离，这时采用矩阵算法比较简单有效。矩阵算法是利用矩阵来求出网络的最短距离矩阵。假设×()ijnnDd是带权无向图的邻接矩阵，定义ijd为图中两相邻点的距离，若i与j不相邻，令ijd，则矩阵D表明从i点到j点的直接最短距离。但从i点到j点的最短路不一定是i→j，可能是i→l→j，i→l→k→j，或i→l→…→k→j。先考虑i与j之间有一个中间点的情况，则ijd的最短距离应为1122min{,,,}ijijikkjdddddd，这里11ijdd表示从结点i经过中间点1到结点j的路径长度，22ijdd表示从结点i经过中间点2到结点j的路径长度，其余各项的意义与此相同，都表示从结点i经过一个中间点到结点j的路径长度，ijd取它们中的最小值，为此可以构造一个新的矩阵(1)D，令(1)D中每个(1)min{}ijikkjddd，则矩阵(1)D给出了网络中任意两点之间直接到达和包括经一个中间点时的最短距离。再构造矩阵(2)D，令(2)(1)(1)min{}ijikkjddd，则(2)D给出网络中任意两点直接到达，及包括经过一至三个中间点时的最短距离。一般地有()(1)(1)min{}kkkijikkjddd，矩阵()kD给出网络中任意两点直接到达，经过一个、两个、…、到(21)k个中间点时比较得到的最短距离。设网络图有p个点，则一般计算到不超过()kD，k的值按下式计算：121221kkp即lg(1)1lg2pkk如果计算中出现(1)()mmDD时，计算也可结束，矩阵()mD中的各个元素值即为各点间最短距离。3应用实例案例网络中的服务及设施布局长虹街道近年新建了11个居民小区，各小区的大致位置及相互间的道路距离（单位：100m）如图1所示。各居民小区居民数为：○13000，○23500，○33700，○45000，○53000，○62500，○72800，○84500，○93300，○104000，○113500。试帮助决策：在11个小区内准备共建一套医务所、邮局、综合超市等服务设施，应建于哪一居民小区，使对居民总体来说感到方便。图1解：（１）用矩阵算法求各点之间的最短距离。定义D为图1的邻接矩阵，ijd为图中两相邻点的距离，若i与j不相邻，令ijd=∞，由此0468407570656505665048654078045684045674065065660D(1)0411611812134075101212111170116514126511059106101111106504128612125940117138121012048591211146811404951210678401261359120611121395660D(2)04116111581216131740751012121115171611701165181412231865110591061015111110650412861712151259401511719138121810121504859121114681140495161512106784012613172315171959120617161811121395660D(3)(2)DD(2)D中的元素(2)ijd表明网络图中从i点到j点的最短距离。（２）将计算得到的(2)D的第一行数字乘以居民小区○1的居民数，则乘积数字为假定服务设施建于各小区时，小区○1居民获取服务时单程所走路程。将(2)D中第二行数字乘以小区○2的居民数，得服务设施建于各小区时，小区○2居民获取服务时单程所走路程。依次类推可计算得到表1。表1最下面一行为各列累加数字，表示若服务设施建于第i个小区时，11个小区居民累计的获取一次服务单程所走路程。表1设施建于各小区时居民获取服务所走路程Table1Thepaththattheresidentsgetserviceswhenthefacilitiesarebuiltineachlocation○1○2○3○4○5○6○7○8○9○10○11○1012000330001800033000450002400036000480003900051000○2140000245001750035000420004200038500525005950056000○3407002590004070022200185006660051800444008510066600○4300002500055000025000450005000030000500007500055000○5330003000018000150000120003600024000180005100036000○6375003000012500225001000003750027500175004750032500○7224003360050400280003360042000011200224001400025200○8540004950063000270003600049500180000180004050022500○9528004950039600330001980023100264001320003960019800○10520006800092000600006800076000200003600048000024000○11595005600063000385004200045500315001750021000210000∑395900379500451000300200324600398600352000285700339800472200388600由表中累加数知，该服务设施应建在第8个小区，对居民总体来说感到方便。４结语对于只包含1种设施的区位选择是比较单纯的，同时有好几种设施的布局选址问题就复杂得多。这时要对各种各样设施的区位进行组合，划定各自的服务圈范围，考虑把综合最优作为衡量指标。这时可采用近似探索式算法或遗传算法等，借助计算机来进行最优设施的选址。参考文献[1]张伟，頋朝林．城市与区域规划模型系统[M]．南京：东南大学出版社，2000：96－102．[2]叶嘉安，宋小冬等．地理信息与规划支持系统[M]．北京：科学出版社，2006：104－123．[3]ChurchR．1999．LocationmodelingandGIS．In：LongleyP，GoodchildM,MaguireDandRhindD，(ed)．GeographicalInformationSystems，Volume1，PrinciplesandTechnicalIssues．SecondEdition．NewYork：JohnWileyandSons．293~303．[4]刘湘南，黄方等．GIS空间分析原理与方法[M]．北京：科学出版社，2005：154－157．[5]胡运权等．运筹学基础及应用，北京：高等教育出版社[M]．2005：158－176．[6]陈忠暖，阎小培．区位模型在公共设施布局中的应用[J]．经济地理，2006，26(1)：23－26．StudyonLocation-AllocationModelBasedonMatrixAlgorithmXUXiang-ping(SchoolofMathematics,PhysicsandSoftwareEngineering,LanzhouJiaotongUniversity,Lanzhou730070,China)Abstract:Location-AllocationModelismainlyd