基于遺傳算法的景區公共設施和配送中心選址

張鑫 李柯宜 趙越

摘?要：2022年6月，國家推出《“十四五”國民健康規劃》，提出扎實推進健康中國建設。為響應政策號召，解決居民對醫療物資和服務等公共衛生設施日常和應急需求，有必要對其選址進行研究。本文利用POI興趣點，基于聚類分析和改進的遺傳算法構建數學模型，實現多目標的選址任務，并創新地進行組合優化?？紤]到南京市景區較多，本文以風景名勝相關數據為需求點，并對其進行實證分析，最終得到了541個設施選址點和180個醫療中心選址點，實現“一站多點”的選址模式，從而縮小區域間醫療資源配置、服務能力和健康水平差異。

關鍵詞：多目標規劃；POI數據；聚類分析；遺傳算法

中圖分類號：F25?????文獻標識碼：A??????doi：10.19311/j.cnki.16723198.2023.19.015

1?引言及文獻綜述

近年來，重大公共衛生事件頻發，對各國人民的安全和社會的經濟造成了嚴重的影響，如何應對這些緊急事件已成為了國內外學者探討研究的焦點。隨著我國《“十四五”國民健康規劃》的提出以及對全面推進健康中國指導思想建設的強調，基層的醫療衛生系統的解決刻不容緩。與此同時，隨著旅游業的復興和游客數量的暴增，景區是否能在短時間內及時提供物資和援助直接關系到應急醫療工作的時效性及準確性，因此科學正確地對物資發放點和醫療站進行選址非常關鍵。

從國內外相關學者的研究進展來看，公共設施選址問題涉及大數據的應用，汪曉春、熊峰等人（2021）在武漢市養老設施規劃布局的實例研究中，通過對Python導出并轉換格式的POI數據進行聚類分析和網格分化，結合機器學習算法，得到了養老設施的選址。由此可見，POI信息點為規劃人員在數據挖掘上提供了更全面和科學的方式，優化了選址規劃的過程，使結果更具可靠性和參考價值。在基礎經典選址模型研究中，張金鳳（2021）在其論文研究中提到，選址問題的目標分為成本型、利潤型、需求型目標、環境型目標四類。而隨著選址問題研究的深入，對選址有了更高的要求，需要同時兼顧多種目標，面對優化改進問題，郭昌勇（2022）在覆蓋模型的基礎上，利用非支配排序遺傳算法，以效益最大化和覆蓋水平最大化為優化目標，建立了多目標二次規劃模型。整理現有研究發現，鮮少有文獻將設計醫療設施類選址的方法論科學系統的搭建起來并加以定量數據分析。

本文將以南京市風景名勝作為研究對象，在結合收集南京市POI數據的基礎上，運用改進的遺傳算法在規定的參數下進行數學建模反復迭代直到得出滿足目標的解。

2?理論分析

2.1?數據來源

根據研究需求，POI數據是描述城市各類功能空間分布的基本數據，通常分為公共設施、科教文化服務、風景名勝、公司企業等。本文所使用的南京市POI數據是從高德地圖為開發者所提供的GIS獲取的，如表1所示，為統計得到的南京市各區POI興趣點個數，其中江寧區數據最多，秦淮，玄武和鼓樓區相對較多，與其行政區面積和發展水平有關。

2.2?聚類分析

聚類分析是一種典型的無監督學習，用于對未知類別的樣本進行劃分，將樣本中的數據按照一定的規則劃分成若干個類族，把相似的樣本聚在同一個類簇中，把不相似的樣本分為不同類簇，從而揭示樣本之間內在的性質以及相互之間的聯系規律。不同的聚類方法適用于不同的條件和數據集。

（1）K-means聚類：計算樣本點與類簇質心的距離，與類簇質心相近的樣本點劃分為同一類簇。K-均值通過樣本間的距離來衡量它們之間的相似度，兩個樣本距離越遠，則相似度越低，否則相似度越高。該方法適用于較大的數據集，且對K的取值很敏感。

（2）密度（DBSCAN）聚類：密度聚類算法利用密度思想，將樣本中的高密度區域劃分為簇，將簇看作是樣本空間中被稀疏區域（噪聲）分隔開的稠密區域，通過局部密度和局部距離的計算，實現自適應挑選聚類中心的功能，避免在一處很密集的地方有多個中心，又賦予了偏遠地區中出現中心的可能。

3?模型設計

3.1?數據處理

根據南京市各區面積和人流量，通過SPSS聚類分析將各區的POI信息點數量按比例縮減至算法可簡便運行范圍內，保留下來的有效數據既可以表現各區數據分布特點，也避免了接下來算法運行中因數據過于密集而無法合理設置參數的問題。

要得到準確的設施備選點坐標，需要通過密度聚類對現有坐標點進行分析，根據所得簇類數確定備選設施點的個數。將上述所得均值聚類中心點代入MATLAB分析計算，在噪聲點數最小的情況下，可得結果為1087簇，即再進行均值聚類時，應當輸入的K值為1087，最終可以得到1087個聚類中心的坐標點，這1087個坐標點即為設施選址的備選點。

3.2?多目標優化算法-遺傳算法的應用

基本遺傳算法是一種通過模擬自然進化過程搜索最優解的方法。遺傳算法通過二進制編碼的“染色體”表示，將原問題的結構變換為染色體的位串結構，從初始化一個編碼表示基因種群出發，采用優勝劣汰、適者生存的自然法則選擇個體，對個體的適應性進行度量，并通過雜交、變異等選擇操作來產生新一代種群，并反復地迭代進化，直到滿足目標為止。

針對此項目研究，做出如下假設和約束條件：（1）一個設施點可為多個需求點提供貨物，且一個設施點至少覆蓋一個需求點（需求點為風景名勝的POI數據）。（2）運輸成本與時間無關。（3）設施點到需求點的平均范圍最少，設施點數量最少，需求點覆蓋量范圍最多。（4）備選點的配送能力與需求點的需求量有關。

該問題的數學建立模型如下：

minF=∑i∈N∑j∈MiωidijCij??????????（1）

s.t.∑j∈MiCij=1，i∈N??????????（2）

Cij≤hj，i∈N，j∈Mi????????（3）

dij≤s??????????????（4）

Cij，hj∈{0，1}，i∈N，j∈Mi????（5）

∑j∈Mihj=n?????????????（6）

其中，Cij表示為設施備選點坐標；hj為0、1整數變量，當hj為1時表示第j個設施點被選中，當hj為0時表示第j個設施點沒有被選中；dij表示需求點i到設施點j的運輸距離；ωi表示需求點i到設施點j的運輸成本；公式（1）表示滿足條件的最少設施點的值；公式（2）表示需求點與設施點的分配關系，確保每一個設施點至少覆蓋一個需求點；公式（6）表示被選為設施點的數量為n。

3.3?改進的交叉算子遺傳算法

基本的遺傳算法解決這類優化存在進化速度慢和出現局部最優解的問題。因此將具有自適應的記憶功能的禁忌搜索算法對基本遺傳算法進行混合，可以增加遺傳算法的全局最優解的能力。具體通過改進交叉算子提高遺傳算法的全局搜索的效果。通常防值個體的交叉操作對算法解的結果有較大影響，一般交叉概率Pcross取0.5。在此問題中定義交叉概率為：

Pcross=11+ek（favg－fmax）（7）

其中，k為常系數，fmax為最大適應度值，favg為平均適應度值。再對算法中設置新的收斂條件，在反復地迭代過程中，父代基因池最優解未被替換，因此可算出全局最優解。

結合實際數據的調查，本文對需求點的需求量和運輸成本進行了預處理。確定需求量時，對各區景點平日客流量數值進行計算，得出的計算值為需求點的需求量。備選點的運輸成本則以南京市各區的地價作為標準來進行計算。在對醫療中心進行選址時，該文將設施選址的最優解作為醫療中心選址的需求點和備選點。備選點的運輸成本以南京市各區的地價作為標準。需求點的需求量則看為一個常數，假設醫療中心選址點的需求量都相同，則公式（1）中的ωi可更換為常數ω進行計算。繼續上文的算法操作，可得出醫療中心選址的最優解。

設施選址和醫療中心選址的結果可視化如圖1和圖2所示。

4?結論及建議

在景區醫療安全突發性事件中，使用多目標規劃的醫療設施選址方案及其優化設計確定配送站的選址具有良好的可行性。本文采用聚類分析與改進的遺傳算法對南京市醫療設施系統選址進行研究，相關結論與建議如下：

（1）相較于傳統的物流配送中心，承擔應急醫療站這一功能的配送中心需要克服的核心問題是如何在面對突發性事件時迅速發揮功能且快速調配物資。因此相較于其他的傳統的選址方法，基于深入的聚類分析和基于改進目標的遺傳算法得出選址方案更加符合南京市的實際情況。將這兩種方法分別運用到便民醫療設施選址模型和優化模型后，成功解決了選址的不合理性和方法復雜性，避免了資源的浪費。通過分析發現，改進的聚類分析實現了在突發事件下的緊急處理，與日常配送工作，使用粒子群算法攻克了選址時的多目標協同。

（2）對于當前的大數據時代，靜態數據分析遠遠不夠，需要打造動態可視化智能物聯網平臺以實現增值服務，對于運用企業而言需要聯合云計算、互聯網、物聯網、人工智能等技術搭建動態實時可視化平臺，及時發現更新的地理數據，從而整合社會新資源，構建協同網絡，實現配送點與配送點之間的交互，提高系統運作效率，實現低碳下的物流運作，提高經濟效益，實現城市物聯。

（3）結合實證分析結果和長期發展目標，可以發現各區設施點配送點分布呈現顯著的差異性。老城區：鼓樓、秦淮、玄武、建鄴設施點數量領先于其他區域屬于第一梯隊，因其發展周期長，商業化程度高、人流量密集、名勝古跡林立而導致應急醫療的需求也隨之增加，所以設施點平均覆蓋面積更小可以讓服務更精準。毗鄰老城區的雨花臺、棲霞兩區人口密集程度有所緩解設施點平均覆蓋面積有所增加，醫療站數量有所減少，避免了配送冗余的問題。江寧、浦口、六合等大區處于第三梯隊，三區面積廣闊人口眾多，是南京發展的新勢力區，因此配送點醫療站數量反而有所增加。高淳、溧水兩區屬于第四梯隊，因其發展尚未成熟，被輻射能力弱，所以設施點需要補強以應對這種缺陷。

（4）基于多目標規劃的醫療設施選址涉及了大量的實時數據，這些難以量化的數據對結果會有影響，數據的難獲取度，也降低的結果的精準度，未來要搭建實時數據云平臺就要致力于攻克此問題。由于結果會隨著需求者的主觀意志發生改變，如何對需求進行定位更新也至關重要，本文搭建數學模型時考慮的是單一運輸單一成本，之后的研究更需要平衡多個目標的權重，考慮多重成本帶來的影響，更加貼合物流與經濟流通的實況。

參考文獻

［1］汪曉春，熊峰，王振偉，等.基于POI大數據與機器學習的養老設施規劃布局—以武漢市為例[J].經濟地理，2021，41（06）：28.

[2]金仙力，李金剛.基于遺傳算法的多目標路徑優化算法的研究[J].計算機技術與發展，2018，28（2）：2.

[3]郭昌勇.基于大數據分析的城市電動汽車充電設施多目標規劃研究[D].重慶：重慶大學，2022：925.

[4]李依麟.基于GIS的零售業選址問題分析[J].商經理論，2016，（4），

[5]張金鳳.設施選址問題的建模及優化算法研究[D].廣州：廣東工業大學，2011：1528.

[6]楊葉勇.“互聯網+”時代農村物流配送中心選址的優化方案設計[J].物流管理，2017，（20）.

[7]萬波，楊超，黃松，等.基于層級模型的嵌套型公共設施選址問題研究[J].武漢理工大學學報（信息與管理工程版），2014，34（2）：35.

[8]湯希峰，毛海軍，李旭宏，等.物流配送中心選址的多目標優化模型[J].東南大學學報（自然科學版），2009，39（2）：384425.