ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 18210|回复: 25

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

[复制链接]

TA的精华主题

TA的得分主题

发表于 2008-11-23 14:33 | 显示全部楼层 |阅读模式
近日看了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 编辑 ]

TSP.rar

32.74 KB, 下载次数: 677

TSP-15图.rar

243.48 KB, 下载次数: 613

140Cities.rar

266.66 KB, 下载次数: 607

TA的精华主题

TA的得分主题

 楼主| 发表于 2008-11-23 20:44 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册

请高手解决,期待2天了

请高手解决,期待2天了

TA的精华主题

TA的得分主题

发表于 2008-11-23 23:04 | 显示全部楼层
还是第一次看到有人在现实工作用到 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个可变单元格了。

TA的精华主题

TA的得分主题

 楼主| 发表于 2008-11-24 12:11 | 显示全部楼层

我用规划求解增强工具,

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

TA的精华主题

TA的得分主题

发表于 2008-11-24 19:28 | 显示全部楼层
我发现规划求解增强工具 solver 有个毛病:求解过程不会严格遵从 约束条件, 我碰过几次求解结果是不符合约束条件的

TA的精华主题

TA的得分主题

 楼主| 发表于 2008-11-24 19:44 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助

请问灰袍法师,如果使用excel求解,如何编写处理子回路的约束条件

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

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

万保成TSP算法.rar

13.83 KB, 下载次数: 290

TA的精华主题

TA的得分主题

 楼主| 发表于 2008-11-24 19:48 | 显示全部楼层

回复灰袍法师

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

TA的精华主题

TA的得分主题

 楼主| 发表于 2008-11-24 19:54 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册

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

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

TA的精华主题

TA的得分主题

发表于 2008-11-24 22:21 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
这个是我差不多两年前做的 Excel求解13个城市的TSP问题

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

规划求解 - 最短路径问题 - TSP问题.rar

11 KB, 下载次数: 516

TA的精华主题

TA的得分主题

 楼主| 发表于 2008-11-24 22:49 | 显示全部楼层

谢谢灰袍法师

我下载了,正在学习!!!
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-3-28 22:37 , Processed in 0.045296 second(s), 9 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表