臺灣博碩士論文加值系統

尋找旅遊資訊以及旅程規劃是一件繁瑣的事情，雖然許多旅遊網站及各地的政府機構都提供相當充足的景點資訊，提供旅遊行程的商家也不在少數，但大部分的旅程都是固定的，並不能符合每位遊客需求，即使使用導航系統規劃旅程，也只能隨著遊客先後輸入的景點順序，去做最短路徑的導航，並沒有考慮其他因素，如：景點的開放時間、旅遊時間以及景點喜愛分數等等。因此有學者對此進行研究，考慮景點特性及遊客需求，並在短時間內計算出最符合需求的遊玩路線，儘管如此還是有不足的地方，如沒有考慮實際的車程時間，或者挑選景點過多時該如何進行篩選，以及如何運用每次計算的結果，讓旅遊行程規劃更佳多元化。

本論文實作出一套結合電子地圖的旅遊網站系統，使用蟻群演算法(Ant algorithm)規劃旅程問題，並考慮實際車程、旅遊時間、景點喜愛分數、景點營業時間等因素，客製化每位遊客的行程，當選擇景點過多，超出旅遊時間時，則以挑選旅程分數最高的組合當作這次的結果;除此之外，我們將每位旅行者比喻成一隻螞蟻，每次的旅程就好比螞蟻走過所遺留下的費洛蒙(Pheromone)，藉由收集這些費洛蒙，我們可以得知景點的流動性，分析出螞蟻最有可能前往的下個景點、以及最熱門的景點等等，這些資訊除了用於推薦給遊客觀看外，還可以提供螞蟻演算法運算所使用，使結果更接近遊客所需，徹底達到螞蟻費洛蒙的特性。經驗證測試，此方法可以在短時間內根據遊客需求客製化旅程，在實驗的最後還經過多次的情境模擬測試，證實本研究可應用於實際的旅程規劃上。

People have taken traveling as an important situation in the life recently. Collecting tourist information is an extremely complicated thing. Nowadays, there is a lot of abundant information about traveling on the tourist websites which are not only provided by the travel agencies, but also the governments. Even though, those useful websites can truly help us gain a lot of traveling information, they are too unchangeable to be suitable to meet everyone’s need. If you use the Navigation System while you traveling in some places, the Navigation System can’t meet you what you need. Because the Navigation System just can search the shortest way for traveling in some areas without considering any factors, such as the opening hours of the scenic spots, the recommendation from other tourists or the time limited touring in some landscapes, etc.

In this paper, we implement a travel system combined with electronic map, use Ant algorithm to develop tourist-oriented itineraries that considered the traveling time, score of scenic spots and opening hours. And then we select a schedule of travel that conforms combination of the score of total scenic spots is highest. In addition, we can obtain some information about route of scenic spots, the popular scenic spots by collecting tourist itineraries, that not only can offers to tourists, but also apply to Ant Colony algorithm calculate and make results closer to the personal travel needs. In this case, people can find the way they really want to travel.

摘要........... i
Abstract........... ii
謝誌........... iii
表目錄........... v
圖目錄........... vi
第一章 簡介........... 1
1.1 研究背景........... 1
1.2 研究動機........... 1
1.3 研究目的........... 2
1.4 論文架構........... 2
第二章 文獻探討........... 3
2.1 旅行者銷售員問題........... 3
2.2 Google Service........... 6
2.3 旅遊路線規劃與比較 ........... 9
2.4 蟻群演算法........... 11
第三章 研究方法........... 15
3.1 系統規劃........... 15
3.1.1 旅遊排程特性說明........... 15
3.1.2 環境架構........... 17
3.1.3 旅遊伺服器架構........... 19
3.1.4 資料庫架構........... 21
3.1.5 系統流程........... 22
3.2 蟻群演算法於旅遊行程規劃........... 25
3.2.1 電子地圖與現實環境對照........... 25
3.2.2 數學模式建立........... 27
3.2.3 蟻群演算法應用於旅遊路線推薦........... 30
第四章 模擬與實作........... 37
4.1 模擬環境........... 37
4.2 模擬評估方法........... 40
4.3 實際例題測試........... 47
第五章 結論與未來展望........... 50
參考文獻........... 51
Extended Abstract........... 53
簡歷(CV)........... 56

[1]M. Dorigo, V. Maniezzo, and A. Colorni, “Ant System: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics—Part B, Vol. 26, No. 1, pp. 29–41, Feb. 1996.
[2]L.M. Gambardella and M. Dorigo, “Solving symmetric and asymmetric TSPs by ant colonies,” in Proc. 1996 IEEE International Conference on Evolutionary Computation (ICEC’96), pp. 622–627, May. 1996.
[3]M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-56, Apr. 1997.
[4]M. Dorigo and L. M. Gambardella, “Ant colonies for the traveling salesman problem,” BioSystems, Vol. 43, No. 2, pp. 73–81, July 1997.
[5]Yin-Fu Huang and Chao-Nan Chen, “Implementation for the arrangement and mining analysis of traveling schedules,” Journal of Information Science and Engineering, Vol. 22, No. 1, pp. 123-146, 2006.
[6]M. Numazawa, and K. Shibata, “A travel scheduling system based on spot evaluation,”2008 IEEE International Conference on Systems, Man and Cybernetics (SMC 2008), pp. 986-990, Oct. 2008.
[7]Yin-Fu Huang and Kun-Ye Zheng, “Schedule arrangement on mobile devices in a GIS environment,” 2010 IEEE Symposium on Industrial Electronics and Applications (ISIEA), pp. 334-339, Oct. 2010.
[8]Chen-Shu Wang, Chia-Chuan Yeh and Chun-Yi Li, “Intelligence traveling schedule recommender based on commonsense reasoning algorithm,” 2010 International Conference on Computer and Communication Engineering (ICCCE), pp. 1-6, May. 2010.
[9]He Li and Lai Zhijian, “The study and implementation of mobile GPS navigation system based on Google Maps,” 2010 International Conference on Computer and Information Application (ICCIA), pp. 87-90, Dec. 2010.
[10]E. H. -C. Lu, Chih-Yuan Lin and V. S. Tseng, “Trip-Mine: An Efficient Trip Planning Approach with Travel Time Constraints,” 2011 12th IEEE International Conference on Mobile Data Management (MDM), Vol. 1, pp. 152-161, June. 2011.
[11]Young-Min Kim, Eun-Jung Lee and Hong-Shik Park, “Ant Colony Optimization Based Energy Saving Routing for Energy-Efficient Networks,” IEEE Communications Letters, Vol. 15, No. 7, pp.779-781, July 2011.
[12]P. Vansteenwegen, W. Souffriau and D. Van Oudheusden, “The city trip planner: An expert system for tourists,” Expert Systems with Applications, Vol. 38, No. 6, pp. 6540-6546, June 2011.
[13]Min Xie, L. V. S. Lakshmanan, P. T. Wood, “CompRec-Trip: A composite recommendation system for travel planning,” 2011 IEEE 27th International Conference on Data Engineering (ICDE), pp. 1352-1355, April 2011.
[14]Yajuan DENG and Shaorong HU, “Route Optimization of Multi-modal Travel Based on Improved Genetic Algorithm,” 2011 International Conference on Transportation, Mechanical, and Electrical Engineering, pp. 1701-1704, Dec. 2011.
[15]Jianyuan Guo, Limin Jia, Jie Xu and Yong Qin, “An Algorithm for Trip Planning with Constraint of Transfer Connection in Urban Mass Transit Network,” 2012 11th International Symposium on Distributed Computing and Applications to Business, Engineering & Science (DCABES), pp. 341-344, Oct 2012.
[16]Ying Lin, Jun Zhang, H. S. -H. Chung, W. H. Ip, Yun Li and Yu-hui Shi, “An Ant Colony Optimization Approach for Maximizing the Lifetime of Heterogeneous Wireless Sensor Networks,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 42, No.3, pp. 408-420, May 2012.
[17]L. S. C. Pun-Cheng, “An Interactive Web-Based Public Transport Enquiry System With Real-Time Optimal Route Computation,” IEEE Transactions on Intelligent Transportation Systems, Vol. 13, No. 2, pp. 983-988, June 2012.
[18]W. Watthayu, “Ant colony algorithm-based travelling route problems: A case study in Bangkok,” 2012 8th International Conference on Computing Technology and Information Management (ICCM), pp. 289-292, April 2012.
[19]Huagang Yin, Changhu Wang, Nenghai Yu and Lei Zhang, “Trip Mining and Recommendation from Geo-tagged Photos,” 2012 IEEE International Conference on Multimedia and Expo Workshops (ICMEW), pp. 540-545, July 2012.
[20]TSPLIB, http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
[21]Google Maps API, https://developers.google.com/maps/?hl=zh-tw