張馳　汪海濤　姜瑛　陳星

摘要：為了有效優(yōu)化旅行商問題（TSP）的旅行路徑，通過分析傳統(tǒng)模擬退火算法的優(yōu)缺性，提出了一種改進(jìn)擾動(dòng)機(jī)制并結(jié)合分支定界的模擬退火算法。為了彌補(bǔ)模擬退火（SA）算法對(duì)初始解的依賴性，該算法首先通過分支定界產(chǎn)生一個(gè)較優(yōu)的初始解，通過對(duì)SA溫度參數(shù)和擾動(dòng)機(jī)制的的有效控制，進(jìn)行全局優(yōu)化。采用TSPLIB中的標(biāo)準(zhǔn)庫文件驗(yàn)證，測(cè)試的數(shù)據(jù)顯示改進(jìn)的SA算法和傳統(tǒng)算法相比較，在針對(duì)此類問題的求解上有著良好的性能。

關(guān)鍵詞：旅行商問題；擾動(dòng)機(jī)制；分支定界算法；模擬退火算法endprint