[發明專利]一種汽車配送路徑規劃的優化方法

有效

• 申請號: 202110405386.4
• 申請日: 2021-04-15
• 公開（公告）號: CN112884254B
• 公開（公告）日: 2022-09-30
• 發明（設計）人: 余永東;余睿然;郭碧寶;劉春芝
• 申請（專利權）人: 廣州市交通技師學院(廣州市交通高級技工學校)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06F30/27;G06N3/12;G06F111/06
• 代理公司: 北京天奇智新知識產權代理有限公司 11340
• 代理人: 陳新勝

本發明公開了一種汽車配送路徑規劃的優化方法，包括設置算法的超參數；獲取并規范化TSPLIB數據集，并規定為*.csv格式的文檔，且文檔第一列為城市的橫坐標，第二列為城市的縱坐標；將城市序列存儲為數組，數組中行數代表染色體；根據指數尺度變換適應度函數，計算出當前種群的每一條染色體的個體適應度；根據適應度，選出此世代得以被保留的父代城市序列染色體；對選出的城市序列染色體，進行部分匹配交叉PMX即城市序列之間交換部分基因；對城市序列染色體進行染色體片段逆轉變異操作，增強種群的基因多樣性；重復上述步驟，直至滿足：當前進化世代數≥終止世代數Ge，則跳出循環，根據當前基因型數組，輸出城市規劃路徑及對應的最短路徑計算結果。

技術領域

本發明涉及汽車配送路徑技術領域，尤其涉及一種汽車配送路徑規劃的優化方法。

背景技術

現有無約束的汽車配送路徑規劃問題，類似是一種“旅行銷售商”問題，是經典的NP-Hard組合優化問題，它的描述如下:設一位商人需要到N個城市推銷商品，依次不重復地訪問每個城市，最終回到起始城市，求解其訪問路線的最短回路。生活中的車輛交通路徑規劃問題、電路板布線問題、最短物流配送問題、車間調度問題等，都可抽象為TSP從而進行求解。比如電力系統巡檢機器人的路徑規劃問題即可以建模成TSP問題，滴滴、順豐、美團等公司經常面臨的車輛調度問題也可以看成是在TSP的基礎上疊加多種業務要求(多車輛、取送貨等)及約束(容量約束、時間約束、續航里程約束等)。因此研究TSP具有較高的實際價值和理論意義。

該類問題的求解主要有完全算法、近似算法以及啟發式算法三大方向。

完全算法如動態規劃法、分支定界法等可以保證搜索到最優解。但由于其時間復雜度過高，且TSP問題的NP-hard屬性，問題的解空間規模往往呈現指數級增長，因此完全算法在大規模問題上往往難以滿足性能要求。

近似算法不保證找到問題的最優解，但是可以在多項式計算復雜度內嚴格保證所找到解的路徑長度與最優解的路徑長度之間的比值不超過一定上限，該上限被稱為近似度。近似度越接近1，算法性能越好。

啟發式算法能在可接受的時間、空間之內找到近似解。但對于較為復雜的非線性問題，傳統的啟發式算法，如：遺傳算法、粒子群優化算法、模擬退火法、蟻群算法等，較為容易陷入局部最優。因此，如何有效優化啟發式算法，改善其全局搜索能力，成為廣大學者關注和研究的熱點。

發明內容

為解決上述技術問題，本發明的目的是提供一種汽車配送路徑規劃的優化方法，該方法基于杰出精英保留機制(Elitist Reservation)，在原有的遺傳算法基礎上，結合錦標賽選擇、部分匹配交叉以及染色體逆轉變異，其分別作為選擇算子、交叉算子和變異算子。通過錦標賽選擇，保留種群中的優勢子代解；利用部分匹配交叉算子保留染色體中的優勢基因；使用染色體逆轉變異的方法，增強城市序列種群的基因多樣性。算法在國際通用的TSPLIB庫提供的數據集上進行方針測試，根據仿真得出的結果，在時間花銷上遠勝于傳統的完全算法，在MER、BER等指標上，效果亦優于一般的遺傳算法、差分進化算法、粒子群優化算法等。與以上算法相比，本算法具有更強的魯棒性，其種群基因的多樣性也得到了增強。

本發明的目的通過以下的技術方案來實現：

一種汽車配送路徑規劃的優化方法，包括

A設置算法的超參數；

B獲取并規范化TSPLIB數據集，并規定為*.csv格式的文檔，且文檔第一列為城市的橫坐標，第二列為城市的縱坐標；

C將城市序列存儲為數組，數組中行數代表染色體；

D根據指數尺度變換適應度函數，計算出當前種群的每一條染色體的個體適應度；

E根據適應度，選出此世代得以被保留的父代城市序列染色體；