旅行商問題-畢業(yè)設(shè)計外文翻譯

1、1旅行商問題旅行商問題1引言引言在運籌學(xué)和理論計算機科學(xué)中，旅行商問題（TSP）是一個NP困難的組合優(yōu)化問題。通過給出成對的城市間距離，找到每個城市恰好訪問一次最短的周游。它是購買者旅行問題的一個特殊情況。問題最早是在1930年作為數(shù)學(xué)問題和優(yōu)化中最深入研究的問題之一被系統(tǒng)地闡述。它成為許多優(yōu)化方法的一個基準(zhǔn)。雖然問題難以計算，但已知大量的啟發(fā)式檢測和確切方法，可以解決含有數(shù)以萬計城市的某些情況。TSP有許多應(yīng)用，甚至基于它最本質(zhì)的概念

2、本身，如規(guī)劃，物流，制造微芯片。略作改動，在許多領(lǐng)域中，它作為子問題出現(xiàn)，如DNA測序。在這些應(yīng)用中，TSP中的城市代表的是客戶，焊接點，或DNA片段，TSP中的距離代表的是，行駛時間或成本，或DNA片段之間的相似性度量。在許多應(yīng)用中，額外的限制，如有限的資源或時間窗口使問題變得相當(dāng)困難。在計算復(fù)雜性理論中，TSP的決定版本（給定一個長度L，目標(biāo)是判斷是否有比L短的任何周游）屬于np完全問題的一類。因此，很可能在最壞的情況下，解決TSP

3、的任何算法所需的運行時間隨城市數(shù)量的增加而成倍增加。2歷史歷史旅行商問題的起源目前還不清楚。一本1832年的手冊提到了旅行推銷員的問題，其中有德國和瑞士周游的例子，但書中未含數(shù)學(xué)處理。旅行商問題在19世紀(jì)被愛爾蘭數(shù)學(xué)家W.R.和英國數(shù)學(xué)家ThomasKirkman所闡述。Hamilton的Icosian游戲就是一個基于找到哈密頓圈的休閑游戲。一般形式的TSP，最早在1930年的維也納和哈佛大學(xué)被數(shù)學(xué)家特別是KarlMenger所研究，K

4、arlMenger定義了問題，考慮了顯然的蠻力算法，并考察了非最近鄰的啟發(fā)式：3邊，路徑距離是邊長。這是一個最小化問題，開始和結(jié)束在一個指定的頂點，其它頂點恰好訪問一次。一個哈密頓圈是TSP的一個最佳周游則每邊的距離成正比。通常情況下，該模型是一個完全圖（即每對頂點是由邊相連）。如果兩個城市之間沒有路徑存在，增加一個任意長度不影響最佳周游的邊，成為完全圖。3.23.2非對稱和對稱非對稱和對稱在對稱的TSP中，兩個城市之間在每一個相反的方

5、向的距離是一樣的，形成一個無向圖。這種對稱將可能的求解分半。在不對稱的TSP中，可能不存在雙向路徑或雙向路徑不同，形成一個有向圖。交通事故，單行道，不同時間和價格的機票正是破壞這種對稱性的例子。3.33.3相關(guān)問題相關(guān)問題在圖論中的一個等價命題是：給定一個完全帶權(quán)圖（其中頂點表示城市，邊表示的路徑，權(quán)值表示成本或距離），找到權(quán)值最小的哈密頓環(huán)。返回出發(fā)城市的要求，并不改變問題的計算復(fù)雜性，看哈密爾頓路徑問題。另一個相關(guān)的問題是瓶頸旅行商

6、問題（瓶頸TSP）：在帶權(quán)圖中找到關(guān)鍵邊權(quán)值最小的一個漢密爾頓環(huán)。問題具有相當(dāng)?shù)膶嶋H意義，除了在明顯的運輸和物流領(lǐng)域，一個典型的例子是制造印刷電路調(diào)度的路線鉆機在PCB上鉆孔。在機械加工或鉆孔應(yīng)用中，“城市”是零件或鉆的孔（尺寸不同），“遍歷的開銷”包含為更換零件（單機作業(yè)排序問題）的時間。廣義旅行商問題涉及“州”，（一個或多個）“城市”，推銷員從各個“州”拜訪每個“城市”一次，也被稱為“旅行政治家問題”。令人驚訝的是，Behzad和M