[發明專利]一種面向大規模車輛路徑問題的快速自適應大規模鄰域搜索方法

有效

• 申請號: 201810355489.2
• 申請日: 2018-04-19
• 公開（公告）號: CN108596469B
• 公開（公告）日: 2021-11-30
• 發明（設計）人: 陽旺
• 申請（專利權）人: 中南大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 長沙市融智專利事務所(普通合伙) 43114
• 代理人: 歐陽迪奇

本發明公開了一種面向大規模車輛路徑問題的快速自適應大規模鄰域搜索方法，通過加入了周期評分機制和策略組合權重調節機制，以N次迭代為一個周期，根據周期內各個策略組合單位執行時間內的表現優劣情況進行權重調整，通過提高表現好的策略組合的權重來增加該策略組合被選中的概率，降低表現差的策略組合的權重來減少該策略組合被選中的概率。隨著迭代的深入，單位執行時間內表現較好的策略組合有更大的概率被選中，實現快速自適應。

技術領域

本發明涉及一種面向大規模車輛路徑問題的快速自適應大規模鄰域搜索方法。

背景技術

車輛路徑問題一般定義為：若干車輛從一個或多個中心點出發，向有著不同貨物需求的若干個顧客點提供服務，在滿足顧客點需求及一定的約束條件下規劃適當的行車路線，達到運輸成本最低的目的。

車輛路徑問題主要有精確算法和啟發式算法兩大類求解方法。對于較小規模的車輛路徑問題，分支界定算法、動態規劃算法等精確算法就可以成功求解，但車輛路徑問題的求解時間隨著問題規模增大呈指數級增長，這使精確算法很難求解大規模的車輛路徑問題。于是，人們開始研究啟發式算法，其中節約法、掃描法、兩階段法等最具有代表性。近些年，啟發式算法快速發展，遺傳算法、模擬退火算法、禁忌搜索算法、大規模鄰域搜索算法等現代優化算法也被應用到車輛路徑問題的求解中。

大規模鄰域搜索算法是毀滅重建算法的擴展，其主要思路是根據毀滅重建原則，構建若干個毀滅因子(表3)和重建因子(表4)。毀滅因子和重建因子兩兩結合形成毀滅重建策略組合(表1)，在算法初始化時，為每個策略組合設定一定的權重，在每一步迭代過程中，根據某種策略選擇一種策略組合對迭代對象進行毀滅與重建，生成新解，根據接受準則來判斷是否接受該新解，并保存當前最優解，迭代循環直到滿足迭代終止條件后輸出最優解。迭代過程中，各個策略組合均有一定的概率被選中，與毀滅重建算法相比有更大的搜索空間，陷入局部最優的可能性更小，增加了得到全局最優解的可能性，所以被稱為大規模領域搜索算法。在每一次迭代過程中，各個策略組合被選中的概率與其權重息息相關，但是在大規模鄰域搜索算法中，各個策略組合的權重在算法初始化的過程中就已經確定且算法過程中不會改變。這就導致算法的靈活性較低，造成求解時間長，且求解的效果不理想的技術問題。

發明內容

本發明的目的是在大規模鄰域搜索算法(Large Neighborhood SearchAlgorithm,LNS)的基礎上提供一種快速的自適應大規模鄰域搜索算法(Fast AdaptiveLarge Neighborhood Search Algorithm,FALNS)解決企業實際物流配送過程中由于配送規模增長原有的傳統算法已經無法在短時間內提供一個高質量可行解的問題。

為了實現上述技術目的，本發明的技術方案是，

一種面向大規模車輛路徑問題的快速自適應大規模鄰域搜索方法，包括以下步驟：

步驟1：參數訓練，基于歷史數據對快速自適應大規模鄰域搜索算法中周期評分機制所涉及的評分參數進行訓練；

步驟2：初始化，設定完成一個周期所需的迭代次數，利用RegretInsert插入法生成初始解；

步驟3：從多個毀滅重建策略組合中按照輪盤法選擇一個策略組合；

步驟4：從當前的若干個最優解集合Solutions中隨機選擇一個解作為迭代對象currentSolution；

步驟5：應用步驟3中選擇的毀滅重建策略組合對步驟4中選擇的迭代對象currentSolution進行毀滅重建，生成新解newSolution，若newSolution優于當前最優解bestEver則以newSolution來更新bestEver；

步驟6：根據閾值接受準則判定是否接受新解newSolution，若接受則更新最優解集合Solutions；