荊懷芳

（咸陽職業(yè)技術學院財經學院 咸陽 712000）

1 引言

近年來，中國舉辦了APEC峰會，多種商業(yè)展覽等多種觀光和展覽活動，但很多游客在一個或多個日子里訪問了一個地區(qū)或城市［1］。到處游覽是不可能的，游客想要選擇他們認為最有吸引力的興趣點（POI）［2］。他們的選擇可以根據網站的信息，雜志上的文章或書店中的指南來進行。一旦做出決定，游客將決定訪問每個點的時間并選擇點之間的路線。然而由于許多因素，例如許多地方擁擠，交通事故可能發(fā)生或道路正在建設中或關閉，這些將導致旅行計劃的不確定性［3］，因此游客難以設計時間表。游客的目標是在有限的時間內盡可能多地訪問POI的旅行計劃。以往的研究大多是在靜態(tài)網絡中解決旅游行程問題，這將不可避免地造成不合理的結果［4～6］，基于靜態(tài)網絡的傳統(tǒng)旅游行程設計已經不能滿足日益增長的行程規(guī)劃需求。綜合移動和感知技術并考慮到實時交通信息，建立基于動態(tài)網絡的旅行者出行設計才能為游客提供個性化和高質量的服務。

目前，旅游行程設計問題（TTDP）常被視為定向問題（OP）的延伸［7］。OP也被稱為選擇性旅行銷售員問題（STSP）［8］，背包問題［9］，最大收集問題（MCP）［10］和銀行劫匪問題［11］。此外，OP可以歸結為資源受限TSP問題的特例（RCTSP）［12］。由于這些問題都是NP難題，大多數(shù)研究集中利用啟發(fā)式算法，例如引導式局部搜索［13］，蟻群算法［14］等。動態(tài)行程設計主要依靠移動通信技術來提供基于旅游位置的實時快速導航服務。同時，它還可以幫助游客選擇目標點并找到到達目的地的最短路線。這類移動導航包括百度地圖，高德地圖和谷歌地圖等［15］。然而，隨著生活質量和審美情趣的不斷提高，游客的喜好也隨之變化。靜態(tài)行程設計不考慮游客的具體情況，例如，旅游者的開始和結束訪問時間，當前時間，預期總時間和天氣狀況等。因此，基于情境和位置的個性化移動導航成為必然趨勢。文獻［16］設計了一個動態(tài)性的旅游指南來決定在一段時間內參觀一座城市，通過語義匹配算法接收興趣匹配點。文獻［17］提出了移動導游個性化的旅游行程設計算法。通過結合人工智能和引導式本地搜索啟發(fā)式方法，為使用移動設備的游客提供快速決策支持。

上述研究只是在基于起點，終點和預算時間內的靜態(tài)網絡研究TTDP，而不涉及動態(tài)時變網絡中的旅游行程設計問題。旅游出行網絡在實際中是依賴展覽或旅游時間。例如，展覽中高峰時間和低谷時間的旅游時間差異顯著。隨著先進的傳感器網絡，信息系統(tǒng)和數(shù)據庫的發(fā)展，在旅游行程規(guī)劃中融入動態(tài)交通信息是有效提升用戶個性化需求的方式。因此，在研究時變網絡中制定旅游出行問題時，本文在時間聚合圖的基礎上提出了一種數(shù)學規(guī)劃模型，并建立了一種標簽校正算法（LCA）來解決動態(tài)旅游行程設計問題。

2 問題描述

2.1 問題假設

時變網絡中的旅游出行設計問題可以表示為給定一組訪問點和游客偏好值，每個訪問點都有一個平均停留時間且每個訪問點只能訪問一次。這個問題的目標是如何決定訪問每個點的時間并選擇點之間的路線，以最大限度地在給定的預算時間內提高游客旅行的總效用，即所有選擇的訪問點的偏好值的總和。本文將基于以下假設解決時變網絡中的旅游出行設計問題：

假設1：在時變網絡中，邊緣上的旅行時間取決于進入的時間，即一旦進入邊緣，旅行時間由進入的起始時間給定。

假設2：游客對每個訪問點都有一個優(yōu)先值，它被設定為一個隨機整數(shù)。這個數(shù)值代表游客對這一點的興趣。在實際應用中，利用移動導航設備的信息檢索或語義識別技術來獲得該偏好值。

假設3：游客根據時間表決定行程計劃，確定預算時間是固定不變的。

假設4：一般來說，一個旅游者不止一次去旅游點，所以每一個景點最多只能被訪問一次。

假設5：不考慮旅行道路上的返程和回合現(xiàn)象。

假設6：考慮到交通傳感器網絡，信息系統(tǒng)和數(shù)據庫的廣泛使用，離散時間的旅行時間被設置為動態(tài)且可用的。

2.2 時間聚合網絡

給定網絡G=(V,E)，其中V={V,i=1,2,…,n)是節(jié)點集，E={eij|Vi,Vj∈V)是邊緣集，如果Vi與Vj相鄰，則存在一個邊eij在它們之間，|E|=m。由于邊緣和邊緣上的旅行時間是時變的，則不容易在每個邊緣上表示游客移動。因此，使用時間聚合圖來表示每個時刻的網絡變化［18］。

在時間聚合圖中，每個弧具有兩個屬性：時間序列ETij表示它們出現(xiàn)的時間點，而旅行時間序列TTij表示各個時刻的旅行時間。ETij=[1,2,…,T]代表每一時刻弧線的存在狀態(tài)，且弧線連接時的一組對應時間表示網絡拓撲隨時間變化。旅行時間序列TTij=(Tij(1),Tij(2),…,Tij(T))表示邊緣存在時的旅行時間，Tij(t)表示當入場時間是t時邊緣eij上的旅行時間。如果邊緣eij在時間t時沒有入場，則Tij(t)=∞，這意味著該邊緣不能通過并且必須等待。例如，在時刻t=1,2,3時的時變網絡如圖1所示。

圖1 基于時間聚合圖的時間相關網絡

該網絡的拓撲結構和傳播時間隨時間而變化。對于邊緣e21，其在時間t=1,2處出現(xiàn)，但在時間t=3處消失，即不通過。此外，邊緣e21的行進時間在時間t=1時等于1，并且在時間t=2時等于5。這個時間聚合圖如圖1（d）所示，其中邊e21有兩個序列屬性：[1,2]表示邊存在時的時間序列，行程時間序列(1.5,∞)表示在時刻1和2的旅行時間。

2.3 旅行演示

在時變網絡中，游客旅行利用時間和空間維度來刻畫，其中，時間可描述為離散單位，空間可表示為V={Vi|i∈[1,|V|]}。因此，旅游行程可以表示為包含元素Vi(ti)的列表，其中，Vi(ti)表示在ti時刻到達節(jié)點Vi。即旅游行程表示為P(V1,Vn)={V1(t1),…,Vn(tn)}，其中，V1是源節(jié)點，Vn是目地節(jié)點。根據時間聚合圖原理，如果節(jié)點Vi處的停留時間為vti，則邊緣eij處的最早到達時間為te=min{t|t≥ti+vti,t∈ETij}。 對于邊緣 eij上的兩個節(jié)點Vi(ti)和Vj(tj)，時間約束表示為tj=ti+vti+Tij(te)。

2.4 數(shù)學模型

模型問題的目標是最大化總效用，建立如下的混合整數(shù)規(guī)劃：

游客的流量守恒約束為

確保每個點最多訪問一次：

在給定的旅行中，如果一個邊緣被訪問，那么沿著節(jié)點的邊到達時間就是先前到達時間，訪問時間和邊緣旅行時間的總和。

約束開始時間和結束時間：

約束變量：

其中，G=(V,E)代表時變網絡，P(i)和S(i)分別表示節(jié)點Vi的前驅節(jié)點集合和后繼節(jié)點集合，T表示旅行的總時間預算，t0表示旅行開始時間，pi，vti和ti分別表示節(jié)點Vi的旅游偏好值、停留時間和到達時間，矩陣tij(t)表示在入場時間為t時的邊緣eij上的行程時間：

3 標簽校正算法

3.1 算法思想

時變型旅游行程設計問題的目標是在考慮到游客偏好和時變網絡的情況下，在時間預算內確定旅游者的總效用最大化的最佳旅程，并通過移動設備向游客提供實時導航服務。在這個動態(tài)網絡中，行程設計和行程時間取決于源節(jié)點的開始時間［19］。因此，從最佳時間開始產生最佳旅程以幫助游客在時間預算內訪問其感興趣的旅游點。本文提出了一種標簽校正算法（LCA）［20］來解決動態(tài)旅游行程設計問題，該算法可以產生最佳旅行計劃并在給定的時間預算內實現(xiàn)最大效用。

下面定義了算法中使用的一些符號：

定義1：Q是要處理的節(jié)點優(yōu)先級隊列，并滿足先進先出（FIFO）原則。

定義2：Ci(t)是時刻t處源節(jié)點Vi的代價，代表時刻t從節(jié)點Vi到目的節(jié)點的旅行時間。

定義3：Uˉi(Vj,t)表示在時刻t到達節(jié)點Vi的總效用t(t∈ETij)，其中Vi是后繼節(jié)點(Vj∈S(i))。

鑒于開始時間是可變的，為了尋求最佳的開始時間和旅行路線，本文使用從目的地節(jié)點到源節(jié)點的標簽校正算法。由于邊緣旅行時間序列表示每個時間單位的邊緣旅行時間，因此標簽會記錄每次從當前節(jié)點到目的地節(jié)點的旅行時間和總效用。該算法計算節(jié)點的出行效用和更新預節(jié)點的標簽，重復上述迭代直到得到最優(yōu)路徑的最佳開始時間。

3.2 算法步驟

根據網絡規(guī)劃和動態(tài)規(guī)劃的思想，本文提出了一種新的標簽校正算法。

步驟1：初始化，給定每個邊緣的兩個屬性：邊緣時間序列ETij和旅行時間序列TTij。V1是源節(jié)點，Vn是目標節(jié)點。 pi表示旅游者對每個旅游點Vi的偏好值，停留時間為 vti，令 p1=pn=0，vt1=vtn=0。

步驟2：對于目標節(jié)點Vn，Cn(t)=0，=pn，t=1,…,T ，其中Vn+1是源節(jié)點Vn的虛擬后繼節(jié)點，Q={Vn}。

步驟6：旅游路線的總效用最大化，根據最大效用的標簽可以得到最佳的開始時間tbest。然后根據這個開始時間返回，將獲得從源節(jié)點V1到目的節(jié)點Vn的最優(yōu)路線，即 P(V1,Vn)={V1(tbest),V2(t2),…,Vn(tn)}。如果有多條路線的總效用最大，則選擇最小C1(t)的路線作為最終的最優(yōu)路線。

3.3 算法的時間復雜度分析

根據算法的步驟，可以看到當節(jié)點的旅行時間和標簽是標量時，最壞情況下的時間復雜度為O(|V|2|E|)。由于每個標簽是在時間序列長度為T時生成的，因此總計算時間為O(|V|2|E|T)。以上分析表明，本文的算法是一個多項式算法，可以滿足實際應用。

步驟3：處理優(yōu)先級隊列Q中的節(jié)點：

1）對于Q中的Vj，從Q中刪除Vj；

2）對 于 Vi∈P(j)，計 算 Ci(t)=Cj(t+vtj+Tij(t))+Tij(t)+vtj，?t∈ETij。 如 果 ci(t)＞T ，則Tij(t)=∞，否則如果ci(t)≤T，則轉到步驟3）；

3）計算游客的總效用和標簽，在時間t計算源節(jié)點Vi到目標節(jié)點的總效用。Uˉn(Vj,t)=Uˉj(Vk,t+vtj+Tij(t))+Pi，Vj∈S(i) ，Vk∈S(j) ，?t∈ETij，標簽為 (Vj,t,Ci(t),Uˉn(Vj,t))；

4）節(jié)點Vi加入到Q中并進行更新；

步驟4：判斷是否所有節(jié)點都已處理完成，如果Q≠φ，則轉到步驟3，否則轉到步驟5；

步驟5：計算路線的總效用，計算Uˉ(V1)=

4 數(shù)值仿真

該算法的效率和可行性將通過數(shù)值示例來仿真。假設給定一個如圖2所示的游客游覽圖，其中V1是入口（源節(jié)點），V6是出口（目的節(jié)點），其他節(jié)點是訪問點；每個節(jié)點的第一個數(shù)字表示停留時間，第二個數(shù)字表示游客的偏好值。旅行的時間預算是T=10，邊上的數(shù)字是旅行時間序列。為了簡化問題，邊上的所有時間序列被設置為ETij=[1,2,…,T]。 ?eij∈E ，如 果 t＞T ，那 么Tij(t)=Tij(T)。本文將使用所提出的標簽校正算法來解決上述例子，并且詳細計算最優(yōu)旅行。

給定在每條邊eij上的時間序列ETij和旅行時間序列TTij，V1是源節(jié)點，Vn是目的節(jié)點。對于每個節(jié)點Vi，優(yōu)先級值為 pi，停留時間為 vti，p1=pn=0，vt1=vtn=0。對于目的節(jié)點Vn，Cn(t)=0 ，Uˉn(vn+1,t)=pn，t=1,2,...,T ，假設Vn的后繼節(jié)點為Vn+1（虛擬節(jié)點），Q={Vn}。優(yōu)先級隊列Q中的每個節(jié)點按照順序處理，標簽的軌跡如表1所示。

圖2 時間相關的展覽圖

由表1可得每個節(jié)點的標簽表示為三元數(shù)組{Sub,TS,TU}，其中Sub表示子標簽節(jié)點后繼的索引，TS是標簽節(jié)點到目的節(jié)點的旅行時間序列，TU是標簽節(jié)點到目的節(jié)點的總效用，對于每個旅行時間系列，如果旅行時間在任何時間超過時間預算，則表示為“—”。

根據源節(jié)點V1的標簽，最大總效用為Uˉn(V1)=17，最佳開始時間為tbest=3。在基于節(jié)點標簽的路線獲得最佳路線如下：

從上述算法的實現(xiàn)中可以明顯看出，所提出的標簽校正算法對于確定最佳開始時間是有效的，并且為提高游客滿意度提供了最佳旅程方案。

5 結語

中國的城市旅游、商業(yè)展覽、主題公園等各種觀光展覽活動發(fā)展迅速，對促進經濟增長起到了重要作用。旅游行程設計問題不僅是旅行計劃的重要內容，也是為游客提供優(yōu)質服務的關鍵。隨著移動通信技術的發(fā)展，移動導航能夠根據地理位置為游客提供實時和個性化的服務。以往的研究忽視了展覽網絡中時變的特征。旅游交通網絡是一個復雜的系統(tǒng)，具有很大的不確定性。展覽網絡中的旅游時間可能由于諸多因素而改變。因此，本文通過引入時間聚集圖建立了基于時變網絡的旅游出行設計模型，并提出了一種標簽校正算法求解動態(tài)旅游行程設計問題，最后通過數(shù)值算例說明算法的有效性和可行性。下一步的研究將集中在多天的多次旅行設計問題上，這為旅客提供更滿意和高質量的服務，同時將考慮到更多的現(xiàn)實因素，例如景點開放時間和容量限制。

表1 標簽校正算法的標簽追蹤