耦合優化蟻群算法與P-Median model 的選址模型設計

顧梓程，胡新玲

（新疆大學 建筑工程學院，新疆 烏魯木齊 830017）

0 引言

人民運動需求令運動場所在城市的規劃中占有一定的比重，其選址關系到城建部門對于公共設施投入成本以及城市人民生活質量問題[1]。

蟻群算法經過20 多年發展，在理論及應用研究上已取得巨大進步。它屬于一種啟發式算法，目前較多學者關注蟻群算法的路徑規劃應用[2-4]，也有學者針對利用蟻群算法實現城市設施的優化選址問題展開研究[5-6]。P-Median model 是依靠ArcGIS 構建網絡分析數據集，模擬現實交通路網并結合具體服務范圍、設施數量、需求點分布情況等因素實現對設施點布局的分析[7]。

雖然蟻群算法可實現分布式計算，但其在進行路徑規劃時具有一定的隨機性[8]，搜尋速率低且易受到需求點人口、出行時間、路況等現實條件的限制，導致精確性不足，P-Median model 可以很好地模擬現實情況對具體路網進行分析，由于該模型的最終目標是使得總出行路徑最短，因而那些極少數位置偏遠的用戶會被犧牲[9]，蟻群算法可以很好地解決這個問題。為此本文在通過優化蟻群算法與P-Median model 融合的基礎上設計了新型設施選址模型，通過蟻群覓食現象進行仿真測試，從而選出使服務區覆蓋范圍最大、可達性最高、路徑成本最低的設施點，降低公共設施投入以及運動人群的出行時間成本，為解決實際問題提出新思路。

1 蟻群算法及P-Median model

1.1 蟻群算法

蟻群算法最早是由意大利學者M.Dorigo 于1991 年提出的一種群智能算法，它是由一群有輕微智能的個體通過相互協作而表現出的智能行為，螞蟻在前往一個地點覓食時，會分泌信息素來引導同伴前往目的地，隨著螞蟻數量的增加，該路徑信息素濃度增大使所有螞蟻沿著此路徑行走，通過這種反饋機制定位最優路徑，如圖1所示。

圖1 蟻群算法示意圖

n只螞蟻從蟻穴A點向食物點E出發，再將食物搬運返回蟻穴A，出發的蟻群理想化分別分為2只螞蟻沿著ABCDE和ABFDE兩條路徑行走，路徑選擇概率均為12，根據時間的變化，較短路徑BCD上停留蟻群信息素濃度大于較長路徑BFD蟻群信息素濃度，導致蟻群選擇路徑BCD的概率增大，23 只螞蟻沿著路徑BCD行走，得到最優路徑ABCDE。

在傳統的蟻群算法中，螞蟻去往地點j的概率以及信息素濃度值的演化模型由式（1）～式（3）表達：

式中：τ為信息素濃度值；φ為能見度值；α、β分別代表信息素濃度的控制系數以及能見度權重，在進行最優解算過程中，其數值選擇起關鍵作用，當α=0 時螞蟻完全根據地點距離做選擇，會形成每一步的最優解，當β=0時，螞蟻完全根據信息素的濃度大小做判斷，使路徑快速收斂，很難達到最優解；由決定最終迭代計算去往下一站的概率；t為當前路徑濃度值；ρ為信息素揮發常數；Δτ為上次路徑ij循環后信息素變化值；Lk為總路程。到此就可以清晰直觀地看出，當總路程縮短時，上次路徑ij循環后信息素濃度變化值會增大，輸出最優解。

1.2 P-Median model

在實際情況中烏魯木齊市研究區域存在高架橋與環形道路，道路情況復雜，如果將覆蓋范圍最大化會存在與實際問題不符的情況。該模型根據所給設施點數量選擇設施空間位置，使范圍內所有用戶達到與其最近的設施點距離成本之和最小的目的，使得總出行代價達到最小[10]。利用位置分配工具評價設施點位置的空間布局是否合理，模擬特定設施點及服務人群，在設施點和需求點之間達到最優可達性，對服務輻射范圍和通行成本進行分析，從而篩選出設施最優布局位置。模型如下：

式中：ρab為所有節點阻抗之和；Nab為節點對（a,b）路徑上所有路段阻抗；xi為路段上到第i個節點所遇阻抗，可用時間表示；p為所有節點數之和。

1.3 蟻群算法與P-Median model 的融合

對于蟻群算法改進問題就是在一定條件下尋找最優方案，使所用功能指標達到最優。首先蟻群算法的核心求的是最短路徑，就是所有螞蟻經過路線組合的最小值，根據P-Median model 求得ρab最小值，針對滿足顯示需求條件的組合模型，將初始信息素與ρab的最小值進行結合，對蟻群算法的搜索效率以及精確性提出改進，如式（5）所示：

式中：ρab為最小阻抗模型下a點到b點所有距離；minρab為最短距離。ρab大小與初始信息素τij(0)大小成反比，通過加入最小參數值，利用比值關系反映路徑選擇，使組合的參數值更加適合現實條件，并提高了搜尋效率，降低出行成本。

2 選址模型的設計

2.1 目標函數的建立

由于蟻群算法依賴于對目標函數計算所獲得的自適應值來運行，通過設計適合本研究的兩種變量構造目標函數，將目標函數作為基于改進蟻群算法上的運動場所選址模型性能標準是有必要的。運動場所的合理選址是為了解決人們對于不同時段能夠實現運動自由以及節省時間成本的需求并滿足交通便利原則的問題，應該滿足以下兩點要求：

1）各運動場所容納的人口之和應大于服務半徑覆蓋區域內需求點包含有運動需求人口之和。

2）服務半徑覆蓋內需求點至運動場所距離成本最小。

根據要求，目標函數設定為：

式中：Darea為柵格面積；C1為人口相對柵格面積系數；U為無運動需求人數柵格面積；Dp為人口密度；f1(x)＞1代表各運動場所容納的人口之和大于有運動需求人口之和，以滿足第一個條件；f2(x)中應用到了曼哈頓距離，也稱城市街區距離，是一種非直線距離，直接引用AB這條線的歐氏距離，必須要進行浮點運算，該運算速度緩慢并且容易有誤差，而用AC和CB這兩條線，則只要計算加減法，大大提高了運算速度，誤差不隨著計算次數的累計而增加[11]；min|x1k-x2k|代表f2(x)中兩個n維向量a與b間的最小距離，滿足第二個條件；pnums-1為除當前運動場所位置點之外其他需求點個數；C2為目標函數f2(x)的系數。

2.2 選址模型構建

柵格數據由柵格單元排列表達，柵格行列坐標可與其他坐標系變換的特性使其適用于遙感影像存儲和管理。在獲得研究區域柵格數據后，將研究區域分為L×L的柵格作為蟻群待搜尋目標，通過研究要求設定目標函數后進行分析，利用蟻群算法與最小化阻抗模型進行耦合，將蟻群信息素賦值為1，每個柵格像元被選擇概率都相等，進行N次迭代后，隨著信息素的疊加，每個柵格像元分為不同濃度信息素，隨著蟻群最優路徑的確定最后對柵格上留下的信息素濃度進行排序，取概率值最大的柵格像元作為最優設施點布設位置，選址模型工作流程如圖2 所示。

圖2 選址模型工作流程圖

詳細步驟如下：

1）進行變量參數初始化，同時設定螞蟻數量k以及目標函數f1(x)、f2(x)的模型設定值n1和n2。

2）對螞蟻數量賦值為1 并置于初始化鄰域，此時螞蟻按照模型公式（1）的概率移動，使螞蟻數量進行k+1 的疊加并進行循環運算。

3）禁忌表初始化，根據公式（5）設定最小參數ρab，計算得到τij(0)后更新禁忌表。

4）根據所得結果判斷提取柵格蟻群殘留信息素濃度是否為MAX，否，則返回步驟3）循環執行。

5）計算目標函數值f1(x)、f2(x)更新信息素。

6）判斷目標函數值f1(x)、f2(x)是否小于模型設定值n1和n2，否，則返回步驟2）循環執行。

7）f1(x)、f2(x)小于模型設定值n1和n2，就用f1(x)、f2(x)替換n1和n2，并輸出蟻群信息素濃度殘留最大的柵格像元位置，否，則返回步驟4）循環執行。

3 數據與研究區域

3.1 數據來源

1）點位數據來源于OSM平臺，包含小區信息及點位信息、分布路網數據、道路長度信息、道路節點屬性和部分建筑屬性，人口數據取自國家統計局第七次人口普查[12]。

2）根據國體委運動場所管理規定：在駕車或騎車15～20 min 內所經過的最短路程為最大阻力值。

3）《道路通行能力手冊》指出，普通人在人行道步行的速度為1.52 m/s。

4）根據國家體育總局發布的國家公共體育設施基本準則中運動場所建設的標準，大型全民健身活動中心要求建筑面積為8 000～12 000 m2，室內、外體育場地面積不宜小于5 000 m2；游泳館要求泳池面積不低于500 m2。

5）以《烏魯木齊市城市社區健身人群體育鍛煉情況調查與分析》中所采取的三種統計方法得到的健身人群年齡分布占比為依據，取平均年齡25～55 歲為健身主要人群年齡段[13]。

6）根據烏魯木齊市人口年齡分布統計數據，中長期有運動需求的人口按照常駐人口的30%～40%計算，為了使得人口覆蓋最大化，采取40%作為計算值[14]。

根據以上要求，用高德SDK 管理平臺調用API 接口檢索研究區域所有的運動場所，通過Java 將所得文件批量化處理后，最終得到符合數據要求的研究區域內的設施點位信息需求點人口數據見表1。

表1 需求點人口信息

3.2 研究區概況

烏魯木齊市的天山區、水磨溝區、新市區、沙依巴克區，面積約1 021.56 km2。由于本研究選取人口活動分布廣泛的區域進行研究較具有實際意義，通過在GeoSpatialDataCloud 平臺下載的夜間燈光遙感數據繁衍人口密度，用ArcGIS 將新疆2022 年夜間燈光遙感柵格圖與烏魯木齊市行政邊界進行掩膜提取得出結果圖進行投影，根據反映得出的人口活動分布圖選擇的研究區域如圖3 所示。

圖3 研究區域圖

由圖3 看出，該市人口活動主要分布在天山區、水磨溝區、新市區和沙依巴克區4 個下轄區的交匯處，以轄區交界點為中心的人口密集地區范圍作為研究區域更具有研究意義。

4 實驗與分析

4.1 交通路網可達性

可達性目的是表達人到達某地的潛力，為一種基于固有設施的供給側的特征屬性表達，其取決于路網密度、路網覆蓋度和路網與城市土地使用協調度，路網密度反映路網數量上的總體建設水平，也反映路網的平均間距[15]。

對研究區域路網數據建立網絡數據集，利用出發點-目的地建立OD 成本矩陣并對其進行求解，得出可達性數值范圍并進行可視化如圖4 所示。

圖4 研究區域路網可達性分布

可達性計算公式為：

式中：D為路網可達性；T為時間成本；N為總OD 路徑數量。[0.00，3.12]、[3.13，6.15]、[6.16，9.19]、[9.20，12.23]、[12.24，15.27]可達性數值范圍覆蓋了研究區域的最大范圍，令每個區間設定評價權重β0分別為0.25、0.20、0.15、0.10、0.05。對于時間的加權公式為：

式中：tc為加權后道路節點的通行時間；β0為不同區間段可達性賦權。

4.2 柵格位置提取

采用Python 語言進行優化實驗，按照經驗取值方法設置蟻群算法參數，設置信息素濃度τ=10 000，信息素的揮發系數ρ=0.01，蟻群中螞蟻的數量初始化設定為k=1，信息素啟發因子α=1。選址模型提取柵格衛星影像圖如圖5 所示。

圖5 柵格選取圖

從圖5 的結果得知，模型選址結果基本符合實際情況，該點位于人民路與新華南路的交匯處，人口活動密度較大的南門與北門均在所選設施點附近，兼顧了距離成本最小目標與容納的人口數量目標。

4.3 模型分析結果對比

用ArcGIS 對研究區進行空間柵格數據信息編輯，利用選址模型做模擬計算，可以直觀顯示計算數據結果。經過最小化阻抗模型A 與文獻[16]的最大化覆蓋模型B以及本文設計的選址模型C分析得出運動場所服務半徑覆蓋對比如圖6所示，需求點覆蓋具體情況如表2所示。

表2 不同模型下選址需求點覆蓋情況個

將不同模型分析結果進行對比，加入選址系統挑選的最優選址點相比直接采用最小化阻抗覆蓋范圍模型得到的覆蓋率上升10.42%；相比最大化覆蓋模型上升6.95%。隨著體育設施選址個數的增加，具體選址地址基本考慮了距離目標和人口數量目標，在整體上選址效果良好，與實際情況相符。

設施點建設的不同位置與不同的路徑規劃關系到不同服務半徑需求點個數，在C 模型僅添加一個設施點的情況下，三種模型在不同服務半徑覆蓋率雷達圖如圖7 所示。

圖7 三種模型下不同服務半徑覆蓋率雷達圖

由圖7 可知：在500 m 之內需求點覆蓋率由高到低排序依次為B＞C＞A；在500～800 m 之內需求點覆蓋率由高到低排序依次為B＞A＞C；在800～1 100 m 之內需求點覆蓋率由高到低排序依次為C＞A＞B；在所規劃設施點覆蓋范圍之外的需求點覆蓋率由高到低排序依次為A＞B＞C。

總體而言，C 模型相對于A、B 模型總體覆蓋率效果是最佳的。

5 結語

在人民運動需求上升的背景下，選擇好相應的城市體育設施場所位置，平衡城建部門的公共設施投入成本與人民生活質量之間的關系對一個城市的規劃是尤為重要的。用傳統蟻群算法解決選址問題多基于其隨機性與歷史經驗，導致結果與現實情況偏離并難以獲得最優選址結果。本文在利用優化蟻群算法與P-Median model 進行融合的基礎上構建了新型選址模型，研究了如何提高城市中運動場所對需求點服務半徑覆蓋范圍，分析了如何優化選址的過程。將兩種不同優化選址模型與本文所設計的選址模型分析結果可視化進行對比，結果表明本文所設計的選址模型在只增加了一個設施點的情況下，服務覆蓋率均大于另外兩個優化選址模型，整體而言效果明顯，但仍有部分需求點未在服務半徑覆蓋范圍之內，在分級覆蓋范圍內的500 m、800 m 這兩種較優的覆蓋范圍內需求點個數較低，后續研究希望繼續改進解決此類問題，在研究基礎上對已設計的模型繼續優化，達到更佳效果。

注：本文通訊作者為胡新玲。