我已經(jīng)寫了兩篇多旅行商問題（MTSP）的文章了，如果大家沒有看過的話可以點擊下面鏈接可跳轉(zhuǎn)查看：

（1）模擬退火解決“多旅行商問題”

（2）如何求解有條件的“多旅行商問題”

今年深圳杯C題就和這個多旅行商問題很類似，而我們說過所謂的MTSP實際上就是車輛路徑問題的一類，因此大家可以在網(wǎng)上搜索車輛路徑問題的相關(guān)文獻。
下面我就放上Matlab寫的模擬退火求解MTSP的核心代碼：

（1）模擬退火生成初始解的代碼

%?city_num表示待訪問的城市數(shù)量（不包括起始城市）??

%?salesman_num表示可以安排訪問任務(wù)的旅行商數(shù)量??

path0?=?randperm(city_num);??%?首先生成所有待訪問城市的一個隨機組合序列??

%?在上面的序號中間插入0，實際上就是我們的分割點（最多salesman_num個旅行商工作）??

for?i?=?1:salesman_num-1?%?使用循環(huán)，在path0中隨機插入car_num-1個0??

????len?=?length(path0);?%?計算此時path0的長度（因為在不斷插入0，所以長度會不斷增加）??

????ind?=?randi(len);?%?生產(chǎn)一個1-len之間的隨機數(shù)，ind表示要插入0的位置??

????path0?=?[path0(1:ind),0,path0(ind+1:end)];?%?插入0??

end??

（2）對生成的解進行清理分割的代碼

%%?clear_path函數(shù)用來對原來的解進行分割，中間的0就是分割的位置??

%?輸入??

%?path：原來的解，是一個向量，中間的0表示分割的位置??

%?salesman_num：旅行商數(shù)量（不一定都分配工作哦）??

%?輸出??

%?cpath：一個元胞數(shù)組，用來存儲參與運輸?shù)拿總€旅行商經(jīng)過的城市??

%?k：有多少旅行商工作了??

function?[cpath,k]=?clear_path(path,salesman_num)??

????cpath?=?cell(salesman_num,1);????%?新建一個元胞數(shù)組，用來存儲參與工作的每個旅行商經(jīng)過的城市??

????ind?=?find(path==0);??????%?找到所有分割點的位置??

????k?=?1;??????%?初始化計數(shù)器，k表示參與工作的旅行商數(shù)??

????for?i?=?1:salesman_num-1?%?一共salesman_num-1個分割點，我們開始循環(huán)??

????????if?i?==?1??%?如果是第1個分割點??

????????????c?=?path(1:ind(i)-1);??%?提取第一個旅行商經(jīng)過的城市??

????????else??

????????????c?=?path(ind(i-1)+1:ind(i)-1);???%?提取中間的旅行商所經(jīng)過的城市??

????????end??

????????if?~isempty(c)??%?只有c非空的話才保存到cpath中（注意～符號表示取反的意思）??

????????????cpath{k}?=?c;??%?把c保存到元胞cpath的第k個位置??

????????????k?=?k+1;???????%?參與工作的旅行商數(shù)目加1??

????????end??

????end??

????%?別忘了從最后一個分割點哦，它和第1個分割點一樣，需要單獨討論??

????c?=?path(ind(end)+1:end);????%?提取最后一個旅行商經(jīng)過的城市??

????if?~isempty(c)??%?只有c非空的話才保存到cpath中??

???????cpath{k}?=?c;??%?把c保存到元胞cpath的第k個位置??

????else??

????????k?=?k?-?1;??

????end??

????cpath?=?cpath(1:k);?%?只保留元胞中前k個非空的部分??

end??

（3）計算當前解對應(yīng)的成本（這里沒有加任何限定條件，大家可以根據(jù)自己的需求來改，詳情請看本文最上方對應(yīng)的第二篇文章）

%%?計算當前解對應(yīng)的成本??

%?輸入??

%?cpath：當前解經(jīng)過清洗拆分后得到的一個元胞數(shù)組，用來存儲參與運輸?shù)拿總€旅行商經(jīng)過的城市??

%?k：有多少旅行商工作了??

%?d：距離矩陣（別忘了第一個位置表示起始的城市）??

%?例如一共n個城市，那么起始城市要放在第一個位置，d是n*n的距離矩陣??

%?輸出??

%?cost：當前解對應(yīng)的總成本（所有旅行商的路程長度的總和）??

%?every_cost：每個旅行商的成本（路程）??

??

function?[cost,every_cost]?=?calculate_mtsp_cost(cpath,k,d)??

%?要計算所有旅行商的路程長度的總和，我們需要首先計算每個旅行商的路程長度??

????every_cost?=?zeros(k,1);??%?初始化每個旅行商的路程長度全為0??

????for?i?=?1:k?%?對每個旅行商開始循環(huán)???

????????path_i?=?cpath{i};??%?第i個旅行商所經(jīng)過的路線??

????????n?=?length(path_i);?%?第i個旅行商經(jīng)過的城市的數(shù)量??

????????for?j?=?1:n??

????????????if?j?==?1??

????????????????every_cost(i)?=?every_cost(i)?+?d(1,path_i(j)+1);??%?一定要注意，d中第一個位置表示起始的城市??

????????????else??

????????????????every_cost(i)?=?every_cost(i)?+?d(path_i(j-1)+1,path_i(j)+1)?;??

????????????end??

????????end??

????????every_cost(i)?=?every_cost(i)?+?d(path_i(end)+1,1);?%?別忘了加上從最后一個城市返回到起始城市的路程??

????end??

????cost?=?sum(every_cost);??%?計算總的成本??

end??

（4）產(chǎn)生新解的方法

%%?gen_new_path函數(shù)用來產(chǎn)生新解??

%?輸入??

%?path0:?原來的路徑??

%?p1:?使用交換法產(chǎn)生新路徑的概率??

%?p2:?使用移位法產(chǎn)生新路徑的概率??

%?注意：1-p1-p2就是使用倒置法產(chǎn)生新路徑的概率??

%?輸出??

%?path1：新路徑??

function?path1?=?gen_new_path(path0,p1,p2)??

????n?=?length(path0);??

????r?=?rand(1);?%?隨機生成一個[0?1]間均勻分布的隨機數(shù)??

????if??r<?p1????%?使用交換法產(chǎn)生新路徑???

????????c1?=?randi(n);???%?生成1-n中的一個隨機整數(shù)??

????????c2?=?randi(n);???%?生成1-n中的一個隨機整數(shù)??

????????path1?=?path0;??%?將path0的值賦給path1??

????????path1(c1)?=?path0(c2);??%改變path1第c1個位置的元素為path0第c2個位置的元素??

????????path1(c2)?=?path0(c1);??%改變path1第c2個位置的元素為path0第c1個位置的元素??

????elseif?r?<?p1+p2?%?使用移位法產(chǎn)生新路徑??

????????c1?=?randi(n);???%?生成1-n中的一個隨機整數(shù)??

????????c2?=?randi(n);???%?生成1-n中的一個隨機整數(shù)??

????????c3?=?randi(n);???%?生成1-n中的一個隨機整數(shù)??

????????sort_c?=?sort([c1?c2?c3]);??%?對c1?c2?c3從小到大排序??

????????c1?=?sort_c(1);??c2?=?sort_c(2);??c3?=?sort_c(3);??%?c1?<?=?c2?<=??c3??

????????tem1?=?path0(1:c1-1);??

????????tem2?=?path0(c1:c2);??

????????tem3?=?path0(c2+1:c3);??

????????tem4?=?path0(c3+1:end);??

????????path1?=?[tem1?tem3?tem2?tem4];??

????else??%?使用倒置法產(chǎn)生新路徑??

????????c1?=?randi(n);???%?生成1-n中的一個隨機整數(shù)??

????????c2?=?randi(n);???%?生成1-n中的一個隨機整數(shù)??

????????if?c1>c2??%?如果c1比c2大，就交換c1和c2的值??

????????????tem?=?c2;??

????????????c2?=?c1;??

????????????c1?=?tem;??

????????end??

????????tem1?=?path0(1:c1-1);??

????????tem2?=?path0(c1:c2);??

????????tem3?=?path0(c2+1:end);??

????????path1?=?[tem1?fliplr(tem2)?tem3];???%矩陣的左右對稱翻轉(zhuǎn)?fliplr，上下對稱翻轉(zhuǎn)?flipud??

????end??

end??

上面就是我用Matlab寫的MTSP的核心代碼部分了，大家如果看了之前文章的話，應(yīng)該有能力能夠?qū)懗鰧?yīng)的代碼了。