現在位置首頁 > 博碩士論文 > 詳目
論文中文名稱:鄰避設施覆蓋選址問題之研究 [以論文名稱查詢館藏系統]
論文英文名稱:A Study of Undesirable Facilities Covering Location Problem [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:工業工程與管理研究所
畢業學年度:97
出版年度:98
中文姓名:李煜坤
英文姓名:Yu-Kun, Lee
研究生學號:96378036
學位類別:碩士
語文別:中文
口試日期:2009-06-29
論文頁數:49
指導教授中文名:吳建文
口試委員中文名:黃祥熙;陳凱瀛
中文關鍵詞:鄰避設施GRASP塔布搜尋法
英文關鍵詞:Undesirable facilitiesGRASPTabu search
論文中文摘要:本篇論文主要是針對研究定址設施的位址問題。文章中研究的設施性質,屬於令人不喜愛的設施,也就是鄰避(NIMBY, Not-In-My-Back-Yard)設施之定址的問題。當設施類型為令人不喜愛的設施,可以想像每個人一定是避之唯恐不及。但是一些社會性的設施,比如像是垃圾掩埋場、發電廠(特別是核能發電廠)、監獄這方面的設施,這類設施對社會來說,是重要且不可或缺的。所以,要如何能夠用一套適當的方式來設置這些設施,使其能夠對社會提供服務,又要使其對於設置當地帶來的影響達到最小,這是一項重要的議題。本篇文章承襲了Berman與Huang的研究,對於其所使用的數學模型之演進與觀念會有詳細的介紹;而在實驗分析的部分,提出使用GRASP方法來解決此類問題,並且與作者所提出的塔布搜尋法(Tabu Search),進行解的品質與所花的時間,這兩方面作比較。在犧牲掉時間的情形之下,解的品質可以比作者的方法更精進一些。主要目標是希望能夠進一步改善,解決此類問題的品質部分,同時,也希望藉由此研究,能夠帶進後續相關的深入探討,使得鄰避設施的設置問題,能夠更受到大家的重視。
論文英文摘要:This article discusses the problem of siting undesirable facilities location. Undesirable facilities have special phenomenon toward the society. They provide services to the society but it has bad impacts on the region nearby. So, people want these facilities to be away from the population centers or communities. Berman and Huang proposed models to deal with the issue of siting undesirable facilities regarding the distance between facilities. Based on their research, we propose a GRASP heuristic to solve it. GRASP is a multi-start heuristic. It contains two phases: construction and local search phase. We compare our heuristic with their best method (tabu search). The experiment results are provided in this article. The results show that our approach demonstrates good quality of solution.
論文目次:摘 要i
ABSTRACTii
誌 謝iii
目 錄iv
表目錄v
圖目錄vi
第一章 緒論1
1.1 研究動機與背景1
1.2 研究目的2
1.3 研究範圍與限制3
1.4 研究流程與架構3
第二章 文獻探討5
2.1 設施規劃問題5
2.1.1. MILP、LIP與rLIP5
2.1.2. ACLP9
2.1.3. minimum-envy問題11
2.1.4. 設施規劃模型分析13
2.1.5. 設施規劃模型應用15
2.2 GRASP方法16
2.3 小結19
第三章 研究方法20
3.1 MCLPDC模型20
3.2 方法解說25
3.2.1 Greedy Method26
3.2.2 塔布搜尋法(Tabu Search)27
3.2.3 拉氏釋限法(Lagrangian Relaxation)28
3.2.4 GRASP34
第四章 實驗結果與分析41
第五章 結論與未來研究方向44
參考文獻46
論文參考文獻:[1]林立千,設施規劃與物流中心設計,台北市:智勝文化事業有限公司,民國90年。
[2]邵柏林、游文清、陳智瑋、林煜超、高子傑譯,Facilities Planning,台中市:滄海書局,民國94年。
[3]A. Duarte and R. Marti, "Tabu search and GRASP for the maximum diversity problem," European Journal of Operational Research, vol. 178, 2007, pp. 71-84.
[4]A. Mehretu, R. I. Wittick and B. W. Pigozzi, "Spatial design for basic needs in eastern Upper Volta," Journal of Developing Areas, vol.17, no. 3, 1983, pp. 383-394.
[5]A. M. Geoffrion, "Lagrangian relaxation and its uses in integer programming," Math Programming, vol. 2, 1974, pp. 82-114.
[6]A. T. Murray and R. L. Church, "Solving the anti-covering location problem using lagrangian relaxation," Computers & Operations Research, vol. 24, 1997, pp. 127-140.
[7]A. T. Murray, R. L. Church, R. A. Gerrard and Wing-Sing Tsui, "Impact models for siting undesirable facilities," The Journal of the Regional Science Association International, vol. 77, 1998, pp. 19-36.
[8]B. Farhan and A. T. Murray, "Distance decay and coverage in facility location planning," Ann. Regional Science, vol. 40, 2006, pp. 279-295.
[9]C. Toregas and C. ReVelle, "Optimal location under time or distance constraints," Paper in regional science, vol. 28, 1972, pp. 133-143.
[10]C. Toregas, R. Swain, C. ReVelle and L. Bergman, "The location of emergency service facilities," Operational Research, vol. 19, 1971, pp. 1363-1373.
[11]D. J. Eaton, R. L. Church, V. L. Bennett, B. L. Hamon and L. G. Valencia-Lopez, "On deployment of health resources in rural Valle del Cauca, Colombia," TIMS Studies in the Management Sciences, vol. 17, 1981, pp. 331-359.
[12]E. Erkut, "The discrete p-dispersion problem," European Journal of Operational Research, vol. 46, 1990, pp. 48-60.
[13]E. Rolland, D. A. Schilling and J. R. Current, "An efficient tabu search procedure for the p-median problem," European Journal of Operational Research, vol. 96, 1996, pp. 329-342.
[14]F. Glover and M. Laguna, Tabu Search, Norwell, Massachusetts: Kluwer Academic Publishers, 1997.
[15]I. D. Moon and S. Chaudhry, "An analysis of network location problems with distance constraints," Management Science, vol. 30, 1984, pp. 290-307.
[16]I. Espejo, A. Marin, J. Puerto and A. M. Rodriguez-Chia, "A comparison of formulations and solution methods for the minimum-envy location problem," Computers & Operations Research, vol. 36, 2009, pp. 1966-1981.
[17]J. Yamashita, "Effects of spatial interaction on spatial structure: a case of day center location in Malmo," Geographical Review Japan, vol. 66, 1993, pp. 156-172.
[18]L. Murawski and R. L. Church, "Improving accessibility to rural health services: The maximal covering network improvement problem," Socio-Economic Planning Sciences, vol. 43, 2009, pp. 102-110.
[19]M. G. C. Resende and C. C. Ribeiro, "GRASP," AT&T Labs Research Technical Report, 2008.
[20]M. G. C. Resende and R. F. Werneck, "A hybrid heuristic for the p-median problem," AT&T Labs Research Technical Report TD-5NWRCR, 2003.
[21]M. G. C. Resende, R. Marti, M. Gallego and A. Duarte, "GRASP and path relinking for the max-min diversity problem," Computers & Operations Research, doi:10.1016/j.cor.2008.05.011, 2008.
[22]M. Kuby, "Programming models for facility dispersion: The p-dispersion and maxisum dispersion problems," Geographical Analysis, vol. 19, 1987, pp. 315-329.
[23]M. Laguna and R. Marti, "Grasp and path relinking for 2-layer straight line crossing minimization," INFORMS Journal on Computing, vol. 11, 1999, pp. 44-52.
[24]O. Berman and R. Huang, "The minimum weighted covering location problem with distance constraints," Computers & Operations Research, vol.35, 2008, pp. 356-372.
[25]R. L. Church and C. ReVelle, "The maximal covering location problem," Papers of Region Science Association, vol. 32, 1974, pp. 101-118.
[26]R. L. Church and J. Cohon, "Multiobjective location analysis of regional energy facility siting problems," BNL Report Number 50567, Brookhaven National Laboratories, Upton, New York, 1976.
[27]R. L. Church and R. S. Garfinkel, "Locating an obnoxious facility on a network," Transportation Science, vol. 12, 1978, pp. 107-118.
[28]O. Fotheringham and M. O’Kelly, Spatial interaction models: formulations and applications, Amsterdam: Kluwer, 1989.
[29]S. Hakimi, "Optimum distribution of switching centers in a communications network and some related graph theoretic problems," Operations Research, vol. 13, 1965, pp. 462-475.
[30]S. Hakimi, "Optimal location of switching centers and the absolute centers and medians of a graph," Operations Research, vol. 12, 1964, pp. 450-459.
[31]T. A. Feo, M. G. C. Resende and S. H. Smith, "A greedy randomized adaptive search procedure for maximum independent set," Operations Research, vol. 42, 1994, pp. 860-78.
論文全文使用權限:不同意授權