matlab
tsp问题代码Traveling
Santa
2018-Prime
Paths(Kaggle竞赛)
这是我为2018年旅行圣诞老人创建的代码,这是我第一次参加Kaggle比赛,我获得了210/1874的排名(排名前12%)。
这是一个高度参与的竞赛,吸引了Bill
Cook和Keld
Helsgaun等顶尖研究人员参加,他们最终赢得了比赛。
这个问题与带有197769个城市的TSP非常相似。
竞争图如下所示,红色节点代表第一个/最后一个节点。
(从下载city.csv文件。)
但是,有一个扭曲:提交是根据您提交的路径的欧几里得距离进行评分的,但前提是每10个步骤的长度要增加10%,除非来自主要的CityId。
我的方法是首先找到不考虑质数惩罚的最佳汉密尔顿周期,然后从该初始解中进行优化。
第1步-LKH
我使用开源代码找到了解决此问题的最佳汉密尔顿周期。
在微调其参数后,我让它运行2天,偶尔会中断。
概括地说,我的方法是:
设置相当长的初始时间以在第一次运行中使用梯度上升来计算节点惩罚(万秒)
在第一次运行中,我使用8步顺序移动进行本地搜索,并逐渐减小该数字,直到达到3步
2025-04-28 18:47:27
602KB
系统开源
1