使用规划求解，求解TSP问题讨论--改进了算法，轻松求取了140城市的TSP

johncabin

近日看了Chrisfang的关于使用规划求解计算旅行商问题的视频，地址：http://www.excelhome.net/post/483.htm。
这个问题在实际工作中确实经常用到，我深受启发，马上照作了一个，见附件。但发现在物流中，单车配送5个客户时初始方案就有3个自闭合回路，然后再手工打开这些回路就非常麻烦，各位高手是否可以想个办法改善求解方案。

附件是我改进的TSP的excel实现方法，在Excel中应用规划求解增强工具可以方便求出15个城市的TSP问题，求解结果和过程见附件，用到了万保成的约束条件，和9楼的灰袍法师的约束条件，这样确实计算时间大大降低了。我不知道这样是否可以，但结果好像可以接受。13个结点的在excel自带的规划求解宏里测试通过，15个结点的使用增强的规划求解工具里测试通过（用时都不超过10秒钟）。
例外，我不太懂VBA，懂VBA的同志们麻烦帮我编一个VBA程序，使得城市间的距离矩阵可以改变为我使用"点与点"的距离表，使用"点与点"的距离表可以方便编写excel公式。我的"点与点"的距离表都是根据距离矩阵手工调整的。
还有，附件中附有20个点的例子，大家可以试一试。
规划求解增强工具可以到http://club.excelhome.net/thread-371458-1-1.html下载。

[ 本帖最后由 johncabin 于 2009-8-4 00:45 编辑 ]

johncabin

请高手解决，期待2天了

灰袍法师

还是第一次看到有人在现实工作用到 TSP 呢

如楼主所言，Chrisfang的求解模型还不完整，不能很好地处理子回路的问题

专门的运筹学软件Lingo有示范程序处理TSP问题的子回路，我也推荐用这个软件去做这种事情

详细的算法和数学证明在一本书有，下载地址是
http://www.sciencenet.cn/bbs/showpost.aspx?id=16424
或者你可以搜索 万保成 LINGO8.0 for windows软件及应用

实际上，同样的算法用Excel实现也是可以的

不过相当麻烦而且很不实用，由于Excel 200可变单元格的限制，最多只能求解13个城市的问题 13*13=169, 另外处理子回路需要额外的13单元格，所以一共是 182个可变单元格了。

johncabin

我用规划求解增强工具，可变单元格的限制可以到2000个，基本可以解决实际问题，也就是单车配送40个客户(40×40＝1600)都可以解，但就是要改进Chrisfang的算法。

灰袍法师

我发现规划求解增强工具 solver 有个毛病：求解过程不会严格遵从 约束条件， 我碰过几次求解结果是不符合约束条件的

johncabin

请问灰袍法师，如果使用excel求解，如何编写处理子回路的约束条件，我看了（万保成）LINGO8.0 for windows软件及应用的算法，想了一个晚上还是没有想出来。附万保成TSP算法。

[ 本帖最后由 johncabin 于 2008-11-24 19:52 编辑 ]

johncabin

灰袍法师，你将你在5楼遇到的情况发给我，我用这个增强工具好像还比较顺手。

johncabin

能攻克这个NP难问题是为世界人民作贡献。

灰袍法师

这个是我差不多两年前做的 Excel求解13个城市的TSP问题

用的是万保成那本书的算法，另加上我自己实际使用发现可以大大提高速度的 第三个约束矩阵

johncabin

我下载了，正在学习！！！