Shortest walking tour to 81,998 bars in Korea – TSP solved in 178 days
a year ago
- #Optimization
- #Traveling Salesman Problem
- #South Korea
- 解决了韩国境内包含81,998个站点的最大规模旅行商问题（TSP）路网实例
- 最优路线的总步行时间为15,386,177秒（178天1小时56分17秒）
- 使用开源路由引擎OSRM计算了3,361,795,003个点对点行程时间
- 结合LKH和Concorde算法求解最优方案，并应用割平面法
- 打破了2021年2月荷兰57,912个站点路网的原有纪录
- 计算工作于2024年12月至2025年3月在罗斯基勒大学与滑铁卢大学完成
- 可通过交互式地图查看路线，支持显示站点标记与路径连线
- 通过先进优化方法澄清了关于大规模TSP求解的常见误解
- 鸣谢IBM CPLEX优化器、OpenStreetMap及韩国警察厅的技术支持