[發明專利]一種多點位置最短路徑計算方法

在審

• 申請號: 202010812977.9
• 申請日: 2020-08-13
• 公開（公告）號: CN111985705A
• 公開（公告）日: 2020-11-24
• 發明（設計）人: 歐陽春;甘中學;甄俊杰;管宇翔;祝興
• 申請（專利權）人: 復旦大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06Q50/30;G06N3/00
• 代理公司: 上海德昭知識產權代理有限公司 31204
• 代理人: 盧泓宇

本發明提供了一種多點位置最短路徑計算方法，在該計算方法中，由于在超啟發式算法中將作為高階啟發式算法的離散ABC算法以及作為低級啟發式算法的鄰域搜索相結合，離散ABC算法中的新蜜源可以根據鄰域中的調用表調用一個低啟發式算法操作從而實現新蜜源自動更新，因此可以更快速地找到多點位置的最短路徑序列。通過本發明提供的多點位置最短路徑計算方法能夠取得更好的最短路徑序列。在實際應用中，本方法可以根據該最短路徑序列對旅行商的行程進行最合理地安排，也可以設計出最高效的物流路線，還可以為航空公司制定較好的飛機飛行路線，可以解決一系列多點位置最短路徑問題。

技術領域

本發明涉及一種多點位置最短路徑計算方法。

背景技術

多點位置最短路徑問題屬于非確定性多項式難問題(簡稱NP難 問題)，而旅行商問題(簡稱TSP問題)是NP難問題中的一個典型， 它具有精確求解困難但結果驗證容易的特點。TSP問題描述的是以下 場景：一個旅行商想走訪若干個城市，然后回到他的出發地，給定各 個城市之間所需的旅行時間后，怎樣計劃他的路線，使得他能對每個 城市恰好進行一次訪問，而總時間最短。

目前，求解TSP問題的算法有群體智能算法中的基于種群的隨 機優化技術算法(簡稱PSO)、蟻群算法(簡稱ACO)、螢火蟲算法 (FA)蝙蝠算法(BA)、人工蜂群算法(ABC)以及一些混合算法。 然而以上算法在TSP問題實例基準模型中的求解結果與正確解偏差 較大，都不能很好地求解TSP問題。

另外，Lin-Kernighan算法(簡稱LK算法)也是解決旅行商問題 的重要研究方法。LK算法在解決組合問題方面相當有效，但是LK 算法不允許進行非順序交換，這可能會導致減少針對多個TSP實例 的最佳解決方案搜索，不能求解出更好的近似解。

因此，還沒有有效算法能夠較好地求解出TSP問題的近似解， 也無法有效解決實際應用中類似于TSP問題的多點位置最優排序問 題，如物流路線規劃、航空公司飛機航線規劃、課程表中的課程排序 等等影響工作生活的多點位置最短路徑問題。

發明內容

為解決上述問題，本發明提供了一種能夠對多點位置進行規劃得 到最短路徑的計算方法，本發明采用了如下技術方案：

本發明提供了一種多點位置最短路徑計算方法，用于求解出路過 且只路過一次所有位置的最短路徑序列，其特征在于，包含如下步驟： 步驟S1，將由若干個預定位置隨機排成的隨機序列設定為蜜源；步 驟S2，根據公式(1)隨機創建Popsize/2個可行的解決方法以初始 化蜜源得到初始蜜源a_i，給每個初始蜜源a_i配一只雇傭蜂：

a_i＝[1,randperm(n_citys-1)+1,1] (1)

式中，i∈{1,2,...,Popsize/2}，Popsize/2是雇傭蜂的數量，n_citys表示城 市個數；步驟S3，雇傭蜂通過預定算法從多個低啟發式算法操作中 選擇一個低啟發式算法操作從而更新初始蜜源得到新蜜源n_i：

n_i＝llh_x(a_i) (2)

式中，llh_x是第x個低啟發式算法操作；步驟S4，雇傭蜂根據公式(3) 比較適應值fit_i并采用貪婪方法從初始蜜源a_i以及新蜜源n_i中進行選 定操作：

式中，f_i是函數值；步驟S5，雇傭蜂通過輪盤賭方法招募跟隨蜂，跟 隨蜂對雇傭蜂所對應的蜜源進行選擇，雇傭蜂所對應的蜜源被選擇的 概率P_i如公式(4)所示：