含住宿及興趣景點考量之旅遊規劃系統

本論文提出一套基於旅行推銷員演算法之旅遊規劃系統，適用於開車自助旅行者。此系統能針對自助旅行者給定之必經景點、住宿飯店、必經路徑、每日旅遊距離上下限以及跨天總景點數，推薦出符合使用者條件的旅遊行程。本研究包含兩部份，第一部份是各種旅遊準則的設計，根據使用者給定的條件轉換為距離準則符合度、必經路徑準則符合度、興趣景點準則符合度及跨天總景點數準則符合度，並以等權重的方式計算總準則符合度作為路線好壞的依據。第二部分是各種實驗的設計，除了設計三種常見的旅遊型態，也針對較多景點、分散式景點及在限制跨天總景點數下之旅遊型態作討論，以滿足各種使用者的需求，並針對每項實驗觀察其收斂速度，進而了解搜尋效率之優劣。本旅遊系統的設計與實作，採用地標三角A*(ALT)演算法來計算景點間的最短距離，另外使用模擬退火演算法來安排景點的探訪順序，使其總移動距離接近最短。根據實驗結果顯示，此種近似解的探訪順序誤差及時間皆在可容忍範圍內，方便使用者作自助旅遊之安排。

關鍵字

住宿；旅行推銷員問題；最短路徑演算法；旅遊規劃系統

並列摘要

This work presents a travel recommender system based on solution of the traveling salesman problem. The system is intended for driving travelers with accommodation in mind. It can provide a suitable tour itinerary given the required spots, hotels, and paths; optional spots of varying interest levels; the per day upper and lower bounds for touring time and distance; and the fixed number of total visited spots. The work will first introduce the design of various criteria which include the distance criterion, the time criterion, the required path criterion, the interest spots criterion, and the total visited spots criterion. These criteria are merged on a weighted basis to evaluate the goodness of a tour itinerary. A search algorithm based on the simulated annealing is used to search for the best tour itinerary. In current implementation, the shortest time or distance between adjacent spots in an itinerary is computed by the A* with landmark and triangle algorithm (ALT). For demonstration, several experiments are conducted which include the 3 common modes of travel patterns: the base camp pattern, the regional tour pattern, and the trip-chaining pattern; and other special cases: one with many spots, one with dense spots, and one with a fixed number of total visited spots. The convergence speed for each experiment is also shown. The results show that the sub-optimal solution returned by the simulated annealing is acceptable in terms of execution time and deviation from the optimal solution. Thus the system is fit for personal independent travelers who want to plan a tour with accommodations on their own.

並列關鍵字

Accommodations ； Traveling Sslesman Problem ； Shortest Path Alogorithm ； Tour Planning System

參考文獻

[5] 蕭雍勳(2003)。都市地區旅遊路線模式影響因素之研究。朝陽科技大學休閒事業管理系。

[1] 陳囿成(2007)。基於旅行推銷員演算法之旅遊行程規劃研究─以台灣地圖為例。淡江大學資訊管理研究所碩士論文，台北縣。

[4] 張宏瑋(2007)。動態式準則評估於旅遊行程安排之最優化。大同大學資訊經營研究所碩士論文，台北市。

[8] Garey, M.R. and Johnson, D.S.(1979), Computers and Intractability: A Guide to the Theory of NP-completeness, W.H.Freeman and Company.

[10] Hoffman, A. J. and Wolfe P. (1985), “History,” The Traveling Salesman Problem: A Guide Tour of Combinatorial Optimization. Edited by Lawler, E. L. et. al., Wiley.

國際替代計量

含住宿及興趣景點考量之旅遊規劃系統

全文下載

主題瀏覽