TSP Solver

用于求解旅行商问题的路径优化软件

在免费在线演示版中试用 1,000 个随机点生成随机 AIR 点并比较各算法。随机生成的 AIR 点不受演示版 100 点上限的限制。打开“数据”→“随机生成”,即可选择点的数量。 在线试用算法

什么是 TSP Solver?

TSP Solver 是一款用于优化旅行商问题(TSP)路径的软件。旅行商问题是组合优化中最著名的问题之一,目标是寻找一条尽可能短的实用路线,恰好访问每个给定点(城市)一次,最后返回起点。软件支持二维和三维坐标(x、y、z),并提供交互式 3D 可视化。它适用于物流与路线规划,也可用于无人机飞行路径规划、机器人技术,以及工业应用,例如激光雕刻、印刷电路板(PCB)钻孔或3D 打印和 CNC 机床。在这些应用中,路径优化可以显著缩短生产时间。

TSP Solver 3.05采用重新设计的界面和更新的 Robopol Refined 核心,支持 AIR 2D/3D、道路路线以及通过 LKH 规划的多车辆路线。Fast、Balanced 和 Heavy配置用于控制搜索力度。

Balanced是兼顾速度与质量的默认配置。在 30 个修改后的四面体实例中,它在 27 个实例上找到了比 LKH(DELAUNAY)更短的路线,在另外 3 个实例上获得了相同的路线长度。它达到最优值的次数为 24 次,而 LKH 为 3 次。Heavy会探索更多候选方案,而Fast优先缩短计算时间。结果取决于数据和设置。

您可以使用随机生成的点,在TSP Solver 在线版中体验算法的性能。这项功能同样适用于免费演示版。

在线应用以及 Windows 和 Linux 版本均提供英语、德语、西班牙语和简体中文界面、提示信息及用户手册。切换语言时,正在编辑的路线会保留。

Balanced 在 30 个实例中的 27 个上获得更短路线

Balanced是兼顾速度与质量的默认配置。在 30 个修改后的四面体实例中,它在 27 个实例上找到了比 LKH(DELAUNAY)更短的路线,在另外 3 个实例上获得了相同的路线长度。它达到最优值的次数为 24 次,而 LKH 为 3 次。Heavy会探索更多候选方案,而Fast优先缩短计算时间。结果取决于数据和设置。

TSP Solver 3.05 新界面与计算完成的路线。

TSP Solver 3.05 新界面与计算完成的路线。

路径优化

在选定的点之间寻找尽可能短的优化路线。Fast、Balanced 和 Heavy 配置可用于权衡计算速度与搜索深度。

支持三维点

使用三维坐标(x、y、z)进行空间优化,适用于无人机飞行路径规划、优化机械臂的运动、在多层仓库中导航,以及优化3D 打印和 CNC 机床的运动路径。交互式 3D 可视化支持旋转和缩放计算得到的路线。

TSP Art

用一条穿过数千个点的连续线条创作艺术作品。

高级算法

Balanced是兼顾速度与质量的默认配置。在 30 个修改后的四面体实例中,它在 27 个实例上找到了比 LKH(DELAUNAY)更短的路线,在另外 3 个实例上获得了相同的路线长度。它达到最优值的次数为 24 次,而 LKH 为 3 次。Heavy会探索更多候选方案,而Fast优先缩短计算时间。结果取决于数据和设置。

导入与导出

从文本文件导入点、导出路线、保存项目,并将结果生成图像。

道路距离与Google 地图

基于实际道路网络计算优化路线。您可以直接在 Google 地图中打开结果,并发送到手机进行导航。

多车辆 mTSP

使用 LKH 算法将路线分配给多辆车辆,主要支持 AIR 2D 和道路距离。对于较大的 AIR 3D 任务,建议先使用较小的数据集进行验证。您可以设置车辆数量、车场、优化目标(MINSUM/MINMAX)以及每辆车的停靠点数量限制。Professional 许可证提供此功能。

针对移动设备优化

应用采用响应式设计,方便在平板电脑和智能手机上使用。您也可以通过tspsolver.robopol.sk直接使用在线版,无需安装。

软件截图

TSP Solver 3.05——Windows 版 John Wick TSP Art

Windows 版 TSP Art——John Wick,100,000 个点

TSP Solver 主窗口

TSP Solver 主窗口

TSP Solver——捷克各城市之间的路线可视化

捷克各城市之间的优化路线可视化

AIR 3D——龙模型,12,000 个点,Refined Balanced

AIR 3D——龙模型,12,000 个点,Refined Balanced

经过巴黎的优化道路路线

经过巴黎的优化道路路线

经过芬兰的优化道路路线

经过芬兰的优化道路路线

道路地址与 Google 地图导航

道路地址与 Google 地图导航

TSP Solver——多车辆 3D mTSP

多车辆 mTSP——三维路线(x、y、z)

TSP Solver——多车辆道路 mTSP

多车辆 mTSP——道路距离

使用流程

1

输入点

您可以在画布上单击以手动输入点(城市),从文件导入点,或输入地址进行地理编码以规划道路路线。

2

选择算法

根据问题规模和所需精度选择算法及参数。

3

计算

软件使用选定的算法计算优化路线。

4

结果

查看结果,包括路线可视化和统计信息。

技术详情

使用的算法

TSP Solver Desktop 3.05 提供以下算法。

  • LKH + Robopol Refined——适用于 AIR 2D/3D TSP 的组合模式。它以高质量的 LKH 路线为起点,在 Refined 优化过程中有选择地采用 LKH 的进一步改进。
  • Robopol Refined——更新的核心提供 Fast、Balanced 和 Heavy 配置。在下方基准测试中,Balanced 在 30 个实例中的 27 个上找到了比独立 LKH(DELAUNAY)更短的路线。
  • LKH-3.0.10——用于独立的 AIR 路径优化,也是道路路线和 mTSP 的计算方法。

Balanced是兼顾速度与质量的默认配置。在 30 个修改后的四面体实例中,它在 27 个实例上找到了比 LKH(DELAUNAY)更短的路线,在另外 3 个实例上获得了相同的路线长度。它达到最优值的次数为 24 次,而 LKH 为 3 次。Heavy会探索更多候选方案,而Fast优先缩短计算时间。结果取决于数据和设置。

性能

Balanced是兼顾速度与质量的默认配置。在 30 个修改后的四面体实例中,它在 27 个实例上找到了比 LKH(DELAUNAY)更短的路线,在另外 3 个实例上获得了相同的路线长度。它达到最优值的次数为 24 次,而 LKH 为 3 次。Heavy会探索更多候选方案,而Fast优先缩短计算时间。结果取决于数据和设置。

在 8 核 CPU 上测试

AMD Ryzen 7 5700X3D

8 个物理核心/ 16 个硬件线程

3.05 基准测试——汇总与设置

TSP Solver 3.05 基准测试包含30 个修改后的四面体实例 T′n,m,规模从 157 到 4,396 个点,共得到 120 个结果。测试于 2026 年 9 月 7 日进行。各方法使用相同的点,最优值来自该实例族中已通过数学证明的最优路线。

Balanced 在 30 个实例中的 27 个上获得了比 LKH(DELAUNAY)更短的路线,在另外 3 个实例上获得了相同的路线长度。Balanced 达到最优值 24 次,Heavy 为 27 次,混合方法为 28 次,独立 LKH 为 3 次。这些结果适用于该实例族及所列设置。

偏差(%)=(路线长度 − 最优值)/ 最优值 × 100。路线长度为各段欧氏距离之和,包含返回起点的路段。评估时,各条边的长度保持原有精度,仅对表格中显示的数值进行舍入。

算法 / 配置达到最优值的次数平均偏差最大偏差平均运行时间
Robopol Refined — Balanced24/300.00002968 %0.00083493 %2.060 s
Robopol Refined — Heavy27/302.160785E-9 %0.00000004 %4.327 s
LKH + Robopol Refined — Balanced28/301.245357E-9 %0.00000002 %5.696 s
LKH-3.0.10 (DELAUNAY)3/300.11724559 %0.46287393 %2.399 s

LKH (DELAUNAY):RUNS=10、MAX_TRIALS=1、MAX_CANDIDATES=5、MOVE_TYPE=5、PATCHING_C=1、PATCHING_A=1、INITIAL_PERIOD=100。求解器采用 EXACT_2D 度量。Refined 使用现有的 Balanced 和 Heavy 配置,混合方法使用 Balanced。

运行时间包含调用本地应用和计算的耗时,每个实例与配置组合记录一次成功运行。各方法的时间预算不同。混合方法有两次初始化失败后进行了重试,平均时间不包含失败尝试的耗时。

全部 30 个实例的比较
实例点数已证明的最优值Balanced 偏差Heavy 偏差混合方法偏差LKH(DELAUNAY)偏差
Tprime_40_22157192.2128826610 %0 %0 %0 %
Tprime_40_30172194.8478375000 %0 %0 %0 %
Tprime_40_40187192.9627202280 %0 %0 %0.01764535 %
Tprime_40_60223195.0279849940 %0 %0 %0.40535398 %
Tprime_60_30244317.7349128900 %0 %0 %0 %
Tprime_40_80256194.5790792680 %0 %0 %0.41976394 %
Tprime_60_45277320.0106589550 %0 %0 %0.08743262 %
Tprime_60_60307318.0085498000 %0 %0 %0.09902683 %
Tprime_60_90373320.1964660000 %0 %0 %0.44791308 %
Tprime_100_50424569.4680156300 %0 %0 %0.00013950 %
Tprime_60_120436319.7193449270 %0 %0 %0.46287393 %
Tprime_100_75487571.8078312760 %0 %0 %0.02681372 %
Tprime_100_100547569.7488821060 %0 %0 %0.00996326 %
Tprime_100_150673571.9968221090 %0 %0 %0.32110210 %
Tprime_180_907841073.8860050020 %0 %0 %0.00009610 %
Tprime_100_200796571.5058876760 %0 %0 %0.00077966 %
Tprime_180_1359071076.2561503220 %0 %0 %0.16263537 %
Tprime_180_18010271074.1706995840 %0 %0 %0.13688396 %
Tprime_180_27012731076.4468342450 %0 %0 %0.19100221 %
Tprime_300_15013241830.8689210900.00000106 %0 %0 %0.00009747 %
Tprime_180_36015161075.9494208580 %0 %0 %0.19676975 %
Tprime_300_22515371833.2515532630 %0 %0 %0.07704029 %
Tprime_300_30017471831.1553024850 %0 %0 %0.06825336 %
Tprime_300_45021731833.4429849040 %0 %0 %0.11744864 %
Tprime_500_25022243092.6680152350.00000264 %0 %0 %0.00003802 %
Tprime_500_37525873095.0574317930 %0 %0 %0.00114559 %
Tprime_300_60025961832.9429222790.00000002 %0.00000004 %0.00000002 %0.12092710 %
Tprime_500_50029473092.9553460790.00005165 %0 %0 %0.00144848 %
Tprime_500_75036733095.2492847630.00083493 %0.00000001 %0 %0.07134219 %
Tprime_500_100043963094.7477884190.00000002 %0.00000002 %0.00000002 %0.07343120 %
全部 120 个结果及运行时间
实例点数算法 / 配置最优值路线长度偏差是否达到最优值运行时间
Tprime_40_22157Robopol Refined — Balanced192.212882661192.2128826610 %是0.909 s
Tprime_40_22157Robopol Refined — Heavy192.212882661192.2128826610 %是1.729 s
Tprime_40_22157LKH + Robopol Refined — Balanced192.212882661192.2128826610 %是1.096 s
Tprime_40_22157LKH-3.0.10 (DELAUNAY)192.212882661192.2128826610 %是0.224 s
Tprime_40_30172Robopol Refined — Balanced194.847837500194.8478375000 %是0.926 s
Tprime_40_30172Robopol Refined — Heavy194.847837500194.8478375000 %是1.656 s
Tprime_40_30172LKH + Robopol Refined — Balanced194.847837500194.8478375000 %是1.114 s
Tprime_40_30172LKH-3.0.10 (DELAUNAY)194.847837500194.8478375000 %是0.172 s
Tprime_40_40187Robopol Refined — Balanced192.962720228192.9627202280 %是0.995 s
Tprime_40_40187Robopol Refined — Heavy192.962720228192.9627202280 %是2.226 s
Tprime_40_40187LKH + Robopol Refined — Balanced192.962720228192.9627202280 %是1.364 s
Tprime_40_40187LKH-3.0.10 (DELAUNAY)192.962720228192.9967691730.01764535 %否0.214 s
Tprime_40_60223Robopol Refined — Balanced195.027984994195.0279849940 %是0.935 s
Tprime_40_60223Robopol Refined — Heavy195.027984994195.0279849940 %是1.934 s
Tprime_40_60223LKH + Robopol Refined — Balanced195.027984994195.0279849940 %是1.232 s
Tprime_40_60223LKH-3.0.10 (DELAUNAY)195.027984994195.8185386880.40535398 %否0.303 s
Tprime_60_30244Robopol Refined — Balanced317.734912890317.7349128900 %是0.947 s
Tprime_60_30244Robopol Refined — Heavy317.734912890317.7349128900 %是1.905 s
Tprime_60_30244LKH + Robopol Refined — Balanced317.734912890317.7349128900 %是1.263 s
Tprime_60_30244LKH-3.0.10 (DELAUNAY)317.734912890317.7349128900 %是0.410 s
Tprime_40_80256Robopol Refined — Balanced194.579079268194.5790792680 %是1.184 s
Tprime_40_80256Robopol Refined — Heavy194.579079268194.5790792680 %是2.380 s
Tprime_40_80256LKH + Robopol Refined — Balanced194.579079268194.5790792680 %是1.327 s
Tprime_40_80256LKH-3.0.10 (DELAUNAY)194.579079268195.3958520770.41976394 %否0.326 s
Tprime_60_45277Robopol Refined — Balanced320.010658955320.0106589550 %是1.013 s
Tprime_60_45277Robopol Refined — Heavy320.010658955320.0106589550 %是2.027 s
Tprime_60_45277LKH + Robopol Refined — Balanced320.010658955320.0106589550 %是1.187 s
Tprime_60_45277LKH-3.0.10 (DELAUNAY)320.010658955320.2904526550.08743262 %否0.194 s
Tprime_60_60307Robopol Refined — Balanced318.008549800318.0085498000 %是1.058 s
Tprime_60_60307Robopol Refined — Heavy318.008549800318.0085498000 %是2.182 s
Tprime_60_60307LKH + Robopol Refined — Balanced318.008549800318.0085498000 %是1.229 s
Tprime_60_60307LKH-3.0.10 (DELAUNAY)318.008549800318.3234635840.09902683 %否0.226 s
Tprime_60_90373Robopol Refined — Balanced320.196466000320.1964660000 %是1.155 s
Tprime_60_90373Robopol Refined — Heavy320.196466000320.1964660000 %是2.398 s
Tprime_60_90373LKH + Robopol Refined — Balanced320.196466000320.1964660000 %是1.367 s
Tprime_60_90373LKH-3.0.10 (DELAUNAY)320.196466000321.6306678520.44791308 %否0.550 s
Tprime_100_50424Robopol Refined — Balanced569.468015630569.4680156300 %是1.142 s
Tprime_100_50424Robopol Refined — Heavy569.468015630569.4680156300 %是2.295 s
Tprime_100_50424LKH + Robopol Refined — Balanced569.468015630569.4680156300 %是1.443 s
Tprime_100_50424LKH-3.0.10 (DELAUNAY)569.468015630569.4688100150.00013950 %否1.120 s
Tprime_60_120436Robopol Refined — Balanced319.719344927319.7193449270 %是1.268 s
Tprime_60_120436Robopol Refined — Heavy319.719344927319.7193449270 %是2.682 s
Tprime_60_120436LKH + Robopol Refined — Balanced319.719344927319.7193449270 %是1.699 s
Tprime_60_120436LKH-3.0.10 (DELAUNAY)319.719344927321.1992424180.46287393 %否1.073 s
Tprime_100_75487Robopol Refined — Balanced571.807831276571.8078312760 %是1.211 s
Tprime_100_75487Robopol Refined — Heavy571.807831276571.8078312760 %是2.294 s
Tprime_100_75487LKH + Robopol Refined — Balanced571.807831276571.8078312760 %是1.458 s
Tprime_100_75487LKH-3.0.10 (DELAUNAY)571.807831276571.9611542140.02681372 %否0.193 s
Tprime_100_100547Robopol Refined — Balanced569.748882106569.7488821060 %是1.325 s
Tprime_100_100547Robopol Refined — Heavy569.748882106569.7488821060 %是2.537 s
Tprime_100_100547LKH + Robopol Refined — Balanced569.748882106569.7488821060 %是1.557 s
Tprime_100_100547LKH-3.0.10 (DELAUNAY)569.748882106569.8056476540.00996326 %否0.188 s
Tprime_100_150673Robopol Refined — Balanced571.996822109571.9968221090 %是1.459 s
Tprime_100_150673Robopol Refined — Heavy571.996822109571.9968221090 %是2.710 s
Tprime_100_150673LKH + Robopol Refined — Balanced571.996822109571.9968221090 %是1.691 s
Tprime_100_150673LKH-3.0.10 (DELAUNAY)571.996822109573.8335159070.32110210 %否0.222 s
Tprime_180_90784Robopol Refined — Balanced1073.8860050021073.8860050020 %是1.498 s
Tprime_180_90784Robopol Refined — Heavy1073.8860050021073.8860050020 %是3.303 s
Tprime_180_90784LKH + Robopol Refined — Balanced1073.8860050021073.8860050020 %是2.426 s
Tprime_180_90784LKH-3.0.10 (DELAUNAY)1073.8860050021073.8870369570.00009610 %否1.526 s
Tprime_100_200796Robopol Refined — Balanced571.505887676571.5058876760 %是1.692 s
Tprime_100_200796Robopol Refined — Heavy571.505887676571.5058876760 %是3.781 s
Tprime_100_200796LKH + Robopol Refined — Balanced571.505887676571.5058876760 %是3.620 s
Tprime_100_200796LKH-3.0.10 (DELAUNAY)571.505887676571.5103434900.00077966 %否2.003 s
Tprime_180_135907Robopol Refined — Balanced1076.2561503221076.2561503220 %是1.301 s
Tprime_180_135907Robopol Refined — Heavy1076.2561503221076.2561503220 %是2.676 s
Tprime_180_135907LKH + Robopol Refined — Balanced1076.2561503221076.2561503220 %是1.845 s
Tprime_180_135907LKH-3.0.10 (DELAUNAY)1076.2561503221078.0065235330.16263537 %否0.208 s
Tprime_180_1801027Robopol Refined — Balanced1074.1706995841074.1706995840 %是1.753 s
Tprime_180_1801027Robopol Refined — Heavy1074.1706995841074.1706995840 %是3.276 s
Tprime_180_1801027LKH + Robopol Refined — Balanced1074.1706995841074.1706995840 %是1.944 s
Tprime_180_1801027LKH-3.0.10 (DELAUNAY)1074.1706995841075.6410669260.13688396 %否0.253 s
Tprime_180_2701273Robopol Refined — Balanced1076.4468342451076.4468342450 %是2.217 s
Tprime_180_2701273Robopol Refined — Heavy1076.4468342451076.4468342450 %是4.296 s
Tprime_180_2701273LKH + Robopol Refined — Balanced1076.4468342451076.4468342450 %是7.379 s
Tprime_180_2701273LKH-3.0.10 (DELAUNAY)1076.4468342451078.5028714820.19100221 %否0.299 s
Tprime_300_1501324Robopol Refined — Balanced1830.8689210901830.8689405220.00000106 %否2.203 s
Tprime_300_1501324Robopol Refined — Heavy1830.8689210901830.8689210900 %是5.207 s
Tprime_300_1501324LKH + Robopol Refined — Balanced1830.8689210901830.8689210900 %是3.286 s
Tprime_300_1501324LKH-3.0.10 (DELAUNAY)1830.8689210901830.8707056740.00009747 %否0.826 s
Tprime_180_3601516Robopol Refined — Balanced1075.9494208581075.9494208580 %是2.224 s
Tprime_180_3601516Robopol Refined — Heavy1075.9494208581075.9494208580 %是4.691 s
Tprime_180_3601516LKH + Robopol Refined — Balanced1075.9494208581075.9494208580 %是3.634 s
Tprime_180_3601516LKH-3.0.10 (DELAUNAY)1075.9494208581078.0665638170.19676975 %否3.967 s
Tprime_300_2251537Robopol Refined — Balanced1833.2515532631833.2515532630 %是1.819 s
Tprime_300_2251537Robopol Refined — Heavy1833.2515532631833.2515532630 %是3.635 s
Tprime_300_2251537LKH + Robopol Refined — Balanced1833.2515532631833.2515532630 %是2.767 s
Tprime_300_2251537LKH-3.0.10 (DELAUNAY)1833.2515532631834.6638955230.07704029 %否0.285 s
Tprime_300_3001747Robopol Refined — Balanced1831.1553024851831.1553024850 %是1.798 s
Tprime_300_3001747Robopol Refined — Heavy1831.1553024851831.1553024850 %是5.210 s
Tprime_300_3001747LKH + Robopol Refined — Balanced1831.1553024851831.1553024850 %是2.940 s
Tprime_300_3001747LKH-3.0.10 (DELAUNAY)1831.1553024851832.4051275750.06825336 %否0.367 s
Tprime_300_4502173Robopol Refined — Balanced1833.4429849041833.4429849040 %是2.643 s
Tprime_300_4502173Robopol Refined — Heavy1833.4429849041833.4429849040 %是5.356 s
Tprime_300_4502173LKH + Robopol Refined — Balanced1833.4429849041833.4429849040 %是10.208 s
Tprime_300_4502173LKH-3.0.10 (DELAUNAY)1833.4429849041835.5963388450.11744864 %否4.273 s
Tprime_500_2502224Robopol Refined — Balanced3092.6680152353092.6680967580.00000264 %否2.643 s
Tprime_500_2502224Robopol Refined — Heavy3092.6680152353092.6680152350 %是5.014 s
Tprime_500_2502224LKH + Robopol Refined — Balanced3092.6680152353092.6680152350 %是5.387 s
Tprime_500_2502224LKH-3.0.10 (DELAUNAY)3092.6680152353092.6691911970.00003802 %否1.274 s
Tprime_500_3752587Robopol Refined — Balanced3095.0574317933095.0574317930 %是2.388 s
Tprime_500_3752587Robopol Refined — Heavy3095.0574317933095.0574317930 %是4.948 s
Tprime_500_3752587LKH + Robopol Refined — Balanced3095.0574317933095.0574317930 %是4.079 s
Tprime_500_3752587LKH-3.0.10 (DELAUNAY)3095.0574317933095.0928883460.00114559 %否0.387 s
Tprime_300_6002596Robopol Refined — Balanced1832.9429222791832.9429226180.00000002 %否6.203 s
Tprime_300_6002596Robopol Refined — Heavy1832.9429222791832.9429229580.00000004 %否11.963 s
Tprime_300_6002596LKH + Robopol Refined — Balanced1832.9429222791832.9429226180.00000002 %否17.524 s
Tprime_300_6002596LKH-3.0.10 (DELAUNAY)1832.9429222791835.1594469530.12092710 %否11.462 s
Tprime_500_5002947Robopol Refined — Balanced3092.9553460793092.9569434580.00005165 %否2.437 s
Tprime_500_5002947Robopol Refined — Heavy3092.9553460793092.9553460790 %是5.059 s
Tprime_500_5002947LKH + Robopol Refined — Balanced3092.9553460793092.9553460790 %是4.988 s
Tprime_500_5002947LKH-3.0.10 (DELAUNAY)3092.9553460793093.0001470560.00144848 %否0.479 s
Tprime_500_7503673Robopol Refined — Balanced3095.2492847633095.2751278480.00083493 %否6.109 s
Tprime_500_7503673Robopol Refined — Heavy3095.2492847633095.2492850380.00000001 %否13.684 s
Tprime_500_7503673LKH + Robopol Refined — Balanced3095.2492847633095.2492847630 %是10.741 s
Tprime_500_7503673LKH-3.0.10 (DELAUNAY)3095.2492847633097.4575034130.07134219 %否4.530 s
Tprime_500_10004396Robopol Refined — Balanced3094.7477884193094.7477890030.00000002 %否7.343 s
Tprime_500_10004396Robopol Refined — Heavy3094.7477884193094.7477890030.00000002 %否16.750 s
Tprime_500_10004396LKH + Robopol Refined — Balanced3094.7477884193094.7477890030.00000002 %否69.093 s
Tprime_500_10004396LKH-3.0.10 (DELAUNAY)3094.7477884193097.0202987490.07343120 %否34.420 s
数据下载与测试方法

输入数据与最优路线(JSON) · 全部结果(CSV) · 结果、路线与设置(JSON)

实例构造与最优性证明见Hougardy–Zhong: Hard to Solve Instances of the Euclidean Traveling Salesman Problem。测试使用论文中修改后的实例族。作者档案中的 EUC_2D 文件采用了舍入后的表示。

提交前,所有坐标统一放大 1,000 倍。EXACT_2D 使用有限精度。返回的路线与最优值在原始几何上以 70 位精度独立评估,并以 110 位精度复核。判断是否达到最优值时,容差为原始单位的 10−40。非零偏差会如实保留。

已发布的 LKH 结果使用修正后的 17 位有效数字坐标导出。输入 JSON 包含理想坐标、实际提交的精确点数据、n 和 m 参数、参考路线以及最优值。JSON 中的路线索引从零开始。

系统要求

  • Windows 10/11 或 Ubuntu 24.04 及以上版本(x86_64,glibc 2.39+)
  • 至少 2 GB 内存
  • 1 GB 可用磁盘空间
  • 屏幕分辨率至少为 1024 × 768

3.05 版本的新功能

TSP Solver 版本与许可证

TSP Solver 3.05采用重新设计的界面和更新的 Robopol Refined 核心,支持 AIR 2D/3D、道路路线以及通过 LKH 规划的多车辆路线。Fast、Balanced 和 Heavy配置用于控制搜索力度。

TSP Solver 演示版

免费试用版本。Windows 和 Linux 桌面版可向 RoboPol 申请获取。
您可以直接在线试用应用。启动 TSP Solver 在线版。您可以在演示版中用随机生成的 AIR 点试用算法,这些随机生成的点不受 100 点上限限制。

  • 创建和测试 AIR 点,无通用许可证点数上限
  • 将路线导出为图像
  • 修改显示设置
  • 在导入图像上手动点击添加点,最多 100 个
  • 桌面版 TSP Art 支持最多 20,000 个点
  • 创建最多包含 5 个地址的道路路线
  • 导入和导出最多 100 个点
  • 将路线发送至 Google 地图
  • 将路线发送至移动设备进行导航
向 RoboPol 申请 用户手册

TSP Solver Basic 许可证

适用于旅行规划和小型项目。

  • 桌面版与在线版均可进行 AIR 计算,无通用许可证点数上限
  • 桌面版 Refined 的 Fast、Balanced、Heavy 配置及 LKH 设置无单独的许可证限制
  • 通过 .txt 文件导入和导出最多 5,000 个点
  • 创建最多包含 100 个地址的道路路线
  • 导入和导出图像
  • 桌面版 TSP Art 无许可证点数上限
  • 将路线发送至 Google 地图
  • 将路线发送至移动设备进行导航
购买许可证(每年 120 欧元)
推荐

TSP Solver Professional 许可证

适用于运输与工业企业。

  • 桌面版与在线版均可进行 AIR 计算,无通用许可证点数上限
  • 桌面版 Refined 的 Fast、Balanced、Heavy 配置及 LKH 设置无单独的许可证限制
  • 导入和导出点,无许可证数量限制
  • 道路路线无许可证地址数量限制
  • 导出路线
  • 导入和导出图像
  • 桌面版 TSP Art,用于生成艺术图像
  • 多车辆 mTSP——通过 LKH 规划多车辆路线(2D/3D/道路)
  • 将路线发送至 Google 地图
  • 将路线发送至移动设备进行导航
购买许可证(每年 390 欧元)

桌面应用与在线服务器的许可证限制

Normal 指付费的 Basic 许可证。桌面应用在本地运行,在线版在服务器上运行,两者采用相同的许可证限制。

桌面应用

功能 Demo Normal / Basic Professional
AIR 计算——Robopol Refined / LKH + Robopol Refined / LKH-3.0.10 无通用许可证点数上限 无通用许可证点数上限 无通用许可证点数上限
在图像上手动点击添加的点 100 个点 无许可证限制 无许可证限制
点的导入与导出 100 个点 5,000 个点 无许可证限制
道路路线 5 个地址 100 个地址 无许可证限制
多车辆 mTSP 否 否 是
Refined 配置与 LKH 设置 无许可证设置限制 无许可证设置限制 无许可证设置限制

在线服务器

功能 Demo Normal / Basic Professional
AIR 计算 无通用许可证点数上限 无通用许可证点数上限 无通用许可证点数上限
在图像上手动点击添加的点 100 个点 无许可证限制 无许可证限制
点的导入与导出 100 个点 5,000 个点 无许可证限制
道路路线 5 个地址 100 个地址 无许可证限制
多车辆 mTSP 否 否 是
可用的算法设置 无许可证设置限制 无许可证设置限制 无许可证设置限制

在线版与桌面应用采用相同的许可证限制,计算分别在服务器和本地计算机上进行。

常见问题

什么是旅行商问题?

旅行商问题(TSP)要求寻找一条最短路线,恰好访问每个给定点(城市)一次,最后返回起点。它属于 NP 难问题。对于大规模实例,目前尚无已知的通用高效算法能够保证在实用时间内求得精确解。

Basic 与 Professional 版本有什么区别?

Normal / Basic 是付费许可证。AIR 计算无通用许可证点数上限,5,000 点限制适用于点的导入与导出。Professional 增加了 mTSP 功能、无限制的点导入与导出,以及无许可证地址数量限制的道路路线。桌面版实际可处理的规模取决于硬件、内存和所选模式。

计算一条优化路线需要多长时间?

计算时间取决于点数、搜索配置和硬件。3.05 版本使用更新的编译核心及并行处理。当前包含 30 个已知最优值实例的基准测试列出了各实例的实测时间、参数和结果。

可以从外部来源导入点吗?

可以。TSP Solver 支持从 TXT 文件导入点,详细信息请参阅用户手册。

软件使用哪些算法?各有什么特点?

桌面版 3.05 使用三种主要算法。

  • LKH + Robopol Refined——混合方法,以高质量的 LKH 路线为起点,在 Refined 搜索过程中选择性地与 LKH 协作。在本页基准测试中,该方法在 30 个实例中的 28 个上达到了最优值。
  • Robopol Refined——更新的核心提供 Fast、Balanced 和 Heavy 配置。在下方基准测试中,Balanced 在 30 个实例中的 27 个上找到了比独立 LKH(DELAUNAY)更短的路线。
  • LKH-3.0.10——用于独立的 AIR 路径优化,也是道路路线和 mTSP 的计算方法。

安装时 Windows 显示安全警告,应该怎么办?

下载安装文件后,Windows 可能提示无法识别程序发布者。对于 TSP Solver,此提示与缺少数字签名有关,较小开发者发布的应用可能会遇到这类安全提示。您可以按以下步骤继续安装。

  1. 在安全提示窗口中点击“更多信息”链接
  2. 然后点击“仍要运行”按钮
  3. 程序将启动,您可以继续安装

出现此提示是因为程序缺少 Windows 认可的发布者数字签名,这在较小型应用中较为常见。

软件适合实际应用吗?

适合。TSP Solver 面向物流、路线规划和配送优化等实际应用,也适用于工业用途,例如激光雕刻或印刷电路板(PCB)钻孔。这些场景通常涉及数千乃至数百万个点,路径优化可以显著缩短生产时间。