一種求解多旅行商問題雙層降解混合算法

摘要：為了能快速近似求解多旅行商問題，提出了雙層降解混合算法。首層降解根據(jù)問題空間展布特性，利用聚類技術(shù)將問題分解為若干子類問題，底層降解將子類問題轉(zhuǎn)換為經(jīng)典的旅行商問題，通過縮減子類問題初始狀態(tài)下的邊數(shù)量，使得子類問題求解難度得到再度降低，最終利用精確算法進(jìn)行求解能夠得到高質(zhì)量優(yōu)化解。對比實(shí)驗(yàn)表明雙層降解混合算法具有計(jì)算時(shí)間短和求解質(zhì)量高的優(yōu)勢，說明了新算法的有效性和高效性。