人工智慧最佳化於警車巡邏問題之研究

Artificial Intelligence Optimization for the Police Car Patrol Problem

黃泊晴(Bo-Ching Huang)

指導教授 ： 謝益智

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

摘要

本研究探討含巡邏區間限制的警車巡邏問題，在此問題中警車從警局出發，巡邏每位民眾一次或多次，其中每位民眾所要求的巡邏區間限制為相臨二次的巡邏區間需滿足每位民眾給定之要求，而此警車巡邏問題欲最小化警車所行駛的總距離。本研究應用用免疫演算法、基因演算法和粒子群演算法來探討此警車巡邏問題，我們提出兩種編碼方式(編碼一與編碼二)可以同時解決警車巡邏民眾的順序及符合每位民眾的巡邏時段。除此之外，本文以單因子變異數分析來研究此三種演算法的數值結果是否有顯著差異性。本研究以高雄地區的某一區域為例探討含巡邏區間限制的警車巡邏問題，數值結果顯示，免疫演算法與編碼一的編碼方式之結合能夠迅速的獲得此問題之最佳解或臨近最佳解。

關鍵字

車輛途程問題 ； 時窗限制 ； 免疫演算法 ； 基因演算法 ； 粒子群演算法

並列摘要

This thesis investigates the police car patrol problem with constrained time intervals. The police car starts from the police station and then patrols each customer once or multiple times based upon his/her requirement. The studied police car patrol problem aims to minimize the total completion distance. This thesis applied three artificial intelligence approaches, namely, immune algorithm, genetic algorithm, and particle swarm optimization, to solve the police car patrol problem. We propose two coding approaches (coding-1 and coding-2) for finding the order of customers and their patrol time intervals simultaneously. In addition, ANOVA is used to test the performance of these three artificial intelligence approaches. Numerical results of Kaohsiung city show that immune algorithm with coding-1 performs better than the others combinations.

並列關鍵字

Vehicle Routing Problem ； Time Windows Constraints ； Immune Algorithm ； Genetic Algorithms ； Particle Swarm Optimization

參考文獻

6.李旺蒼 (2006)，以粒子群最佳化為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究，國立中央大學土木工程研究所，碩士論文。

18.蔡崑佑 (2009)，警察巡邏路線之研究，朝陽科技大學建築與都市設計研究所，碩士論文。

13.陳思齊 (2007)，巡邏車輛途程問題，國立中央大學土木工程學系，碩士論文。

10.張榮芳 (2000)，電力用戶負載歸類及整合，國立中山大學電機工程研究所，博士論文。

15.黃維 (2005)，以類免疫系統法建置垃圾郵件過濾系統之研究，中原大學資訊管理學系，碩士論文。