[發明專利]多目標區域的最短路徑規劃方法、系統、設備及存儲介質

有效

• 申請號: 202110882110.5
• 申請日: 2021-08-02
• 公開（公告）號: CN113705858B
• 公開（公告）日: 2023-07-11
• 發明（設計）人: 洪曉鵬;關慶澍;柯煒;龔怡宏
• 申請（專利權）人: 西安交通大學
• 主分類號: G06Q10/047
• 分類號: G06Q10/047;G06N3/04;G06N3/08
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 崔方方

本發明屬于人工智能和組合優化領域，公開了一種多目標區域的最短路徑規劃方法、系統、設備及存儲介質，包括以下步驟：S1：獲取各目標區域的歸一化坐標；S2：隨機選取一目標區域的歸一化坐標，通過預設的自組織神經網絡模型，得到當前目標區域的獲勝神經元；S3：迭代重復S2；當前迭代次數加1，并當當前迭代次數大于預設閾值時，獲取各目標區域的獲勝神經元；S4：獲取各目標區域的獲勝神經元的索引，根據各目標區域的獲勝神經元的索引，得到多目標區域的最短路徑。能夠在計算資源有限的情況下，快速求解多目標區域的最短路徑規劃問題，同時保證解具有較高的質量。

技術領域

本發明屬于人工智能和組合優化領域，涉及一種多目標區域的最短路徑規劃方法、系統、設備及存儲介質。

背景技術

旅行商問題作為一經典的路徑規劃問題，是由Dantzig在1959年提出的一種經典組合優化問題，其中，單源旅行商問題可定義為：給定一組城市和它們的坐標，旅行商從其中一個城市出發，遍歷所有城市，且每個城市僅訪問一次，最后回到首次出發的城市，求使總路徑最短的遍歷城市順序，即路徑。單源旅行商問題已經應用在車輛路徑規劃、物流配送、海事救援以及電路板鉆孔等眾多領域。

現有常見的單源旅行商問題，如：清潔機器人清潔多個目標區域時，若能找到多個目標區域的最短遍歷路徑，那么將極大的降低清潔機器人清潔多個目標區域的耗時，提升清潔效率。

目前，針對單源旅行商問題通常采用路徑規劃算法進行求解，常用的路徑規劃算法有遺傳算法、模擬退火算法、粒子群算法和禁忌搜索算法等。但是，這些方法在求解單源旅行商的路徑規劃時，在目標城市節點較多的情況下，往往耗時很多才能得到較為精確的解，計算復雜度較高。

發明內容

本發明的目的在于克服上述現有技術中，多目標區域的最短路徑規劃效率低且復雜度高缺點，提供一種多目標區域的最短路徑規劃方法、系統、設備及存儲介質。

為達到上述目的，本發明采用以下技術方案予以實現：

本發明第一方面，一種多目標區域的最短路徑規劃方法，包括以下步驟：

S1：獲取各目標區域的歸一化坐標；

S2：隨機選取一目標區域的歸一化坐標，通過預設的自組織神經網絡模型，得到當前目標區域的獲勝神經元；

S3：迭代重復S2；當前迭代次數加1，并當當前迭代次數大于預設閾值時，獲取各目標區域的獲勝神經元；

S4：獲取各目標區域的獲勝神經元的索引，根據各目標區域的獲勝神經元的索引，得到多目標區域的最短路徑。

本發明多目標區域的最短路徑規劃方法進一步的改進在于：

所述獲取各目標區域的歸一化坐標的具體方法為：

獲取各目標區域的坐標x′_ij，將各目標區域的坐標組合為N*2的目標區域矩陣X，N為目標區域的數量；

根據下式對各目標區域的坐標x′_il進行歸一化：

其中，x_il為第i個目標區域的歸一化坐標，c[l]＝maxX(:,l)為目標區域矩陣X在第l維的最大值，d[l]＝minX(:,l)為目標區域矩陣X在第l維的最小值。

所述通過預設的自組織神經網絡模型，得到當前目標區域的獲勝神經元前，將自組織神經網絡模型的各輸出神經元均在(0,1)范圍內進行隨機初始化。

所述通過預設的自組織神經網絡模型，得到當前目標區域的獲勝神經元時，自組織神經網絡模型通過下式更新獲勝神經元的優勝鄰域內的各輸出神經元：