求解多旅行商问题的模拟退火核心代码
我已经写了两篇多旅行商问题（MTSP）的文章了，如果大家没有看过的话可以点击下面链接可跳转查看：
今年深圳杯C题就和这个多旅行商问题很类似，而我们说过所谓的MTSP实际上就是车辆路径问题的一类，因此大家可以在网上搜索车辆路径问题的相关文献。
下面我就放上Matlab写的模拟退火求解MTSP的核心代码：
（1）模拟退火生成初始解的代码
% city_num表示待访问的城市数量（不包括起始城市）
% salesman_num表示可以安排访问任务的旅行商数量
path0 = randperm(city_num); % 首先生成所有待访问城市的一个随机组合序列
% 在上面的序号中间插入0，实际上就是我们的分割点（最多salesman_num个旅行商工作）
for i = 1:salesman_num-1 % 使用循环，在path0中随机插入car_num-1个0
len = length(path0); % 计算此时path0的长度（因为在不断插入0，所以长度会不断增加）
ind = randi(len); % 生产一个1-len之间的随机数，ind表示要插入0的位置
path0 = [path0(1:ind),0,path0(ind+1:end)]; % 插入0
end
（2）对生成的解进行清理分割的代码
%% clear_path函数用来对原来的解进行分割，中间的0就是分割的位置
% 输入
% path：原来的解，是一个向量，中间的0表示分割的位置
% salesman_num：旅行商数量（不一定都分配工作哦）
% 输出
% cpath：一个元胞数组，用来存储参与运输的每个旅行商经过的城市
% k：有多少旅行商工作了
function [cpath,k]= clear_path(path,salesman_num)
cpath = cell(salesman_num,1); % 新建一个元胞数组，用来存储参与工作的每个旅行商经过的城市
ind = find(path==0); % 找到所有分割点的位置
k = 1; % 初始化计数器，k表示参与工作的旅行商数
for i = 1:salesman_num-1 % 一共salesman_num-1个分割点，我们开始循环
if i == 1 % 如果是第1个分割点
c = path(1:ind(i)-1); % 提取第一个旅行商经过的城市
else
c = path(ind(i-1)+1:ind(i)-1); % 提取中间的旅行商所经过的城市
end
if ~isempty(c) % 只有c非空的话才保存到cpath中（注意～符号表示取反的意思）
cpath{k} = c; % 把c保存到元胞cpath的第k个位置
k = k+1; % 参与工作的旅行商数目加1
end
end
% 别忘了从最后一个分割点哦，它和第1个分割点一样，需要单独讨论
c = path(ind(end)+1:end); % 提取最后一个旅行商经过的城市
if ~isempty(c) % 只有c非空的话才保存到cpath中
cpath{k} = c; % 把c保存到元胞cpath的第k个位置
else
k = k - 1;
end
cpath = cpath(1:k); % 只保留元胞中前k个非空的部分
end
（3）计算当前解对应的成本（这里没有加任何限定条件，大家可以根据自己的需求来改，详情请看本文最上方对应的第二篇文章）
%% 计算当前解对应的成本
% 输入
% cpath：当前解经过清洗拆分后得到的一个元胞数组，用来存储参与运输的每个旅行商经过的城市
% k：有多少旅行商工作了
% d：距离矩阵（别忘了第一个位置表示起始的城市）
% 例如一共n个城市，那么起始城市要放在第一个位置，d是n*n的距离矩阵
% 输出
% cost：当前解对应的总成本（所有旅行商的路程长度的总和）
% every_cost：每个旅行商的成本（路程）
function [cost,every_cost] = calculate_mtsp_cost(cpath,k,d)
% 要计算所有旅行商的路程长度的总和，我们需要首先计算每个旅行商的路程长度
every_cost = zeros(k,1); % 初始化每个旅行商的路程长度全为0
for i = 1:k % 对每个旅行商开始循环
path_i = cpath{i}; % 第i个旅行商所经过的路线
n = length(path_i); % 第i个旅行商经过的城市的数量
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）产生新解的方法
%% gen_new_path函数用来产生新解
% 输入
% path0: 原来的路径
% p1: 使用交换法产生新路径的概率
% p2: 使用移位法产生新路径的概率
% 注意：1-p1-p2就是使用倒置法产生新路径的概率
% 输出
% path1：新路径
function path1 = gen_new_path(path0,p1,p2)
n = length(path0);
r = rand(1); % 随机生成一个[0 1]间均匀分布的随机数
if r< p1 % 使用交换法产生新路径
c1 = randi(n); % 生成1-n中的一个随机整数
c2 = randi(n); % 生成1-n中的一个随机整数
path1 = path0; % 将path0的值赋给path1
path1(c1) = path0(c2); %改变path1第c1个位置的元素为path0第c2个位置的元素
path1(c2) = path0(c1); %改变path1第c2个位置的元素为path0第c1个位置的元素
elseif r < p1+p2 % 使用移位法产生新路径
c1 = randi(n); % 生成1-n中的一个随机整数
c2 = randi(n); % 生成1-n中的一个随机整数
c3 = randi(n); % 生成1-n中的一个随机整数
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 % 使用倒置法产生新路径
c1 = randi(n); % 生成1-n中的一个随机整数
c2 = randi(n); % 生成1-n中的一个随机整数
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]; %矩阵的左右对称翻转 fliplr，上下对称翻转 flipud
end
end
上面就是我用Matlab写的MTSP的核心代码部分了，大家如果看了之前文章的话，应该有能力能够写出对应的代码了。
