雲端運算應用在智慧行動裝置之旅遊排程系統

The Application of Mobile Cloud Computing on Genetic Algorithm for Tour Planning

王彥翔(Yan-Siang Wang)

指導教授 ： 周信宏

長榮大學/資訊暨工程學院/資訊管理學系(所)/碩士(2013年)

https://doi.org/10.6833/CJCU.2013.00173

摘要

本研究結合了智慧型手機，開發出一套具備個人化的旅遊行程服務系統。以Traveling Salesman Problem為核心，提出結合Cloud Computing與Genetic Algorithm之架構，並與本論文所提出的分區最短路徑法比較運算時間及最短距離，實驗結果顯示分區最短路徑法的運算時間比Genetic Algorithm快，而Genetic Algorithm在計算最短距離上比分區最短路徑還小，因此我們可以確定利用基因演算法可以得到不錯的近似最佳解。

關鍵字

智慧型手機 ； 旅行推銷員問題 ； 雲端運算 ； Hadoop ； 基因演算法

並列摘要

In this thesis, we introduce our cloud mobile computing app for tour planning. Most of tourist websites or apps only provide static information, such as the introduction of scenic spots and pre-scheduled tour packages, which are not friendly for the tourists or backpacking travellers those who are unfamiliar with the visiting place. Our app provides not only the static spot information but also the dynamic customized tour planning. We adopt the genetic algorithm for solving the Traveling Salesman Problem by the cloud mobile computing model. For the offline situation, we also implement a Region Shortest Path heuristic algorithm in app for tour planning.

並列關鍵字

Smart Phone ； Traveling Salesman Problem ； Cloud Computing ； Hadoop ； Genetic Algorithm

參考文獻

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

[12] E. Goldberg(1989), “Genetic Algorithm in search, Optimization and Machine Learning,” Addison Weslery.

[13] GB. Datzig, D.R. Fulkerson, and S.M. Johnson(1954), “Solution of a large-scale Traveling Salesman Problem,” Operations Research, 2(4), pp. 393-410.

[16] Karthik Kumar and Yung-Hsiang Lu(2010), “Cloud Computing for Mobile Users : Can Offloading Computation Save Energy?” IEEE Computer Society, vol. 43(4), pp. 51-56.

[17] M. Bellmore, G.L. Nemhauser(1968), “The Traveling Salesman Problem: A Survey,” Operation Research, 16(3), pp. 538-558.