多天數(shù)旅遊行程規(guī)畫系統(tǒng)之實(shí)作

《多天數(shù)旅遊行程規(guī)畫系統(tǒng)之實(shí)作》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

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

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

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

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

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

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

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