基于遺傳算法的旅游最優路徑探究

李振業 陳婷 陳靜

摘要：旅游越來越成為人們喜愛的一種娛樂方式，但隨著大量游客的涌入，各個旅游園區迫切需要設計合理高效的旅游路線提高游客的旅游質量。以徐州潘安湖風景區為例，采用遺傳算法生成最優旅游路徑，高效簡單，能快速為消費者找到限制條件下的最優路徑方案。

關鍵詞：最優路徑;遺傳算法;旅游路線;數學建模

中圖分類號：TP302? ? ? ? 文獻標識碼：A? ? ? ? 文章編號：1009-3044（2018）34-0181-03

1 問題描述

1.1 問題背景

隨著徐州當地經濟的發展，徐州潘安湖濕地公園游客不斷增加，設計合理高效的旅游線路直接影響到園區的游客承受能力、廣大游客的游覽體驗以及園區的經濟效益等。

1.2 問題描述及假設

選取潘安湖景區的部分景點（如圖1所示，每兩景點之間往返距離已知）給出如下假設：

（1）各景點設置編號表示：S0：景石，S1：游客服務中心，S2：陽光草坪，S3：森林小劇場，S4：兒童科普體驗區，S5：兒童戲水場，S6：濕地博物館，S7：濕地商業街。

（2）任兩個景點間存在最短步行距離分別為d（n1，n2）表示景點n1到景點n2的最短路徑。

（3）假設游客的步行速度平均在2km/h左右。

（4）游客在景區停留的時間由“景點之間的步行時間”“景點游覽時間（即在景點內游玩的時間）” 和“在景區外的等待時間”三部分組成，其他時間忽略不計。

有3個旅游團，12：00同時從景石出發，要求三個旅游團17：00前到達濕地商業街，17：30離開濕地商業街（注：?各景點限時開放?森林小劇場只在半點或整點開放;?濕地商業街游覽時間至少為30分鐘），并且每個景點（濕地商業街除外）同時只能容納1個旅游團游覽，按照時間順序后到達的旅游團，需要等待先到達的旅游團游覽結束之后才能開始游覽。建立數學模型，為三個旅游團分別設計一條能游覽完全部7個景點且游覽總時間最長的游覽路線。

3 結論

3.1 模型的優點

（1）計算簡單，結果準確，符合實際，具有可行性;

（2）遺傳算法具有系統優化、適應和學習的高性能計算，不需要求導或其他輔助知識，只需要適應度函數值。基于自適應搜索技術增加搜索過程的靈活性，具有較好的全局優化求解能力。直接以目標函數值為搜索信息，對函數的形態無要求，具有較好的普適性和易擴充性，更適合大規模復雜問題的優化。

3.2 模型的缺點

（1）約束條件少，具有理想化;

（2）節點變多會使計算量劇增;

（3）輪盤賭法策略可能會產生較大的抽樣誤差，如果產生異常個體引起早熟收斂，影響求得全局最優解，

（4）進化過程中產生大量數據，計算大、占用時間長。

3.3 模型的改進

（1）改變遺傳算法的控制參數，控制參數一般有群體大小、交叉概率、變異概率等，它們對算法性能有很大影響。

（2）輪盤賭法可能產生較大的抽樣誤差，可選用改進方法，如非線性排名選擇，基于局部競爭機制的選擇等。

參考文獻：

[1] 王法有，劉玉娟.通過數學建模設計四川11名景最佳旅游路線[J].數學學習與研究，2010（17）.

[2] 于瑩瑩，陳燕，李桃迎.改進的遺傳算法求解旅行商問題[J].控制與決策，2014，29（8）.

[3] 李波，秦華旺.路徑優化案例遺傳算法的實現[J].電子設計工程，2017，25（20）.

[4] 鄧雪，李家銘.層次分析法在權重計算方法分析極其應用研究[J].數學的實踐與認識，2012，42（7）.

[5] 常洪江.遺傳算法綜述[J].電腦學習，2016（3）.

【通聯編輯：代影】