基於MapReduce的基因演算法於旅遊行程規劃之研究

近年來，行動網路以及手持行動裝置快速的發展與普及，資料快速的流通，人們在旅遊時採用自助旅行的方式占了八成以上。自助旅行從規劃到執行都必須自行處理，如何在各種限制下規劃出最節省交通時間的旅遊行程最為關鍵，這往往決定整趟旅遊的成敗。在眾多的旅遊服務中大多著重於熱門景點的推薦，缺乏旅遊行程規劃之研究，規劃時間不但長且規劃結果不佳，故本研究提供一套系統，提供旅遊行程規劃服務，並改善進行規劃的基因演算法，在較短時間內提供使用者較佳的行程規劃建議。本研究以行動裝置為主要溝通介面，提供使用者在任何時空環境下皆可以進行旅遊資訊查詢與旅遊路線規劃。旅遊規劃利用基於主從式架構的MapReduce基因演算法來求解，並結合最近鄰居法以及特殊的交配模式的基因演算法來提升運算效能與結果，以這樣的架構在短時間內來滿足使用者行程規劃的需求。從本研究的實驗結果發現，提出的基因演算法用於解決行程規劃提升結果品質達44.89%，且將演算法架構於MapReduce方法中也提升了執行效率27.45%，從這些結果中可以發現本研究提出的架構有良好的效果。

關鍵字

旅遊規劃；旅行推銷員問題；基因演算法； MapReduce

並列摘要

In recent years, mobile networks and mobile devices are rapidly developed and popularized. Information is in circulation rapidly. In tourist industry, the type of independent travel has occurred more than eighty percent. Independent travelers must handle their own trips from planning to implementation. How to plan the most time-saving transportation during the travel period is the most critical concern, which often determines the success or failure of the trip. Most traveling services focus on the attractions recommendation, lack of research regarding travel planning. This study proposes a system that users can plan their own trips. This study also tries to improve the planning algorithm so that in such a structure to meet the needs of users in shorter time. In this study, a mobile device is used as the primary communication interface. It provides the user for searching information and planning the trip in any environment. Travel planning is helped based on Genetic Algorithm with MapReduce mechanism, the master-slave architecture on a Hadoop cloud platform. This study also proposes an enhanced Genetic Algorithm. It combines the Nearest Neighbor method and uses the unusual crossover approach to improve the performance and results. As the result shows, the system proposed in this study satisfies users’ needs. As the result shows, the proposed genetic algorithm for solving travel planning enhances the quality of the planning results of 44.89%. The algorithms based on MapReduce method also improves the efficiency of 27.45%. From the results of this study, it shows that the proposed framework has a good effect.

並列關鍵字

Travel Planning ； Traveling Salesman Problem ； Genetic Algorithms ； MapReduce

參考文獻

3. 王裕廷，「基因演算法應用於具時窗限制之多天旅遊行程規劃」，碩士論文，長榮大學資訊管理學系，2010。

2. 張偉振，「應用群蟻演算法於旅遊路線規劃之研究」，碩士論文，朝陽科技大學建築及都市設計研究所，2009。

4. 楊郁樓，「旅遊行程規劃模式與系統之建置－以台北市為起點之旅遊為例」，碩士論文，國立台灣大學地理環境資源學系，2010。

6. Carter, A. E. and Ragsdale C. T., “A new approach to solving the multiple traveling salesperson problem using genetic algorithms,” European Journal of Operational Research, vol. 175, no. 1, 2006, pp. 246-257.

7. Dao, T. H., Jeong, S. R. and Ahn, H., “A novel recommendation Model of Location-based Advertising: Context-aware Collaborative Filtering using GA Approach,” Expert Systems with Applications, vol. 39, no. 3, 2012, pp. 3731-3739.

國際替代計量

基於MapReduce的基因演算法於旅遊行程規劃之研究

全文下載

主題瀏覽