林峰田臺灣大學：建築與城鄉研究所鍾偉信Chung, Wei-ShinWei-ShinChung2007-11-292018-06-292007-11-292018-06-292004http://ntur.lib.ntu.edu.tw//handle/246246/61919在都市研究中，有許多依據活動強度而劃設的分區問題。過去服務範圍分區多以最短服務距離為目標，但在許多情形下，距離並非最重要的考量因子，市場規模可能才是業者關心的重點（如電業、通訊業、有線電視等），故需有新的求解方法。 由於分區問題屬於多極值問題類型，且因模擬退火法具有跳脫區域最適解進而找到全域最適解的能力，故本研究採用模擬退火法做為分區問題的演算法核心，以電業分區為研究案例，求解在市場規模相等（近）目標下的合理分區。在空間屬性的處理上係將空間視為一個網格系統，以需求者觀點設計一電量分派模式，將用戶實際用電需求分派於網格系統中以為分區依據；在演算法的處理上則提出結合「有效參數設定」及「初始條件設定策略」，能夠有效提昇模擬退火法求解分區問題的演算效率與演算品質，進而得到符合研究者需求之全域最適解。 研究獲致成果如下：第一，模擬退火法可提供有效之分區劃設工具；第二，網格系統設計以2×2公里2之單位網格設計表現最佳，並可於合理時間內求解；第三，對於模擬退火法的演算機制之運算效率提昇，本研究提出最大搜尋次數設定為Lmax= ，可有效降低模擬退火法應用於分區問題之演算時間；輔以初始條件設定策略，可使分區演算品質符合本研究提出之「可接受上限」，並可進一步依據抽樣分配理論求得負向5%最小值區間（最適解信任區間）之「可信任最適解」，提昇分區結果之可信度In urban study, there are many redistricting problems (RP), which subdivide spaces based on various activity intensities. In the past, such problems usually set their objective functions in accordance with the Euclidian distance from certain points. However, distance is not the only consideration, in stead, market shares is probably the other factor to determine the service areas of some industries, like electronic power, telecommunications or cable TV. Therefore, a new algorithm for market based RP (MRP) is needed. In this study, to comply with the MRP which has multi-minimal solutions, the simulated annealing algorithm (SA), capable of escaping from a local minimal to seek a global one, is adopted by taking power service MRP as an illustrative case. The study area is represented as a grid system. After estimating the volumes of power consumption for every grid, the study area is partitioned into a given number of contiguously grid regions subject to the total difference of power consumptions of all the regions is minimized. This research focuses on finding appropriate initial values of some parameters of SA to improve computational efficiency while satisfied solutions can still be obtained. In the illustrative case, it concludes that: (1) SA is confirmed to be a valid algorithm for MRP; (2) A grid size representing a 2×2 KM2 area is recommended; (3) Given a tolerable error, the number of iteration times can be sufficiently set to to have credible solutions with 95% confidence level.目 錄 第一章　緒論 　　第一節　研究動機與目的 1 　　第二節　研究內容與範圍 3 　　第三節　分區問題定義 4 　　第四節　研究方法與流程 4 　　第五節　研究架構 6 第二章　文獻回顧 　　第一節　傳統規劃模型之限制 7 　　第二節　模擬退火法理論基礎 10 　　第三節　相關分區研究回顧 14 第三章　研究方法 　　第一節　電量分派模式 17 　　第二節　最短距離分區法 18 　　第三節　模擬退火法 19 　　第四節　退火方法特性 23 第四章　電量分派模式 　　第一節　前言 25 　　第二節　分派準則及分派來源對應 26 　　第三節　網格套疊分區 34 　　第四節　網格分派結果 36 第五節 最適解可接受上限 39 第五章　分區演算程序與結果分析 　　第一節　分區問題之模擬退火演算程序 47 　　第二節　程式驗證 51 　　第三節　分區結果分析 53 第四節 綜合分析 74 第六章　結論與建議 　　第一節　結論 81 　　第二節　建議 82 參考文獻 85 附錄 附錄一　分區類別對應之電量分派來源 89 圖　目 錄 圖1-1：研究流程圖 5 圖2-1：區域最適解與全域最適解示意 9 圖2-2：exp(－△E／T )與△E／T之對應關係 11 圖2-3：模擬退火法演算流程 13 圖3-1：Moore八鄰近概念 20 圖3-2：模擬退火法最大搜尋次數及迭代次數圖解 20 圖3-3：接受機率與ΩE／Tf之關係 22 圖4-1：電量分派至不同土地使用分區概念 30 圖4-2：網格電量分派情境 35 圖4-3：8216電量分派網格矩陣 36 圖4-4：8216電量分派值之標準化分配 36 圖4-5：分派查核一 36 圖4-6：分派查核二 36 圖4-7：2080電量分派網格矩陣 37 圖4-8：2080電量分派值之標準化分配 37 圖4-9：945電量分派網格矩陣 37 圖4-10：945電量分派值之標準化分配 37 圖4-11：520電量分派網格矩陣 38 圖4-12：520電量分派值之標準化分配 38 圖4-13：336電量分派網格矩陣 38 圖4-14：336電量分派值之標準化分配 38 圖4-15：8216極端值網格分佈 41 圖4-16：2080極端值網格分佈 42 圖4-17：945極端值網格分佈 43 圖4-18：520極端值網格分佈 44 圖4-19：336極端值網格分佈 45 圖5-1：Moore八鄰近移步策略 48 圖5-2：第一次經驗參數修正之分區結果 55 圖5-3：第二次經驗參數修正之分區結果 57 圖5-4：最大搜尋次數之設定探討 58 圖5-5：正規化參數配合第一次最大搜尋次數修正之分區結果 60 圖5-6：二元樹搜尋最小值概念圖 61 圖5-7：正規化參數配合第二次最大搜尋次數修正之分區結果 62 圖5-8：隨機選取策略測試樣本最小值之分區結果 65 圖5-9：電量排序策略測試樣本最小值之分區結果 68 圖5-10：電量排序分區結果涵蓋範圍–以520最小值為例 69 圖5-11：市鎮中心候選網格位置示意 70 圖5-12：市鎮中心策略測試樣本最小值之分區結果 72 圖5-13：分區結果顯示演算機制可有效涵蓋初始策略之種子網格–以2080最小值為例 73 圖5-14：研究範圍內台電各營業區處之轄區範圍與售電量統計 76 圖5-15：電量排序520分區結果最小值之電量統計 76 圖5-16：市鎮中心2080分區結果最小值之電量統計 76 圖5-17：分區結果與土地使用分區套疊驗證 77 圖5-18：分區結果標準差之標準化分配圖 78 圖5-19：最適解信任區間示意 80 表　目 錄 表4-1：台灣地區1999-2003年行業別售電量統計 26 表4-2：營造業行業別項目 27 表4-3：台灣地區1999-2003「電燈」及「電力」售電結構 27 表4-4：住宅區及商業區分派比例 28 表4-5：四縣市1999-2003年電燈及電力售電結構 29 表4-6：行業別電量分派比例及對應之土地使用分區 31 表4-7：基隆市行業別電量分派結果 32 表4-8：台北市行業別電量分派結果 32 表4-9：台北縣行業別電量分派結果 33 表4-10：桃園縣行業別電量分派結果 33 表4-11：網格電量分派計算表示意 35 表4-12：分派結果統計 39 表4-13：8216電量分派極端值分佈 41 表4-14：2080電量分派極端值分佈 42 表4-15：945電量分派極端值分佈 43 表4-16：520電量分派極端值分佈 44 表4-17：336電量分派極端值分佈 45 表4-18：不同網格矩陣大小之最適解可接受上限 46 表5-1：測試結果一 51 表5-2：測試結果二 52 表5-3：測試結果三 53 表5-4：第一次經驗參數修正之最適解判定結果 54 表5-5：第二次經驗參數修正之最適解判定結果 56 表5-6：正規化參數配合第一次最大搜尋次數修正之最適解判定結果 59 表5-7：正規化參數配合第二次最大搜尋參數修正之最適解判定結果 61 表5-8：隨機選取策略之測試結果 64 表5-9：電量排序策略之測試結果 67 表5-10：電量排序分區結果涵蓋鄉鎮區整理–以520最小值為例 69 表5-11：市鎮中心策略之測試結果 71 表5-12：網格大小判定分析 75 表5-13：電量排序策略符合負向5%最小值區間之分區結果 79 表5-14：市鎮中心策略符合負向5%最小值區間之分區結果 801710301 bytesapplication/pdfen-US市場分區模擬退火法最適解feasible solutionmarket based redistricting problemssimulated annealing algorithmthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/61919/1/ntu-93-R90544016-1.pdf