一種基于評價指標體系的優(yōu)化TSP模型在多日旅行規(guī)劃中的應用

劉長迎,高遠昕,湯恬恬,楊 柳

(南京信息工程大學 a.數(shù)學與統(tǒng)計學院; b.大氣科學學院;c.應用氣象學院,南京 210044)

0 引 言

隨著生活水平的提高, 人們對旅游的熱情持續(xù)增長, 優(yōu)良的旅行規(guī)劃不僅安排合理， 使旅行者觀感舒適, 還能降低旅行社成本、 提高效益[1]。 目前, 絕大多數(shù)旅行電商平臺仍采用給定起始點的單日路線規(guī)劃方案, 忽視了游客作息和不同景點觀賞時間的問題，缺乏合理性和實際意義, 多日旅行規(guī)劃成為各大旅行電商平臺亟待優(yōu)化的熱門問題。 為解決該問題, 現(xiàn)階段主要采用改進后的TSP模型進行多日旅行規(guī)劃: 文獻[2]以福州為例, 提出了一種基于時間框架的多日游行程優(yōu)化方法; 文獻[3]給出了一種基于興趣點與旅行效益值的多日行程規(guī)劃方式， 但由于此類模型不能根據(jù)實況靈活調(diào)整, 篩選出的最優(yōu)方案常常不具時效性。

為此,本文采用一種“虛擬點”的實施策略,運用基于熵權法的TOPSIS分級模型對基于旅行效率和舒適度的游客體驗感評價指標體系進行打分,進而優(yōu)化TSP模型在多日旅行規(guī)劃中的應用。改進的TSP模型可以靈活安排作息時間,亦可設置拓展端口接入實時路況、路線費用等,提高了實用價值。

1 問題描述與分析

對于旅行線路的規(guī)劃,傳統(tǒng)方法多將其轉換為基于時間或路程的旅行商問題(TSP)進行求解,得到一條不間斷的“路線環(huán)”。 而對于多日旅行規(guī)劃, 考慮到入住地的頻繁更換對旅行者十分不便,若假設每日入住同一地點(即每日旅行路線的起止點相同), 該問題便可轉換為:設置“虛擬點”將由傳統(tǒng)TSP模型所生成的“原始路線環(huán)”斷開為多段路線鏈, 每一段路線鏈對應一日的旅行規(guī)劃， 其難點在于如何設置“虛擬點”。 為此，建立基于旅行效率和舒適度的游客體驗感評價指標體系, 運用基于熵權法的TOPSIS分級模型, 對“虛擬點”的設置進行評價, 得到最優(yōu)解。

2 模型構建

2.1 生成“原始路線環(huán)”集

出行常用的5種交通方式:地鐵、公交、自駕、騎行、步行,設以上交通方式的平均速度分別為a、b、c、d、e;景點i到j(i,j=1,2…,N)有K種交通工具組合方式,假設第k(k=1,2,…,K)種組合下5種交通方式的里程分別為Aij、Bij、Cij、Dij、Eij,則該種組合總耗時為

(1)

將該問題轉化成一個關于時間的TSP問題[4-6]:構建無向圖G1,將每個景點視為一個點,構成頂點集V1={v1,v2,…,vN},其中N為計劃游覽景點數(shù);任意兩個景點交通耗時構造為一條邊,構成邊集E1={eij,i,j,…,N,i≠j};每條邊eij賦以權重tij，即交通耗時。假設2個景點的旅行順序對交通耗時沒有影響,則tij=tji,故圖G1是無向圖,其權矩陣也是對稱的。

采用蟻群算法[7-8]求解該TSP問題。由于該算法存在不穩(wěn)定性,為了盡可能尋找最優(yōu)解,在利用該算法進行多次求解后,濾去結果中超過當前次數(shù)中最優(yōu)結果20%的解,得到路線環(huán)共計L個,稱為“原始路線環(huán)”集。

2.2 設置虛擬點

對路線的多日規(guī)劃,相當于將1個“原始路線環(huán)”截斷為多段, 每段對應一日的旅行路線, 對此引入“虛擬點”進行截斷操作?！疤摂M點”的設置流程圖如圖1所示。

圖1 虛擬點設置流程Fig.1 Flow chart of virtual point setting method

①選定景點Ji(i=1,2,…,N)作為首日的起始景點,稱為首日虛擬點;②沿著原始路線環(huán),根據(jù)各景點的游玩時間、景點之間的交通耗時,在景區(qū)開放時間T的限制范圍內(nèi),確定該日的最后一個景點;③得到每日的虛擬點(如第2日首個景點為“第2日虛擬點”),重復步驟②,直至完成所有景點的游覽;④遍歷N個景點作為首日虛擬點,共得到N×L種虛擬點的設置方案。

可見,在確定首日虛擬點后,沿原始路線環(huán)順時針或逆時針進行游覽會得到不同結果,故實際將產(chǎn)生2N×L種虛擬點的設置方案。根據(jù)實際情況,可適當拓展虛擬點的設置規(guī)則②,對游覽時間、交通耗時等進行修正。本文以修正交通耗時為例，引入交通擁堵系數(shù)，設工作日早、晚高峰平均道路擁堵系數(shù)分別為a1、a2,周末早、晚高峰平均道路擁堵系數(shù)分別為b1、b2，此時,若旅行者于工作日早高峰從景點i前往景點j,則修正后的交通耗時tij′=a1×tij。

2.3 游客體驗感指標體系的建立[9]

為了尋找最優(yōu)的方案,本文基于旅行時間與舒適度,建立如下指標體系對虛擬點生成的2N×L種方案進行尋優(yōu)。

2.3.1 旅行效率影響指標 1)交通時間σ1。理想的旅行方案應當在交通上花費的時間更少。

(2)

2)等待時間σ2。 若旅行者在景區(qū)開放前到達, 則等待開放的時間將被視為一種損耗。

(3)

2.3.2 舒適度影響指標 1)旅行靈活度σ3。旅行中存在突發(fā)狀況,故旅行者某日在游覽完最后一個景點時距離景點關閉時間越長,就有更高的靈活度。

(4)

2)交通擁擠度σ4。早晚交通高峰造成的堵車會大大降低旅行舒適度。

(5)

3)景點疲憊度σ5。 若旅行者在某天游覽景點數(shù)大于日平均, 記pi=1； 否則，記pi=0。

(6)

綜上,游客體驗感評價指標體系如圖2所示。

圖2 游客體驗感評價指標體系Fig.2 Tourist experience evaluation index system

2.4 基于熵權法的TOPSIS評價模型的建立

2.4.1 數(shù)據(jù)預處理 對虛擬點生成的2N×L種方案對應的5個指標構建原始矩陣X2NL×3, 并進行趨同化處理, 將低優(yōu)指標轉化成高優(yōu)指標， 再將數(shù)據(jù)標準化, 得到標準化矩陣Z2NL×5。

(7)

2.4.2 熵權法確定權重 熵權法是指在進行指標評價的過程中,根據(jù)各指標的差異程度確定權重的一種客觀賦權方法,主要通過熵值的大小來度量該指標值所提供的信息量的有效程度[10-11]。確定權重步驟如下:對于標準化數(shù)據(jù)矩陣Z,首先計算第j個指標下第i個評價對象的指標值的比重pij

(8)

再計算第j個指標的熵值ej

(9)

其中,k=1/ln(2NL), 最終得出第j個指標對應的熵權wj

(10)

2.4.3 TOPSIS法進行評價 TOPSIS法是根據(jù)有限個評價對象與理想化目標的接近程度進行排序的方法,是在現(xiàn)有的對象中進行相對優(yōu)劣的評價[12-13]。它將各對象的評價指標值組成一個空間,通過計算空間中各點與正負理想解的距離得到與正理想解的接近程度,從而對評價對象進行定量排序。具體步驟如下:

1)計算與正負理想解的距離。據(jù)標準化數(shù)據(jù)矩陣Z,得到最優(yōu)向量Z+(正理想解)和最劣向量Z-(負理想解)

(11)

(12)

其中,wj為第j個指標的權重, 由熵權法得到。

3)計算與最優(yōu)解的接近程度。 根據(jù)以上各對象和最優(yōu)向量與最劣向量的距離, 計算各方案與理想最優(yōu)解的接近程度εi

(13)

其中： 0≤εi≤1,εi→1表明評價對象越優(yōu)。

4)據(jù)εi的大小對虛擬點所生成的方案進行綜合排序,εi越大,表明該虛擬點設置方案越優(yōu)。

3 算例分析

3.1 算例求解

根據(jù)建立的基于評價指標體系的優(yōu)化TSP模型,對南京旅游年卡覆蓋的市區(qū)24個景點進行多日旅行線路規(guī)劃。

3.1.1 構建原始路線環(huán)集并生成虛擬點 24個景點已由表1列出并編號(N=24), 同時將旅行者住所定于交通樞紐南京站附近。 運用百度地圖相關數(shù)據(jù), 根據(jù)式(1)得到每兩個景點及每個景點到南京站的最短交通用時,與景點官網(wǎng)的建議旅行時間一并代入2.1節(jié)模型,得到L=5條原始路線環(huán),如表2所示。

表1 旅游景點及編號Table 1 Tourist attractions and numbers

表2 原始路線環(huán)集Table 2 Original alignment ring set

通過數(shù)據(jù)調(diào)查,交通早高峰時段為7:00—9:00,晚高峰時段為17:00—19:00。 本文沿用2019年8月19—25日為期一周的南京早晚高峰擁堵情況,得到工作日早晚高峰平均擁堵系數(shù)a1=a2=1.656,周末早晚高峰平均擁堵系數(shù)b1=1.135,b2=1.365。再通過2.2節(jié)模型,得到240種虛擬點的設置方案。

表3 旅行線路相關指標Table 3 Travel routes and relevant indicators

圖3 最優(yōu)旅行方案線路圖Fig.3 Route map of optimal travel scheme

3.2 結果對比

為了驗證本文模型在解決多日旅行規(guī)劃問題上的優(yōu)越性, 將得到的最優(yōu)旅行路線與百度地圖生成的最優(yōu)路線進行對比。根據(jù)優(yōu)化景點數(shù)的不同,共進行5組實驗,得到各路線的εi值,從而得到優(yōu)化模型和軟件生成方案的平均εi及評分對比結果(圖4)。 從不同旅行景點數(shù)限制下路線評分對比可知,本文提出的優(yōu)化路線評分值高于地圖軟件生成的最優(yōu)路線,且隨著景點數(shù)的增多,評分增幅有顯著提升，表明本文模型得到的路線結果相較于現(xiàn)行算法更為優(yōu)質,能更加高效地解決旅行景點數(shù)較多情況下的多日行程規(guī)劃問題。

圖4 最優(yōu)路線方案結果對比Fig.4 Comparison of optimal route results

3.3 模型穩(wěn)定度分析

繪制以5條原始路線環(huán)分類的240種方案評分箱線圖(圖5)。

圖5 以5條原始路線環(huán)分類的方案評分箱線圖Fig.5 Box diagram of scheme score classified by 5 original routes

組內(nèi)來看,紅十字點被視為“離群點”而處于內(nèi)限之外, 說明這些數(shù)據(jù)點相較于數(shù)據(jù)群體非?！俺鲱惏屋汀保幢疚乃⒌脑u價模型能有效區(qū)分方案的優(yōu)劣, 篩選出來的最優(yōu)方案具有絕對的優(yōu)勢。組間來看,該評價模型對第2～4條原始路線環(huán)中虛擬點設置方案優(yōu)劣度的區(qū)分性很強,對第1條原始路線環(huán)區(qū)分度較強,且每組最優(yōu)解的評分很接近，在一定程度上彌補了因蟻群算法的不穩(wěn)定性而造成在求解TSP模型時可能引起的方案漏選,大大增強了模型整體的穩(wěn)定度。

4 結果與討論

通過引入“虛擬點”概念,對傳統(tǒng)TSP模型在多日旅行規(guī)劃中的應用進行了優(yōu)化,并從旅行效率及舒適度兩方面建立了指標體系,運用基于熵權法的TOPSIS評價模型確定出最優(yōu)方案。通過實例驗證發(fā)現(xiàn)，本文提出的基于指標體系的優(yōu)化TSP模型相較于現(xiàn)有算法,在解決多日旅行規(guī)劃時能夠獲得質量更優(yōu)的解。但研究還存在不足,尚有旅行費用及住宿問題未得到充分考慮,將來可以通過文中提及的拓展端口對模型進行修正,進一步提升實用性及穩(wěn)定性。