MTSP问题的简单介绍

MTSP问题的简单介绍1.TSP问题与MTSP问题1.1TSP与MTSP问题的介绍:TSP:是指旅行家(1名)要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。TSP问题(图片来自网络)MTSP:有m个旅行商去旅游n个城市,规定都必须从同一个出发点出发,而且返回原出发点,需

大家好,欢迎来到IT知识分享网。

1. TSP问题与MTSP问题

1.1 TSP与MTSP问题的介绍:

  • TSP:是指旅行家(1名)要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短
MTSP问题的简单介绍

TSP问题(图片来自网络)
  • MTSP:m个旅行商去旅游 n个城市,规定都必须从同一个出发点出发,而且返回原出发点,需要将所有的城市遍历完毕,每个城市只能游历一次,但是为了路径最短可以路过这个城市多次。这个就是多旅行商问题。是在TSP问题的基础上进行了扩展。
MTSP问题的简单介绍

MTSP问题(图片来自网络)

1.2 MTSP与TSP问题的区别:

  •  TSP指的是单个旅行商遍历一圈,将所有城市旅行一遍。
  •   MTSP指的是将城市群划分成M个组,每组采用TSP得到最短的旅行路线,所以问题的关键在于如何确定城市群的分组

2. MTSP问题的目标

MTSP问题是一个多目标问题,且平均分配各旅行商的任务是多旅行商问题的一个重要的环节。MTSP问题的目标一般如下[1]:

  • 最小化总行程 && 均分多个旅行商访问节点数(不同城市数量)
  • 最小化总行程 && 均分访问路程

2.1 均分访问节点数的MTSP问题

目标函数1:image
目标函数2:image
合并为一个目标函数:(↓更正:最后一个“+”应为“*”)

MTSP问题的简单介绍

总目标函数既能使总行程达到最小,同时也能达到平均分配 M个旅行商的访问节点数的目的。

2.2 均分行驶路程的多旅行商问题

目标函数1:image
目标函数2:image
合并为一个目标函数:

MTSP问题的简单介绍

总目标函数中,前一项体现均分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)

MTSP问题的简单介绍

本题使用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.

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/30460.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信