考慮多點覆蓋之路徑問題

近年來全球因溫室效應導致氣候變遷、海水上升，導致各地區氣候異常並發生了許多天然的災害，其中台灣因先天的氣候因素、地形環境導致水災、土石流等天災時常發生，故建立了許多的雨量觀測站來掌握多變的氣候狀況，其設置問題也顯得十分重要。在過去的測站設置規劃中，並不會討論後續的維修部分，但由於維修雨量站的頻率及次數相當可觀，所以本研究在設置觀測站的同時，把後續的維修路線考量進去。透過修改覆蓋問題(Set Covering Problem)和中國郵差問題(Chinese Postman Problem)自行發展出求解架構，利用求解修改覆蓋問題所得到的設站位置與數量作為基礎，計算出通過全部測站的最短路徑並將其紀錄為原始解，接著透過增加點位找出所有路徑組合並求解其最短路徑成本。藉由常態分佈生成的亂數進行數據測試，發現其結果皆優於原始解。本研究之啟發式演算法將可以提供決策者在測站設置與路徑規劃上，評估測站地點的一項參考依據。

關鍵字

觀測站設置；覆蓋問題；中國郵差問題；啟發式演算法

並列摘要

In recently years, Greenhouse Effect has increasing which leads to abnormal weather conditions and many natural disasters in each area. Among Taiwan, the natural disasters such as floods, landslides, always happen due to the congenital climates and terrain environment. Therefore, setting up many precipitation stations to grasp variable climate conditions is a very important thing. The installment of precipitation stations did not discuss the maintenance in the past. However, the frequency for preservation is quite considerable. Therefore, in the research, setting up the precipitation stations, meanwhile, we consider the preservation follow-up service. Automatically develop the solution structure by revising Set Covering Problem and Chinese Postman Problem, based on the station locations and numbers which come from the above solution, calculate the shortest route passing through all stations and record as the original solution. Next, find all route combination by increasing point locations and calculate the costs of the shortest route. Test data by random number which generates from normal distribution and find all the results are better than the original results. The research of heuristic algorithms can provide a valuable reference for decision makers to evaluate station locations.

並列關鍵字

Setting precipitation stations ； Set Covering Problem ； Chinese Postman Problem ； Heuristic Algorithm

參考文獻

颱風洪水研究中心. (2014). 資料來源：

陳正改. (2000). 台灣地區的氣象災害與防災策略.

Aráoz, J., Fernández, E., & Meza, O. (2009). Solving the prize-collecting rural postman problem. European Journal of Operational Research, 196(3), 886-896.

Ávila, T., Corberán, Á., Plana, I., & Sanchis, J. M. (2015). A new branch-and-cut algorithm for the Generalized Directed Rural Postman Problem. Transportation Science.

Caprara, A., Toth, P., & Fischetti, M. (2000). Algorithms for the set covering problem. Annals of Operations Research, 98(1-4), 353-371.

國際替代計量

考慮多點覆蓋之路徑問題

全文下載

主題瀏覽