[發(fā)明專利]一種基于啟發(fā)式算法的景區(qū)個性化線路設計方法

在審

• 申請?zhí)枺?/td>: 201710316894.9
• 申請日: 2017-05-08
• 公開（公告）號: CN107194503A
• 公開（公告）日: 2017-09-22
• 發(fā)明（設計）人: 鄭偉民;廖治學
• 申請（專利權）人: 廈門大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/14;G06N3/12
• 代理公司: 廈門市首創(chuàng)君合專利事務所有限公司35204
• 代理人: 張松亭,楊鍇

技術領域

本發(fā)明涉及線路設計技術，更具體地說，涉及一種基于啟發(fā)式算法的景區(qū)個性化線路設計方法。

背景技術

由于具有很好的便捷性和很強的性價比，“一日游”成為很多游客游覽景區(qū)的重要方式。這種方式對一些按日付費的景區(qū)來說尤為常見。但是景區(qū)中常常包含大量的景點，游客很難在有限的時間內(nèi)游覽完所有的景點。

因此，游客需要選擇一部分他們認為最有價值的景點，然后確定游覽的順序和每個景點分配的時間。為游客設計個性化的景區(qū)“一日游”線路成為很多旅游實踐者和研究者所共同關注的問題。

關于一日游線路建議系統(tǒng)的現(xiàn)有技術，存在以下幾點不足：

(1)通常只針對景點組合和景點順序的設計，而對于景點中的逗留時間則往往是根據(jù)其他游客的經(jīng)驗；

(2)假設游客不會重復游覽相同的景點，而重復游覽著名景點在很多主題公園是非常常見的；

(3)很少考慮游客在景點逗留時間與他們所取得的效益值之間的關系，同時往往不考慮游客“審美疲勞”這種現(xiàn)象；

(4)在設計線路時往往不考慮訪問景點的時刻，而實際上，訪問景點的時刻不同，游客看到的風景可能不同，他們所收獲的價值也就往往不同。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服現(xiàn)有技術的不足，提供一種線路設計更符合實際情況、同時能夠更加個性化的基于啟發(fā)式算法的景區(qū)個性化線路設計方法。

本發(fā)明的技術方案如下：

一種基于啟發(fā)式算法的景區(qū)個性化線路設計方法，步驟如下：

1)定義雙層可變?nèi)旧w對線路進行編碼，雙層可變?nèi)旧w的結構包括位于上層、用于表示線路中的景點組合及順序的POI₁…POI_i…POI_n，位于下層、用于表示在對應景點逗留的時長的POI_i表示景點，為離散變量；表示逗留時長，為連續(xù)變量；

2)構建初始線路集；

3)線路集進化，具體為：首先采用遺傳算法對整條線路進行優(yōu)化，再運用差分進化算法對線路各個景點的逗留時長進行優(yōu)化；

4)對步驟3)優(yōu)化后的線路進行評估，具體為：分別計算每條線路的效用值；根據(jù)效用值大小從大到小排序；選擇預設種群規(guī)模Q條效用值最高的路線組成新的線路集，并進入新一次的迭代；當?shù)螖?shù)達到預設的次數(shù)時，則結束，最終產(chǎn)生的線路集中效用值最高的線路，即為推薦線路。

作為優(yōu)選，步驟2)的初始線路集中的線路通過步驟1)的雙層可變?nèi)旧w進行表達，步驟3)中，通過遺傳算法對整個雙層可變?nèi)旧w進行優(yōu)化，通過差分進化算法對雙層可變?nèi)旧w的下層進行優(yōu)化。

作為優(yōu)選，步驟2)中，通過優(yōu)化貪婪算法構建初始線路集，優(yōu)化貪婪算法的輸入包括景點集合S_POI、候選景點集合CS、線路總時間T、算法參數(shù)m，優(yōu)化貪婪算法的輸出為一條初始線路IR；

具體為：

2.1)設定初始狀態(tài)下，初始線路IR是一個空集合，不含任何景點，相應的線路總時間T等于0；

2.2)計算下一個階段游覽景點集合S_POI中各個景點的潛在效用值pu，并按潛在效用值pu從大到小對各個景點進行排序；

2.3)按潛在效用值pu從大到小選擇m個景點插入到候選集合CS中；

2.4)從候選集合CS中隨機選擇一個景點POI_i作為候選景點，在0.5×t_i和2×t_i之間隨機產(chǎn)生一個數(shù)值作為景點POI_i的逗留時長其中，t_i表示歷史游客在景點POI_i的平均逗留時長；

如果則將景點POI_i及其逗留時長插入到初始線路IR上，并更新線路總時間T，否則，從候選集合CS中選擇其他景點，重復步驟2.4)，生成一條初始線路IR；

其中，Δt_i表示從當前位置到景點POI_i的交通時間，T_max表示預算時間。

作為優(yōu)選，步驟2.2)中，潛在效用值pu的計算方法為：假定游客在下一個階段選擇景點POI_i，游客在該景點的逗留時長為歷史游客的逗留時長的平均值，則其潛在效用值pu由如下公式獲得：