郭文月，劉海硯，余岸竹，劉晨帆

（信息工程大學 地理空間信息學院，河南 鄭州450001）

地理位置通常被視為影響服務設施運轉(zhuǎn)效率的關鍵因素［1］，良好的地理位置有助于保證成本穩(wěn)定低廉，提高設施點對需求點的吸引力?？臻g分析是依賴分析對象位置信息的技術(shù)［2－3］，空間位置分配根據(jù)地理實體的空間位置、空間關系和屬性特征，結(jié)合用戶需求，研究和確定空間對象的最優(yōu)位置和資源分配，為用戶提供輔助決策依據(jù)。位置分配的目的是以合適的方式定位設施點，從而保證最高效地滿足需求，顧名思義，位置分配是定位設施點的同時將需求點分配給設施點的雙重問題。

解算整體最優(yōu)空間位置分配問題的方法主要有啟發(fā)式 算 法［4－6］、蟻 群 算 法［7－8］等。這 些 算 法 從 不同角度考慮空間位置分配問題的影響因素，并以總成本最小為原則實現(xiàn)對整體最優(yōu)空間位置分配問題的解算，但在解算效率、參數(shù)選取等方面仍可進一步改進。本文在解決整體最優(yōu)空間位置分配問題時，將通過設施點和需求點間的網(wǎng)絡元素所要消耗的成本整合為阻抗，用阻抗大小作為影響成本的因素，并在解算時引入等級劃分的方法，提出基于阻抗等級劃分的空間位置分配算法，有效提高解算效率。

1 整體最優(yōu)位置分配及算法

整體最優(yōu)空間位置分配問題是以指定區(qū)域內(nèi)若干需求點與設施點間的整體成本最優(yōu)作為求解標準，實現(xiàn)整體資源配置最佳化，旨在解決多條件、大范圍、多數(shù)量的空間點位分配分析問題，用于設施點的宏觀部署和整體利益優(yōu)化。目前，常用于解決此類問題的算法——貪婪取走啟發(fā)式算法，該算法需多次掃描比較數(shù)據(jù)集，在運算效率方面還有較大提升空間。

1．1 基于阻抗的整體最優(yōu)位置分配表達

判斷某一候選設施點的優(yōu)劣時需要考慮的影響因素隨用戶需求的不同而不同，總體來說，用戶希望盡可能減少從設施點到需求點的成本消耗，因而將通過設施點和需求點間的網(wǎng)絡元素所要消耗的成本整合為阻抗，將其表示為

式中：i，j為需求點和設施點序號；Nj為設施點；x為需求點為設施點與需求點間可行路徑長度；ωi為需求點權(quán)重；fij為設施點與需求點間單位路程運費。設施點對需求點的吸引力與兩點間的阻抗成反比，阻抗值越大，表示該設施點對某需求點的吸引力越小。在可提供貨物與服務的候選設施點以及消耗這些貨物及服務的需求點已經(jīng)給定的情況下，從候選設施點中選取用戶指定數(shù)量的點作為設施定位點，并將需求點分配給選出的設施點，使得各個需求點與所分配到的設施點間阻抗總和最小?；谧杩沟恼w最優(yōu)空間位置分配問題表示

式中：m為需求點的數(shù)量；k為最終確定的設施點數(shù)量，且由用戶指定；nk為分配到第j個設施點的需求點數(shù)量；δ為分配時允許的最大阻抗。整體最優(yōu)空間位置分配問題是選擇候選設施點集N的子集P，使得所有需求點到其分配設施點之間的阻抗總和最小。

1．2 貪婪取走啟發(fā)式算法

貪婪取走啟發(fā)式算法是解決上述整體最優(yōu)空間位置分配問題的常用算法之一［5－7］，其解算步驟：

步驟1：假設設施定位點集合P＝N，即選中所有候選設施點；

步驟2：將各個需求點分配給與該需求點間阻抗最小的候選設施點；

步驟3：選擇并取走一個候選設施點Nj，將其取走并將其對應的需求點，按照阻抗最小原則分配給其它候選設施點，總阻抗增加值最??；

步驟4：從P中刪除點Nj，重復步驟3，直到剩余的候選設施點數(shù)目與用戶需求相同。

貪婪取走啟發(fā)式算法從候選設施點集合中逐一刪除對最優(yōu)整體阻抗值影響最小的候選設施點，直到剩余的候選設施點個數(shù)滿足用戶需求。這種算法保證了每次迭代時的整體阻抗值最小，有效實現(xiàn)設施點的選取，但該算法每排除一個候選設施點就需要至少一次掃描數(shù)據(jù)集，當候選設施點數(shù)目遠遠大于需求設施點數(shù)目時，該算法的解算效率明顯過低。為提高整體最優(yōu)空間位置分配問題的解算效率，本文在貪婪取走啟發(fā)式算法基礎上提出一種基于等級劃分的解算方法。

2 空間位置分配方法

本文采用等級劃分的方法，將候選設施點與需求點間的阻抗按照值相近的原則聚合為若干等級，在求解計算時，用阻抗等級替代阻抗值，這樣的等級劃分方法實現(xiàn)了在保證整體最優(yōu)的前提下，較大程度地減少了空間位置分配問題求解的運算量。

2．1 阻抗等級劃分

采取等差劃分的方法，假設n個候選設施點與m個需求點間所有小于阻抗中斷的阻抗值為｛d11，d12，…，dnm｝，找出其中的最大值dmax和最小值dmin，根據(jù)阻抗值大小和用戶需要選擇的設施點數(shù)目k，確定劃分阻抗等級數(shù)目h，那么每個阻抗等級跨度

根據(jù)等級跨度，確定每個阻抗等級的分界值，最終將阻抗值劃分為h個等間隔的區(qū)間：

根據(jù)這些區(qū)間，將阻抗值聚合為D1，D2，…，Dh個等級，在求解計算中用阻抗等級代替阻抗值。

2．2 求解算法

基于阻抗等級的空間位置分配的解算思路：首先，根據(jù)各候選設施點和需求點間的阻抗值大小，以及設施點的數(shù)目將阻抗值劃分成若干阻抗等級。解算時，先將各個需求點分配給阻抗等級最低的候選設施點，再依次選擇并取走對總阻抗等級影響最小的候選設施點，并將其分配到的需求點分配給其它候選設施點，直至候選設施點數(shù)目滿足用戶需求，具體解算步驟為

步驟1：設候選設施點集合 N＝｛N1，N2，Nj，…，Nn｝，其子集 P＝｛P1，P2，…，Pk｝為最終確定的設施點集合，設需求點集合為x＝｛x1，x2，xi，…，xm｝，為每個候選設施點創(chuàng)建一個需求點分配集合Xj，用以記錄分配給該候選設施點的需求點位置和數(shù)目，初始Xj＝φ；

步驟2按照各候選設施點和需求點的阻抗值大小，將所有小于阻抗中斷的阻抗值進行等級劃分，聚合成h個阻抗等級，按照阻抗值從小到大依次為D1，D2，…，Dh，大于阻抗中斷的阻抗等級表示為∞；

步驟3：標記所有D1級阻抗，將需求點分配給D1級阻抗對應的候選設施點，若D1級阻抗對應多個候選設施點，則其為比較真實的阻抗值，選擇真實值最小的候選設施點，并更新候選設施點Nj的需求點分配集合Xj；

步驟4：排除所有需求點分配集合為空的候選設施點，判斷選出的設施點數(shù)目是否滿足用戶需求，則進行步驟5，否則，除去候選設施點Nj，將分配集合Xj中的需求點分配給其它候選設施點，總阻抗等級增加最小，直到剩余的候選設施點數(shù)目滿足用戶需求；

步驟5：結(jié)束計算，最終確定的設施點為P1，P2，…，Pk，各需求點的分配情況用分配集合X1，X2Xk表示。

3 實驗與結(jié)果分析

3．1 模擬數(shù)據(jù)驗證

為驗證本文提出算法的合理性和高效性，進行模擬實驗。選取平面區(qū)域內(nèi)任意分布的10個點作為候選設施點，同一區(qū)域內(nèi)任意分布的10個點作為需求點，模擬從10個候選設施點中選出3個作為設施定位點，并將10個需求點依總阻抗最小原則分配給這3個設施定位點。在模擬實驗中為10個需求點分別賦予權(quán)重值，使得10個點的權(quán)重相加為1，設單位里程平均運費為5。

10個候選設施點位置如表1所示，10個需求點位置及權(quán)重如表2所示，為充分驗證等級劃分對運算效率的影響，分別將阻抗值劃分為3個等級（三分法）和6個等級（六分法），并與直接運用阻抗值進行計算的貪婪取走啟發(fā)式算法在運算結(jié)果和效率上進行對比。

表1 候選設施點分布位置

表2 需求點位置及其權(quán)重

根據(jù)式（1）計算得到各個設施點與候選設施點間的阻抗值，劃分阻抗等級。兩次不同等級劃分方式的模擬實驗結(jié)果均選取N6，N8，N10作為最終的設施定位點，如表3所示，運算結(jié)果、運用位置與貪婪取走啟發(fā)式算法進行解算的結(jié)果一致，由于基于等級劃分的空間位置分配算法將相近阻抗值聚合為同一等級，并在實際運算中用阻抗等級代替阻抗值進行結(jié)算，因而在排除候選設施點的過程中，比較范圍不再是整個候選設施點集，而是縮小到迭代當時最小阻抗等級對應的候選設施點范圍，這樣既保證了分配需求點時整體阻抗最小，又大大提高運算效率，在模擬數(shù)據(jù)情況下，三分法和六分法對數(shù)據(jù)集的掃描對比次數(shù)分別為基于阻抗值的貪婪取走啟發(fā)式算法的92%和78%左右。當數(shù)據(jù)量較大時，選擇合適的等級劃分可以更大程度地提高運算效率。但并非等級劃分越精細，則解算速度越快，實際劃分等級數(shù)目，根據(jù)用戶候選設施點數(shù)目和阻抗值來確定。

表3 空間位置分配結(jié)果

3．2 模型構(gòu)建與應用

空間分析依賴于空間分析模型，建立空間分析模型的過程是綜合分析處理和應用空間數(shù)據(jù)的有效手段，也是開發(fā)分析決策性GIS不可或缺的步驟［9－13］。為驗證本文提出的空間位置分配算法的可用性，實驗利用Arc GIS提供的可視化模型構(gòu)建工具——Model Builder及編程語言構(gòu)建空間位置分配分析模型。構(gòu)建好的模型如圖1所示，將基于阻抗等級劃分的空間位置分配算法寫入到“位置分配”模塊，其余基礎環(huán)節(jié)直接調(diào)用Arc Tool box工具。

圖1 可視化建模模型結(jié)構(gòu)

利用某地區(qū)道路網(wǎng)絡數(shù)據(jù)和點數(shù)據(jù)，分別選取快遞投送站和重要客戶所在位置作為候選設施點和需求點。該地區(qū)按照行政區(qū)劃可分為10個行政區(qū)域，模擬從248個快遞投送站候選位置中選出10個作為設施定位點，并將208個重要客戶分配到這10個設施點，由于需求點在10個行政區(qū)劃范圍內(nèi)不均勻分布，選出的10個設施點與行政區(qū)劃模糊對應，且這10個快遞投送站到各自分配到的重要客戶的阻抗總和最小。圖2為空間位置分配前候選設施點與需求點的分布情況，圖3為設施點的選取和需求點的分配結(jié)果，解決快遞投送站和重要客戶間基于阻抗的整體最優(yōu)空間位置分配問題。

圖2 需求點與候選設施點分布

為驗證實驗結(jié)果的準確性，將全區(qū)域分為若干小區(qū)域，如圖4所示，每個小區(qū)域內(nèi)包含且僅包含一個已選設施點、分配到的需求點、以及未選中的候選設施點若干。分別將各個區(qū)域中的需求點分配給阻抗中斷內(nèi)除已選中設施點之外的候選設施點，計算總阻抗值，結(jié)果如圖5所示，在每個區(qū)域內(nèi)，第一個值為已選設施點到各需求點的阻抗和，其余點為該區(qū)域內(nèi)未被選取的候選設施點到各需求點的阻抗和，數(shù)值證明，每個區(qū)域內(nèi)已選設施點到各個需求點的阻抗和均小于其它候選設施點到各需求點的阻抗和，因而通過實驗選出的設施點滿足全區(qū)域范圍整體阻抗最小。

圖3 空間位置分配結(jié)果

圖4 設施點及分配的候選設施點

實驗證明，利用Model Buil der構(gòu)建基于阻抗等級的整體最優(yōu)空間位置分配分析模型，此模型可以解決本文提出的算法應用問題。本文提出的利用阻抗等級劃分的空間位置分配方法可應用于多種類型的空間位置分配問題中，用數(shù)值的等級代替數(shù)值進行解算的方法在保證阻抗最小化原則基礎上，縮小比較區(qū)間，能夠較大程度提高問題的解算效率。

4 結(jié) 論

本文探討基于阻抗的整體最優(yōu)空間位置分配問題，提出一種利用等級劃分的空間位置分配求解算法，實現(xiàn)整體最優(yōu)化空間位置分配分析。用阻抗等級代替阻抗值，與貪婪取走啟發(fā)式算法相比，較大程度縮小對比區(qū)間，提高解算速度，實現(xiàn)優(yōu)化服務點部署，并通過可視化建模的方式解決選址中的實際應用問題。但是以下問題需要深入研究：

1）如何根據(jù)用戶需求和實際數(shù)據(jù)，更加合理的確定阻抗等級和聚合區(qū)間；

圖5 各區(qū)域內(nèi)候選設施點與需求點的阻抗和對比

2）本文在進行位置分配分析時，沒有將阻抗中斷之外的需求點分配，而在很多實際問題中，仍需要考慮這些需求點。

［1］ 李煉，余代俊，曾濤．困難地區(qū)大型工程預選址新方法探討［J］．測繪工程，2014，23（1）：61－64．

［2］ 邊馥苓，朱國賓，余潔．地理信息系統(tǒng)原理與方法［M］．北京：測繪出版社，1996：149－172．

［3］ 紀曉東，王雙龍，汪其志．基于工作流的地質(zhì)信息空間分析模型的設計與實現(xiàn)［J］．測繪工程，2010，19（3）：20－23．

［4］ 劉璇．基于GIS的物流配送中心選址方法的研究［D］．長沙：中南大學，2012．

［5］ Arya V，Garg N，Khandekar R et al．Local Search Heuristics for P－median and Facility Location Pr oblems［J］．SIA M Jour nal on co mputering，2004，33（3）：544－562．

［6］ 關懷慶，張畢西，歐江艷．貪婪取走啟發(fā)式算法在離散網(wǎng)絡選址中的研究［J］．系統(tǒng)科學學報，2010，18（3）：49－52．

［7］ Deneubourg J L，Gross S，F(xiàn)ranks N，et al．The Dynamics of Collective sorting robot－like ants and ant－like robot［A］．Proceedings of the 1stConference on Si mulation of Adaptive Behavior［C］．1990：356－363．

［8］ 秦固．基于蟻群優(yōu)化的多物流配送中心選址算法［J］．系統(tǒng)工程理論與實踐，2006（4）：120－124．

［9］ 程滿，梁虹，馮濤．基于空間問題建模概念過程的空間分析建模與實現(xiàn)［J］．計算機工程與設計，2007，28（6）：4042－4045．

［10］方芳，徐世武，萬波．GIS空間分析建模技術(shù)研究進展［J］．測繪科學，2010，35（6）：137－138．

［11］左興東．三維GIS的數(shù)據(jù)結(jié)構(gòu)探討［J］．測繪與空間地理信息，2014，37（7）：120－122．

［12］董孟秋，李景文，張紫萍．基于面向?qū)ο髷?shù)據(jù)模型的地理實體距離度量關系分析方法［J］．測繪與空間地理信息，2014，37（5）：64－67．

［13］周國清，陳昆華，何素楠，等．來賓市巖溶塌陷的時空分布特征分析［J］．測繪與空間地理信息，2014，37（4）：3－7．