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

第一章、	緒論	1
1.1	研究背景及動機	1
1.2	研究目的及重點	1
1.3	研究範圍及限制	1
1.4	論文架構	2
第二章、	文獻探討	3
2.1 旅遊規劃系統	3
2.2 旅行推銷員問題（Traveling Salesman Problem）	4
2.2.1 基因演算法（Genetic Algorithm）	4
2.2.2 螞蟻演算法（Ant Colony Optimization）	5
2.2.3 模擬退火（Simulated Annealing）	6
2.3 有收益之旅行推銷員問題（Traveling Salesman Problem with Profits）	7
2.4 最短路徑搜尋演算法	8
2.5 Web Services相關協定	9
2.5.1 XML-RPC	9
2.5.2 SOAP	9
2.5.3 WSDL	10
第三章、	方法介紹	12
3.1 問題定義	12
3.2 挑選景點	13
3.3 景點排序	15
3.4 安排住宿	15
第四章、	實作架構	17
4.1 地圖資料	18
4.2 最短路徑模組評估	19
4.3 排程模組評估	26
4.4系統架構及旅途規劃例	28
4.5 結果討論	43
第五章、	結論與未來發展	45
參考文獻	47
圖目錄

圖 1 SOAP message的主要元素	10
圖 2 WSDL規範	11
圖 3 使用增量參數Δd的中心點模式（Δd > 0）挑選景點法	15
圖 4 使用Δd參數影響景點選擇示意圖	15
圖 5 系統架構圖	17
圖 6 Dijkstra距離成本最短路徑服務的WSDL文件內容	21
圖 7 客戶端要求Dijkstra距離成本最短路徑服務的SOAP封裝之http內容	23
圖 8 伺服端回覆Dijkstra距離成本最短路徑服務的SOAP封裝之http內容	24
圖 9 距離成本平均所需Web Services時間	25
圖 10 時間成本平均所需Web Services時間	25
圖 11 ulyssess16結果比較長條圖	27
圖 12 ulyssess22結果比較長條圖	27
圖 13 att48結果比較長條圖	27
圖 14 berlin52結果比較長條圖	27
圖 15 旅遊規劃流程圖	29
圖 16 總長度差異示意圖	31
圖 17 本旅遊行程規劃系統操作畫面	31
圖 18 案例1─11景點、2旅館地圖位置	34
圖 19 案例2─8景點、1旅館地圖位置	37
圖 20 案例3─8景點、1旅館地圖位置	39
圖 21 案例4─16景點、3旅館地圖位置	43
表目錄

表 1 使用者輸入條件	12
表 2 系統內建資訊列表	12
表 3 實驗環境	17
表 4 地標地物點資料欄位	18
表 5 道路圖層資料欄位	18
表 6 路段向量資料欄位	18
表 7 道路節點圖層資料欄位	19
表 8 前處理的時間與所需硬碟空間比較	25
表 9 各級道路速限表	25
表 10 各演算法參數列表	26
表 11 四個實際測試案例輸入條件比較表	30
表 12 案例1條件輸入	32
表 13 案例1結果時間表	32
表 14 案例2條件輸入	35
表 15 案例2結果時間表	35
表 16 案例3條件輸入	37
表 17 案例3結果時間表	38
表 18 案例4條件輸入	40
表 19 案例4結果時間表	40
表 20 四旅遊規畫案例之成本誤差比及執行時間比	44

[1]	交通部運輸研究所，路網數值圖1.1版，http://www.iot.gov.tw/mp.asp，2004年。
[2]	李昇暾、詹智安，JAVA Web Services實務程式設計，旗標，2004年。
[3]	吳瑞千、林惠娟、江鳳儀，用類神經的方法試解推銷員問題，http://wayne.cs.nthu.edu.tw/~roland/nn/index2c.html。
[4]	柯博昌、高怡君、楊佳蕙，以服務導向為基礎之個人化旅遊代理人系統，International Conference of Information Management，高雄縣大樹鄉，2006年。
[5]	紀婉容、許永真，以族群競爭式基因演算法解決具有次序與時間限制的載運路徑規劃問題，臺灣大學台大工程學刊，第九十期，第121–130頁，2004年。
[6]	連英惠，智慧型旅遊路線排程系統，靜宜大學資訊管理系碩士論文，2002年。
[7]	陳泰瑜，基於旅遊偏好之個人化行程推薦系統，清華大學資訊工程系碩士論文，2005年。
[8]	葉禮宗，對話介面代理人─以推薦旅遊行程為例，清華大學資訊工程系碩士論文，2002年。
[9]	謝逢鳴，在容錯下最短路徑演算法之研究，淡江大學資訊管理系碩士論文，2006年。
[10]	謝東穎，個人旅遊系統的雛型設計與實作，靜宜大學資訊管理系碩士論文，2004年。
[11]	E. Cerami, “Web Services Essentials, First Edition”, O’Reilly, 2002.
[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.
[15]	D. Feillet, P. Dejax, and M. Gendreau, “The Selective Traveling Salesman Problem and extensions: An overview”, Technical Report CER 00-05, A Laboratoire Productique Logistique, Ecole Centrale Paris, 2000.
[16]	D. Feillet, P. Dejax, and M. Gendreau, “Traveling Salesman Problems with Profits: An Overview”, the OR Peripatetic Post-Graduate Programme, Paris, 2001.
[17]	M. Fischetti, J.J. Salazar Gonz´alez., and P. Toth, “A Branch-and-Cut algorithm for the Generalized Traveling Salesman Problem,” Operations Research, 45(3), pp.378-394, 1997.
[18]	M. Gendreau, G. Laporte, F. Semet, “A Branch-and-Cut Algorithm for the Undirected Selective Traveling Salesman Problem,” Networks, 32(4), pp.263-273, 1998.
[19]	A.V. Goldberg and C. Harrelson, “Computing the Shortest Path: A* Search Meets Graph Theory,” 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, 2005.
[20]	B. Golden, L. Levy, & R. Vohra, “The Orienteering Problem,” Naval Research Logistics, 34, pp.307-318, 1987.
[21]	Google, “Google Earth,” http://earth.google.com/.
[22]	P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, SSC4 (2), pp.100-107, 1968.
[23]	J. H. Holland, “Adaptation in Natural and Artificial Systems,” The MIT Press, pp.141-153, 1975.
[24]	S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi, “Optimization by Simulated Annealing,” Science, 220(4598), pp.671-680, 1983.
[25]	G. Laporte and S. Martello, “The Selective Travelling Salesman Problem,” Discrete Applied Mathematics, 26(2-3), pp.193–207, 1990.
[26]	S.-H. Liang, “Recommending a Trip Plan By Negotiation With a Software Travel Agent,” Master’s Thesis, Tsinghua University, 2001.
[27]	Maction, “PaPaGO! V7,“ http://www.papago.com.tw/.
[28]	A. Maruyama, N. Shibata, Y. Murata, K. Yasumoto, and M. Ito, “A Personal Tourism Navigation System to Support Traveling Multiple Destinations with Time Restrictions,” 18th International Conference on Advanced Information Networking and Applications, Volume 2, pp.18-21, 2004.
[29]	A. Maruyama, N. Shibata, Y. Murata, K. Yasumoto, and M. Ito, “P-Tour: A Personal Navigation System for Tourism,” Proc. of 11th World Congress on ITS, Volume 2, pp.18-21, 2004.
[30]	A. Mingozzi, L. Bianco, and S. Ricciadelli, “Dynamic Programming Strategies for the Travelling Salesman Problem with Time Windows and Precedence Constraints,” Operations Research, 45(3), pp.365-377, 1997.
[31]	M. Modschinga, R. Kramera, and K. ten Hagen, “Integration of a Restaurant as a Tour Component into a Tour Guide Planning System,” ?, 2005.
[32]	I. Pohl “Bi-directional Search,” Machine Intelligence, 6, Edinburgh Univ. Press, Edinburgh, pp.124-140, 1971.
[33]	Simple Object Access Protocol 1.1, http://www.w3.org/TR/2000/NOTE-SOAP-20000508/.
[34]	Sun, “Java Web Services Developer Pack,” http://java.sun.com/webservices/jwsdp/index.jsp.
[35]	T. Thomadsen and T. Stidsen, “The Quadratic Selective Travelling Salesman Problem,” Technical Report 17 Informatics and Mathematical Modeling Technical University of Denmark, 2003.
[36]	TSPLIB, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.
[37]	P. Vansteenwegen, D. Van Oudheusden, “Selection of Tourist Attractions and Routing Using Personalised Electronic Guides,” ENTER, Ecole Hoteliere De Lausanne, 2005.
[38]	Web Services Description Language (WSDL) 1.1, http://www.w3.org/TR/wsdl/.
[39]	XML-RPC, http://www.xmlrpc.com/.
[40]	L. Yao, B. Huang & D.-H. Lee, “A Criteria-based Approach for Selecting Touring Paths Using GIS & GA,” Intelligent Transportation Systems, 2, pp.958-963, 2004.