求解多旅行商問(wèn)題的模擬退火核心代碼
我已經(jīng)寫(xiě)了兩篇多旅行商問(wèn)題（MTSP）的文章了，如果大家沒(méi)有看過(guò)的話可以點(diǎn)擊下面鏈接可跳轉(zhuǎn)查看：
今年深圳杯C題就和這個(gè)多旅行商問(wèn)題很類似，而我們說(shuō)過(guò)所謂的MTSP實(shí)際上就是車(chē)輛路徑問(wèn)題的一類，因此大家可以在網(wǎng)上搜索車(chē)輛路徑問(wèn)題的相關(guān)文獻(xiàn)。
下面我就放上Matlab寫(xiě)的模擬退火求解MTSP的核心代碼：
（1）模擬退火生成初始解的代碼
%?city_num表示待訪問(wèn)的城市數(shù)量（不包括起始城市）??
%?salesman_num表示可以安排訪問(wèn)任務(wù)的旅行商數(shù)量??
path0?=?randperm(city_num);??%?首先生成所有待訪問(wèn)城市的一個(gè)隨機(jī)組合序列??
%?在上面的序號(hào)中間插入0，實(shí)際上就是我們的分割點(diǎn)（最多salesman_num個(gè)旅行商工作）??
for?i?=?1:salesman_num-1?%?使用循環(huán)，在path0中隨機(jī)插入car_num-1個(gè)0??
????len?=?length(path0);?%?計(jì)算此時(shí)path0的長(zhǎng)度（因?yàn)樵诓粩嗖迦?，所以長(zhǎng)度會(huì)不斷增加）??
????ind?=?randi(len);?%?生產(chǎn)一個(gè)1-len之間的隨機(jī)數(shù)，ind表示要插入0的位置??
????path0?=?[path0(1:ind),0,path0(ind+1:end)];?%?插入0??
end??
（2）對(duì)生成的解進(jìn)行清理分割的代碼
%%?clear_path函數(shù)用來(lái)對(duì)原來(lái)的解進(jìn)行分割，中間的0就是分割的位置??
%?輸入??
%?path：原來(lái)的解，是一個(gè)向量，中間的0表示分割的位置??
%?salesman_num：旅行商數(shù)量（不一定都分配工作哦）??
%?輸出??
%?cpath：一個(gè)元胞數(shù)組，用來(lái)存儲(chǔ)參與運(yùn)輸?shù)拿總€(gè)旅行商經(jīng)過(guò)的城市??
%?k：有多少旅行商工作了??
function?[cpath,k]=?clear_path(path,salesman_num)??
????cpath?=?cell(salesman_num,1);????%?新建一個(gè)元胞數(shù)組，用來(lái)存儲(chǔ)參與工作的每個(gè)旅行商經(jīng)過(guò)的城市??
????ind?=?find(path==0);??????%?找到所有分割點(diǎn)的位置??
????k?=?1;??????%?初始化計(jì)數(shù)器，k表示參與工作的旅行商數(shù)??
????for?i?=?1:salesman_num-1?%?一共salesman_num-1個(gè)分割點(diǎn)，我們開(kāi)始循環(huán)??
????????if?i?==?1??%?如果是第1個(gè)分割點(diǎn)??
????????????c?=?path(1:ind(i)-1);??%?提取第一個(gè)旅行商經(jīng)過(guò)的城市??
????????else??
????????????c?=?path(ind(i-1)+1:ind(i)-1);???%?提取中間的旅行商所經(jīng)過(guò)的城市??
????????end??
????????if?~isempty(c)??%?只有c非空的話才保存到cpath中（注意～符號(hào)表示取反的意思）??
????????????cpath{k}?=?c;??%?把c保存到元胞cpath的第k個(gè)位置??
????????????k?=?k+1;???????%?參與工作的旅行商數(shù)目加1??
????????end??
????end??
????%?別忘了從最后一個(gè)分割點(diǎn)哦，它和第1個(gè)分割點(diǎn)一樣，需要單獨(dú)討論??
????c?=?path(ind(end)+1:end);????%?提取最后一個(gè)旅行商經(jīng)過(guò)的城市??
????if?~isempty(c)??%?只有c非空的話才保存到cpath中??
???????cpath{k}?=?c;??%?把c保存到元胞cpath的第k個(gè)位置??
????else??
????????k?=?k?-?1;??
????end??
????cpath?=?cpath(1:k);?%?只保留元胞中前k個(gè)非空的部分??
end??
（3）計(jì)算當(dāng)前解對(duì)應(yīng)的成本（這里沒(méi)有加任何限定條件，大家可以根據(jù)自己的需求來(lái)改，詳情請(qǐng)看本文最上方對(duì)應(yīng)的第二篇文章）
%%?計(jì)算當(dāng)前解對(duì)應(yīng)的成本??
%?輸入??
%?cpath：當(dāng)前解經(jīng)過(guò)清洗拆分后得到的一個(gè)元胞數(shù)組，用來(lái)存儲(chǔ)參與運(yùn)輸?shù)拿總€(gè)旅行商經(jīng)過(guò)的城市??
%?k：有多少旅行商工作了??
%?d：距離矩陣（別忘了第一個(gè)位置表示起始的城市）??
%?例如一共n個(gè)城市，那么起始城市要放在第一個(gè)位置，d是n*n的距離矩陣??
%?輸出??
%?cost：當(dāng)前解對(duì)應(yīng)的總成本（所有旅行商的路程長(zhǎng)度的總和）??
%?every_cost：每個(gè)旅行商的成本（路程）??
??
function?[cost,every_cost]?=?calculate_mtsp_cost(cpath,k,d)??
%?要計(jì)算所有旅行商的路程長(zhǎng)度的總和，我們需要首先計(jì)算每個(gè)旅行商的路程長(zhǎng)度??
????every_cost?=?zeros(k,1);??%?初始化每個(gè)旅行商的路程長(zhǎng)度全為0??
????for?i?=?1:k?%?對(duì)每個(gè)旅行商開(kāi)始循環(huán)???
????????path_i?=?cpath{i};??%?第i個(gè)旅行商所經(jīng)過(guò)的路線??
????????n?=?length(path_i);?%?第i個(gè)旅行商經(jīng)過(guò)的城市的數(shù)量??
????????for?j?=?1:n??
????????????if?j?==?1??
????????????????every_cost(i)?=?every_cost(i)?+?d(1,path_i(j)+1);??%?一定要注意，d中第一個(gè)位置表示起始的城市??
????????????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);?%?別忘了加上從最后一個(gè)城市返回到起始城市的路程??
????end??
????cost?=?sum(every_cost);??%?計(jì)算總的成本??
end??
（4）產(chǎn)生新解的方法
%%?gen_new_path函數(shù)用來(lái)產(chǎn)生新解??
%?輸入??
%?path0:?原來(lái)的路徑??
%?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);?%?隨機(jī)生成一個(gè)[0?1]間均勻分布的隨機(jī)數(shù)??
????if??r<?p1????%?使用交換法產(chǎn)生新路徑???
????????c1?=?randi(n);???%?生成1-n中的一個(gè)隨機(jī)整數(shù)??
????????c2?=?randi(n);???%?生成1-n中的一個(gè)隨機(jī)整數(shù)??
????????path1?=?path0;??%?將path0的值賦給path1??
????????path1(c1)?=?path0(c2);??%改變path1第c1個(gè)位置的元素為path0第c2個(gè)位置的元素??
????????path1(c2)?=?path0(c1);??%改變path1第c2個(gè)位置的元素為path0第c1個(gè)位置的元素??
????elseif?r?<?p1+p2?%?使用移位法產(chǎn)生新路徑??
????????c1?=?randi(n);???%?生成1-n中的一個(gè)隨機(jī)整數(shù)??
????????c2?=?randi(n);???%?生成1-n中的一個(gè)隨機(jī)整數(shù)??
????????c3?=?randi(n);???%?生成1-n中的一個(gè)隨機(jī)整數(shù)??
????????sort_c?=?sort([c1?c2?c3]);??%?對(duì)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中的一個(gè)隨機(jī)整數(shù)??
????????c2?=?randi(n);???%?生成1-n中的一個(gè)隨機(jī)整數(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];???%矩陣的左右對(duì)稱翻轉(zhuǎn)?fliplr，上下對(duì)稱翻轉(zhuǎn)?flipud??
????end??
end??
上面就是我用Matlab寫(xiě)的MTSP的核心代碼部分了，大家如果看了之前文章的話，應(yīng)該有能力能夠?qū)懗鰧?duì)應(yīng)的代碼了。
