✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，matlab项目合作可私信。
🍎个人主页：Matlab科研工作室
🍊个人信条：格物致知。
更多Matlab仿真内容点击👇
⛄ 内容介绍
旅行商问题是一个经典的NP完全问题,多人旅行商问题的求解则更具挑战性.以往对求解多人旅行商问题的研究局限于以所有成员路径总和最小为优化标准,而对以所有成员路径最大值最小为优化标准的另一类多人旅行商问题却未加注意.文章给出了这两类多人旅行商问题的形式化描述,探讨了利用遗传算法求解这两类多人旅行商问题的基本思想和具体方案,进行了仿真实验验证.仿真实验数据表明,这是一种高效而且适应性强的多入旅行商问题求解方法.
⛄ 部分代码
function varargout = mtspf_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res)
% MTSPF_GA Fixed Multiple Traveling Salesmen Problem (M-TSP) Genetic Algorithm (GA)
% Finds a (near) optimal solution to a variation of the M-TSP by setting
% up a GA to search for the shortest route (least distance needed for
% each salesman to travel from the start location to individual cities
% and back to the original starting place)
%
% Summary:
% 1. Each salesman starts at the first point, and ends at the first
% point, but travels to a unique set of cities in between
% 2. Except for the first, each city is visited by exactly one salesman
%
% Note: The Fixed Start/End location is taken to be the first XY point
%
% Input:
% XY (float) is an Nx2 matrix of city locations, where N is the number of cities
% DMAT (float) is an NxN matrix of city-to-city distances or costs
% SALESMEN (scalar integer) is the number of salesmen to visit the cities
% MIN_TOUR (scalar integer) is the minimum tour length for any of the
% salesmen, NOT including the start/end point
% POP_SIZE (scalar integer) is the size of the population (should be divisible by 8)
% NUM_ITER (scalar integer) is the number of desired iterations for the algorithm to run
% SHOW_PROG (scalar logical) shows the GA progress if true
% SHOW_RES (scalar logical) shows the GA results if true
%
% Output:
% OPT_RTE (integer array) is the best route found by the algorithm
% OPT_BRK (integer array) is the list of route break points (these specify the indices
% into the route used to obtain the individual salesman routes)
% MIN_DIST (scalar float) is the total distance traveled by the salesmen
%
% Route/Breakpoint Details:
% If there are 10 cities and 3 salesmen, a possible route/break
% combination might be: rte = [5 6 9 4 2 8 10 3 7], brks = [3 7]
% Taken together, these represent the solution [1 5 6 9 1][1 4 2 8 1][1 10 3 7 1],
% which designates the routes for the 3 salesmen as follows:
% . Salesman 1 travels from city 1 to 5 to 6 to 9 and back to 1
% . Salesman 2 travels from city 1 to 4 to 2 to 8 and back to 1
% . Salesman 3 travels from city 1 to 10 to 3 to 7 and back to 1
%
% 2D Example:
% n = 35;
% xy = 10*rand(n,2);
% salesmen = 5;
% min_tour = 3;
% pop_size = 80;
% num_iter = 5e3;
% a = meshgrid(1:n);
% dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
% [opt_rte,opt_brk,min_dist] = mtspf_ga(xy,dmat,salesmen,min_tour, ...
% pop_size,num_iter,1,1);
%
% 3D Example:
% n = 35;
% xyz = 10*rand(n,3);
% salesmen = 5;
% min_tour = 3;
% pop_size = 80;
% num_iter = 5e3;
% a = meshgrid(1:n);
% dmat = reshape(sqrt(sum((xyz(a,:)-xyz(a',:)).^2,2)),n,n);
% [opt_rte,opt_brk,min_dist] = mtspf_ga(xyz,dmat,salesmen,min_tour, ...
% pop_size,num_iter,1,1);
%
% See also: mtsp_ga, mtspo_ga, mtspof_ga, mtspofs_ga, mtspv_ga, distmat
% Process Inputs and Initialize Defaults
nargs = 8;
for k = nargin:nargs-1
switch k
case 0
xy = 10*rand(40,2);
case 1
N = size(xy,1);
a = meshgrid(1:N);
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);
case 2
salesmen = 5;
case 3
min_tour = 2;
case 4
pop_size = 80;
case 5
num_iter = 5e3;
case 6
show_prog = 1;
case 7
show_res = 1;
otherwise
end
⛄ 运行结果
⛄ 参考文献
[1]葛春志, 汪亚东, 王荣鑫,等. 基于遗传算法的旅行商问题多量值最优化求解研究[J]. 黑龙江大学自然科学学报, 2013(5):8.
[2]吴云, 姜麟, 刘强. 基于并行遗传算法多旅行商问题的求解[J]. 微型电脑应用, 2011(7):4.
