TSP問題的算法與應(yīng)用的研究.pdf

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

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

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