應用人工智慧演算法於大樓的週期性資源回收之路線規劃問題

Artificial Intelligence Approaches for the Periodic Recycle Routing Problem of Buildings

鄞玉婷(Yu-Ting Yin)

指導教授 ： 謝益智

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

摘要

本研究探討週期性資源回收之路線規劃問題，此問題屬於週期性車輛路徑問題(Periodic Vehicle Routing Problem, PVRP)的應用，也是車輛路徑問題(Vehicle Routing Problem, VRP)的延伸問題。週期性資源回收之路線規劃問題中，不同大樓有不同週期的資源回收需求，例如：每天都需收取、兩天收取一次、三天收取一次等，問題目標為有效地規劃每一天的資源回收點與其收取之路徑順序，以使六天的路徑總距離為最短(目標1)及最小化車輛間每天路徑距離的差距(目標2)。
本研究運用基因演算法(Genetic Algorithm, GA)、免疫演算法(Immune Algorithm, IA)以及粒子群演算法(Particle Swarm Optimization, PSO)來求解此問題。除此之外，本研究亦提出一個新的編碼方式，能同時解決週期性資源回收中每天回收地點組合與其路徑順序。本研究以台中某區域大樓為例，將車輛數、車輛容量上限、目標權重等，以不同組合來求解此週期性資源回收之路線規劃問題。數值結果顯示，此三種演算法皆能有效地規劃出六天中，此區域每一天的資源回收點與其收取之路徑順序，以使六天的路徑總距離為最短及最小化車輛間每天路徑距離的差距。此外，本研究將三種演算法做比較，其數值結果顯示，基因演算法求解速度優於其他兩種演算法，而免疫演算法求解品質優於其他兩種演算法。

關鍵字

週期性車輛路徑問題 ； 車輛路徑問題 ； 基因演算法 ； 免疫演算法 ； 粒子群演算法 ； 田口方法 ； 週期性資源回收

並列摘要

This thesis explored the periodic recycle routing problem. This problem is classified into the periodic vehicle routing problem, and it’s also an extension of the vehicle routing problem. In the periodic recycle routing problem, the buildings have different demands for the periodic recycle collection. For example, some buildings need the recycle collection for every day, and some buildings need the recycle collection for once per two days or once per three days. The goal of the periodic recycle routing problem is to schedule the buildings and the routes for recycle collection every day, so as to minimize the total distance and the gap of routing distance between the cars every day.
In this thesis, we apply Genetic Algorithm(GA), Immune Algorithm(IA), and Particle Swarm Optimization(PSO) to solve this problem. Besides, we also propose a new encoding method to compose of the buildings and schedule the routes for periodic recycle collection every day. In this thesis, we solved the periodic recycle routing problem by the three algorithms for the buildings at some area in Taichung with various combinations of numbers of cars, capacity of cars and the objective weights. The numerical results show that these three algorithms can schedule the buildings and the routes for recycle collection every day effectively and minimize the total routing distance of cars and the gap of routing distance between the cars. In addition, we compared these three algorithms and found that Genetic Algorithm is faster than the other two algorithms and Immune Algorithm performs better than the other two algorithms.

並列關鍵字

Periodic Recycle Routing Problem ； Vehicle Routing Problem ； Genetic Algorithm ； Immune Algorithm ； Particle Swarm Optimization ； Taguchi Method ； Periodic Recycle Collection

參考文獻

9. 徐志明、陳子安、李漢宗(2011)，「以基因規劃和人工免疫演算法最佳化薄型晶圓片切割參數」，明新學報，37卷，2期，頁165-183。

13. 陳惠國、余彥儒(2013)，「圖書館書籍通閱移送之車輛途程問題－巨集啟發式演算法之應用」，運輸學刊，25卷，1期，頁1-29。

16. 楊士杰、李坤洲(2012)，「粒子群演算法應用於線性天線陣列最佳化」，華岡工程學報，29期，頁109-114。

23. 韓復華、卓裕仁(2002)，「包容性深廣度搜尋法在週期性車輛路線問題之應用」，運輸計劃季刊，31卷，1期，頁1-35。

4. 王順德(2002)，應用基因演算法於多層甲板結構物之最佳化設計，國立成功大學造船及船舶機械工程學系，碩士論文。