首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >运筹学教学|分枝定界求解旅行商问题

运筹学教学|分枝定界求解旅行商问题

作者头像
用户1621951
发布2018-04-19 16:07:04
1.9K0
发布2018-04-19 16:07:04
举报
文章被收录于专栏:数据魔术师数据魔术师
分枝定界(branch and bound)某年某月某日,小编正在绝地岛横行霸道。此时,突然手机屏幕一亮,老板来电话,说是有一个branch and bound要写,小编内心一凉,冒着被打成盒子的危险,给出了这个推文。利用分支定界求解旅行商问题(Travelling Salesman Problem,TSP)

分枝定界算法的基本思路如下:

假设有最小化的整数规划问题A,它相应的线性松弛(LP relaxation)规划问题为B。从解问题B开始,若其最优解不符合A的整数条件,那么B的最优目标函数值必是A的最优目标函数值 z* 的下界,记作 Z ;而 A 的任意可行解的目标函数值将是 z* 的一个上界 z 。分枝定界法就是将 A 的可行域分成子区域的方法,逐步增大 Z 和减小z ,最终求到 z* 。

通常,把全部可行解空间反复地分割为越来越小的子集,称为分枝;并且对每个子集内的解集计算一个目标下界(对于最小值问题),这称为定界。在每次分枝后,凡是界限超出已知可行解集目标值(即上界)的那些子集不再进一步分枝,这样,许多子集可不予考虑,这称为剪枝。这就是分枝定界法的主要思路。

求解TSP通常采用的定界方法是用分配问题定界或者是1-tree来定界。

分配问题的匈牙利算法在之前的文章中有过介绍,在此便不再赘述,详情请参考本公众号文章

运筹学教学 | 十分钟教你求解分配问题(assignment problem)

关于1-tree我们在这里简单介绍一下,更加详细的介绍将会在之后的附件中给出,请关注留言区

在一个图G(V,E)中,节点集合V = {1...n},我们定义{2...n}节点组成的子图的生成树以及两条与1节点的边组成的新图为1-tree。如下图:

TSP的可行解是1-tree的一种,因此最小权值1-tree (minimum weight 1-tree)可以作为TSP的一个下界,因此可以利用这个性质来作为定界的标准。

最小权值1-tree的很容易求得,只需要求解子图{2...n}的最小生成树再加上两条与1节点相连的最短的边即可。

一棵1-tree是一个TSP的可行解的充要条件是1-tree中所有节点的度(degree)均为2。这样分枝的方法也就有了,即寻找1-tree中所有度大于等于3的节点,枚举并依次删除这个节点所有的边,依次求解最小权值1-tree,直到找到可行的TSP解。如下图所示:

上面就是关于使用分枝定界算法求解TSP的基本思路,如果读者有什么不懂的地方,可以参考留言区给出的链接,其中有一份详细介绍上述算法的PPT,相信一定能解决你的问题!

在本文的代码中,求解分配问题采用的是之前推文中提到的匈牙利算法,用system调用Hungary.exe来求解并利用get_circle函数来判断环路。1-tree的求解采用的是kruscal算法,也就是里面的kruscal函数。之后用degree_c函数来检查节点的度。分枝定界搜索过程是采用递归的方法实现的,递归的两个函数分别为branch_and_bound_hungary 和branch_and_bround_one。

代码时刻

又到了看代码的季节了,想要下载文字版的代码请移步全文链接,或者打开下面的网址:https://paste.ubuntu.com/26159997/,或者去留言区获取资源下载链接。

算例展示:

输入:

(第一行整数代表城市数目n,接下来第i(i = 1,2,...,n)行每行n个数分别表示城市i到其他城市的距离,极大的正数使用99999)

5

99999 132 217 164 58

132 99999 290 201 79

217 290 99999 113 303

164 201 113 99999 196

58 79 303 196 99999

输出:

ans = 668(表示最小路径长度)

P.S.输出有很多行,只需要关注最后一行(有last_ans的一行)即可,输出中还有一个文件名,路径方案被保存在这个文件中。使用匈牙利算法定界时还需要一个编译好的匈牙利算法的exe文件。具体的使用说明在留言区的网盘链接中给出。

编辑:贺兴(hexing15@gmail.com)

华中科技大学管理学院本科三年级

代码:贺兴(hexing15@gmail.com)

华中科技大学管理学院本科三年级

汪文宇(wangwenyu0928@gmail.com)

华中科技大学管理学院本科四年级

指导老师:秦时明岳(professor.qin@qq.com)

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-12-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 数据魔术师 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档