韩国81998家酒吧的最短步行路线 – 用178天解决的 TSP 问题
korea81998
韩国81998家酒吧的最短步行路线
首尔的众多酒吧。 点击.
路线的线条图。 点击.
大田，IBS 和 KAIST 的所在地。 点击.
韩国酒吧的地点。 点击.
韩国杂志 Math Dong-A 中的英国酒吧 TSP。点击.
上一个 
下一个
我们解决了访问韩国 81998 家酒吧的旅行商问题 (TSP)。该问题使用 Open Source Routing Machine (OSRM) 创建，构建了一个包含 3,361,795,003 个点到点旅行时间的表格，每个酒吧位置对应该表中的一个时间。我们的计算生成了一条路线，并证明了在使用 OSRM 时间测量时，这是访问所有 81998 个站点的最短可能路线。
这将是一次非常漫长的酒吧之旅。往返的总步行时间为 15,386,177 秒，或 178 天 1 小时 56 分 17 秒。您需要在途中停下来喝很多酒（如果您想在短短几年内完成路线，最好坚持喝水、茶或健怡可乐），因此您不太可能在这样的旅程中计算每一秒。但是，这种精确度表明，这不仅仅是一条好路线，它是 81998 站 TSP 的最佳解决方案。不可能重新排列站点的顺序，甚至节省 OSRM 估计步行时间的一秒钟。
这是已解决的具有可证明最优性的最大规模的 TSP 路线图实例，超过了 2021 年 2 月解决的 荷兰 57,912 站路线。计算于 2024 年 12 月至 2025 年 3 月在 Roskilde University 和 University of Waterloo 进行。有关计算工作的详细信息，请参见 Computation 页面。
交互式地图
下图是 korea81998 路线的交互式地图的屏幕截图。左侧的菜单使您可以选择七个区域之一进行查看。在右上角，您可以选择使用彩色街道地图或不带街道标签的灰度地图。在此菜单的正下方，您可以选择是否显示站点标记、是否显示路线边缘或是否同时显示两者。您可以通过单击图像来查看地图。
路线快照
如果您在查看交互式地图时遇到问题，可以单击下面的图纸以查看路线的高分辨率图像。有关城市区域的特写视图，请参见 Cities 页面。
最优性
报纸、大众期刊、博客和科学新闻稿经常报道，使用当前一代计算机解决甚至微小的 TSP 实例也是不可能的。一个典型的例子是《华盛顿邮报》的以下引言。
"例如，一台笔记本电脑需要 1000 年的时间才能计算出 22 个城市之间最有效的路线。" 量子计算机可能比人工智能更迫在眉睫的威胁，《华盛顿邮报》，2018 年 2 月 5 日。
诸如此类的陈述假设解决 TSP 的唯一方法是逐一检查每个可能的路线。对于我们已解决的任何大型 TSP 实例，这显然行不通。korea81998 案例中的路线数量大约是 2 后面跟 367308 个零。
如此庞大的可能解决方案数量令人恐惧，但这并不意味着我们无法解决这个大型 TSP 示例。我们的方法结合了用于计算非常好的 TSP 解决方案的 LKH 代码和用于应用所谓的 "切割平面方法" 以产生质量保证的 Concorde 代码。您可以在 Computation 页面上看到关于我们如何应用这些工具的简短讨论。
要快速了解切割平面方法，以下是我在 Scientific American 的一篇短文中 描述该过程的方式
"这个想法是遵循 Yogi Berra 的建议“当你走到岔路口时，走它。” 一种称为线性规划的工具使我们能够做到这一点，为连接城市对的道路分配分数，而不是立即决定是否使用道路。 在此模型中，沿着岔路的两个分支发送一半的推销员是完全可以的。" "该过程始于对每个城市的要求，即分配给到达和离开道路的分数之和均为一。 然后，逐步添加更多限制，每个限制都涉及分配给道路的分数之和。 线性规划最终会将我们指向每条道路的最佳决策，从而指向最短的可能路线。"
如果您有几分钟，可以观看在 National Museum of Mathematics 举行的 Optimal Tours 演讲视频，其中详细描述了该方法。或者，继续以韩国为主题，请观看在 KAIST 于 2024 年 3 月举行的 Amazon Deliveries, Pub Walks, and Astro Tours 演讲视频。
P vs NP
在 Lance Fortnow 的文章 Fifty Years of P vs. NP and the Possibility of the Impossible 中，可以找到对 P 和 NP 复杂性类的精彩讨论，包括与 TSP 的联系。
来源：https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/
大局
我们使用旅行商问题的大型示例作为开发和测试通用优化方法的一种手段。世界上的资源有限，数学优化 和运筹学 等应用数学领域的目的是创建工具来帮助我们尽可能高效地利用这些资源。
有关数学建模及其对工业、商业、医学和环境的影响的一般信息，我们向您推荐一些支持数学研究和教育的社团：American Mathematical Society, Mathematical Association of America, Mathematical Optimization Society, INFORMS (运筹学), 和 SIAM (应用数学)。
研究团队
William Cook, Combinatorics and Optimization, University of Waterloo, Canada Daniel Espinoza, Alicanto Labs, Chile Marcos Goycoolea, School of Business, Universidad Adolfo Ibanez, Chile Keld Helsgaun, Computer Science, Roskilde University, Denmark
致谢
计算中产生的大量线性规划模型是使用 IBM CPLEX Optimizer 解决的。非常感谢 IBM 使他们的出色软件免费用于学术研究。
该路线的地图图纸是使用 Leaflet 开放源代码 JavaScript 库创建的，该库适用于移动友好的交互式地图，并使用了由 OpenStreetMap、Carto Basemaps 和 Stadia Maps 构建的地图瓦片。
我们感谢 Dr. Sang-il Oum，Institute for Basic Science (IBS) Discrete Mathematics Group 的首席研究员，感谢他获得了韩国酒吧的位置。这些位置是从韩国国家警察局维护的数据库 下载的。
点对点步行时间的表格是使用 Open Source Routing Machine (OSRM) 创建的。
其他公路旅行
40,426 家日本 Konbini。
英国的 49,687 家酒吧。
49,603 个美国历史古迹。
57,912 座荷兰古迹。
延伸阅读
TSP 简介，包括其历史、应用和解决方案技术。
TSP 切割平面法的详细计算研究。
P vs NP 问题及其后果的简单介绍。
了解如何使用 TSP 通过一条线创建漂亮的图像。
TSP 近似算法理论的最新研究。
这本 1994 年出版的书提供了 TSP 的应用，现在可以免费下载。