简介
TSP Solver 求解旅行商问题(TSP),即寻找一条尽可能短的闭合路线,恰好访问每个点一次,然后回到起点。应用场景包括物流配送、路线规划、印制电路板钻孔、数控和激光加工、机器人以及无人机的二维和三维航线规划。
应用提供 LKH、Robopol Refined 及混合算法,支持按点之间的直线距离或实际道路网络的距离计算路线。
快速入门
- 使用坐标时选择直线距离(AIR),使用地址时选择道路(ROAD)。
- 在画布上添加点,或从
.txt文件导入坐标。使用道路模式时,每行输入一个地址,然后执行地理编码。 - 按所需的计算速度和路线质量选择算法和预设。
- 启动计算,查看绘制的路线。
- 导出点、图片或 SVG,或将整个项目保存为
.json。
工作区
左侧栏包含项目、数据集和系统工具。中间是画布。右侧面板用于选择算法、启动计算、查看路线摘要及详细信息。

点数按不同坐标统计。计算前,金色标记指向第一个输入点;计算后,指向路线的起终点或多车辆路线的共同出发点。路线详情列出坐标、已删除的重复项和计算用时,支持复制、清空及导出。
重复的输入记录不会增加唯一点数。
布局与全屏
在较窄的屏幕上,结果显示在画布下方,点击菜单按钮即可打开导航。使用画布右上角的图标切换全屏,进入全屏后仍可通过菜单访问各项工具。
数据量大时,可在画布外观设置中跳过绘制。计算继续进行,界面暂停绘制点和路线。
三维直线距离(x, y, z)
开启三维直线距离(Air 3D)后,求解器使用空间距离。手动添加点时可通过滑块将高度 z 设为 −1000 至 1000。也可以导入 x y z 坐标,或生成高度固定或在指定区间内均匀分布的随机点。
计算后打开三维视图,拖动可旋转,滚动鼠标滚轮可缩放。退出三维视图后,计算模式仍由复选框控制。开启三维模式或任一点的 Z 值非零时,TXT 导出包含 Z 坐标。可用分隔符见数据导入和导出。

算法
LKH-3.0.10
适用于直线距离路线、道路路线和多车辆路线。对于 AIR 路线,可以对比不同 CANDIDATE_SET_TYPE 的结果,合适的值取决于点的分布。
EUC_2D / EUC_3D 将每条边的欧氏距离取整,EXACT_2D / EXACT_3D 使用更高的精度。
LKH + Robopol Refined
优先考虑直线距离路线质量的混合算法,可能需要更长的计算时间。
Robopol Refined
RoboPol 的优化算法提供 Fast、Balanced 和 Heavy 三种预设,分别侧重速度、平衡速度与质量以及优先提高路线质量。
总距离精度很重要时,请选择 EXACT_2D / EXACT_3D。建议先使用内置配置方案。Fast 适合较短的计算,Balanced 适合日常工作,Heavy 或 LKH + Robopol Refined 适合优先考虑路线质量的任务。首次计算可能包含一次性的初始化开销。
中文界面中的配置方案名称为快速(Fast)、均衡(Balanced)和深度(Heavy)。
性能
计算时间取决于点的数量和分布、算法、预设及硬件。对业务关键的路线,可比较不同预设的结果。点数很多时,可以跳过画布绘制,让界面保持响应。
Fast 优先考虑响应速度,Balanced 提供默认的速度与质量平衡,Heavy 优先考虑质量。没有任何配置方案适用于所有数据集。应用支持带交互式可视化的二维和三维坐标,也支持基于真实道路网络的公路路线,并可导出至 Google Maps。来源:RoboPol TSP Solver 产品页面。
选择算法和预设
- 快速响应:Robopol Refined 的 Fast 预设。
- 常规任务:Robopol Refined 的 Balanced 预设。
- 优先提高直线距离路线质量:Heavy 或 LKH + Robopol Refined。
- 道路或多车辆路线:LKH-3.0.10。
建议先使用内置预设。调整高级参数可能增加运行时间、处理器负载和内存占用,对路线的影响取决于数据集。
内置配置方案提供经过测试的速度与质量等级,无需手动调参。高级自定义设置适合有经验的用户。增大数值并不能保证在某个数据集上获得更好的路线。
文件操作
新建项目会清空画布和输出,并保留设置。直线距离项目保存为 tsp_air_data.json,道路项目保存为 tsp_road_data.json。保存后可在 TSP Solver 中重新打开。
可以导入图片作为背景模板,也可以将当前视图导出为图片。SVG 将路线和点保存为可缩放的矢量图形。
保存的项目使用 .json 扩展名,矢量图使用 .svg 扩展名。另存为会打开文件命名对话框。
数据导入和导出
支持的全部坐标格式
x y或x y zx, y或x, y, zx; y或x; y; zn) x y或n) x y zn: x y或n: x y zn, x y或n, x y z
仅当编号带有明确的分隔符 )、: 或 , 时,才将其识别为编号。这可防止将有效三维文件中作为第一个坐标的整数误认为编号。小数使用点号(.)。
计算前会突出显示第一行对应的点。计算后,金色标记按实际路线顺序显示。重复坐标只计一次。TXT 导出保存路线点。三维模式关闭且所有 Z 值均为零时,导出使用 x y,否则使用 x y z。生成随机点后,点击计算求解路线。
结构化 mTSP 导出适用于机器和工具。元数据语法如下:
# TSP_SOLVER_TXT 1 # mode: air # depot: 1 # vehicles: k # objective: MINSUM|MINMAX|MINMAX_SIZE POINTS id x y [z] ROUTES V <vehicle_id> cost=<cost> stops: id id id ...
ROAD 模式使用 # mode: road,点格式为 id lat lon "address"。点 ID 按文件顺序从 1..n 编号,路线通过这些 ID 引用点。
TXT 导出会尽可能保留坐标分隔符(空格、逗号或分号)及编号样式。在随机点生成器中选择分布类型,生成点后再计算路线。
外观和算法设置
详细外观选项
打开系统 → 外观设置,或点击画布中的设置按钮。画布选项卡包含主题、背景颜色、点颜色、线颜色、点大小、线宽、淡色网格及跳过绘制选项。界面选项卡控制页面、侧边栏、面板、强调色、深色强调色、文字、边框及输入框的颜色。重置页面颜色恢复默认颜色。
处理数万至数百万点的超大数据集时,启用跳过绘制可提高界面响应速度。暂停绘制点和路线期间,求解器仍继续运行。
配置方案与搜索工作量
算法设置包含路线规划、Robopol Refined 和 LKH 选项卡。点击应用设置确认修改。先使用内置配置方案,再根据具体应用场景的测量结果调整单项数值。部分参数由所选方法自动管理。
Robopol Refined 提供行为可预期的搜索工作量控制项。敏感内部参数由配置方案管理。它们之间存在非线性交互,单独调整可能减少有效优化工作量,或降低路线质量。
- 配置方案加载一组完整且经过测试的速度与质量设置。
- 运行次数设置独立优化尝试的次数,并保留最佳结果。
- 每次运行的搜索预算限制每次尝试的搜索工作量。
- 搜索宽度设置同时保留的有希望的备选路线数量。
- 每轮候选方案数设置每轮搜索中评估的备选方案数量。
- Fast、Balanced 和 Heavy 的自定义值分别保存在浏览器中,切回相应方案时会恢复。
- 重置当前配置方案只会清除该方案的自定义值,并恢复其内置值。
增加工作量通常会延长计算时间,并可能提高结果稳定性。随机优化无法保证每一次计算都优于工作量较低的配置方案。
全部 mTSP 字段
- 问题类型选择单路线 TSP 或多车辆 mTSP。
- 车辆数(
vehicles)设置车辆或子路线数量。 - 目标(
mtsp_objective):MINSUM最小化所有路线的距离或时间之和。MINMAX最小化最长单条路线的距离或时间。MINMAX_SIZE最小化单辆车的最大停靠点数,以平衡工作量,而非直接优化距离。 - 车场序号(1..n)(
depot_index)指定所有路线共同的起点和终点。1 表示第一个点。在 ROAD 模式中,索引按成功完成地理编码的地址顺序计算,失败的地址行会跳过。 - 每辆车最少停靠点数(
mtsp_min_size)可防止 1 对 99 等不均衡分配。车场不计入停靠点数。 - 每辆车最多停靠点数(
mtsp_max_size)限制每辆车的工作量。车场不计入停靠点数。 - 公路优化依据(
road_objective)选择距离(公里)或时间(秒)。
应用会自动禁用或管理不适用于当前方法的 LKH 高级选项。增加 RUNS 和 MAX_TRIALS 通常会增加运行时间。其他高级选项应根据经过验证的基准测试或技术支持建议调整。较高的数值无法保证更好的结果。mTSP 需要 Professional 版。每辆车的 TXT 输出格式见数据导入与导出。



mTSP 使用 LKH-3.0.10,主要面向 AIR 2D 和 ROAD 工作流程。使用 AIR 3D 时,请先验证较小任务,再运行大型计算。
编辑和计算
点击画布添加点。启用删除模式后再点击,可移除单个点。移除连线可清除已绘制的路线,清空操作会移除所有点、路线和背景图。计算至少需要两个坐标不同的点。
添加点时会突出显示第一个输入点。计算后,标记显示路线实际的起点和终点。在删除模式中点击某个点即可将其移除。
TSP 艺术
在桌面版的数据集菜单中选择图片并输入点数。快速预览时可先用几千个点。用 LKH 快速计算时,可尝试 DELAUNAY、RUNS = 1、MAX_TRIALS = 1、MOVE_TYPE = 3,并将两个拼接参数设为 0。计算后可调整颜色和线宽,并导出结果。
示例使用 5 万至 10 万个点。运行时间随数据、设置和硬件而异。



参考图像:约翰·威克 · WildCats Conservation Alliance · Liam Nguyen / Unsplash
桌面版操作流程为数据集 → 生成 TSP 艺术,选择图像并输入点数。增加点数会提高细节,同时延长转换和计算时间。选择 LKH-3.0.10,打开算法设置 → LKH并使用上述数值。点击应用设置,然后点击计算。在外观 → 画布中调整背景、点和路线颜色。根据需要导出图像、点或 SVG。
作者提供的截图展示完整的 3.05 版界面,包括所选算法与结果。John Wick 示例使用 LKH 计算了 100,000 个唯一点,老虎示例在浅色界面中使用 100,000 个点,玫瑰示例在深色界面中使用 50,000 个点。这些示例仅用于展示,不保证其他电脑或数据集的运行时间。
示例和屏幕截图
每张截图均展示完整的 3.05 版窗口。点击图像可将其打开,选择 1:1 可查看原始尺寸。
图像背景操作步骤
- 打开文件 → 导入图像。
- 在图像上添加点,选择算法并点击计算。
- 导出图像、点或 SVG,并使用另存为保存项目。
TXT 坐标操作步骤
- 使用支持的分隔符准备坐标数据。
- 打开数据集 → 导入点,然后计算路线。
- 对比唯一点数和路线详情,再导出结果。
道路路线
在多车辆模式下,各车辆都从共同出发点出发,并返回该点。depot_index 从 1 开始,按成功完成地理编码的地址排序;失败的地址会被跳过。地址地理编码和道路路线计算依赖外部服务。
公路模式结合地理编码与真实道路网络上的路线规划。在算法设置 → 路线规划中启用 mTSP,并设置车辆数、目标、车场及停靠点上下限。同一功能也支持 AIR 2D。AIR 3D 应先用较小任务验证。
选择 ROAD,每行输入一个地址,对列表进行地理编码后计算路线。显示地图打开交互式预览。导出至 Google Maps 可用于导航或将路线发送到手机。此功能需要互联网连接,外部路线服务请求可能使计算变慢。


许可证和版本
各版本在点数上限、导入导出权限及公路路线功能方面有所不同。在信息 → 许可证密钥中激活已购买的功能。Demo 版用于评估,点数和功能有限。Basic 版适合较小项目和出行规划。Professional 版提供完整功能和更高限额。实际可处理的数据规模取决于硬件、内存及所选模式。
浏览器要求
需要现代浏览器和网络连接。三维查看器需要 WebGL。计算在服务器上执行。
在线计算无需安装桌面求解器。
提示
- 提供街道、门牌号、邮政编码、城市和国家或地区,可提高地理编码的准确率。
- 对于大型 AIR 数据集,可从 Fast 预设开始,必要时跳过绘制。
- 如需在矢量图形软件中编辑路线,可导出 SVG。坐标文件使用英文句点表示小数点。
SVG 适合无损缩放及矢量编辑,例如在 Inkscape 或 Illustrator 中进行后期处理。
语言选择器会在当前工作区内切换界面语言,同时保留点、路线、地址、打开的对话框及正在进行的计算。
