一、問(wèn)題描述：是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題
一個(gè)商人從一點(diǎn)出發(fā)，經(jīng)過(guò)所有點(diǎn)后返回原點(diǎn)。
目標(biāo)：經(jīng)過(guò)所有點(diǎn)的最短路程。
約束：
1，除起點(diǎn)和終點(diǎn)外，所有點(diǎn)當(dāng)且僅當(dāng)經(jīng)過(guò)一次；
2，起點(diǎn)與終點(diǎn)重合；所有點(diǎn)構(gòu)成一個(gè)連通圖
圖論解釋：該問(wèn)題實(shí)質(zhì)是在一個(gè)帶權(quán)完全無(wú)向圖中，找一個(gè)權(quán)值最小的哈密爾頓回路
哈密爾頓回路（Hamilton回路）
定義：G=(V,E)是一個(gè)圖，遍歷圖中每個(gè)頂點(diǎn)一次且僅一次的路線稱為哈密爾頓路徑，遍歷圖中每個(gè)頂點(diǎn)一次且僅一次的回路(從哪里出發(fā)再回到哪里)稱為哈密爾頓回路。具有哈密爾頓回路的圖叫做哈密爾頓圖。
【離散數(shù)學(xué)】圖論（四）哈密頓回路（Hamiltonian cycle） - 簡(jiǎn)書(shū) (jianshu.com)
二、TSP問(wèn)題建模
(29條消息) 旅行商(TSP)問(wèn)題建模和子路徑(subtour)消除約束詳解_Dragon Fly的博客-CSDN博客_tsp約束條件
三、存在子回路（subtour）
導(dǎo)致解中含有多個(gè)相離的環(huán)，也就是subtour。需要的解是一個(gè)單個(gè)的經(jīng)過(guò)所有點(diǎn)的大環(huán)
? 子路徑消除約束常見(jiàn)兩種：
- 加入
subtour-elimination?約束 -
加入Miller-Tucker-Zemlin(MTZ)約束
1：?subtour-elimination?消除子環(huán)路
主要想法就是，根據(jù)子環(huán)路的特點(diǎn)，在模型中添加相應(yīng)的約束，將其破開(kāi)>>增加子環(huán)路不存在的條件就是(即破圈的方法)
粗獷理解：點(diǎn)的個(gè)數(shù)為N，S為點(diǎn)的集合，除了包含全部點(diǎn)的集合的情況，所有其他少了一個(gè)或幾個(gè)點(diǎn)的集合所形成的點(diǎn)點(diǎn)線條必須小于等于（集合中點(diǎn)總數(shù)-1）(即少了一個(gè)或幾個(gè)點(diǎn)后，連線邊要求比現(xiàn)存的點(diǎn)少）
subtour-elimination的約束，思路就是相當(dāng)于割平面法，是一個(gè)枚舉的約束，復(fù)雜度
采用Gurobi或者CPLEX求解器中提供的callback(回調(diào)函數(shù))的方法來(lái)動(dòng)態(tài)的添加subtour-elimination約束。
2 ： Miller-Tucker-Zemlin(MTZ)約束消除子環(huán)路
對(duì)每個(gè)結(jié)點(diǎn)，引入一個(gè)決策變量，
?
?粗獷理解：M 取無(wú)窮大數(shù)，是運(yùn)籌學(xué)中常見(jiàn)的基本操作???????，取M = N （N為節(jié)點(diǎn)的個(gè)數(shù)）
由于TSP的起點(diǎn)和終點(diǎn)是一致的，如果不做處理，會(huì)出現(xiàn)infeasible的情況
?修正：點(diǎn)集為V ′ = { 1 , 2 , ? ??, N , N + 1 } V'=\{1,2,..., N,N+1}，一共N + 1 個(gè)點(diǎn)，其中點(diǎn)1和點(diǎn)N + 1 是同一個(gè)點(diǎn)，點(diǎn)1表示起點(diǎn)，點(diǎn)N + 1 表示終點(diǎn)
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-437160.html
???????(29條消息) 運(yùn)籌學(xué)修煉日記：TSP中兩種不同消除子環(huán)路的方法及callback實(shí)現(xiàn)（Python調(diào)用Gurobi求解，附以王者榮耀視角解讀callback的工作邏輯）_劉興祿的博客-CSDN博客文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-437160.html
到了這里，關(guān)于旅行商問(wèn)題 Traveling Salesman Problem(TSP)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
