TSP問題的算法與應用的研究.pdf

1、TSP問題是一個典型的組合優(yōu)化問題。近些年來，研究人員試圖運用各種方法對該問題進行求解。由于該問題的可行解隨著頂點數(shù)的增加會成指數(shù)型增長，容易產(chǎn)生組合爆炸，所以試圖使用精確算法求解TSP問題的研究基本銷聲匿跡，取而代之的是各種近似方法。 本文是結(jié)合上海市公安部第三研究所863子項目所進行的研究。論文首先介紹了TSP問題及其涉及的數(shù)學模型。在求解該問題的眾多算法中，著重對遺傳算法和蟻群算法進行了分析和研究：采用最優(yōu)個體保留策略的選

2、擇算子，雙點交叉的交叉算子并加入移民思想實現(xiàn)了遺傳算法；采用經(jīng)大量實驗得出的最優(yōu)化參數(shù)、下一個城市的輪賭法選擇策略和ant-cycle模型信息素更新策略實現(xiàn)了蟻群算法。通過算法的比較和TSPLIB的驗證，給出了在算法執(zhí)行次數(shù)和運算結(jié)果最優(yōu)化之間有良好平衡的蟻群算法的實現(xiàn)方法。 其次，對TSP算法應用的實現(xiàn)方式也作了詳細研究。本文提出了網(wǎng)絡瀏覽器運行的實現(xiàn)方法，給出了系統(tǒng)實現(xiàn)的B/S三層架構(gòu)，并就以數(shù)據(jù)執(zhí)行和結(jié)果存取為核心功能的實

3、現(xiàn)技術(shù)作了深入討論，該方法在用戶使用的方便性、應用的廣泛性和系統(tǒng)的可維護性上得到了較大的提高。 最后，針對ERP系統(tǒng)中的物流配送路徑的優(yōu)化問題，運用本文研究的算法和實現(xiàn)的技術(shù)，作為應用實例實現(xiàn)了ERP物流配送路徑?jīng)Q策支持系統(tǒng)的原型，以良好的系統(tǒng)性能和滿意的運行結(jié)果進一步證明了本文針對TSP問題的算法與應用研究的正確性、創(chuàng)新性和實用性。 此研究結(jié)果將對TSP問題在其它應用領域的算法與應用的研究起到拋磚引玉的作用，并具有重要