TSP，即Traveling Salesman Problem，也就是旅行商問題，又譯為旅行推銷員問題、貨郎擔(dān)問題，簡(jiǎn)稱為TSP問題，是最基本的路線問題，該問題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本。最早的旅行商問題的數(shù)學(xué)規(guī)劃是由Dantzig(1959)等人提出。

TSP問題算法小軟件數(shù)學(xué)模型簡(jiǎn)介

“旅行商問題”常被稱為“旅行推銷員問題”，是指一名推銷員要拜訪多個(gè)地點(diǎn)時(shí)，如何找到在拜訪每個(gè)地點(diǎn)一次后再回到起點(diǎn)的最短路徑。規(guī)則雖然簡(jiǎn)單，但在地點(diǎn)數(shù)目增多后求解卻極為復(fù)雜。以42個(gè)地點(diǎn)為例，如果要列舉所有路徑后再確定最佳行程，那么總路徑數(shù)量之大，幾乎難以計(jì)算出來。多年來全球數(shù)學(xué)家絞盡腦汁，試圖找到一個(gè)高效的算法，在大型計(jì)算機(jī)的幫助下才取得了一些進(jìn)展[1] 。 TSP問題 TSP問題

TSP問題在物流中的描述是對(duì)應(yīng)一個(gè)物流配送公司，欲將n個(gè)客戶的訂貨沿最短路線全部送到。如何確定最短路線。

TSP問題最簡(jiǎn)單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨于無窮大的復(fù)雜解的空間，搜索空間是n個(gè)點(diǎn)的所有排列的集合，大小為(n-1)。可以形象地把解空間看成是一個(gè)無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達(dá)到山頂或谷底的過程。

旅行商問題字面上的理解是：有一個(gè)推銷員，要到n個(gè)城市推銷商品，他要找出一個(gè)包含所有n個(gè)城市的具有最短路程的環(huán)路。 TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周游問題，即對(duì)于國際象棋棋盤中的64個(gè)方格，走訪64個(gè)方格一次且僅一次，并且最終返回到起始點(diǎn)。 TSP由美國RAND公司于1948年引入，該公司的聲譽(yù)以及線性規(guī)劃這一新方法的出現(xiàn)使得TSP成為一個(gè)知名且流行的問題。

旅行推銷員的問題，我們稱之為巡行(Tour)，此種問題屬于NP-Complete的問題，所以旅行商問題大多集中在啟發(fā)式解法。

TSP問題算法小軟件更新日志

1.質(zhì)點(diǎn)坐標(biāo)是屏幕像素坐標(biāo)，left,top,縱坐標(biāo)向下不是向上，與數(shù)學(xué)上的縱坐標(biāo)方向相反。

2.坐標(biāo)為屏幕像素坐標(biāo)，所以只能整數(shù)。

3.點(diǎn)坐標(biāo)可以用鼠標(biāo)拖動(dòng)，拖動(dòng)時(shí)可以超出屏幕范圍自動(dòng)產(chǎn)生滾動(dòng)條，但點(diǎn)坐標(biāo)不可以為負(fù)數(shù)。

本次升級(jí)5.0主要修改如下：

1。增加了concorde算法。附帶有原作者的開源ansi-C源代碼和文件。

2。將原來隱藏的窮舉法分支限界法中的初始值可以手工輸入框顯示出來。

本次升級(jí)4.0主要修改如下：

1。增加了LKH算法。

2。附帶有LHK原作者的開源C++源代碼和4個(gè)PDF文件。

本次升級(jí)3.7主要修改如下：

1。增加了模擬退火算法。

2。分支限界改名為窮舉算法。

本次升級(jí)3.6主要修改如下：

1。更正了計(jì)算路長(zhǎng)時(shí)有別名的BUG。

2。更正了分支限界算法的一個(gè)BUG。

本次升級(jí)3.5主要修改如下：

1。優(yōu)化了動(dòng)態(tài)規(guī)劃算法和分支限界算法。

2。質(zhì)點(diǎn)可以右鍵中設(shè)置別名。

本次升級(jí)3.0主要修改如下：

1。當(dāng)鼠標(biāo)移到邊線條時(shí)，高亮顯示邊與邊長(zhǎng)數(shù)字。

2。點(diǎn)坐標(biāo)可以用鼠標(biāo)拖動(dòng)，拖動(dòng)時(shí)可以超出屏幕范圍自動(dòng)產(chǎn)生滾動(dòng)條，但點(diǎn)坐標(biāo)不可以為負(fù)數(shù)。

3。增加了分支限界算法。

4。修正了點(diǎn)坐標(biāo)的BUG，點(diǎn)坐標(biāo)與屏幕坐標(biāo)完全相同。