本論文提出一套基於旅行推銷員演算法之旅遊規劃系統，適用於開車自助旅行者。此系統能針對自助旅行者給定之必經景點、住宿飯店、必經路徑、每日旅遊距離上下限以及跨天總景點數，推薦出符合使用者條件的旅遊行程。本研究包含兩部份，第一部份是各種旅遊準則的設計，根據使用者給定的條件轉換為距離準則符合度、必經路徑準則符合度、興趣景點準則符合度及跨天總景點數準則符合度，並以等權重的方式計算總準則符合度作為路線好壞的依據。第二部分是各種實驗的設計，除了設計三種常見的旅遊型態，也針對較多景點、分散式景點及在限制跨天總景點數下之旅遊型態作討論，以滿足各種使用者的需求，並針對每項實驗觀察其收斂速度，進而了解搜尋效率之優劣。本旅遊系統的設計與實作，採用地標三角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.

目錄
1. 第一章  緒論	1
1.1 研究背景與動機	1
1.2 研究問題與目的	1
1.3 研究架構	2
2. 第二章  文獻探討	4
2.1 旅行銷售員問題 (Traveling Salesman Problem)	4
2.2 旅遊路線模式 (Tourist Itinerary Model)	4
2.3 多目標規畫法	6
2.4 模擬退火 (Simulated Annealing)	7
2.5 多目標模擬退火 (Multi-Objective Simulated Annealing)	10
2.6 螞蟻演算法、基因演算法及模擬退火演算法之比較	12
3. 第三章 方法介紹	14
3.1 問題定義	14
3.2 模擬退火解法	15
3.2.1 決策因子	16
3.2.2 準則類型	17
3.2.3 準則符合度計算	17
3.2.4 準則符合度計算例	23
3.2.5 挑選鄰居	25
3.2.6 新增或替換景點	27
3.2.7 溫度平衡條件	27
3.2.8 終止條件	27
3.3 模擬退火找尋最短旅遊路線流程圖	28
4. 第四章 實作架構	31
4.1 實驗設計	31
4.2 實驗環境	31
4.3 模擬退火參數設定	31
4.4 命令列參數設定	32
4.5 實驗結果	34
4.5.1 基本營區模式設計	34
4.5.2 區域旅遊模式設計	37
4.5.3 鏈狀旅遊模式設計	40
4.5.4 較多景點旅遊規劃例	44
4.5.5 分散式景點旅遊規劃例	47
4.5.6 限制跨天總景點數旅遊規劃例	50
4.5.7 收斂速度實驗	54
4.5.8 時間準則旅遊規劃例	58
5. 第五章  結論與未來發展	62
6. 參考文獻	64

圖目錄
圖 1 1：研究流程	3
圖 2 1：Lue et al.旅遊路線空間模式(蕭，2003)	6
圖 2 2：遞減演算法之搜尋能力示意圖(王，2002)	8
圖 2 3：模擬退火法之搜尋能力示意圖(王，2002)	9
圖 2 4：模擬退火演算法程序圖	10
圖 2 5：模擬退火與螞蟻演算法及基因演算法比較圖(陳，2007)	12
圖 3 1：本研究距離準則符合度示意圖(參考自張，2007)	18
圖 3 2：本研究時間準則符合度示意圖(參考自張，2007)	19
圖 3 3：跨天總景點數符合度示意圖	22
圖 3 4：挑選鄰居流程	26
圖 3 5：模擬退火找尋最短旅遊路線流程圖	30
圖 4 1：基本營區模式退火路線規劃圖(其結果與窮舉法相同)	37
圖 4 2：區域旅遊模式退火路線圖(其結果與窮舉法相同)	40
圖 4 3：鏈狀旅遊模式最佳解	43
圖 4 4：較多景點旅遊規劃路線圖	46
圖 4 5：分散式景點旅遊規劃例路線圖	49
圖 4 6：限制跨天總景點數退火解	52
圖 4 7：限制跨天總景點數窮舉解	53
圖 4 8：基本營區模式收斂速度示意圖	54
圖 4 9：區域旅遊模式收斂速度示意圖	54
圖 4 10：鏈狀旅遊模式收斂速度示意圖	55
圖 4 11：較多景點旅遊規劃例收斂速度示意圖	55
圖 4 12：分散式景點旅遊規劃例收斂速度示意圖	56
圖 4 13：限制跨天總景點數旅遊規劃例收斂速度示意圖	56
圖 4 14：使用時間準則最佳規劃路線圖(景點數=8)	60
圖 4 15：使用距離準則最佳規劃路線圖(景點數=15)	60

表目錄
表 2 1：實際物理系統與最佳化問題對照表(王，2002)	8
表 3 1：使用者輸入條件	15
表 3 2：系統內建資訊(參考資料：交通部運研所路網數值圖1.3版)	15
表 3 3：有無指定興趣景點及跨天總景點數下之求解法比較表	28
表 4 1：實驗環境	31
表 4 2：參數設定表	32
表 4 3：命令列參數說明	33
表 4 4：基本營區模式條件參數	35
表 4 5：基本營區模式模擬退火解	36
表 4 6：基本營區模式窮舉解	36
表 4 7：區域旅遊模式條件參數	38
表 4 8：區域旅遊模式模擬退火解	39
表 4 9：區域旅遊模式窮舉解	39
表 4 10：鏈狀旅遊模式條件參數	41
表 4 11：鏈狀旅遊模式模擬退火解	42
表 4 12：鏈狀旅遊模式窮舉解	42
表 4 13：較多景點旅遊條件參數	44
表 4 14：較多景點旅遊規劃結果	45
表 4 15：分散式景點旅遊規劃例條件參數	47
表 4 16：分散式景點旅遊規劃例模擬退火解	48
表 4 17：限制跨天總景點數旅遊規劃例條件參數	50
表 4 18：限制跨天總景點數旅遊規劃例退火解	51
表 4 19：限制跨天總景點數旅遊規劃例窮舉解	51
表 4 20：時間準則旅遊規劃例條件參數	58
表 4 21：時間準則實驗結果	59
表 4 22：距離準則實驗結果	59

[1]	陳囿成(2007)。基於旅行推銷員演算法之旅遊行程規劃研究─以台灣地圖為例。淡江大學資訊管理研究所碩士論文，台北縣。
[2]	江柏彥(2006)。蟻群系統於多目標流程式排程有效解之研究。天主教輔仁大學管理學研究所碩士論文，台北市。
[3]	王裕元(2002)。應用多目標決策模式建立護理人員排班方法之研究。國立屏東科技大學工業管理所碩士論文，屏東縣。
[4]	張宏瑋(2007)。動態式準則評估於旅遊行程安排之最優化。大同大學資訊經營研究所碩士論文，台北市。
[5]	蕭雍勳(2003)。都市地區旅遊路線模式影響因素之研究。朝陽科技大學休閒事業管理系。
[6]	故鄉市場調查公司(2007)。中華民國96年國人旅遊狀況調查報告。交通部觀光局。
[7]	交通部運輸研究所(2006)。交通部運輸研究所路網數值圖1.3版。
[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.
[9]	Hillis, W.D. (1992), “Coevolving parasites improve simulated evolution as an optimization procedure,” In Langton, C.G., Taylor, C., Farmer, J.D., & Rasmussen, S. (Eds), Artificial Life II , Redwood City, CA: Addison Wesley. , pp.313-324.
[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.
[11]	Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983), “Optimization by simulated annealing,” Science, 220, 671-680.
[12]	Koopmans, T. C. (1951), “Analysis of Production as an efficient combination of activities,” Activity analysis of production and allocation, Cowles Commission Monograph 3, Wiley, New York,pp. 33-91.
[13]	Kuhn, H.W. and Tucker, A.W. (1951), “Nonlinear programming”, Proceeding of 2nd Berkeley Symposium, 481-492, Berkeley, University of California Press.
[14]	Loukil, T., Teghem, J., & Tuyttens, D. (2005), “Solving multi-objective production scheduling problems using metaheuristics,” European Journals of Operational Research, 26, 679-693.
[15]	Lue, C. C., Crompton, J. L. and Fesenmaier, D. R.（1993）, “Conceptualization of Multi-destination Pleasure Trips,” Annals of Tourism Research, Vol. 20, No. 2, pp. 289-301.
[16]	Metropolis, N., Rosenbluth, A., Teller, A., & Teller, E. (1953), “Equation of state calculations by fast computing machines,” Journal of Chemical Physics, 21, 1087-1092.
[17]	Hassler Whitny(1934), <http://en.wikipedia.org/wiki/Traveling_salesman_problem>, (Retrieved Feb. 2009)