组合优化与智能计算分享 http://blog.sciencenet.cn/u/fswdong 清淡的生活,枯燥的钻研,幸福的泪水,拼搏的超脱

博文

[下载,原创]旅行商问题初始边集化简工具

已有 4242 次阅读 2009-8-11 15:34 |个人分类:试算工具|系统分类:科研笔记| 化简, 旅行商问题, TSP, 初始边集

    众所周知,旅行商问题的求解难度在于其问题可行解的数量极其庞大,特别是对于对称旅行商问题来说,每两个城市之间彼此可以互达,这样如果设N为问题的规模,即N个城市,则问题初始边集包含有C(N,2)条边,问题的可行解数量约为N!,所以该类问题的求解随着问题规模的扩大,问题求解计算所花费的时间呈指数阶增长。

    本人一直努力尝试如何有效地化简问题的初始边集,初始边集中变得数量的减少,就意味着问题求解难度的降低。本次发布的化简工具中一个方法是三年实现的,另外一个方法是最近正在进行的实验。第一种方法,平均可以将问题初始边集的数量缩减到问题规模的2倍,大大次缩减了问题的求解难度,同时为基于边集的优化算法(比如链式Lin-kernighan算法)提供了更为高效计算的基础。第二种方法,目标预期达到将问题初始边集化简到为问题规模的1.8倍,欢迎同行共同进行试算,并给出更好的意见和建议。

下载连接:旅行商问题初始边集化简工具

随计算工具包中含有以坐标方式给出的二维旅行商问题的TSPLIB95中的数据集。



https://blog.sciencenet.cn/blog-253220-248751.html

上一篇:[下载,原创]小规模旅行商问题蒙特卡罗精确求解器
下一篇:[原创]求解旅行商问题的自组织映射算法源程序
收藏 IP: .*| 热度|

0

发表评论 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 23:16

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部