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

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

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

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