改進的Dijkstra 標號法在城鄉規劃中小學選址的應用＊

曾麗群，單國彬

（1.柳州工學院土木工程系，廣西 柳州 545616；2.柳州市公共資源服務交易中心，廣西 柳州 545616）

1 Dijkstra 標號法

1.1 Dijkstra 最短距離標號法

1959 年，迪杰斯特拉提出的標號法是最短路徑問題的最好求解方法，用于計算1 個節點到其他節點的最短路徑。基本思路為：將各頂點用可行的路徑進行連線，得到1 個賦權圖G。假設V1為起點，Vk為終點，則V1在圖G 中有k-1 種路徑可以達到終點Vk，之后依次計算Vi（i=2，3，4，…，k）到V1的距離T（Vi），則minT（Vi）對應的路徑為最優路徑。

1.2 最短距離標號法的應用

近年來，Dijkstra 最短距離標號法主要應用于自駕游最短線路、最佳導航線路、人員疏散路徑、最佳交通線路、應急救援及避災線路選擇等最短線路規劃和最優路徑選擇中[1-5]，在應用中是以使最佳選址位置所在的頂點到網絡圖中其他各個頂點的最短路徑（空間）距離總和的最小值作為選址判定的依據。

城鄉規劃中涉及消防站、醫院、中小學等公共服務設施的選址，主要考慮服務半徑即服務范圍，可以應用標號法求出公共服務設施的最優選址，其質量判據為最大服務距離最小化[6-10]。其基本思想為：在賦權有向圖G 中，對圖中的每條邊都賦予1 個權值（距離），圖中的各頂點分別用Vi（i=1，2，…，k）表示。在圖G 中選擇其中的任一點Vi作為擬選址點，求出Vi到其余各頂點的最短距離，計為dij（j=1，2，…，k），這樣就得到K 行、K 列的距離矩陣Dk×k。在距離矩陣Dk×k中，先求出每行元素的最大值max（di），之后再求出每行max（di）的最小值min［max（di）］，該最小值min［max（di）］所對應的元素dij、所在列的列號j、所在頂點Vj即為最優選址點，如果最小值min［max（di）］對應的元素不唯一，則說明最優選址不唯一，最優選址為多個。

2 Dijkstra 標號法的改進

2.1 距離因子的修正

在前期城鄉規劃中，小學的選址很少考慮建設后的服務人口分布狀態，而服務人口的分布狀態關系到選址合理性與滿意度。在滿足服務半徑要求的小學選址中，存在居住區到學校的距離近但該居住區小學適齡人口少、居住區到學校距離較遠但該居住區小學適齡人口較多的情況。造成這些情況的原因是只考慮了距離，未考慮服務人口的影響。因此，在選址時，應綜合考慮出行距離和服務人口雙重影響因子，需對標號法中的距離修正為加權距離，即加權距離為距離（單位：m）和學生人數（單位：人）的乘積。

2.2 改進后的模型

在最短距離標號法的基礎上，考慮服務人口分布對選址的影響，對距離因子進行上述的修正后，修正后的距離dij＝dij·Pi（j=1，2，…，k；i=1，2，…，k），Pi為i 地塊的學齡兒童人數。根據GB 50180—2018《居住區規劃設計標準》，通過推演得出，各居住區學齡兒童人數Pi=用地面積×容積率/人均居住建筑面積×適齡兒童比例。根據上述1.2 所述，距離矩陣Dk×k的對應元素為d'ij，求出距離矩陣Dk×k。根據中位點選址問題的質量判據是：使最佳選址位置所在的頂點到網絡圖中其他各個頂點的最短路徑距離的總和達到最小，先求出Dk×k中各行的總和e（di）=∑dij（j=1，2，…，k），再求出min［e（di）］，其最小值所對應的頂點就是最優選址點。

3 改進的最短距離標號法在小學選址規劃中的應用

3.1 柳州市里雍鎮概況

廣西柳州市里雍鎮距離柳州市25km，由于地形地貌酷似柳州市城區，素有“小柳州”之稱，全鎮總面積243km2，下轄9個村民委員會和1 個社區居民委員會。目前，里雍鎮鎮區人口約為0.6 萬，規劃到2035 年人口約為1.5 萬。由于鎮區離市區較遠，目前的小學已不能滿足人口發展的需要，規劃中應新建1 所小學。

3.2 數據來源與整理

按照就近入學的原則，在城鄉規劃中進行小學選址時，需綜合考慮居住區到小學的距離和服務的學齡兒童人數。根據里雍鎮的土地規劃圖，將里雍鎮鎮區內的道路抽象為線，小學可能的選址地塊抽象為點，把點和線連起來就得到一個賦權圖，如圖1 所示。

圖1 賦權

依據土地利用規劃中居住用地的開發強度和適齡兒童比例，可以計算出各頂點適齡兒童的人數（見表1）。

表1 各居住用地小學生人數

3.3 計算

根據上述1.2 最短距離標號法，并結合里雍鎮的賦權圖，可計算得出Dk×k。

在矩陣Dk×k中，可以求出：max（d1）=1 131，max（d2）=856，max（d3）＝1 069，max（d4）＝1 317，max（d5）＝1 362，max（d6）＝1 159，max（d7）=989，max（d8）=887，max（d9）=708，max（d10）＝830，max（d11）=1 030，max（d12）=1 069，max（d13）=1 058，max（d13）＝1 362。根據質量判據min［max（d）i］，可以求出min［max（di）］=708，其對應的頂點為V9。

根據上述1.2 中改進的最短距離標號法模型d'ij=d·ijPi，將表1 中的人口數據代入，對Dk×k進行加權修正后得到D'k×k。

在Dk×k中，由e（d ）i=∑d （ijj=1，2，…，k）可以求出：e（d1）=999 435，e（d2）=621 441，e（d3）＝632 238，e（d4）＝792 016，e（d5）＝810 778，e（d6）＝742 128，e（d7）＝642 125，e（d8）＝578 273，e（d9）＝587 279，e（d10）＝658 802，e（d11）＝683 664，e（d12）＝851 441，e（d13）=755 974，e（d14）=984 470。根據質量判據min［e（di）］，可以求出min［e（di）］=578 273，其對應的頂點為V8。

3.4 結果分析

從上述計算結果得出，如果只考慮空間距離，根據最短距離標號法求出里雍鎮小學的最優選址為頂點V9，即9 號地塊。而從綠色出行、減少交通出行消耗、提高服務滿意度等方面考慮，對最短距離標號法進行改進后，求出里雍鎮小學的最優選址為頂點V8，即8 號地塊。因此，在里雍鎮的城鄉規劃中，小學的最優選址為8 號地塊。

4 結語

在小城鎮的小學選址中，從綠色出行、減少交通出行消耗和提高滿意度的角度出發，應用步行實際距離和服務人數的乘積，對最短距離標號法中的距離進行修正，建立改進的標號法模型，適用于小城鎮或是城市中某一區域的小學選址規劃，特別是新建小學的選址規劃和新區規劃中的小學選址，同時也適用于其他公共服務設施的選址。為提高改進標號法在城市公共服務設施選址規劃中的應用與推廣，可以簡化計算，提高效率。上述實例中，依據《中華人民共和國城鄉規劃法》（2019 修正）和《居住區規劃設計標準》，中小學的服務半徑不大于500m。結合里雍鎮鎮區的土地利用規劃方案，可初步判定2，8，9，11 地塊的服務范圍符合要求，為小學選址的備選方案。應用改進后的標號法計算對應的e（di）=∑dij（j=1，2，…，k），可簡化計算步驟、減少數據的處理，大大縮短計算工作量，提高工作效率。