多代理人協商與拍賣之旅遊路線規劃

Multi-Agent Tourist Route Planning through Coalition and Negotiation in an Auction

王逸民

指導教授 ： 蘇豐文

國立清華大學/電機資訊學院/資訊工程學系/碩士(2012年)

摘要

旅遊行程規劃包含了景點、住宿與交通的完整安排，一般使用者只能表達對景點、飯店、交通方式等的大概偏好與預算，路線的細節與行程表則交由旅遊代理人來規劃安排，而旅遊的滿意程度往往取決於路線的安排與花費是否划算。這篇論文中，我們著眼於交通行程的路線規劃，但是有別於一般由一位旅遊代理人集中查詢所有相關服務並規劃最合適路線，從多位交通服務提供者的角度來提供動態的時程與彈性的票價，依照遊客實際的需求來調整班次，基於交通服務者的利潤來提供更吸引人的票價。為了提供令使用者滿意的行程，我們採用啟發式演算法來規畫並篩選出多條較符合使用者偏好的路徑，再讓交通服務代理人在以使用者偏好為價碼的拍賣中競標來提供最符合使用者需求的路徑。在這篇論文中，我們展示了交通服務提供者如何在多代理人的環境下互相協商溝通來解決旅遊路線規劃的問題，除了提升使用者的滿意度外，交通服務提供者的獲利、經營策略與隱私等議題的加入，使得整個環境更為周詳與逼真。

關鍵字

旅遊行程 ； 多代理人系統 ； 規劃 ； 溝通與協商 ； 拍賣

並列摘要

Tour planning involves the detail scheduling of scenic spots, accommodation, and routes. In general users merely provide vague preferences about the scenic spots, hotels, and type of transportation, and thus the travel agent has to arrange feasible schedules and tourist routes with these constraints and preferences. However customer satisfaction often ascribes to the smooth execution of the tourist route and high cost-effectiveness. So, in this thesis, we focus on the route planning part of a tourist plan. But in contrast to central travel agent planning based on collected timetables, multiple transportation agents are introduced to offer dynamic latest timetables and flexible ticket fares. A transportation agent adjusts vehicle, flight, or ship dispatch based on customer demands and offers appealing fares based on profits. To find out the best route fitting user preferences, a heuristic most suitable path finding algorithm is used to generate user preferred routes with variations as candidate routes, and the transportation agents within the candidate routes compete in a user-preference based auction to decide the best route. In this thesis, we show how multiple transportation agents could negotiate and form coalition with each other to form competitive and appealing tourist routes. Besides higher customer satisfaction, the integration of the profit, privacy, and business strategies of transportation agents makes the multi-agent environment more complete and believable.

並列關鍵字

Tourist route ； Multi-agent system ； Planning ； Negotiation and coalition ； Auction

參考文獻

[3] World Tourism Organization UNWTO http://www.unwto.org/

[6] Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson.1999. Graph Theory, 1736-1936. Oxford University Press.

[8] Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, Philip M., II. 1977. An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM Journal on Computing 6 (5): 563-581.

[10] Clemons, E., Hahn, I. and Hitt, L.. 2002. Price dispersion and differentiation in on-line travel - an empirical investigation. Management Science Volume 48 Issue 4. 534-549.

[13] Dickson K. Chiu, Yves T. Yueh, Ho-Fung Leung, and Patrick C. Hung. 2009. Towards ubiquitous tourist service coordination and process integration: A collaborative travel agent system architecture with semantic web services. Information System Frontiers Volume 11 Issue 3. 241-256.