現在位置首頁 > 博碩士論文 > 詳目
論文中文名稱:萬用啟發式方法應用在最大覆蓋選址問題之研究 [以論文名稱查詢館藏系統]
論文英文名稱:A Study of Metaheuristics for The Maximal Covering Location Problem [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:資訊與運籌管理研究所
畢業學年度:99
出版年度:100
中文姓名:陳典廷
英文姓名:Tien-Ting Chen
研究生學號:98938002
學位類別:碩士
語文別:中文
口試日期:2011-06-15
論文頁數:29
指導教授中文名:吳建文
口試委員中文名:陳育威;杜壯
中文關鍵詞:最大覆蓋選址問題啟發式方法演算法萬用啟發式方法
英文關鍵詞:MCLPHeuristicsalgorithmMetaheuristics
論文中文摘要:最大覆蓋選址問題(Maximal Covering Location Problem, MCLP)在許多領域裡都扮演著非常重要的角色。例如配置緊急設施位址、設置無線網路路由器位址、工廠(倉儲)的選址等。在這個問題中,在給定的服務距離內,配置n個設施,使得能覆蓋或服務最多的需求數。在設置上述之設施時,通常需要考慮到該設施能夠服務到最多的需求點,且需求點到該設施的距離或時間最短。
過往用來解決MCLP的方法可分為:(1)啟發式方法、(2)精確方法。然而,近年來最常被用到的萬用啟發式方法是當中能以較快速度求得臨近最佳解的方法,但萬用啟發式演算法法有很多種,因此,本研究嘗試拿未曾用在解MCLP上的重覆性局部搜尋法(ILS)搭配貪婪增加法(Greedy methods)而成的新方法與過往的方法進行比較,經實驗證實,ILS演算法亦能有效的解決MCLP的問題,改善的幅度也可達到0.166%。
論文英文摘要:Given a set of client sites and a set of server sites, the maximum covering location problem (MCLP) seeks to find a fixed number of server sites in order to cover the maximum number of client sites. A client site is said to be covered if it is within a user-specified service distance from any selected server sites. The MCLP is important for its wide applicability. Typical applications include ambulance location selection, public facilities location selection, police station location selection, data abstraction, cluster analysis, list selection, and so on.
Traditional approaches for solving MCLP are (1) Heuristics methods and (2) Exact methods. But exact methods compute exact solutions but perform disappointingly for large problems. Therefore, we proposed the ILS algorithm combined with the greedy adding algorithm to solve the MCLP. Experiments show that such an approach achieves good performance on solving the MCLP.
論文目次:摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
第一章 緒論 1
1.1 研究動機與目的 1
1.2 研究目的 3
1.3 研究限制 3
1.4 研究架構 3
第二章 文獻探討 5
2.1 最大覆蓋選址問題 5
2.2 相關文獻及應用 7
2.3 啟發式方法回顧 8
2.3.1 傳統的啟發式方法 8
2.3.2 精確的方法 9
2.3.3 萬用啟發式方法(Metaheuristics) 10
第三章 研究方法 14
3.1 參數定義與數學模型 14
3.1.1 參數定義 14
3.2 研究方法 15
3.2.1 貪婪增加演算法 15
3.2.2 ILS演算法 16
3.2.2.1 將起始解利用ILS演算法 16
3.2.2.2 擾動目前的解 18
3.2.3 HC+ILS 18
3.2.3.1 第一階段:起始解的產生 18
3.2.3.2 第二階段:針對CS列表使用重複性局部搜尋方法 19
3.2.3.3 鄰居的挑選 20
3.2.3.4 更新最佳解 20
3.2.3.5 擾動目前的解 20
3.2.3.6 第三階段:對所有可行解再做一次局部搜尋 21
3.3 研究方法演算流程 21
第四章 實驗設計與實驗結果 22
4.1 實驗設計 22
4.1.1 測試資料產生 22
4.1.2 實驗參數設定 22
4.2 實驗結果 23
4.3 實驗結果分析 25
第五章 結論與建議 26
5.1 結論 26
5.2 未來方向與建議 26
參考文獻 27
論文參考文獻:[1]R. Church and C. ReVelle, "The maximal covering location problem," Papers of the Regional Science Association, vol. 32, 1974, pp. 101-18
[2]O. Karasakal, Esra K. Karasakal, "A maximal covering location model in the presence of partial coverage," Computers & Operations Research, vol. 31, Issue 9, 2004, pp. 1515-1526
[3]G. Lee and A. T. Murray, "Maximal covering with network survivability requirements in wireless mesh networks, "Computers, Environment and Urban Systems, Vol.34, Issue 1, 2010, pp. 49-57
[4]Megiddo, N., E. Zemel, S. L. Hakimi, "The maximum coverage location problem," SIAM J. Algebraic Discrete Methods, vol.4, pp. 253-261
[5]R. Dieguez Galvao and C. ReVelle, "A Lagrangean heuristic for the maximal covering location problem," European Journal of Operational Research, Vol. 88, Issue 1, 1996, pp. 114-123
[6]R. A. Gerrard and R. L. Church, "Closest assignment constraints and location models: Properties and structure," Location Science, Vol. 4, Issue 4, 1996, pp. 251-270
[7]J. M. Lee and Y. H. Lee, "Tabu based heuristics for the generalized hierarchical covering location problem,"Computers & Industrial Engineering, Vol 58, Issue 4, 2010, pp. 638-645
[8]R. L. Church and C. S. ReVelle, "Theoretical and Computational Links between the p_Median, Location Set-covering, and the Maximal Covering Location Problem," Geographical Analysis, vol. VIII, 1976, pp. 12-75
[9]C. ReVelle, M. Scholssberg and J. Williams, "Solving the maximal overing location problem with heuristic concentration," Computers & Operations Research, Vol. 35, Issue 2, 2008, pp. 427-435
[10]A. Grosso, M. Locatelli and Wayne Pullan, "Simple ingredients leading to very efficient heuristics for the maximum clique problem," Journal of Heuristics, Vol.14, Issue 6, 2008, pp. 587-612
[11]R. Church, J. Current and J. Storbeck, "A bicriterion maximal covering location formulation which considers the satisfaction of uncovered demand," Decision Sciences, Vol. 22, 1991, pp. 38-52
[12]T. D. Klastorin, "On the maximal covering location problem and the generalized assignment problem," Management Science, Vol. 25, 1979, pp. 107-111
[13]J. E. Storbeck, "The spatial structuring of central places," Geographical Analysis, Vol. 20, 1988, pp. 93-110
[14]J. E. Storbeck, "Classical central places as protected thresholds," Geographical Analysis," Vol. 22, 1990, pp. 4-21
[15]R. Church and M. E. Meadows, "Location modeling utilizing maximum service distance criteria," Geographical Analysis, vol. 11, 1979, pp. 101-118
[16]A. Mehrez and A. Stulman, "The maximal covering location problem with facility placement on the entire plane," Journal of Regional, vol. 22, 1982, pp. 361-365
[17]C. D. T. Watson-Gandy, "Heuristic procedures for the m-partial cover problem on a plane," European Journal of Operational Research, vol. 11, 1982, pp.149-157
[18]A. Mehrez, "A note on the linear integer formulation of the maximal covering location problem with facility placement on the entire plane," Journal of Regional Science, vol.23, 1983, pp. 553-555
[19]A. Mehrez and A. Stulman, "An extended continuous maximal covering location problem with facility placement," Computers and Operations Research, vol.23, 1984, pp.553-555
[20]F. R. Dwyer and J. R. Evans, "A branch and bound algorithm for the list selection problem in direct mail advertising," Mgmt Sci, Vol.27, pp. 658-667.
[21]C-H. Chung, "A maximal covering approach to the list selection problem in direct mail advertising," Proceeding of the Seventeenth Annual Meeing of American Institute of Decisionn Science, 1985
[22]Luis Fanjul-Peyro, Ruben Ruiz, "Iterated greedy local search methods for unrelated parallel machine scheduling," European Journal of Operational Research, Volume 207, Issue 1, 16 November 2010, pp. 55-69
[23]F. Della Croce, T. Garaix, A. Grosso, "Iterated local search and very large neighborhoods for the parallel-machines total tardiness problem," Computers & Operations Research, In Press, Corrected Proof, Available online, 2010
[24]X.G. Dong, H.K. Huang and P. Chen, "An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion," Computers & Operations Research, vol. 36, 2009, pp. 1664-1669
[25]Oded beman, Dmitry Krass, "The generalized maximal covering location problem," Compute Operations Research, vol. 29, 2002, pp. 563-581
[26]Lin, S. & B.W. Kernighan, "Computer Solutions of the Traveling Salesman Problem," Bell System Technology Journal, vol. 44, pp. 2245-2269
論文全文使用權限:不同意授權