改進的Ejection Chain局部搜索算法與混合算法求解旅行商問題.pdf

1、作為組合優(yōu)化中經(jīng)典的NP-hard問題之一，旅行商問題(TSP)在實際生產中有廣泛的應用，如物流路線規(guī)劃、電路板印刷等。對該問題的研究不管是在實際應用中還是在科學研究中都有十分重大的意義。
　　1992年Ejection Chain算法被提出，隨后被證明在求解旅行商問題中和有名的Lin-Kernighan(LK)啟發(fā)式算法一樣高效。在本文中，我們著重研究了EjectionChain算法及其混合算法。我們對Ejection Chai

2、n算法進行了改進，并進行了大規(guī)模的算法性能實驗測試。與其他研究僅僅關注算法實驗最終結果不同，本文中使用多種時間維度來分析算法在整個運行過程中的狀態(tài)。
　　本文中的工作為以下四個方面:第一，我們研究了高效的Ejection Chain算法，并且在原始的Ejection Chain算法上進行了多項改進，比如針對Ejection Chain算法的特點設計了高效的數(shù)據(jù)存儲結構，對根節(jié)點候選集合的大小進行探索實驗，同時對Ejection C

3、hain算法的終止條件策略進行了調整，得到改進的EjectionChain算法在測試的110個實例求解全局最優(yōu)解中，比原始Ejection Chain算法多解決了28％的測試實例。
　　第二，我們對Ejection Chain算法進行了大規(guī)模的實驗測試，通過與LK局部搜索算法相比較，深入分析了Ejection Chian算法性能。
　　第三，由于局部搜索算法以及組合局部搜索算法（LS-LS混合算法）容易陷入局部最優(yōu)，所以我們