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

A Tour Planning System Based on Solving the Traveling Salesman Problem Using the Taiwan Map

陳囿成(Yu-Cheng Chen)

指導教授 ： 魏世杰

淡江大學/管理學院/資訊管理學系碩士班/碩士(2007年)

https://doi.org/10.6846/TKU.2007.00512

摘要

本論文提出一套基於旅行推銷員演算法之旅遊規劃系統，此系統能針對自助旅行者給定之旅遊時間、興趣類別、以及景點範圍，推薦出符合使用者條件的旅遊行程。本研究包含三部份，第一部分是旅行推銷員問題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.

並列關鍵字

Traveling Salesman Problem ； Shortest Path Algorithm ； Tour Planning System

參考文獻

[9] 謝逢鳴，在容錯下最短路徑演算法之研究，淡江大學資訊管理系碩士論文，2006年。

[10] 謝東穎，個人旅遊系統的雛型設計與實作，靜宜大學資訊管理系碩士論文，2004年。

[12] G.. Dantzig, R. Fulkerson, and S. Johnson, ”Solution of a Large-Scale Travelling Salesman Problem,” Operations Research, 2, pp.393-410, 1954.

[13] E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, 1, pp. 269–271, 1959.

[14] M. Dorigo, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, 1(1), pp.53-66, 1997.