改進的容量約束設施區劃模型的算法及應用

吳建軍 孔云峰

關鍵詞：容量約束;改進區劃模型;求解算法;公共服務設施優化

0 引言（Introduction）

公共服務設施空間布局的公平性是指服務的需求者對設施的使用機會是均等的，這也是公共服務設施空間布局的最終目的。公共服務設施空間布局涉及的是復雜空間的設施區位問題，簡單來說就是對設施進行選址定位，具體是利用數學模型和算法尋找復雜問題中的最佳或近似最佳的解答，進而改善或優化現有系統的效率[1-3]。

現階段，國內關于公共服務設施空間布局優化的研究比較豐富，邵暉等[4]、安蕓睿[5]和許翔宇[6]采用各區人口與公共設施數量的比值等方法研究公共服務資源空間分布特征。李旭麗等[7]和羅萌[8]根據以研究區域內的公共服務設施數量與人口數量的供需情況采用對比分析的方法進行了研究。還有學者采用基于GIS的多準則決策分析的最優選址模型等方法進行了分析探討[9-11]。這些研究都是較粗略的定量分析研究。空間布局優化研究所涉及的數據量非常大，目前關于公共服務設施優化布局的研究，已有理論研究者提出了一些數學模型和算法，但由于這些模型和算法屬于NP難問題（NP-Hard），尤其對于中大規模問題，難以獲得精確解，因此，這也是目前國內鮮少研究的領域。

1 經典的CFLP模型算法（Classic CFLP modelalgorithm）

得益于近幾年計算機技術的進步和發展，空間布局規劃問題模型解算效率快速提升，已逐步滿足很多實際應用。基于此，本項目以基本醫療衛生服務設施為具體研究對象，借用經典的CFLP模型，并對模型進行進一步優化，設計、開發出解算工具，為實現公民公平享有公共衛生服務資源、節約政府公共投資提供技術支持。

優化設施布局就要進行精確的定量分析，本研究的算法原理是基于CFLP模型（經典的容量約束設施區位問題），首先令集合I={1，2，…，n}表示n 個候選醫療服務設施的空間位置，設施i（i∈I）有最大接診量Si。令集合J={1，2，…，m}表示m 個需求點，需求點j（j∈J）的就醫服務需求量為dj。空間單元i 與單元j 之間的距離成本為cij。定義布爾型決策變量xij 為是否指派醫療服務設施i 到需求空間j 進行服務，布爾型決策變量yi 表示是否在區位i 上建設醫療衛生服務設施，經典的單源CFLP模型如下：

其中：目標函數（1）最小化設施固定成本和使用服務的旅行成本;約束條件（2）保證每一個空間單元的需求獲得公共服務;約束條件（3）保證每一個服務設施分配的服務量不超過其供給量;條件（4）定義決策變量xij 和yi。

2CFLP模型算法改進原理（Principle of improvingCFLP model algorithm）

經典的CFLP模型沒有考慮設施服務半徑，這會使得部分需求區位距離服務設施過遠，缺少公平性方面的考慮。為克服這一局限，本文提出改進方法，即在模型中引入覆蓋半徑。令覆蓋半徑為?，在約束條件（2）中加入服務半徑限制，見約束條件（5）：

但是，約束條件（5）會導致所需設施數量大幅增加。為平衡服務成本、服務質量和空間公平性三者之間的關系，本文引入最低覆蓋率μ繼續對模型進行改進。在經典模型中增加新的約束條件（6），即設施在服務半徑內覆蓋需求總量滿足最低覆蓋率指標。

考慮到設施建設成本在規劃階段難以精確地估算，可將建設成本設置為一個較大的固定數值CAP，從而將目標函數（1）修改為（7）：

基于上述改進的CFLP模型，本研究進行算法求解的設計。借鑒單源CFLP數學啟發算法進行求解。算法原理概括如下：（1）通過構造啟發式算法獲得問題初始解;（2）從當前解中隨機選擇一個超大鄰域，獲取鄰域內的需求點、當前設施和候選設施集合;（3）構造鄰域內子問題模型，求解模型獲得局部解，并使用局部解更新當前全局解;（4）重復執行“步驟（2）”和“步驟（3）”，直到不能更新當前解。“步驟（2）”能構造一個大鄰域，“步驟（3）”能發現鄰域內的最優解。

模型經以上改進后，所有需求區位都能夠滿足服務半徑的要求。

3 算法應用（Algorithm application）

3.1 軟件安裝

本研究所提算法的求解實質是求解線性規劃問題的最優解。線性規劃是研究線性約束條件下線性目標函數的極值問題的數學理論和方法。Python中有許多第三方的工具可以解決這類問題，本研究采用的是常用的pulp工具包。軟件運行環境為Windows 10。此外，需要安裝Gurobi（全球綜合能力排名第一的數學規劃求解器），獲取Gurobi商業版或學術版軟件，并安裝在運行算法的計算機中。

3.2 數據準備

首先給定城市基本空間單元（500 m×500 m 的網格）、單元內就醫需求數量（居民人數）、候選設施空間位置（醫療服務設施的地點）和設施的最大服務容量（衛生服務中心或衛生院的接診量），其次選擇一定數量的區域內醫療服務設施，滿足所有居民點的就醫需求，并指定服務半徑（?）和需求覆蓋率（μ）要求，研究的最終目標是讓所需要的服務設施的數目（N ）最少，使居民看病就醫的旅行成本最低。

使用ARCGIS 10.6地理信息系統軟件創建醫療服務供應者圖層，在該圖層中保持原有的29個基本醫療衛生服務設施，并在此基礎上于KF市區的基本空間單元中選擇173個候選點，作為備選醫療服務設施的備選點。本算法的目的是快速從候選點中選出最合適的服務設施的空間位置，從而盡可能地使每個居民點距離所對應的衛生服務設施最短，并且不能超過該服務設施的最大服務能力，即獲得最優解。同時，要保證醫療服務設施數量最少。

從ArcGIS 10.6相關圖層導出相應的屬性表，進行整理后最終形成以下文本文件：

應用以上文本文件描述需求點和候選設施點。第1列為點位ID（整數類型），要求ID唯一;第2列為該點位服務需求量（整數類型），在本研究中具體指城市空間單元格的人數;第3、4列為坐標，單位為m;第5列為候選設施點的類型，對于現有的衛生服務中心和衛生院設置為“1”，即必選項，對于其他設施點設置為0;第6列為候選設施投資建設成本，為了盡可能地減少設施數量，設置了一個較大的數值，即1.0e8;第7列為設施容量，備選點為KF市區2021年基本醫療衛生服務設施的平均接診量，現有的衛生服務設施必選點則是該點2021年的實際接診量。

3.3 設施選址計算

本研究的算法使用Python程序設計，調用Gurobi優化求解器求解子問題模型。實驗計算環境為PC個人計算機，配置英特爾Core i5-9400 @ 2.90 GHz六核處理器、16 GB內存和Windows 10操作系統。安裝軟件包括Python 2.7、ArcGIS 10.0和Gurobi 9.5.2。在ArcGIS中準備案例數據，包括城市基本空間單元及其屬性di 和si、單元間距離成本cij 采用兩個單元中心點的直線距離。

研究設置不同的參數，通過程序運行結果分析、總結設施布局優化方案。程序是在Windows命令窗口運行相關命令的。表1至表3是在分別設置了不同的規劃參數即服務半徑（?）和覆蓋率（μ），并設置不同服務設施總數量的情況下，應用改進模型算法得出的服務設施規劃結果的統計。

從表1中可以看出，雖然設置了規劃參數服務半徑為1.0 km和覆蓋率為80%，但是從實際的程序計算結果來看，在新增5個、29個現有設施點必選、共有34個衛生服務設施的限制條件下，滿足規劃參數服務半徑為1.0 km時，其實際的人口覆蓋率μ只有54.14%。

從表2中可以看出，雖然設置了規劃參數服務半徑為1.5 km和覆蓋率為70%，但是從實際的程序計算結果來看，在新增5個、29個現有設施點必選、共有34個服務設施的限制條件下，當滿足規劃參數服務半徑為1.5 km時，實際的人口覆蓋率有70.12%，完全達到了預先設置的70%的人口覆蓋率的規劃參數。

從表3中可以看出，設置了規劃參數服務半徑為1.5 km和覆蓋率為80%，從實際的程序計算結果來看，在保證29個現有設施點必選、不限定設施總數量的情況下，滿足規劃參數服務半徑為1.5 km時，其實際的人口覆蓋率為80.04%，完全達到了預先設置的規劃參數，但是需要新增加18個衛生服務設施點。

圖1顯示的是在現有的29個基礎衛生設施的基礎之上，根據程序運算優化的結果，增加5個衛生服務設施的空間位置，城市空間單元選擇500 m×500 m的網格，并刪除50人以下的低密度人口區域網格。

圖2顯示的是限定34個設施（新增5個），優化新增衛生服務設施后的泰森多邊形，平均就醫距離為1.74 km，平均每個設施點服務2.80萬人，最遠就醫距離為10 km，占比為0.067 6%，約642人，醫療衛生設施利用率較高。

不限定衛生服務設施總數的規劃方案如圖3所示，該方案沒有限定衛生服務設施數量，根據程序計算得出共計47個衛生服務設施（新增18個），平均就醫距離為1.38 km，平均每個設施點服務2.02 萬人，最遠就醫距離為9 km，占比為0.057 7%，約549人，醫療衛生設施利用率較低。

4 結論（Conclusion

文章分析了經典的CFLP模型存在的局限性，為克服這一局限，提出可引入覆蓋半徑?、最低覆蓋率μ、設施建設成本CAP 對模型進行改進，實驗結果表明，與傳統模型算法相比，該模型算法兼顧了服務成本、服務質量和空間公平性三者之間的關系，改進的CFLP模型算法更加科學、合理，實用性更強，也可以應用于公共服務體系中的其他領域，如義務教育、公共文化設施等公共服務空間可達性評估，以利于優化布局。

該模型未來可以考慮引入居民的性別、年齡、職業、需求偏好等參數，進一步提高其準確性，為構建高質量和人性化的公共服務體系提供更可靠的技術支持。