應用群蟻演算法於旅遊路線規劃研究

A Study of Applying Ant Colony Algorithm in Tourism Itinerary Planning

張偉振(Wei-Chen Chang)

指導教授 ： 沈永堂

朝陽科技大學/設計學院/建築及都市設計研究所/碩士(2009年)

摘要

於現代化社會中，人們對於外出旅遊時的品質已開始重視，遊客於從事旅遊活動時，寧可花費較多金錢於旅途中，也不願於不確定的時間中等待。因此，若在規劃旅遊活動之際，將旅遊路線規劃列為預前處理階段的考慮因素，則有利於從事旅遊活動中節省時間與成本，使規劃過程更加完善，是為本研究目的。
旅遊路線規劃屬於傳統旅行推銷員問題（Traveling Salesman Problem；TSP），本研究於考量總旅行時間成本下，利用傳統啟發式演算法中的最近鄰點法（Nearest Neighbor Method）計算總路線成本，後端配合群蟻演算法（Ant Colony Algorithm）提高旅遊排程之效率，進而達到旅遊路線成本之最小之目標。
本研究採用三階段操作步驟，先將各景點相鄰路線做一連結後，再配合傳統啟發式演算法進行第一次搜尋，並以群蟻演算法進行改善。研究利用Microsoft Office Excel 2007軟體進行群蟻演算法求解以及績效評估比較，以實例操作證明其演算法應用於旅遊路線上之有效性。其結果證明可有效提高群蟻演算法於路網中之效率。
實證研究以2007年度台中市經濟局商業發展課所規劃的形象商圈為對象，資料庫採用台中市政府空間地圖地理資訊圖檔進行分析處理，研究發現應用群蟻演算法於旅行推銷員問題之旅遊路線規劃上，其路網中景點設置為10點以下，為避免容易費洛蒙收斂速度過快，費洛蒙衰退參數(ρ)設計不宜高於0.5以上。其次，若應用群蟻演算法於台中市形象商圈之旅遊路線規劃，可有效改善多重目的區域環旅遊路線類型旅遊路線28.9％路線成本，並於整體路網中提升8.5%的節省率。

關鍵字

最近鄰點法 ； 群蟻演算法 ； 旅遊路線規劃

並列摘要

In the modern society, people have focused on the quality of tourism. Tourists would like to pay more money during the trip rather than wait under uncertain time. Therefore, the purpose of this study is to explore whether the listing of tourism itinerary planning as a decision factor in the pre-stage of tour planning can be helpful for not only saving time and cost but also making the plan more complete.
The tourism itinerary planning belongs to the traditional traveling salesman problem. Under considering the cost of total travel time, this study adopts nearest neighbor method to calculate the cost of total tourism itinerary and cooperate with Ant Colony Algorithm to promote the efficiency of tour schedule in order to achieve the goal of lowest cost of itinerary.
This study applies Ant Colony Algorithm for solving tourism itinerary planning problem and comparing performance assessments. In addition, the a case study which proves the effectiveness of Ant Colony Algorithm in tourism itinerary planning. The subject of this case study is image commercial which is worked out by commercial development section, department of economic development, Taichung City Government. The data used to analyze in the study are from the database of GIS published by Taichung City Government.
This study explores that applying Ant Colony Algorithm in TSP tourism itinerary planning should set up the destinations under ten in order to avoid the convergence rate of pheromone raising too fast. In fact, the pheromone decay parameter (ρ) cannot be designed over 0.5. Furthermore, applying Ant Colony Algorithm in the tourism itinerary planning of Taichung image commercial can effectively improve 28.9% cost of tourism itinerary of multiple destinations and also raise 8.5% saving rate in the whole itinerary.

並列關鍵字

Ant Colony Algorithm ； Nearest Neighbor Method ； Tourism Itinerary Planning.

參考文獻

4、朱道力，2005，"旅遊路線設計與關連聚落之區位分析"，《社會科教育研究》，第10期，pp.1-21。

11、林志鴻、許晉嘉，2006，"宅配業車輛路線問題之研究"， 《運輸學刊》，第三十五卷，第四期，pp.443-474。

12、林志鴻，2005，"宅配業車輛路線規劃問題之模式建立與求解"， 《運輸學刊》，第十七卷，第一期，pp.65-94。

13、林志鴻，2005，"考量板架具相同裝載限制之新車配送路線規劃問題"， 《運輸學刊》，第十七卷，第四期，pp.393-422。

15、林志鴻、陳春益、林育俐、曾智強，2002，"委外校車路線規劃問題之研究"，《運輸學刊》，第三十一卷，第二期，pp.391-428。