[發明專利]一種基于改進蟻群算法的城市旅游路線規劃方法在審

申請號：	201611149671.X	申請日：	2016-12-13
公開（公告）號：	CN106779212A	公開（公告）日：	2017-05-31
發明（設計）人：	張登銀;牛悅誠	申請（專利權）人：	南京郵電大學
主分類號：	G06Q10/04	分類號：	G06Q10/04;G06Q50/12;G06N3/00
代理公司：	南京知識律師事務所32207	代理人：	李湘群
地址：	210003 江蘇***	國省代碼：	江蘇;32
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	一種基于改進算法城市旅游路線規劃方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

技術領域

本發明涉及一種基于改進蟻群算法的城市旅游路線規劃方法，屬于人工智能領域。

背景技術

2008年國際商用機器公司(IBM)推出“智慧地球”商業計劃，其核心是以一種更智慧的方法通過利用新一代信息技術來改變政府、公司和人們相互交互的方式，以便提高交互的明確性、效率、靈活性和相應速度。智慧城市是“智慧地球”在城市建設和管理中的具體實踐。IBM認為21世紀的“智慧城市”能夠充分運用信息和通訊技術手段感測、分析、整合城市運行核心系統的各項關鍵信息，從而對于包括民生、環保、公共安全、城市服務、工商業活動在內的各種需求做出智能的響應，為人類創造更美好的生活。

智能路徑規劃是在智慧城市的基礎上發展而來，是一種以物聯網、云計算、下一代通信網絡、高性能信息處理、智能數據挖掘等技術在地圖類APP的應用。它以融合的通信與信息技術為基礎，以互動體驗為中心，簡單地說，就是使用者與網絡實時互動。

傳統的地圖類APP可以進行兩點之間的路徑規劃，或是連續多個地點的路徑規劃。但現有的地圖類APP并不能解決如下的問題，如一次旅行中，需要參觀多個景點，如何使得旅行過程花費在路上的時間盡可能短，用于參觀景點的時間盡可能長，就需要進行智能的旅游路徑規劃，這種場景是從酒店出發，參觀景點，最后回到酒店。這種情況與旅行商問題(Travelling Salesman Problem,TSP)的設定是一致的。

旅行商問題是路徑優化中最為典型的一類問題，是一種經典的NP難題(Non-deterministic Polynomial，多項式復雜程度的非確定性問題)。旅行商問題的經典描述為：已知N個城市及其相互間的距離，旅行商從某城市出發遍歷這N個城市后再回到原點，在每個城市都只訪問一次的前提下，確定一條最短路徑。

目前針對旅行商問題的算法主要有蟻群算法等。蟻群算法是一種仿生物智能算法，其模型是螞蟻群體尋找食物的過程。蟻群算法分布式的特征使得算法可靠，全局搜索能力比較強，同時也可以有效地和其他算法進行結合。但是也存在不足：搜索時間長，過快地收斂于局部最優解。

發明內容

本發明要解決的技術問題是針對蟻群算法存在的搜索時間長，過快地收斂于局部最優解的問題。

鑒于此，本發明提出一種基于改進蟻群算法的城市旅游路線規劃方法，針對需要多天旅游的人，通過本方法可以為其提供一種合理的城市旅游路線。本發明的技術方案具體為一種基于改進蟻群算法的城市旅游路線規劃方法，包括以下步驟：

步驟1：應用場景的設置：選定住宿地點及旅游景點，設定場景參數；

步驟2：設定信息素的初始分布矩陣及蟻群算法的初始化參數；

步驟3：設定改進的路徑選擇概率更新規則，螞蟻按照改進的路徑選擇概率進行路徑選擇，并修改禁忌表；

步驟4：設定改進的信息素更新規則，對路徑信息素進行全局更新；

步驟5：判斷迭代次數是否滿足要求，若滿足要求，則輸出結果，否則轉至步驟3。

作為優選，上述步驟1所定義的應用場景為多次需要返回起點的路徑規劃。

上述步驟3中所述改進的路徑選擇概率更新規則是通過隨機因子和隨機因子額定閾值對基本蟻群算法的路徑選擇概率更新規則進行了改進。

上述步驟4所述信息素更新規則的改進是通過設置合理的揮發系數對基本蟻群算法的信息素更新規則進行了改進。