市場分區之模擬退火演算法

A Simulated Annealing Algorithm for Market Based Redistricting Problems

鍾偉信(Wei-Shin Chung)

指導教授 ： 林峰田

國立臺灣大學/工學院/建築與城鄉研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.01815

摘要

在都市研究中，有許多依據活動強度而劃設的分區問題。過去服務範圍分區多以最短服務距離為目標，但在許多情形下，距離並非最重要的考量因子，市場規模可能才是業者關心的重點（如電業、通訊業、有線電視等），故需有新的求解方法。
由於分區問題屬於多極值問題類型，且因模擬退火法具有跳脫區域最適解進而找到全域最適解的能力，故本研究採用模擬退火法做為分區問題的演算法核心，以電業分區為研究案例，求解在市場規模相等（近）目標下的合理分區。在空間屬性的處理上係將空間視為一個網格系統，以需求者觀點設計一電量分派模式，將用戶實際用電需求分派於網格系統中以為分區依據；在演算法的處理上則提出結合「有效參數設定」及「初始條件設定策略」，能夠有效提昇模擬退火法求解分區問題的演算效率與演算品質，進而得到符合研究者需求之全域最適解。
研究獲致成果如下：第一，模擬退火法可提供有效之分區劃設工具；第二，網格系統設計以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.

並列關鍵字

feasible solution ； market based redistricting problems ； simulated annealing algorithm

參考文獻

台灣經濟研究院（2003）。電業營業區域之研究。經濟部能源委員會。

Wey, Wann-Ming (2003). Dynamic school facility location with time dependent demand: The progressive p-Median problem. In International Symposium on Urban Planning, 2003 (pp.B1-1-1 - B1-1-9). Taipei: NTU.

Chang, H. H., & Su, C. T. (2000). Optimization of parameter design: an intelligent approach using neural network and simulated annealing. International Journal of Systems Science, 31(12), 1543-1549.

Cunha, M. C., & Sousa, J. (1999). Water distribution network design optimization: Simulated annealing approach. Journal of Water Resources Planning and Management. 215-221.

Day, P. N., Pachter, R., Gordon, M. S., & Merrill, G. N. (2000). A study of water clusters using the effective fragment potential and Monte Carlo simulated annealing. Journal of Chemical Physics, 112(5).