1. TSP问题与MTSP问题
1.1 TSP与MTSP问题的介绍：
- TSP：是指旅行家（1名）要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的 路程最短。
TSP问题（图片来自网络）
- MTSP：有 m个旅行商_去旅游 n个城市_，规定都必须从同一个出发点出发，而且返回原出发点，需要将所有的城市遍历完毕，每个城市只能游历一次，但是为了路径最短可以路过这个城市多次。这个就是多旅行商问题。是在TSP问题的基础上进行了扩展。
MTSP问题（图片来自网络）
1.2 MTSP与TSP问题的区别：
- TSP指的是单个旅行商遍历一圈，将所有城市旅行一遍。
- MTSP指的是将城市群划分成M个组，每组采用TSP得到最短的旅行路线，所以问题的关键在于如何确定城市群的 分组。
2. MTSP问题的目标
MTSP问题是一个多目标问题，且 平均分配各旅行商的任务是多旅行商问题的一个重要的环节。MTSP问题的目标一般如下[1]：
- 最小化总行程 && 均分多个旅行商访问节点数（不同城市数量）
- 最小化总行程 && 均分访问路程
2.1 均分访问节点数的MTSP问题
目标函数1：
目标函数2：
合并为一个目标函数：（↓更正：最后一个”+”应为”*”）
总目标函数既能使 总行程达到最小，同时也能达到平均分配 M个旅行商的访问节点数的目的。
2.2 均分行驶路程的多旅行商问题
目标函数1：
目标函数2：
合并为一个目标函数：
总目标函数中，前一项体现均分M个路径长度的效果，后一项则是总路径长度。k为调节总目标函数中两个组成部分之间比例的系数(k>0)。
3. MTSP问题的求解方法及代码
主要基于GA（遗传算法）与SA（模拟退火算法）解决MTSP问题。
代码详见：https://github.com/Star-Stone/MTSP-GA-and-SA ，以下样例基于此代码。
问题一：
工厂安排 巡检路线问题，即多个员工巡检完全部检查点。
class GA:
"商旅数量、城市数量、出发城市编号、文件路径、最大循环次数、路程权重、均衡度权重"
def __init__(self, salesman_num, city_num, start_index,
filename, max_gen, distance_weight, balance_weight):
以上是定义的 GA类初始化所需传入的相关参数，注意其中的 路程权重、均衡度权重,在目标函数求解中将用到。
核心思路：虚点
通过增加虚点，将MTSP问题转化为TSP问题
总共8个城市，3号城市为起始点.下列染色体组成我们把起点和终点省略，看情况是否 增加虚点
- 1个旅行商：一个chrom = [把3剔除，其余数字由1到8组成]
如[1,5,4,2,6,8,7]表示旅行商路线为3->1->5->4->2->6->8->7->3 - 2个旅行商：一个chrom = [1个9(9代表虚点，其实也是起点3)，其余数字由1到8组成]。以此类推到多个旅行商的情况。
如[1,5,4,9,2,6,8,7]表示：
旅行商1路线为3->1->5->4->3(9)
旅行商2路线为3(9)->2->6->8->7->3 - 3个旅行商：一个chrom = [9,10，其余数字由1到8组成]
如[1,5,4,9,2,6,10,8,7]
旅行商1路线为3->1->5->4->3(9)
旅行商2路线为3(9)->2->6->3(10)
旅行商3路线为3(10)->8->7->3
即m个旅行商，增加((m-1))个虚点，沿虚点分割路线即为每个旅行商的路线。
目标函数：路程与均衡度的加权平均
目标函数 Z = distance_weight _总路程 + balance_weight_均衡度
均衡度 = (max(l)-min(l))/ max(l)
本题使用SA算法的思路与GA算法类似。详情请阅读代码，不做详细展开。
- THE END –
参考文献
[1]卢厚清,王辉东,黄杰,等. 任务均分的多旅行商问题[J]. 系统工程,2005,23(2):19-21. DOI:10.3969/j.issn.1001-4098.2005.02.005.
[2]郭强,迟洪钦. 基于GA的MTSP问题的研究[J]. 计算机与数字工程,2010,38(10):5-7,18. DOI:10.3969/j.issn.1672-9722.2010.10.002.
Original: https://www.cnblogs.com/litecdows/p/16500123.html
Author: litecdows
Title: MTSP问题的简单介绍
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/609769/
转载文章受原作者版权保护。转载请注明原作者出处！