耦合優(yōu)化蟻群算法與P-Median model 的選址模型設(shè)計(jì)

顧梓程，胡新玲

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

0 引言

人民運(yùn)動(dòng)需求令運(yùn)動(dòng)場(chǎng)所在城市的規(guī)劃中占有一定的比重，其選址關(guān)系到城建部門對(duì)于公共設(shè)施投入成本以及城市人民生活質(zhì)量問(wèn)題[1]。

蟻群算法經(jīng)過(guò)20 多年發(fā)展，在理論及應(yīng)用研究上已取得巨大進(jìn)步。它屬于一種啟發(fā)式算法，目前較多學(xué)者關(guān)注蟻群算法的路徑規(guī)劃應(yīng)用[2-4]，也有學(xué)者針對(duì)利用蟻群算法實(shí)現(xiàn)城市設(shè)施的優(yōu)化選址問(wèn)題展開(kāi)研究[5-6]。P-Median model 是依靠ArcGIS 構(gòu)建網(wǎng)絡(luò)分析數(shù)據(jù)集，模擬現(xiàn)實(shí)交通路網(wǎng)并結(jié)合具體服務(wù)范圍、設(shè)施數(shù)量、需求點(diǎn)分布情況等因素實(shí)現(xiàn)對(duì)設(shè)施點(diǎn)布局的分析[7]。

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

1 蟻群算法及P-Median model

1.1 蟻群算法

蟻群算法最早是由意大利學(xué)者M(jìn).Dorigo 于1991 年提出的一種群智能算法，它是由一群有輕微智能的個(gè)體通過(guò)相互協(xié)作而表現(xiàn)出的智能行為，螞蟻在前往一個(gè)地點(diǎn)覓食時(shí)，會(huì)分泌信息素來(lái)引導(dǎo)同伴前往目的地，隨著螞蟻數(shù)量的增加，該路徑信息素濃度增大使所有螞蟻沿著此路徑行走，通過(guò)這種反饋機(jī)制定位最優(yōu)路徑，如圖1所示。

圖1 蟻群算法示意圖

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

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

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

1.2 P-Median model

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

式中：ρa(bǔ)b為所有節(jié)點(diǎn)阻抗之和；Nab為節(jié)點(diǎn)對(duì)（a,b）路徑上所有路段阻抗；xi為路段上到第i個(gè)節(jié)點(diǎn)所遇阻抗，可用時(shí)間表示；p為所有節(jié)點(diǎn)數(shù)之和。

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

對(duì)于蟻群算法改進(jìn)問(wèn)題就是在一定條件下尋找最優(yōu)方案，使所用功能指標(biāo)達(dá)到最優(yōu)。首先蟻群算法的核心求的是最短路徑，就是所有螞蟻經(jīng)過(guò)路線組合的最小值，根據(jù)P-Median model 求得ρa(bǔ)b最小值，針對(duì)滿足顯示需求條件的組合模型，將初始信息素與ρa(bǔ)b的最小值進(jìn)行結(jié)合，對(duì)蟻群算法的搜索效率以及精確性提出改進(jìn)，如式（5）所示：

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

2 選址模型的設(shè)計(jì)

2.1 目標(biāo)函數(shù)的建立

由于蟻群算法依賴于對(duì)目標(biāo)函數(shù)計(jì)算所獲得的自適應(yīng)值來(lái)運(yùn)行，通過(guò)設(shè)計(jì)適合本研究的兩種變量構(gòu)造目標(biāo)函數(shù)，將目標(biāo)函數(shù)作為基于改進(jìn)蟻群算法上的運(yùn)動(dòng)場(chǎng)所選址模型性能標(biāo)準(zhǔn)是有必要的。運(yùn)動(dòng)場(chǎng)所的合理選址是為了解決人們對(duì)于不同時(shí)段能夠?qū)崿F(xiàn)運(yùn)動(dòng)自由以及節(jié)省時(shí)間成本的需求并滿足交通便利原則的問(wèn)題，應(yīng)該滿足以下兩點(diǎn)要求：

1）各運(yùn)動(dòng)場(chǎng)所容納的人口之和應(yīng)大于服務(wù)半徑覆蓋區(qū)域內(nèi)需求點(diǎn)包含有運(yùn)動(dòng)需求人口之和。

2）服務(wù)半徑覆蓋內(nèi)需求點(diǎn)至運(yùn)動(dòng)場(chǎng)所距離成本最小。

根據(jù)要求，目標(biāo)函數(shù)設(shè)定為：

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

2.2 選址模型構(gòu)建

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

圖2 選址模型工作流程圖

詳細(xì)步驟如下：

1）進(jìn)行變量參數(shù)初始化，同時(shí)設(shè)定螞蟻數(shù)量k以及目標(biāo)函數(shù)f1(x)、f2(x)的模型設(shè)定值n1和n2。

2）對(duì)螞蟻數(shù)量賦值為1 并置于初始化鄰域，此時(shí)螞蟻按照模型公式（1）的概率移動(dòng)，使螞蟻數(shù)量進(jìn)行k+1 的疊加并進(jìn)行循環(huán)運(yùn)算。

3）禁忌表初始化，根據(jù)公式（5）設(shè)定最小參數(shù)ρa(bǔ)b，計(jì)算得到τij(0)后更新禁忌表。

4）根據(jù)所得結(jié)果判斷提取柵格蟻群殘留信息素濃度是否為MAX，否，則返回步驟3）循環(huán)執(zhí)行。

5）計(jì)算目標(biāo)函數(shù)值f1(x)、f2(x)更新信息素。

6）判斷目標(biāo)函數(shù)值f1(x)、f2(x)是否小于模型設(shè)定值n1和n2，否，則返回步驟2）循環(huán)執(zhí)行。

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

3 數(shù)據(jù)與研究區(qū)域

3.1 數(shù)據(jù)來(lái)源

1）點(diǎn)位數(shù)據(jù)來(lái)源于OSM平臺(tái)，包含小區(qū)信息及點(diǎn)位信息、分布路網(wǎng)數(shù)據(jù)、道路長(zhǎng)度信息、道路節(jié)點(diǎn)屬性和部分建筑屬性，人口數(shù)據(jù)取自國(guó)家統(tǒng)計(jì)局第七次人口普查[12]。

2）根據(jù)國(guó)體委運(yùn)動(dòng)場(chǎng)所管理規(guī)定：在駕車或騎車15～20 min 內(nèi)所經(jīng)過(guò)的最短路程為最大阻力值。

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

4）根據(jù)國(guó)家體育總局發(fā)布的國(guó)家公共體育設(shè)施基本準(zhǔn)則中運(yùn)動(dòng)場(chǎng)所建設(shè)的標(biāo)準(zhǔn)，大型全民健身活動(dòng)中心要求建筑面積為8 000～12 000 m2，室內(nèi)、外體育場(chǎng)地面積不宜小于5 000 m2；游泳館要求泳池面積不低于500 m2。

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

6）根據(jù)烏魯木齊市人口年齡分布統(tǒng)計(jì)數(shù)據(jù)，中長(zhǎng)期有運(yùn)動(dòng)需求的人口按照常駐人口的30%～40%計(jì)算，為了使得人口覆蓋最大化，采取40%作為計(jì)算值[14]。

根據(jù)以上要求，用高德SDK 管理平臺(tái)調(diào)用API 接口檢索研究區(qū)域所有的運(yùn)動(dòng)場(chǎng)所，通過(guò)Java 將所得文件批量化處理后，最終得到符合數(shù)據(jù)要求的研究區(qū)域內(nèi)的設(shè)施點(diǎn)位信息需求點(diǎn)人口數(shù)據(jù)見(jiàn)表1。

表1 需求點(diǎn)人口信息

3.2 研究區(qū)概況

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

圖3 研究區(qū)域圖

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

4 實(shí)驗(yàn)與分析

4.1 交通路網(wǎng)可達(dá)性

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

對(duì)研究區(qū)域路網(wǎng)數(shù)據(jù)建立網(wǎng)絡(luò)數(shù)據(jù)集，利用出發(fā)點(diǎn)-目的地建立OD 成本矩陣并對(duì)其進(jìn)行求解，得出可達(dá)性數(shù)值范圍并進(jìn)行可視化如圖4 所示。

圖4 研究區(qū)域路網(wǎng)可達(dá)性分布

可達(dá)性計(jì)算公式為：

式中：D為路網(wǎng)可達(dá)性；T為時(shí)間成本；N為總OD 路徑數(shù)量。[0.00，3.12]、[3.13，6.15]、[6.16，9.19]、[9.20，12.23]、[12.24，15.27]可達(dá)性數(shù)值范圍覆蓋了研究區(qū)域的最大范圍，令每個(gè)區(qū)間設(shè)定評(píng)價(jià)權(quán)重β0分別為0.25、0.20、0.15、0.10、0.05。對(duì)于時(shí)間的加權(quán)公式為：

式中：tc為加權(quán)后道路節(jié)點(diǎn)的通行時(shí)間；β0為不同區(qū)間段可達(dá)性賦權(quán)。

4.2 柵格位置提取

采用Python 語(yǔ)言進(jìn)行優(yōu)化實(shí)驗(yàn)，按照經(jīng)驗(yàn)取值方法設(shè)置蟻群算法參數(shù)，設(shè)置信息素濃度τ=10 000，信息素的揮發(fā)系數(shù)ρ=0.01，蟻群中螞蟻的數(shù)量初始化設(shè)定為k=1，信息素啟發(fā)因子α=1。選址模型提取柵格衛(wèi)星影像圖如圖5 所示。

圖5 柵格選取圖

從圖5 的結(jié)果得知，模型選址結(jié)果基本符合實(shí)際情況，該點(diǎn)位于人民路與新華南路的交匯處，人口活動(dòng)密度較大的南門與北門均在所選設(shè)施點(diǎn)附近，兼顧了距離成本最小目標(biāo)與容納的人口數(shù)量目標(biāo)。

4.3 模型分析結(jié)果對(duì)比

用ArcGIS 對(duì)研究區(qū)進(jìn)行空間柵格數(shù)據(jù)信息編輯，利用選址模型做模擬計(jì)算，可以直觀顯示計(jì)算數(shù)據(jù)結(jié)果。經(jīng)過(guò)最小化阻抗模型A 與文獻(xiàn)[16]的最大化覆蓋模型B以及本文設(shè)計(jì)的選址模型C分析得出運(yùn)動(dòng)場(chǎng)所服務(wù)半徑覆蓋對(duì)比如圖6所示，需求點(diǎn)覆蓋具體情況如表2所示。

表2 不同模型下選址需求點(diǎn)覆蓋情況個(gè)

將不同模型分析結(jié)果進(jìn)行對(duì)比，加入選址系統(tǒng)挑選的最優(yōu)選址點(diǎn)相比直接采用最小化阻抗覆蓋范圍模型得到的覆蓋率上升10.42%；相比最大化覆蓋模型上升6.95%。隨著體育設(shè)施選址個(gè)數(shù)的增加，具體選址地址基本考慮了距離目標(biāo)和人口數(shù)量目標(biāo)，在整體上選址效果良好，與實(shí)際情況相符。

設(shè)施點(diǎn)建設(shè)的不同位置與不同的路徑規(guī)劃關(guān)系到不同服務(wù)半徑需求點(diǎn)個(gè)數(shù)，在C 模型僅添加一個(gè)設(shè)施點(diǎn)的情況下，三種模型在不同服務(wù)半徑覆蓋率雷達(dá)圖如圖7 所示。

圖7 三種模型下不同服務(wù)半徑覆蓋率雷達(dá)圖

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

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

5 結(jié)語(yǔ)

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

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