基於旅行推銷員演算法之旅遊行程規劃系統 : 以台灣地圖為例

機構典藏 > College of Business and Management > Graduate Institute & Department of Information Management > Thesis > Item 987654321/34192

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/34192

Title:	基於旅行推銷員演算法之旅遊行程規劃系統 : 以台灣地圖為例
Other Titles:	A tour planning system based on solving the traveling salesman problem using the Taiwan map 基於旅行推銷員演算法之旅遊行程規劃系統 : 以臺灣地圖為例
Authors:	陳囿成;Chen, Yu-cheng
Contributors:	淡江大學資訊管理學系碩士班魏世杰;Wei, Shih-chieh
Keywords:	旅行推銷員問題;最短路徑演算法;旅遊規劃系統;Traveling Salesman Problem;Shortest Path Algorithm;Tour Planning System
Date:	2007
Issue Date:	2010-01-11 05:01:01 (UTC+8)
Abstract:	本論文提出一套基於旅行推銷員演算法之旅遊規劃系統，此系統能針對自助旅行者給定之旅遊時間、興趣類別、以及景點範圍，推薦出符合使用者條件的旅遊行程。本研究包含三部份，第一部分是旅行推銷員問題TSP（Traveling Salesman Problem）近似法篩選，本文取基因演算法、螞蟻演算法、模擬退火，以標準案例實驗查看各演算法效果，取時間短也比較接近正確解者。第二部份是最短路徑找尋法的篩選，在Web Services環境下測試Dijkstra、直線距離A、有向地標A、無向地標A共四種演算法的速度，挑選速度快而且沒有誤差的方法。第三部份是挑選景點方面，分為縣市模式及中心點模式，滿足使用者不同需求；安排住宿方面，能為每一天安排符合住宿等級而距離最近的旅館。本旅遊系統的設計與實作，最後選出有向地標A來計算景點間的最短距離，另外使用模擬退火演算法來安排景點的探訪順序，使其總移動距離接近最短。根據實驗結果證明，此種近似解的探訪順序誤差在可容忍範圍內，方便使用者作自助旅遊之安排。 A tour planning system based on solving the traveling salesman problem is proposed. Given the per-day traveling times, categories of interest, and the range of scenic spots, the system can recommend a suitable tour plan for the user. The research divides into 3 parts. The first part is the evaluation of three approximation algorithms for solving the traveling salesman problem which include the genetic, the ant colony optimization and the simulated annealing algorithms. Selected cases from a standard test set are tested to find an algorithm which returns a result close to the optimal answer and less time-consuming. The second part is the evaluation of four shortest path web services which include the Dijkastra, the Euclidean A, the directional landmark-based A, and the undirectional landmark-based A* algorithms. A randomly generated test set is tested to find a web service which returns a result fast with least error. The third part is the tour planning itself which includes selection of scenic spots and hotels. To pick scenic spots for visit, our system provides a district mode and a range mode to satisfy different user needs. To pick hotels, our system tries to arrange a hotel both close in distance to the itinerary and in rank to the given grades of hotels. As result, the directional landmark-based A* web service is selected to calculate the shortest distance between two scenic spots. Also the simulated annealing algorithm is selected to arrange the visit order such that the total moving distance in order is approximate to the shortest one. According to the experiment result, the approximation error is tolerable. Thus the proposed tour planning system is suitable for independent travelers who want to arrange self-guided tours spanning several days on their own.
Appears in Collections:	[Graduate Institute & Department of Information Management] Thesis

Files in This Item:

File	Size	Format
	0Kb	Unknown	839	View/Open

Loading...