臺灣博碩士論文加值系統

本文提出一智慧型旅遊路線排程系統，並以WWW為基礎架構出一網站，供國人免費使用，以提高國人週休二日之旅遊品質。為使本系統充份具智慧，本研究包含兩部份，第一部份，本研究首先定義旅遊排程問題(Tripscheduling Problem, TP)與旅遊推銷員問題(TSP)及最小擴張樹(MST)問題為不同問題，不可以現有TSP演算法或MST演算法解旅遊排程問題，本文提出屬於旅遊排程問題特色的樹狀圖，稱之為旅遊路由樹(Trip Routing Tree, TRT)，但因TRT複雜度高達指數時間，為解決TRT的計算與追蹤，本文繼續提出旅遊路由簡化樹(Simplified Trip Routing Tree, STRT)，使無論多複雜的N階TRT，皆可簡化為三階式的旅遊路由簡化樹。藉由STRT結合動態規劃(Dynamic Programming)及二回追蹤法(Two Pass Traversal)進行計算，可使原本複雜度高達指數時間的TRT降為多項式時間，此TRT演算法即為本文用以解決旅遊排程問題之新式可跳點式空間路徑搜尋演算法。第二部份，因旅遊排程問題為一含時間(spatial)、空間(temporal)、資源(resource)、成本(cost)與偏好(preference)眾多因子與條件之複雜問題，且上述各因子又各含子因子，如何整合考量這眾多且異質之因子，對此問題本文以人工智慧、旅遊專業領域知識與多屬性效用理論為基礎，提出一人工智慧決策模型(Artificial Intelligence Decision Model, AIDM)，用以智慧地輔助STRT進行路徑之評估與抉擇。

In this research, an intelligent trip planning system is proposed, implemented,and established on a Web site based on the Word Wide Web (WWW) to promote the local traveling quality in Taiwan.
This research consists of two major parts. In the first part, we define the Trip-scheduling Problem (TP), which is different from the TravelingSalesman Problem (TSP) and the Minimum cost Spanning Tree (MST) problem. In other words, those algorithms used in the TSP or MST can not solve the trip-scheduling problem. We need to propose a new tree structure called Trip Routing Tree (TRT). However, the time complexity of TRT is exponential.Therefore, a Simplified Trip Routing Tree (STRT) is proposed in this research. If the dynamic programming technique and two-pass traversal method are applied to the STRT, the time complexity is reduced to polynomial. We propose a new algorithm based upon STRT to solve the trip-scheduling problem.However, a trip scheduling is very complicated that needs to consider many requirements or factors such as spatial, temporal, resource, cost and preference. Each factor may include many sub-factors. In the second part, to integrate above heterogeneous and variable factors into the procedure in the first part, we propose an Artificial Intelligence Decision Model (AIDM) based on the travel domain knowledge and Multi-Attribute Utility Theory (MAUT). The proposed AIDM can measure and determine the STRT path intelligently.

中文提要　………………………………………………… i
英文提要　………………………………………………… ii
誌謝　…………………………………………………… iii
目錄　…………………………………………………… iv
表目錄　…………………………………………………… vi
圖目錄　…………………………………………………… vii
第一章、 緒論 ………………………………………… 1
1.1 研究動機與背景 ………………………………… 1
1.2 研究目的 ………………………………………… 2
1.3 研究範圍與限制 ………………………………… 4
1.4 論文理論架構與研究流程 ……………………… 5
第二章、 文獻研討 …………………………………… 9
2.1 個人旅行助理 (Personal Travel Assistant, PTA)系統……………………… 9
2.2 TSP與MST演算法研討…………………………… 10
2.3 國內相關旅遊網站訪查 ………………………… 11
2.4 啟發式(heuristics)方法 ……………………… 13
2.5 多屬性效用理論(Multiattribute Utility Theory, MAUT) ………………… 13
2.6 動態規劃(Dynamic Programming) ……………… 14
2.7 網際網路地理資訊系統 ………………………… 15
2.8 人工智慧(Artificial Intelligence) ………… 15
2.9 目標最佳化問題 ………………………………… 16
第三章、 TRT演算法 ………………………………… 17
3.1 旅遊排程問題(Trip-scheduling Problem)特質研討………………………… 17
3.2 旅遊排程問題定義………………………………20
3.3 旅遊路由樹(Trip Routing Tree, TRT)……… 20
3.4 旅遊路由簡化樹(Simplified Trip Routing Tree, TRT)…………………… 23
3.5 TRT演算法 ……………………………………… 25
3.6 二回追蹤法(Two Pass Traversal)…………… 26
第四章、 人工智慧決策模型(Artificial Intelligence Decision Model, AIDM)… 32
4.1 旅遊因子分析…………………………………… 32
4.2 人工智慧決策模型……………………………… 34
4.3 人工智慧法則(AI Rule) ……………………… 35
4.4 STRT與人工智慧決策模型嵌合流程圖………… 41
第五章、 系統架構與展示………………………… 43
5.1 系統架構………………………………………… 43
5.2 系統實作………………………………………… 43
5.3 系統展示………………………………………… 47
第六章、 結論與建議……………………………… 51
6.1 結論……………………………………………… 51
6.2 建議……………………………………………… 52
參考文獻 …………………………………………… 54
簡　　歷 …………………………………………… 56

[1] 戶外生活圖書股份有限公司，「中台灣汽車逍遙遊」(2001)
[2] 多重準繩決策, Milan Zeleny著, 卓武雄譯, 1992.
[3] 故鄉巿場調查股份有限公司，「中華民國八十八年國人國內旅遊狀況調查報告」，委託單位交通部觀光局(1999)
[4] 陳肇男，「旅遊行程安排及探勘分析之實作」，碩士論文，雲林科技大學資訊管理系研究所(2000)。
[5] 梁書豪，「旅遊代理人以協商之方式推薦旅遊行程」，碩士論文，國立清華大學資訊工程學系研究所(2001)
[6] 廖鴻圖，廖平，「資料結構突破」，儒林出版社(2000)
[7] 賴聯福，劉佳灝，李充中，「應用人工智慧與資料庫方法於排課系統之自動化」，第五屆人工智慧與應用研討會論文集(2000)。
[8] 謝伸典，「分散式GIS-T之建立-以WWW 旅遊交通資訊系統為例」，碩士論文，　朝陽科技大學資訊管理系研究所(2000)。
[9] American International Travel, http://www.aitv.com/.
[10]Booking on Line, http://www.bookingonline.com.tw/.
[11]Balabanovic, M. and Shoham, Y., “Combining Content-based and Collaborative Recommendation,” Communication of the ACM, March 1997.
[12]Bellman, R., Dynamic Programming, Princeton University Press Princeton, N.J., 1957.
[13]Dhar, V. and Ranganathan, N., "Integer programming vs. expert An experimental comparison," Communications of the ACM, 33(3): 323-336, 1990.
[14]FIPA Org, http://www.fipa.org/
[15]FIPA 97 Draft Specification Part 4 (1997) Personal Travel Assistance,1997FIPA - Foundation for Intelligent Physical Agents.
[16]Gokhale M., et al., “Combining Content-based and Collaborative Filtering in an On-Line Newspaper,” ACM SIGIR Workshop on Recommender Systems,Berkeley, CA, 1999.
[17]Grill, J., et al, “EUROTRIP: Trip Planning System,” in the Proc. of DRIVE Conference: Advanced Telematics in Road Transport, vol. 1, pp. 824-830.Feb. 1991
[18]Gudes, E., Solotorevsky, G., and Meisels, A., "RAPS: A rule-based language specifying resource allocation and timetabling problems," IEEE Transactions on Knowledge and Data Engineering, 6(5):681-697,1994.
[19] Horowitz, E. and Sahni, S., “Fundamentals of Computer Algorithms”, 1990.
[20]John, P. and Peter, J.,“The acquisition of pre-trip information: A stated preference approach,”Transpn, 20, pp. 179-198, 1993.
[21]Lyons, G.D. and Mike, M.,“Traveler information and the Internet,”Traffic
Engineering and Control, pp.24-32, January 1998.
[22]Monfroglio , A., "Time-tabling through a deductive database: A case study," Data and Knowledge Engineering, 3:1-27,1988.
[23]Nelson, P.C., Lain, C., and Dillenburg, J.,“Vehicle-based Route Planning In Advanced Traveler Information Systems,”Intelligent Vehicles ''93 Symposium.
[24]Parsons, S. and Jennings, N.R., “Negotiation through Argumentation – A Preliminary Report,” in the Proceedings of the 2nd International Conference on Multi-Agent Systems, 1996.
[25]Travel Major, http://www.travelmajor.com/.
[26]Volksen, G., Dieterich, H., and Steiner, D., “Intelligent agents for personal travel assistance,” in the Proc. ITS Congress’97, Berlin 1997.http://www.motiv.de/
[27]Wu, S.H. and Soo, V.W., “Game Theoretic Approach to Multi-Agent Coordination by Negotiation with a Trusted Third Party,” in the Proceedings of the 3rd International Conference on Autonomous Agents, 1999.