多約束條件車輛路徑問題的二階段遺傳退火算法

呂　軍　馮博琴　李　波

摘要：針對多約束條件的多配送中心有時間窗車輛路徑問題，提出了一種二階段遺傳退火算法．在第1階段，使用遺傳算法對客戶按供應量和路徑長度進行模糊分區；在第2階段，采用二維變長染色體編碼及相應的遺傳算子進行混合遺傳算法的全局優化．在初始種群生成和交叉、變異算子中采用了隨機貪心算法以避免無效解，并利用退火選擇來提高種群的多樣性。實驗結果表明，二階段遺傳退火算法可加速收斂，提高搜索效率，在模糊分區上的搜索速度較之標準遺傳算法提高了3～10倍。

關鍵詞：車輛路徑；遺傳退火算法；貪心算法

中圖分類號：TPl8；U116文獻標識碼：A文章編號：0253—987X(2005)12—1299—04