[發明專利]基于模糊蟻群算法的旅游線路優化方法

在審

• 申請號: 201911035554.4
• 申請日: 2019-10-29
• 公開（公告）號: CN110796308A
• 公開（公告）日: 2020-02-14
• 發明（設計）人: 張華;馬洪江;周相兵;辜建剛;沈少朋;陳功鎖;陳亮;溫佐承;張智恒
• 申請（專利權）人: 四川旅游學院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/14;G06N3/00
• 代理公司: 51212 成都賽恩斯知識產權代理事務所(普通合伙)
• 代理人: 張帆;肖國華

本發明提供了一種基于模糊蟻群算法的旅游線路優化方法，包括：收集到達目標景點信息、以及到達各個景點的公共交通方式的時間路程、路況、耗時相關信息；結合用戶選取目標景點和收集到的所述信息計算旅游路線，在計算計算旅游路線時，采用模糊系統自適生成蟻群算法所需要的參數、并用3?Opt解決旅游線路交叉問題。通過螞蟻個體差異以及最差個體交叉數目作為模糊系統參數，模糊系統輸出蟻群算法相關參數，這樣的一個動態反饋機制，可以有效的解決在變化數據下算法普適性，提高算法的穩定性。

技術領域

本發明屬于智能旅游技術領域，具體涉及一種基于模糊蟻群算法的旅游線路優化方法。

背景技術

旅游路線的優化問題是屬于組合優化問題，可以抽象成為簡單的旅行商問題。該問題隨著目的地數據增加求解所需的時間和空間復雜度都會呈現指數級別的增加，在已經被證明為屬于NP難問題。而現階段的路線優化算法大多數只是在理論算法層面上進行研究探討，缺乏對于路線行程種對于路況的考慮，也并沒將各個景區的差異納入考慮范圍，在實際情況中復雜的網絡，將求解的解空間大幅度擴大并且復雜度進一步提高，也無法滿足各類游客旅游行程的個性化需求。

發明內容

本發明提供了一種基于模糊蟻群算法的旅游線路優化方法，以解決至少一個上述技術問題。

為解決上述問題，作為本發明的一個方面，提供了一種基于模糊蟻群算法的旅游線路優化方法，包括：

步驟1，獲取起點景點、目標景點；

步驟2，收集到達目標景點信息、以及到達各個景點的公共交通方式的時間路程、路況、耗時相關信息；

步驟3，結合用戶選取目標景點和收集到的所述信息計算旅游路線，在計算計算旅游路線時，采用模糊系統自適生成蟻群算法所需要的參數、并用3-Opt解決旅游線路交叉問題；

步驟4，根據地圖服務產品的要求，將步驟3中的方法與地圖服務產品對接，在地圖中實現旅游線路優化規劃，并調用地圖所提供的服務進行可視化呈現。

步驟5，將旅游線路優化結果發布在游客終端中，以供游客決策最優的線路選擇。

優選地，計算旅游路線時的路線長度采用下式計算：

其中，D表示節點之間的距離d構成的矩陣，其大小是n*n；

通過各種交通方式下耗費的時間以及路況信息和目的地景區的人流量情況的乘積，將乘積的最小值對應的交通方式的路線長度作為節點之間的距離，節點之間的距離d通過下式計算：

d_i,j＝S(min(T_i,j*I_i,j*DI_i,j))

其中，S表示節點之間各種公共交通方式的實際距離，T表示節點之間各種公共交通方式所耗費的時間加上需要等待的時間，I表示節點之間的路況信息：使用擁堵程度表示，DI表示景區當前人數與景區能承受的總人數的比值。

優選地，所述蟻群算法通過引入模糊系統來設定算法參數，并且以線路的長度S與最差解線路中的交叉數目作為輸入參數來輸出算法參數，在算法運行中動態改變參數以避免算法過早收斂陷入局部最優，獲得更優的結果。

優選地，用3-Opt解決旅游線路交叉問題是指用3-opt算法對蟻群算法輸出的最優路徑進行局部優化，具體地說，通過將路線拆分為三段，通過不同的組合連接方式來尋找更優的連接方式，在更改連接方式時，除了交換的線段，其余路線并沒有進行修改。