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

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

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

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

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

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

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