一種基于阻抗等級劃分的整體最優空間位置分配方法

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

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

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

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

1 整體最優位置分配及算法

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

1．1 基于阻抗的整體最優位置分配表達

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

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

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

1．2 貪婪取走啟發式算法

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

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

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

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

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

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

2 空間位置分配方法

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

2．1 阻抗等級劃分

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

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

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

2．2 求解算法

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

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

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

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

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

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

3 實驗與結果分析

3．1 模擬數據驗證

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

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

表1 候選設施點分布位置

表2 需求點位置及其權重

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

表3 空間位置分配結果

3．2 模型構建與應用

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

圖1 可視化建模模型結構

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

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

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

圖3 空間位置分配結果

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

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

4 結 論

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

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

圖5 各區域內候選設施點與需求點的阻抗和對比

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

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

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

［3］ 紀曉東，王雙龍，汪其志．基于工作流的地質信息空間分析模型的設計與實現［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］ 關懷慶，張畢西，歐江艷．貪婪取走啟發式算法在離散網絡選址中的研究［J］．系統科學學報，2010，18（3）：49－52．

［7］ Deneubourg J L，Gross S，Franks 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］ 秦固．基于蟻群優化的多物流配送中心選址算法［J］．系統工程理論與實踐，2006（4）：120－124．

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

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

［11］左興東．三維GIS的數據結構探討［J］．測繪與空間地理信息，2014，37（7）：120－122．

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

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