MD-MTSP：遗传算法GA求解多仓库多旅行商问题（提供MATLAB代码，可以修改旅行商个数及起点）

一、多仓库多旅行商问题

多旅行商问题（Multiple Traveling Salesman Problem, MTSP）是著名的旅行商问题（Traveling Salesman Problem, TSP）的延伸，多旅行商问题定义为：给定一个𝑛座城市的城市集合，指定𝑚个推销员，每一位推销员从起点城市出发访问一定数量的城市，最后回到终点城市，要求除起点和终点城市以外，每一座城市都必须至少被一位推销员访问，并且只能访问一次，需要求解出满足上述要求并且代价最小的分配方案，其中的代价通常用总路程长度来代替，当然也可以是时间、费用等。多仓库多旅行商问题是其中一种多旅行商问题。

多仓库多旅行商问题（Multi-Depot Multiple Travelling Salesman Problem, MD-MTSP）：𝑚个推销员从𝑚座不同的城市出发，访问其中一定数量的城市并且每座城市只能被某一个推销员访问一次，最后回到各自出发的城市，这种问题模型被称之为MD-MTSP。

二、遗传算法GA

遗传算法（Genetic Algorithm，GA）起源于对生物系统所进行的计算机模拟研究，是一种随机全局搜索优化方法，它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象，从任一初始种群（Population）出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代不断繁衍进化，最后收敛到一群最适应环境的个体（Individual），从而求得问题的优质解。
遗传算法GA介绍

三、遗传算法GA求解多仓库多旅行商问题MDMTSP

遗传算法GA求解多仓库多旅行商问题MDMTSP介绍
本文选取国际通用的TSP实例库TSPLIB中的测试集bayg29，bayg29中城市分布如下图所示：

以四个旅行商为例，部分代码如下：可以修改旅行商个数及起点

完整MATLAB code link ：https://mbd.pub/o/bread/ZJmTlZhxclose all
clear
clc
global data  StartPoint Tnum
%数据集参考文献  REINELT G.TSPLIB-a traveling salesman problem[J].ORSA Journal on Computing,1991,3(4):267-384.
% 导入TSP数据集 bayg29
load('data.txt')
StartPoint=[1 5 10 16];%起点城市的序号(可以修改) 必须由小到大排列 （建议：2到6个旅行商）
Tnum=length(StartPoint);%旅行商个数
Dim=size(data,1)-Tnum;%维度
lb=-100;%下界
ub=100;%上界
fobj=@Fun;%计算总距离
SearchAgents_no=50; % 种群大小（可以修改）
Max_iteration=200; % 最大迭代次数（可以修改）
[fMin,bestX,curve]=GA(SearchAgents_no,Max_iteration,lb,ub,Dim,fobj); 

部分结果如下：

第一次运行结果

第1个旅行商的路径：1->6->9->26->3->29->2->1

第1个旅行商的总路径长度：1041.825321

第2个旅行商的路径：5->12->28->24->4->20->21->5

第2个旅行商的总路径长度：1176.180258

第3个旅行商的路径：10->13->27->8->23->7->19->10

第3个旅行商的总路径长度：1311.258937

第4个旅行商的路径：16->15->18->14->17->22->11->25->16

第4个旅行商的总路径长度：1093.252029

所有旅行商的总路径长度：4622.516546

第二次运行结果

第1个旅行商的路径：1->13->20->2->29->3->26->1
第1个旅行商的总路径长度：1223.356040
第2个旅行商的路径：5->9->12->6->28->24->21->5
第2个旅行商的总路径长度：922.713390
第3个旅行商的路径：10->18->17->22->14->15->4->10
第3个旅行商的总路径长度：830.782763
第4个旅行商的路径：16->19->11->25->7->23->8->27->16
第4个旅行商的总路径长度：1229.796731
所有旅行商的总路径长度：4206.648924

四、完整MATLAB代码