混合式演算法於道路偵測器配置之應用

A Hybrid Algorithm for the Optimal Design of Road-Detector Systems

陳彥伯(Yan-bor Chen)

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2007年)

摘要

「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.

參考文獻

[15] 曹餘偉，2006，應用禁忌搜尋法求解多車種多物流中心之區位途程問題，元智大學，碩士論文

[18] 樓邦儒，2005，多目標決策應用於觀光防災區位之研究--以桃園復興鄉為例，管理科學研究，特刊，(2005/12)，頁45∼56。

[20] 衛萬明、廖晉廷，2004， ”都市停車場區位選擇之研究”，設計學報，9卷1期(2004/03)，頁13∼32。

[14] 黃格威，2006，混合式進化演算法於無線基地台配置決策之應用，虎尾科技大學，碩士論文。

[9] 洪子盛，2003，以模糊多目標規劃法求解消防站配置問題之最佳化，國立成功大學，博士論文。