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

在審

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

1.一種基于啟發式算法的景區個性化線路設計方法，其特征在于，步驟如下：

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

2)構建初始線路集；

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

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

2.根據權利要求1所述的基于啟發式算法的景區個性化線路設計方法，其特征在于，步驟2)的初始線路集中的線路通過步驟1)的雙層可變染色體進行表達，步驟3)中，通過遺傳算法對整個雙層可變染色體進行優化，通過差分進化算法對雙層可變染色體的下層進行優化。

3.根據權利要求1所述的基于啟發式算法的景區個性化線路設計方法，其特征在于，步驟2)中，通過優化貪婪算法構建初始線路集，優化貪婪算法的輸入包括景點集合S_POI、候選景點集合CS、線路總時間T、算法參數m，優化貪婪算法的輸出為一條初始線路IR；

具體為：

2.1)設定初始狀態下，初始線路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之間隨機產生一個數值作為景點POI_i的逗留時長其中，t_i表示歷史游客在景點POI_i的平均逗留時長；

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

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