基于GA－ALNS算法的帶可容忍時間窗的VRP求解

摘要：針對帶可容忍時間窗的車輛路徑規(guī)劃問題，建立最小化配送總成本的規(guī)劃模型，結(jié)合遺傳算法構(gòu)造改進(jìn)自適應(yīng)大鄰域搜索算法對該問題求解.利用遺傳算法構(gòu)建高質(zhì)量解開始自適應(yīng)大鄰域搜索尋優(yōu)，減小算法計算時間成本;加入３種破壞算子和３種修復(fù)算子，以增加種群多樣性;嵌入模擬退火接受準(zhǔn)則以一定概率接受較差解，自適應(yīng)更新破壞和修復(fù)算子權(quán)重，避免算法陷入局部最優(yōu).選取Solomon標(biāo)準(zhǔn)測試集進(jìn)行３組實驗，與已知最優(yōu)解比較距離成本驗證算法可行性;在單邊容忍度時間窗模型下，與基礎(chǔ)ALNS算法對比驗證算法改進(jìn)效果;在雙邊可容忍時間窗模型下，與相關(guān)文獻(xiàn)的最優(yōu)結(jié)果對比.實驗結(jié)果表明，提出的GAＧALNS算法改進(jìn)效果較為顯著，求得的最優(yōu)解同其他算法相比優(yōu)化率較好，計算得到的最優(yōu)方案能實現(xiàn)更低的車輛配送總成本，具有一定的可行性和有效性.

關(guān) 鍵 詞：可容忍時間窗;車輛路徑規(guī)劃問題;自適應(yīng)大鄰域搜索算法;遺傳算法;模擬退火接受準(zhǔn)則

中圖分類號：TP１８;U１１６．２ 文獻(xiàn)標(biāo)志碼：A

doi：１０．３９６９/j．issn．１６７３ ５８６２．２０２４．０１．０１４