|||
众所周知,旅行商问题的求解难度在于其问题可行解的数量极其庞大,特别是对于对称旅行商问题来说,每两个城市之间彼此可以互达,这样如果设N为问题的规模,即N个城市,则问题初始边集包含有C(N,2)条边,问题的可行解数量约为N!,所以该类问题的求解随着问题规模的扩大,问题求解计算所花费的时间呈指数阶增长。
本人一直努力尝试如何有效地化简问题的初始边集,初始边集中变得数量的减少,就意味着问题求解难度的降低。本次发布的化简工具中一个方法是三年实现的,另外一个方法是最近正在进行的实验。第一种方法,平均可以将问题初始边集的数量缩减到问题规模的2倍,大大次缩减了问题的求解难度,同时为基于边集的优化算法(比如链式Lin-kernighan算法)提供了更为高效计算的基础。第二种方法,目标预期达到将问题初始边集化简到为问题规模的1.8倍,欢迎同行共同进行试算,并给出更好的意见和建议。
下载连接:旅行商问题初始边集化简工具
随计算工具包中含有以坐标方式给出的二维旅行商问题的TSPLIB95中的数据集。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-3-29 23:16
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社