臺灣博碩士論文加值系統

「e視訊巡邏」可以彌補員警巡邏的不足，在各地普設偵測器後，警方已經靠著偵測器破獲不少搶奪、肇事逃逸，甚至命案等案件，因此道路偵測器儼然已成治安利器。然而不當偵測器裝設會使道路偵測上產生死角，而過量的偵測器裝設，又將浪費資源，因此道路偵測器問題為複雜之區位問題（Location Problem）。
由於道路偵測器配置問題屬於NP-hard，其求解範圍非常的廣闊，傳統利用最佳化方法如：窮舉法、動態規劃、分支界限法等方法來求解，然而在問題規模稍大時就顯得不實用，有鑑於此，本研究提出一個新的混合免疫演算法（Immune Algorithms）與粒子群最佳化（Particle Swarm Optimization）之方法，並結合修正法來解決複雜之道路偵測器配置問題。
由數值結果可得知，本研究所提出的方法，在不同的道路系統中（例如：直線道路、圓環、十字道路、三岔道路、綜合道路系統與綜合道路系統PRO等），給定不同的預算限制下，均可求得配置方案。

“E-Patrol” could support the lack of policemen to provide patrol services. The policemen have solved several criminal cases with the help of road-detectors of “E-Patrol”. Therefore the road-detector system has been a useful tool for the security of communities. However, it is well known that inappropriate setting of road-detectors will occur some dead angles and dead space. On the other hand, oversetting of road-detectors will waste the limited resources. Therefore, the setting of road-detectors is an important issue and a complex location problem.
Because the setting of road-detectors is a NP problem, its feasible region is usually wide. As known, the conventional approaches, such as exhaustive method, dynamic programming, and branch-and-bound method, can be used to solve the problems. However, these conventional approaches are not practical when the problem size is larger. In this study, we will propose a new hybrid algorithm which mixes both IA (Immune Algorithm) and PSO (Particle Swarm Optimization) to solve the problem. In addition, we will also propose a so-called Revision Algorithm (RA) to improve the solutions by IA and PSO.
Numerical results show that the proposed approaches in this study can solve the complex location problems for various road systems such as straight lines, circles, “X” type roads, “Y” type roads, and the combination road cases.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
圖目錄 vii
第一章 緒論 1
1-1研究背景與動機 1
1-2研究目的 1
1-3研究方法與步驟 2
1-4論文架構 2
第二章 文獻探討 4
2-1區位問題 4
2-1-1一般設施區位問題之特性 4
2-1-2區位問題－依問題型態分類 8
2-1-3區位問題－依變數分類 9
2-2免疫演算法 11
2-2-1免疫系統介紹 11
2-2-2免疫演算法 13
2-3粒子群最佳化（PSO） 16
2-3-1粒子群最佳化之發展背景 16
2-3-2粒子群最佳化演算法之概念說明 17
2-3-3粒子速度更新法則 18
2-3-4粒子群最佳化演算法之演算流程與步驟 19
2-4混合式演算法 21
第三章 問題模式與研究方法 22
3-1問題描述 22
3-1-1問題假設 23
3-1-2問題模式 29
3-2 研究方法 31
3-2-1混合式演算法 31
3-2-2二位元免疫演算法編碼方式 33
3-2-3粒子群最佳化編碼方式 34
3-2-4適應函數（Fitness Function） 35
3-2-5 修正法 36
第四章 測試結果與討論 40
4-1直線道路 41
4-2圓環 44
4-3十字道路 47
4-4三岔道路 49
4-5綜合道路系統 52
4-6綜合道路系統PRO 55
第五章 結論與未來研究方向 59
5-1結論 59
5-2 未來研究方向 59
文獻 60
附錄A 直線道路配置 64
附錄B 圓環配置 72
附錄C 十字道路配置 74
附錄D 三岔道路配置 76
附錄E 綜合道路系統配置 78
附錄F 綜合道路系統PRO 85

中文
[1]王鐸元，1989，焚化爐區位選擇之研究，國立交通大學，碩士論文。
[2]邱明輝，2004，TSK型式之遞迴式模糊類神經網路及其應用：使用新型混合演算法GA_BPPSO，元智大學，碩士論文。
[3]李政佑，2000，工廠與配銷中心區位選擇之研究，國立清華大學，碩士論文。
[4]吳永裕，2005，鄰避設施之廠址選擇及車輛途程問題，雲林科技大學，碩士論文。　
[5]呂登隆，2004，台北地區掩埋場區位適宜性及環境問題之檢討，國立台北大學，碩士論文。
[6]林宏晉，2004，不確定因素考量下之都市鄰里公園區位選擇研究，朝陽科技大學，碩士論文。
[7]林庭予，2004，多重選擇規劃在區位選擇問題之應用，國立台北科技大學，碩士論文。　
[8]林宗儀，2001，垃圾公車清運系統之收集點位置規劃，國立交通大學環境工程研究所，碩士論文。
[9]洪子盛，2003，以模糊多目標規劃法求解消防站配置問題之最佳化，國立成功大學，博士論文。
[10]衷嵐焜，1996，離散區位模型應用於速食外送業態區位評選之研究，國立中央大學，碩士論文。
[11]胡正宏，2003，有容量限制之動態設施區位問題，國立高雄第一科技大學運輸倉儲營運所，碩士論文。
[12]陳欣得，1986，多目標區位問題求解法之研究，國立交通大學，碩士論文。
[13]陳惠國，2005，區位途程與易腐性商品排程之研究，國立中央大學，碩士論文。
[14]黃格威，2006，混合式進化演算法於無線基地台配置決策之應用，虎尾科技大學，碩士論文。
[15]曹餘偉，2006，應用禁忌搜尋法求解多車種多物流中心之區位途程問題，元智大學，碩士論文
[16]馮正民、林禎家，2000， ”都市計畫草圖替選方案分析模式之改進：納入公共設施配置”，都市與計劃，27卷2期(2000/09)，頁233∼254。

[17]鄧宏安，2002，整合CFDRC及類免疫演算法於散熱片之最佳化設計，大同大學，碩士論文。
[18]樓邦儒，2005，多目標決策應用於觀光防災區位之研究--以桃園復興鄉為例，管理科學研究，特刊，(2005/12)，頁45∼56。
[19]鄭炳強、侯雍聰， ”2004 混合基因及螞蟻演算法的TSP解法”， 2004智慧型知識經濟研討會暨第二屆演化式計算應用專題研討會，台北，12月24日。
[20]衛萬明、廖晉廷，2004， ”都市停車場區位選擇之研究”，設計學報，9卷1期(2004/03)，頁13∼32。
[21]蕭再安、曾國雄，1992， ”競爭性設施區位理論的回顧與展望”，科技發展月刊，20卷，6期，頁719∼733。

英文
[1]A. Lim, B. Rodrigues, F. Wang, Z. Xu, 2004, “k-Center problems with minimum coverage”, Computing and Combinatorics, Vol. 3106, pp. 349-359.
[2]A. Weber, 1909, “Theory of the location of industries”, Chicago IL , University of Chicago Press.
[3]C.F. Juang, 2004, “A hybrid of genetic algorithm and particle swarm optimization for recurrent network design”, IEEE Trans. on Systems, Man, Cybernetics- Part: B, Vol. 34, No.2, pp. 997-1006.
[4]C.H. Lin, C.S. Chen, C.J. Wu and M.S. Kang, 2003, “Application of immune algorithm to optimal switching operation for distribution-loss minimization and loading balance”, IEE Proceedings, Generation, Transmission, and Distribution, Vol. 150, No. 2.
[5]C.W. Reynolds, 1987, “Flocks, herds, and schools: A distributed behavioral model”, ACM SIGGRAPH Computer Graphics. Vol. 21, No. 4, pp.25-34.
[6]D. Dasgupta, N. Attoh-Okine, 1997, “Immunity-based systems: A survey”, Proceeding of the IEEE Transactions on Systems, Man and Cybernetics, Vol.1, pp. 369 -374.
[7]H.O. Susan and S.D. Mark, 1998, “Strategic facility location: A review ”, European Journal of Operational Research, Vol.111, pp.423-447.
[8]H. Pirkul, V. Jayaraman, 1998, “A multi-commodity, multi-plant, capacitated facility location problem: formulation and efficient heuristic solution”, Computer Operations Research, Vol. 25, No. 10, pp.869-878.
[9]I.D. Moon and S.S. Chaudhry, 1984, “An analysis of network location problems with distance constraints”, Management Science, Vol. 30, No.3 pp. 290-307.
[10]J. Current , H. Min and D. Schilling, 1990, “Multiobjective analysis of facility locations”, European Journal of Operation Research, Vol. 49, pp295-307.
[11]J.E. Hunt and D.E. Cooke, 1996, “Learning using an artificial immune system”, Journal of Network and Computer Applications, Vol. 19, pp. 189-212.
[12]J. Kennedy and R.C. Eberhart, 1995, “Particle Swarm Optimization”, Proceedings of IEEE International Conference on Neural Networks, Vol. IV, pp.1942-1948.
[13]J. Perl, 1983, “A unified warehouse location-routing analysis”, UMI Dissertation Information Service, USA.
[14]K. Leon, V.E. Marc, H. Pierre, 1977, “A plant and warehouse location problem”, Operational Research Quarterly, Vol. 28, No. 3, pp. 547-554.
[15]L. Min; W. Cheng 1999, “A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines”, Artificial Intelligence in Engineering, Vol. 13, No. 4, pp.399-403.
[16]L.N. de Castro and F.J. Von Zuben, 1999, “Artificial immune systems: part I – basic theory and applications”, Technical Report – RT DCA 01/99, pp. 1-95.
[17]L. Yang, F.J. Bryan and S.H. Yang, 2007, “A fuzzy multi-objective programming for optimization of fire station locations through genetic algorithms”, European Journal of Operational Research. Vol. 181, Issue 2, pp. 903-915.
[18]M.C. Chen, D.M. Tsai and H. Y. Tseng, 1999, “A stochastic optimization approach for roundness measurements”, Pattern Recognition Letters, Vol. 20, No. 7, pp. 707-719.
[19]M. Dorigo, 1992, “Optimization, learning and natural algorithms”. Ph.D.Thesis, Politecnico di Milano, Italy.
[20]M.D. Vose, 1998, The Simple Genetic Algorithm: Foundations and Theory, MIT Press, USA.
[21]M. Laguna, J.P. Kelly, J.L. Gonzalez-Velarde and F. Glover, 1995, “Tabu search for the multilevel generalized assignment problem”, European Journal of Operational Research, Vol. 82, pp.176-189.

[22]N. Mitsumoto, T. Fukuda, F Arai, 1994, “The Immune Mechanism, Adaption, Learning for the Multi Agent System”, IEEE symp. on Emerging Technologies and Factory Automation, Tokyo, Japan.
[23]O. Shigehiro and I. Hiroaki, 2005, “Obnoxious facility location problem with forbidden regions”, Asia Pacific Management Review, Vol.10, No.4,
pp. 255-258.
[24]R. Boyd and P.J. Richerson, 1985, Culture and the Evolutionary Process, University of Chicago Press, Chicago, USA.
[25]R.C. Eberhart and Y. Shi, 1998, “Comparison between genetic algorithms and particle swarm optimization,” Proceedings of the Seventh annual Conference on Evolutionary Programming, Springer Verlag, pp. 611-618.
[26]U.M. Erdem and S. Sclaroff, 2006, “Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements”, Computer Vision and Image Understanding, Vol. 103, pp. 156-169.
[27]Y.H. Shi and R.C. Eberhart, 1998, “A modified particle swarm optimizer”, IEEE World Congress on Computational Intelligence, IEEE Press.
[28]Z. Drezner and G. Wesolowsky, 1997, “On the best location of signal detectors”, IIE Transactions, Vol. 29, pp. 1007-1015.
[29]Z. Michalewicz, 1996, “Genetic algorithms + data structures = evolution programs”, 3th Edition, Springer-Verlag Berlin, Heidelberg.