多天數旅遊行程規畫系統之實作

《多天數旅遊行程規畫系統之實作》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、多天數旅遊行程規畫系統之實作魏世杰淡江大學資訊管理學系助理教授seke@mail.im.tku.edu.tw盧濟安淡江大學資訊管理學系研究生摘要規畫旅遊行程往往會考慮喜好景點及住宿等很多因素，旅遊網站的推薦行程通常是套裝一日或二日遊，無法考慮到使用者個人需求。因此本研究規畫了一套基於旅遊銷售問題之旅遊行程規畫系統，協助使用者做多天數自助旅遊之安排。本研究針對必經之點、每日旅遊距離、必經路徑、興趣景點等決策因子計算對應之符合度，以等權重方式透過模擬退火求解最佳旅遊路線。實驗顯示本作法與窮舉法之最佳解，兩者差異並不大，但卻可節省大量運算時間。關鍵字:模擬退火、旅遊行程規畫。

2、一、前言近年來，隨著社會、經濟的快速發展，國內交通運輸與交通路線逐漸發達，也帶動觀光產業的蓬勃發展。根據觀光局2007年國人旅遊狀況調查報告顯示，隨著周休二日的實施，及國民所得逐年增加，高達九成的國人曾在國內旅遊，每年旅遊次數累計達9,261萬次以上，每人平均4.78次。旅遊因此變成國人常見的遊憩休閒方式，藉著安排旅遊假期，將有助於消除平日的工作壓力，也可從大自然中獲得教育與啟發。為了因應這樣的需求，國內出現了各種旅遊網站。大部分旅行社網站只是放上自己公司的服務項目，例如販售套裝行程、代訂飯店服務等。至於各縣市政府入口網站或是各大景點網站雖然也提供景點簡介及建議，但多數

3、只是固定一日、二日遊之行程或是既定路線之規畫，無法做到客製化的服務，難以滿足使用者特定的需求。相對之下，個人旅行助理(PersonalTravelAssistant,PTA)可以克服上述缺點，提供給旅遊者全方位之服務。完整的個人旅行助理除了平時提供資訊給使用者，行前支援規畫旅程，行中也可以進行GPS、GSM、PDA為基礎之監控支援，讓使用者無論在平時、行前、行中都能充分獲得旅遊之支援，提升旅遊品質。本文將著重在行前旅程之規畫部份。二、文獻探討1.旅行銷售員問題依據陳(2006)論文整理，旅行銷售員問題(TravelingSalesmanProblem,TSP)屬求解組合

4、最佳化問題，旅遊行程規畫為其典型應用。TSP已被證實為一NP-Hard問題，有許多近似解法，例如：基因演算法、螞蟻演算法、模擬退火等。111.旅遊路線模式蕭(2003)研究整理指出，旅客從家出發到目的地走訪的行為模型有眾多型態(Lue，1993)，基本上可依旅遊到訪目的地的數量區分為單目的地旅遊和多目的地旅遊，其中，多目的地旅遊還可以細分為中途點模式，基本營區模式，區域旅遊模式，及鏈狀旅遊模式。2.多目標規畫法多目標規畫法可同時考量多個決策目標，其目的在協助決策者於有限資源及目標衝突的限制下，尋求一個較佳的行動方案。多目標規畫的基本精神為，針對每一目標建立一準則符合度，

5、尋求一個滿意解，以滿足每一個目標與準則符合度之離差總和最小。Loukiletal.(2005)歸納整理出一般多目標規畫常用的五種解法，分別為階層法，加權法，目標規畫法，相互作用法，有效解法或柏拉圖(Pareto)法。每一種方法都有其優點和缺點，例如階層法和加權法和目標規畫法需要較多的參數設定；階層法與加權法比較偏重實用性，卻無法得到所有的有效解；目標規畫法和相互作用法則是比較個案導向；而有效解法比較有通用性。3.模擬退火Metropolis,Rosenbluth與Teller(1953)提出一套模擬金屬退火過程的電腦演算程序，稱作Metropolis程序。模擬退火演算法

6、能夠透過一定的機率決定是否接受狀態往較高的能量移動，以允許接受較差的解，藉此跳脫在遞減演算法求解過程中容易陷入局部最佳解的窘境，進而收斂至整體最佳解。4.多目標模擬退火法江(2006)研究整理指出，Loukiletal.(2005)使用多目標模擬退火法(multi-objectivesimulatedannealing,MOSA)處理多目標組合問題。為了產生各種有效組合，將目標組合的權重做不同變化，每次給予所有目標一組不同的權重後就演算一次，然後讓每一組權重所產生的可能有效解集合互相凌越(dominate)。重覆此步驟多次後所留下無法被凌越的有效解就是最後的近似有效解集

7、合。本研究也將採用其精神，發展出一套結合多目標決策分析之模擬退火演算法，以解決旅程規畫問題。三、方法介紹1.問題定義本文之問題定義為給定旅遊必經景點(至少需含起終點)、住宿飯店、旅遊必經路徑(以相鄰景點順序表示)、每日旅遊距離下限及上限(使用者若不輸入，可由系統給定預設數值)、各等級興趣景點集合等，希望能規畫出一條旅遊路線，從起點出發，終點結束，滿足下列條件之下，總距離最短，通過興趣景點數愈多：(1)每日旅遊距離不得超出上界或低於下界。(2)規畫路線會經過必經景點及必經路徑。11表一列出使用者可輸入的所有條件，表二將本系統使用的主要內建地