友情提示：本文將給出求解多旅行商問題的模擬退火算法的思路，因此想完全弄懂本文的思想，請(qǐng)先提前觀看我在b站發(fā)布的模擬退火視頻，在這個(gè)視頻中有單個(gè)旅行商問題的講解：

數(shù)學(xué)建模清風(fēng)第二次直播：模擬退火算法

我們先來簡單回顧下上面這個(gè)視頻中的內(nèi)容：

（1）旅行商問題(TravelingSalesmanProblem，TSP)是一個(gè)經(jīng)典的組合優(yōu)化問題。經(jīng)典的TSP可以描述為：一個(gè)商品推銷員要去若干個(gè)城市推銷商品，該推銷員從一個(gè)城市出發(fā)，需要經(jīng)過所有城市后，回到出發(fā)地。應(yīng)如何選擇行進(jìn)路線，以使總的行程最短。

（2）由于TSP問題的解是一個(gè)閉環(huán)，因此在模擬退火中構(gòu)造初始解和新解時(shí)，我們不需要指定起點(diǎn)位置。

（3）產(chǎn)生新解我們給了三種方法，分別是交換法，移位法和倒置法。

下面這個(gè)圖就是模擬退火求解單旅行商問題中的四個(gè)時(shí)刻的狀態(tài)圖，左上是初始解時(shí)候?qū)?yīng)的圖像，可以看出初始解非常的亂；經(jīng)過100次迭代后，我們得到了右上的圖像，可以看出，此時(shí)旅行商的路徑已經(jīng)整齊了很多；到迭代300次時(shí)，我們得到的解已經(jīng)非常好了。

另外，我們也可以畫圖每次迭代后找到的最優(yōu)解的圖形，如下圖所示，隨著迭代次數(shù)的增加，我們找到的最優(yōu)解對(duì)應(yīng)的行程越來越短：

下面我們就來正式介紹多旅行商問題。

首先先給大家指出一個(gè)概念，在運(yùn)籌學(xué)中有一個(gè)很著名的問題：車輛路徑問題（Vehicle Routing Problem,VRP），這個(gè)問題有很多種不同的變形，也是運(yùn)籌學(xué)界目前研究的熱點(diǎn)問題之一，今天我們學(xué)習(xí)的多旅行商問題，大家可以視為VRP問題較為簡單的一個(gè)例子，未來有機(jī)會(huì)我再給大家講解幾類常見的VRP的求解。下圖為MBA智庫百科對(duì)于車輛路徑規(guī)劃的介紹，大家課后可以自己搜索：

下面我先給出一個(gè)多旅行商問題的定義，可能和你在其他地方見到的有所不同，不過都大同小異：

經(jīng)典的TSP可以描述為：一個(gè)商品推銷員要去若干個(gè)城市推銷商品，該推銷員從一個(gè)城市出發(fā)，需要經(jīng)過所有城市后，回到出發(fā)地。

多旅行商問題MTSP可以描述為：多個(gè)商品推銷員要去若干個(gè)城市推銷商品，這些推銷員最開始都在同一個(gè)城市，他們可以被分配到不同路徑，在經(jīng)過所有的城市后，大家都回到出發(fā)的城市。

為了讓大家直觀的感受下MTSP和TSP的差異，這里有幾張圖片，分別是存在1,2,3,4,5個(gè)推銷商時(shí)候的情況（圖中紅色的*表示開始的城市）。

這里一共有101個(gè)城市，第一個(gè)圖就是我們之前學(xué)的TSP，可以看出，TSP的解形成的路徑構(gòu)成了一個(gè)閉環(huán)，因此在TSP問題中初始所在的城市我們不用單獨(dú)去考慮，TSP中的初始解我們可以用1至n的一個(gè)隨機(jī)排序。

例如我們將這101個(gè)城市依次編號(hào)為1,2,3,…,101，假設(shè)初始的城市編號(hào)為35，我們得到的最短路徑的編號(hào)為 3-59-78-…-12-35-91-…-3，這時(shí)候我們重新組合下這個(gè)編號(hào)，將其以35開頭和35結(jié)尾，即：35-91-…-3-59-78-…-12-35，這時(shí)候這個(gè)解就是我們想要的解。（這里看的不懂的請(qǐng)看本文最開始的那個(gè)視頻，否則你下面的應(yīng)該也看不懂啦）

在下面的四張圖就是我們要介紹的MTSP，大家應(yīng)該能看出，我們的旅行商都選擇了不同的城市，且分別以起始城市圍成了一個(gè)圈。

接下來就要告訴大家，MTSP中解長什么樣子？????? ?

如果你看了模擬退火的視頻，你就應(yīng)該知道：模擬退火里面最重要的一個(gè)步驟就是如何定義解以及怎么去產(chǎn)生新解。首先要注意的一點(diǎn)就是：在MTSP問題中起始的城市就比較關(guān)鍵了，我們常常將起始的城市用編號(hào)0表示，剩余的城市依次用1,2,3，...,100表示，這樣我們就能表示出每個(gè)旅行商的旅行順序了。

為了方便描述，下面我們就以4個(gè)城市為例，假設(shè)這4個(gè)城市編號(hào)分別為0123，且0號(hào)為MTSP中起始的城市，再假設(shè)現(xiàn)在我們一共有兩個(gè)旅行商，那么，我們這兩個(gè)旅行商旅行方案的所有可能組合為：

?? ? 3? ? ?2? ? ?1? ? ?0

? ? ?3? ? ?2? ? ?0? ? ?1

? ? ?3? ? ?1? ? ?2? ? ?0

? ? ?3? ? ?1? ? ?0? ? ?2

? ? ?3? ? ?0? ? ?2? ? ?1

? ? ?3? ? ?0? ? ?1? ? ?2

? ? ?2? ? ?3? ? ?1? ? ?0

? ? ?2? ? ?3? ? ?0? ? ?1

? ? ?2? ? ?1? ? ?3? ? ?0

? ? ?2? ? ?1? ? ?0? ? ?3

? ? ?2? ? ?0? ? ?3? ? ?1

? ? ?2? ? ?0? ? ?1? ? ?3

? ? ?1? ? ?3? ? ?2? ? ?0

? ? ?1? ? ?3? ? ?0? ? ?2

? ? ?1? ? ?2? ? ?3? ? ?0

? ? ?1? ? ?2? ? ?0? ? ?3

? ? ?1? ? ?0? ? ?3? ? ?2

? ? ?1? ? ?0? ? ?2? ? ?3

? ? ?0? ? ?3? ? ?2? ? ?1

? ? ?0? ? ?3? ? ?1? ? ?2

? ? ?0? ? ?2? ? ?3? ? ?1

? ? ?0? ? ?2? ? ?1? ? ?3

? ? ?0? ? ?1? ? ?3? ? ?2

? ? ?0? ? ?1? ? ?2? ? ?3

這里每一行代表一種方案，我下面就挑幾個(gè)方案給大家解釋：

3 ?? ?2 ?? ?1 ?? ?0：

第1個(gè)旅行商的方案：0-3-2-1-0；第2個(gè)旅行商不出門

3 ?? ?2 ?? ?0? ? ?1：

第1個(gè)旅行商的方案：0-3-2-0；第2個(gè)旅行商的方案：0-1-0

1 ?? ?2 ?? ?0? ? ?3：

第1個(gè)旅行商的方案：0-1-2-0；第2個(gè)旅行商的方案：0-3-0

1 ?? ?0? ? ?2 ?? ?3：

第1個(gè)旅行商的方案：0-1-0；第2個(gè)旅行商的方案：0-2-3-0

0? ? ?3 ?? ?1 ?? ?2：

第1個(gè)旅行商不出門；第2個(gè)旅行商的方案：0-3-1-2-0

不知道大家有沒有看出來眉目，我們這里構(gòu)造的解是0123的一個(gè)隨機(jī)排列，并且，我們可以0作為分割點(diǎn)，將這個(gè)解進(jìn)行劃分，前面構(gòu)成一個(gè)環(huán)用來描述第1個(gè)旅行商的方案，后面也構(gòu)成一個(gè)環(huán)用來描述第2個(gè)旅行商的方案。（如果0的前或后沒有數(shù)字則代表對(duì)應(yīng)的旅行商不出門）

接下來，我們假設(shè)一共有三個(gè)旅行商，那么對(duì)應(yīng)的解應(yīng)該是怎樣的呢？

先不要看下面的答案

下面揭秘答案: 此時(shí)的解應(yīng)該是00123的一個(gè)隨機(jī)排列，如果不考慮重復(fù)的可能，那么所有的情況一共有5!=120種：
??

? ? ?0? ? ?0? ? ?3? ? ?2? ? ?1

? ? ?0? ? ?0? ? ?3? ? ?1? ? ?2

? ? ?0? ? ?0? ? ?2? ? ?3? ? ?1

? ? ?0? ? ?0? ? ?2? ? ?1? ? ?3

? ? ?0? ? ?0? ? ?1? ? ?3? ? ?2

? ? ?0? ? ?0? ? ?1? ? ?2? ? ?3

? ? ?0? ? ?3? ? ?0? ? ?2? ? ?1

? ? ?0? ? ?3? ? ?0? ? ?1? ? ?2

? ? ?0? ? ?3? ? ?2? ? ?0? ? ?1

? ? ?0? ? ?3? ? ?2? ? ?1? ? ?0

? ? ?0? ? ?3? ? ?1? ? ?0? ? ?2

? ? ?0? ? ?3? ? ?1? ? ?2? ? ?0

? ? ?0? ? ?2? ? ?0? ? ?3? ? ?1

? ? ?0? ? ?2? ? ?0? ? ?1? ? ?3

? ? ?0? ? ?2? ? ?3? ? ?0? ? ?1

? ? ?0? ? ?2? ? ?3? ? ?1? ? ?0

? ? ?0? ? ?2? ? ?1? ? ?0? ? ?3

? ? ?0? ? ?2? ? ?1? ? ?3? ? ?0

? ? ?0? ? ?1? ? ?0? ? ?3? ? ?2

? ? ?0? ? ?1? ? ?0? ? ?2? ? ?3

? ? ?0? ? ?1? ? ?3? ? ?0? ? ?2

? ? ?0? ? ?1? ? ?3? ? ?2? ? ?0

? ? ?0? ? ?1? ? ?2? ? ?0? ? ?3

? ? ?0? ? ?1? ? ?2? ? ?3? ? ?0

? ? ?0? ? ?0? ? ?3? ? ?2? ? ?1

? ? ?0? ? ?0? ? ?3? ? ?1? ? ?2

? ? ?0? ? ?0? ? ?2? ? ?3? ? ?1

? ? ?0? ? ?0? ? ?2? ? ?1? ? ?3

? ? ?0? ? ?0? ? ?1? ? ?3? ? ?2

? ? ?0? ? ?0? ? ?1? ? ?2? ? ?3

? ? ?0? ? ?3? ? ?0? ? ?2? ? ?1

? ? ?0? ? ?3? ? ?0? ? ?1? ? ?2

? ? ?0? ? ?3? ? ?2? ? ?0? ? ?1

? ? ?0? ? ?3? ? ?2? ? ?1? ? ?0

? ? ?0? ? ?3? ? ?1? ? ?0? ? ?2

? ? ?0? ? ?3? ? ?1? ? ?2? ? ?0

? ? ?0? ? ?2? ? ?0? ? ?3? ? ?1

? ? ?0? ? ?2? ? ?0? ? ?1? ? ?3

? ? ?0? ? ?2? ? ?3? ? ?0? ? ?1

? ? ?0? ? ?2? ? ?3? ? ?1? ? ?0

? ? ?0? ? ?2? ? ?1? ? ?0? ? ?3

? ? ?0? ? ?2? ? ?1? ? ?3? ? ?0

? ? ?0? ? ?1? ? ?0? ? ?3? ? ?2

? ? ?0? ? ?1? ? ?0? ? ?2? ? ?3

? ? ?0? ? ?1? ? ?3? ? ?0? ? ?2

? ? ?0? ? ?1? ? ?3? ? ?2? ? ?0

? ? ?0? ? ?1? ? ?2? ? ?0? ? ?3

? ? ?0? ? ?1? ? ?2? ? ?3? ? ?0

? ? ?3? ? ?0? ? ?0? ? ?2? ? ?1

? ? ?3? ? ?0? ? ?0? ? ?1? ? ?2

? ? ?3? ? ?0? ? ?2? ? ?0? ? ?1

? ? ?3? ? ?0? ? ?2? ? ?1? ? ?0

? ? ?3? ? ?0? ? ?1? ? ?0? ? ?2

? ? ?3? ? ?0? ? ?1? ? ?2? ? ?0

? ? ?3? ? ?0? ? ?0? ? ?2? ? ?1

? ? ?3? ? ?0? ? ?0? ? ?1? ? ?2

? ? ?3? ? ?0? ? ?2? ? ?0? ? ?1

? ? ?3? ? ?0? ? ?2? ? ?1? ? ?0

? ? ?3? ? ?0? ? ?1? ? ?0? ? ?2

? ? ?3? ? ?0? ? ?1? ? ?2? ? ?0

? ? ?3? ? ?2? ? ?0? ? ?0? ? ?1

? ? ?3? ? ?2? ? ?0? ? ?1? ? ?0

? ? ?3? ? ?2? ? ?0? ? ?0? ? ?1

? ? ?3? ? ?2? ? ?0? ? ?1? ? ?0

? ? ?3? ? ?2? ? ?1? ? ?0? ? ?0

? ? ?3? ? ?2? ? ?1? ? ?0? ? ?0

? ? ?3? ? ?1? ? ?0? ? ?0? ? ?2

? ? ?3? ? ?1? ? ?0? ? ?2? ? ?0

? ? ?3? ? ?1? ? ?0? ? ?0? ? ?2

? ? ?3? ? ?1? ? ?0? ? ?2? ? ?0

? ? ?3? ? ?1? ? ?2? ? ?0? ? ?0

? ? ?3? ? ?1? ? ?2? ? ?0? ? ?0

? ? ?2? ? ?0? ? ?0? ? ?3? ? ?1

? ? ?2? ? ?0? ? ?0? ? ?1? ? ?3

? ? ?2? ? ?0? ? ?3? ? ?0? ? ?1

? ? ?2? ? ?0? ? ?3? ? ?1? ? ?0

? ? ?2? ? ?0? ? ?1? ? ?0? ? ?3

? ? ?2? ? ?0? ? ?1? ? ?3? ? ?0

? ? ?2? ? ?0? ? ?0? ? ?3? ? ?1

? ? ?2? ? ?0? ? ?0? ? ?1? ? ?3

? ? ?2? ? ?0? ? ?3? ? ?0? ? ?1

? ? ?2? ? ?0? ? ?3? ? ?1? ? ?0

? ? ?2? ? ?0? ? ?1? ? ?0? ? ?3

? ? ?2? ? ?0? ? ?1? ? ?3? ? ?0

? ? ?2? ? ?3? ? ?0? ? ?0? ? ?1

? ? ?2? ? ?3? ? ?0? ? ?1? ? ?0

? ? ?2? ? ?3? ? ?0? ? ?0? ? ?1

? ? ?2? ? ?3? ? ?0? ? ?1? ? ?0

? ? ?2? ? ?3? ? ?1? ? ?0? ? ?0

? ? ?2? ? ?3? ? ?1? ? ?0? ? ?0

? ? ?2? ? ?1? ? ?0? ? ?0? ? ?3

? ? ?2? ? ?1? ? ?0? ? ?3? ? ?0

? ? ?2? ? ?1? ? ?0? ? ?0? ? ?3

? ? ?2? ? ?1? ? ?0? ? ?3? ? ?0

? ? ?2? ? ?1? ? ?3? ? ?0? ? ?0

? ? ?2? ? ?1? ? ?3? ? ?0? ? ?0

? ? ?1? ? ?0? ? ?0? ? ?3? ? ?2

? ? ?1? ? ?0? ? ?0? ? ?2? ? ?3

? ? ?1? ? ?0? ? ?3? ? ?0? ? ?2

? ? ?1? ? ?0? ? ?3? ? ?2? ? ?0

? ? ?1? ? ?0? ? ?2? ? ?0? ? ?3

? ? ?1? ? ?0? ? ?2? ? ?3? ? ?0

? ? ?1? ? ?0? ? ?0? ? ?3? ? ?2

? ? ?1? ? ?0? ? ?0? ? ?2? ? ?3

? ? ?1? ? ?0? ? ?3? ? ?0? ? ?2

? ? ?1? ? ?0? ? ?3? ? ?2? ? ?0

? ? ?1? ? ?0? ? ?2? ? ?0? ? ?3

? ? ?1? ? ?0? ? ?2? ? ?3? ? ?0

? ? ?1? ? ?3? ? ?0? ? ?0? ? ?2

? ? ?1? ? ?3? ? ?0? ? ?2? ? ?0

? ? ?1? ? ?3? ? ?0? ? ?0? ? ?2

? ? ?1? ? ?3? ? ?0? ? ?2? ? ?0

? ? ?1? ? ?3? ? ?2? ? ?0? ? ?0

? ? ?1? ? ?3? ? ?2? ? ?0? ? ?0

? ? ?1? ? ?2? ? ?0? ? ?0? ? ?3

? ? ?1? ? ?2? ? ?0? ? ?3? ? ?0

? ? ?1? ? ?2? ? ?0? ? ?0? ? ?3

? ? ?1? ? ?2? ? ?0? ? ?3? ? ?0

? ? ?1? ? ?2? ? ?3? ? ?0? ? ?0

? ? ?1? ? ?2? ? ?3? ? ?0? ? ?0

看在我這么辛苦把這120種情況都列出的情況下，大家要不要考慮給本文點(diǎn)個(gè)贊~（開個(gè)玩笑，我用的是Matlab的perms函數(shù)生成的?。?/strong>

接下來要對(duì)上面的解進(jìn)行解釋了，我們還是挑幾個(gè)典型的：
3 ?? 0??? ?2 ?? ?1 ?? ?0：

第1個(gè)旅行商的方案：0-3-0；第2個(gè)旅行商的方案：0-2-1-0；第3個(gè)旅行商不出門

0 ?? 1 ?? 0 ?? 3 ?? ?2：

第1個(gè)旅行商不出門；第2個(gè)旅行商的方案：0-1-0；第3個(gè)旅行商的方案：0-3-2-0

1 ?? 0 ?? 3 ?? 0 ?? ?2：

第1個(gè)旅行商的方案：0-1-0；第2個(gè)旅行商的方案：0-3-0；第3個(gè)旅行商的方案：0-2-0

2 ??0 ? ?0? ?3 ?? ?1：

第1個(gè)旅行商的方案：0-2-0；第2個(gè)旅行商不出門；第3個(gè)旅行商的方案：0-3-1-0

0 ?? 0 ?? 3 ?? 1 ?? 2：

第1個(gè)旅行商不出門；第2個(gè)旅行商不出門；第3個(gè)旅行商的方案：0-3-1-2-0

這里我們對(duì)其解釋的關(guān)鍵仍然是對(duì)0所在的位置進(jìn)行分割，只不過這時(shí)候有兩個(gè)0，我們可以根據(jù)兩個(gè)0來將整個(gè)解分成三份，每一份作為一個(gè)旅行商的旅行方案，如果相應(yīng)的那一份為空集的話（例如0位于最開始或最后，或者有兩個(gè)0挨在一起），則認(rèn)為該旅行商不出門。

上面的大家如果沒有問題的話，我們來看看一個(gè)更復(fù)雜的情況：現(xiàn)在有21個(gè)城市，第0號(hào)為起始城市，其他城市編號(hào)為1-20，一共有4個(gè)旅行商，其中我們得到的解為：

? 9? ? 19? ? ?4? ? 10??? ?3? ? ?0? ? ?1? ? 15? ? ?2? ? ?0? ? ?5? ? ?7? ? 12? ? 18? ? ?6? ? 11? ? 20? ? ?8? ? 14? ??0? ? ?17? ? 13? ? 16

那么怎么對(duì)這個(gè)解進(jìn)行解釋？

如果大家知道答案的話就可以繼續(xù)看下面的內(nèi)容啦，不知道的話建議再看看前面的內(nèi)容消化消化。

前面我們說過，模擬退火里面最重要的一個(gè)步驟就是如何定義解以及怎么去產(chǎn)生新解，因此上面這些步驟都是告訴大家MTSP中解是如何定義的。

這里我們做一個(gè)總結(jié)：

假設(shè)現(xiàn)在有n+1個(gè)城市，第0號(hào)為起始城市，其他城市編號(hào)為1至n，一共有m個(gè)旅行商，那么我們生成的解應(yīng)該為：

m-1個(gè)0 和 1至n 組成的一個(gè)隨機(jī)排序

注意哦，這里只有m-1個(gè)0，大家別弄錯(cuò)啦。這里的0你實(shí)際上就可以看成將解進(jìn)行分割的位置。

那么，我們應(yīng)該如何產(chǎn)生新解呢？很簡單，和TSP問題一樣就可以，三種方法任你挑選。

下面給大家說說編程的思路，事實(shí)上前面思路弄懂了應(yīng)該就沒問題了，只不過這里的編程還是略微有點(diǎn)復(fù)雜的，我提示大家一下：

（1）產(chǎn)生初始解的時(shí)候，我們可以先用randperm函數(shù)生成1至n的隨機(jī)排序，然后再多次使用randi函數(shù)隨機(jī)生成插入0的位置。

（2）計(jì)算總的距離（總成本）時(shí)，我們需要對(duì)解進(jìn)行拆分，每一個(gè)旅行商經(jīng)過的路徑我們都可以保存在一個(gè)元胞數(shù)組中，這里面可能要用到cell函數(shù)和find函數(shù)。

后面的編程就交給大家自己實(shí)現(xiàn)啦，重點(diǎn)在于建模的思路，希望本文對(duì)大家有所啟發(fā)，未來我會(huì)在購買的建模視頻中給大家免費(fèi)更新模擬退火，到時(shí)候有需要的話我再來詳細(xì)講解這個(gè)內(nèi)容。

標(biāo)簽：