matlab求解tsp_TSP问题、MTSP问题建模及求解（MATLAB）

点击蓝字

关注我们

TSP

问题

PART 01

问题提出

图1｜坐标分布图

数据中心为某辆充电小车的出发点，坐标1~坐标29为29个充电点，充电小车需从数据中心出发并且依次经过29个充电点，最后回到数据中心。为使路线总路径最短，需确定充电小车每一步该怎么走，这就是典型的TSP问题。

模型建立

TSP求解算法对比

蚁群算法求解TSP问题

求解结果

图2｜移动小车充电路线图

MTSP

问题

PART 02

问题提出

        当数据中心含有4辆小车时，4辆小车需要合作完成充电任务，即每辆小车负责一部分充电点的充电，并且使总路程最短，该问题为典型的多旅行社问题，即MTSP问题。

模型建立

遗传求解MTSP问题

求解结果

图3｜多移动小车充电路线图

MATLAB源代码

蚁群算法求解TSP问题

clc;clf;clear;data1 = xlsread('附件1.xlsx');x = data1(:,1);y = data1(:,2);X = data1(:,1:2);[N,n]=size(X);      % N =测试样本数;n =测试样本的属性数;K = 4;              % K = 组数; R = 100;            % R = 蚂蚁数; t_max = 1000;       % t_max =最大迭代次数;                 % 初始化c = 10^-2;tau = ones(N,K) * c;    %信息素矩阵，初始值为0.01的N*K矩阵(样本数*聚类数)q = 0.9;                % 阈值qrho = 0.1;              % 蒸发率best_solution_function_value = inf; % 最佳路径度量值(初值为无穷大，该值越小聚类效果越好)tict = 1; % while ((t<=t_max))                             %达到最大迭代次数而终止% while ((best_solution_function_value>=19727))  %达到一定的聚类效果而终止while ((best_solution_function_value>=19727))        %路径标识字符：标识每只蚂蚁的路径    solution_string = zeros(R,N+1);         for i = 1 : R                       %以信息素为依据确定蚂蚁的路径        r = rand(1,N);    %随机产生值为0-1随机数的1*51的数组        for g = 1 : N            if r(g) < q     %如果r(g)小于阈值                tau_max = max(