学习共享：高级蚁群算法求解1000以上城市的TSP问题（旅行商），附大量TSPLIB数据！

simba4015 · 发表于 2013-11-19 22:53

最近在研究这个，法师牛逼啊，膜拜！{:soso_e196:}

香城泉都 · 发表于 2014-3-16 18:28

法师的帖子的内容值得收藏，小弟初学算法，有很多问题不懂，最近遇到一个实际问题，可将该简化为多旅行商问题，待访问的城市之间并不一定都能直接相连（有的城市之间有连接，有的城市之间不能连接），而且要求最后一个城市为指定的几个城市之一，每只蚂蚁的路径不需要成为封闭的环，对于这样的多旅行商问题，请各位大师指导？

灰袍法师 · 发表于 2014-3-18 23:33

香城泉都发表于 2014-3-16 18:28
法师的帖子的内容值得收藏，小弟初学算法，有很多问题不懂，最近遇到一个实际问题，可将该简化为多旅行商问 ...

不相连的城市，距离矩阵给一个很大的数值即可，或者在选择城市的时候直接忽略。

不要求成为一个环，那就不是TSP问题了，你也许应该用A星寻路算法。

当然，也可以转化为TSP问题，做法是：增加一个新的城市变成N+1的问题，该城市离所有其他城市的距离都是零，然后求TSP闭合回路，其结果去掉新增城市，剩下就是不闭合的N个城市的路径。

自适应 · 发表于 2014-3-25 15:02

楼主，我碰到一个问题请教你一下，我的问题处理转化后变为一个组合优化排序问题，两元素摆在一块中间产生一个连接值（作为距离看待）， AB 与 BA 的连接值是不一样的，连接值越小类似距离越小，现在要求连接值之和最小，这种情况能作为TSP用蚁群算法求解么，点不多，一共19个点，确定起点和终点的，中间17点排序

自适应 · 发表于 2014-3-26 18:19

17个点的SOP问题有3.557*10^14次种排列，遍历不现实吧？

自适应 · 发表于 2014-3-26 19:11

本帖最后由自适应于 2014-3-26 19:13 编辑

今天看了看楼主推荐的书《Ant Colony Optimization》，里面在第五章 NP难问题的蚁群优化的路由问题中提到顺序排列问题（SOP）与这个有点类似，我这个是起点为节点1 终点为节点19，中间的节点需要顺序排列，每两个节点之间会产生一个连接值Z(节点i，节点j)，其中节点i为排在节点j前面，一个顺序确定之后对应的∑Z也就确定了，∑Z最小的顺序即为最优解，下面表格中数据就是各节点的连接值，行标节点为节点i，列标节点为节点j。我把下述表格作为距离矩阵尝试作为一个TSP问题处理，（会点编程，但是自己不太懂TSP求解算法，所以不会写TSP问题程序）借助1stOpt软件能得到最优解，但是得到的结果是环路，也就是不知道哪一个是排在第一位的。望楼主多多指教下

连接值	节点1	节点2	节点3	节点4	节点5	节点6	节点7	节点8	节点9	节点10	节点11	节点12	节点13	节点14	节点15	节点16	节点17	节点18	节点19
节点1	0	543	14484	7407	7560	11443	13531	8538	10023	9133	13932	13824	8210	6458	9555	14006	15153	17616	9864
节点2	7630	0	1493	7630	14331	9562	12214	12319	10362	13366	6753	7607	9501	9781	7980	14159	6908	10257	14641
节点3	0	7664	0	0	8211	4810	11510	7907	5080	8984	8531	10055	3849	3097	3932	19395	9670	13835	10033
节点4	8102	7572	13999	0	191	12210	14222	10905	9976	6530	14627	15227	8395	11199	10374	13175	16290	18091	7515
节点5	5391	11847	10438	5391	0	1019	12415	10888	6935	10461	7758	11516	8460	6938	6891	19184	8383	11822	12062
节点6	10286	13122	11445	10286	13005	0	1224	6391	5848	17776	16135	10431	13829	8543	13782	14147	14920	16979	7453
节点7	10553	9779	13888	10553	11828	12747	0	2682	5621	17575	18586	12156	12838	7456	14269	14240	18023	19316	8114
节点8	5007	9751	10248	5007	9916	7291	6503	0	127	13991	13538	11216	8856	4784	8815	17640	12963	15702	7052
节点9	8702	9312	12631	8702	7223	9832	17676	14057	0	1120	9657	15601	8503	11395	9568	12327	11892	11885	11545
节点10	10316	16092	7041	10316	16639	8032	17354	18081	15396	0	2079	10763	10099	13413	6864	13575	5076	5941	20031
节点11	10095	13767	6914	10095	15386	10569	10579	11998	11107	16567	0	1690	11656	9508	10103	13172	10227	10392	13968
节点12	6063	12605	7158	6063	13212	7155	13897	13318	11143	10811	5268	0	4942	9160	5749	15918	6815	8932	16096
节点13	3110	6440	10021	3110	11309	6930	8682	6145	4848	12094	11641	9487	0	91	6910	17601	11168	13761	8987
节点14	5522	9244	10167	5522	10199	7898	14430	11757	9512	9312	7241	9993	7149	0	2304	15855	10984	10921	13787
节点15	11809	9861	12236	11809	11140	11857	10953	8364	10907	11605	13178	11200	10216	10474	0	8172	14631	14194	10548
节点16	9352	12816	9463	9352	13649	8452	15438	14389	11546	11494	7849	11705	8327	10919	10040	0	4980	9637	14425
节点17	6530	10088	12575	6530	9925	9180	12096	10425	8184	9218	12107	13661	8361	6025	8994	16977	0	9135	9061
节点18	2359	6889	9922	2359	6694	5607	12149	9036	5719	8345	10484	12226	4698	5384	5995	17458	11093	0	7708
节点19	0	7664	7655	0	8211	4810	11510	7907	5080	8984	8531	10055	3849	3097	3932	19395	9670	13835	0

homehomehome · 发表于 2014-3-28 23:31

高级货，收藏了先，谢谢

灰袍法师 · 发表于 2014-4-3 03:04

自适应发表于 2014-3-26 19:11
今天看了看楼主推荐的书《Ant Colony Optimization》，里面在第五章 NP难问题的蚁 ...

实际上，你的问题跟 SOP 问题还是有点不同，要简单一点点。

SOP问题可能存在 X节点必须在Y节点之前的限制，你的问题没有这个限制。

不过，SOP问题本身跟TSP问题很不一样，蚁群算法的发明人Marco Dorigo 有另一篇论文专门说SOP问题，见附件

AN ANT COLONY SYSTEM HYBRIDIZED WITH A NEW LOCAL SEARCH FOR THE SEQUENTIAL ORDERING PROBLEM
简称 HAS-SOP 算法

gambardella00ant.rar (147.85 KB, 下载次数: 46)

梦语星魂 · 发表于 2014-5-9 11:34

非常不错的资源赞一下

zaqwsx135 · 发表于 2014-5-11 14:49

支持下，想问下eil51.tsp城市坐标数据怎么看啊？

		自动登录	找回密码
密码			免费注册

[原创] 学习共享：高级蚁群算法求解1000以上城市的TSP问题（旅行商），附大量TSPLIB数据！

点评