TSP Solver 3.05 · 用户指南

从添加第一个点到生成路线,了解 TSP Solver 的工作区、算法、设置和导出功能。

Ing. Robert Polák (RoboPol)robopol@gmail.com

简介

TSP Solver 求解旅行商问题(TSP),即寻找一条尽可能短的闭合路线,恰好访问每个点一次,然后回到起点。应用场景包括物流配送、路线规划、印制电路板钻孔、数控和激光加工、机器人以及无人机的二维和三维航线规划。

应用提供 LKH、Robopol Refined 及混合算法,支持按点之间的直线距离或实际道路网络的距离计算路线。

快速入门

  1. 使用坐标时选择直线距离(AIR),使用地址时选择道路(ROAD)。
  2. 在画布上添加点,或从 .txt 文件导入坐标。使用道路模式时,每行输入一个地址,然后执行地理编码。
  3. 按所需的计算速度和路线质量选择算法和预设。
  4. 启动计算,查看绘制的路线。
  5. 导出点、图片或 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 z
  • x, y 或 x, y, z
  • x; y 或 x; y; z
  • n) x y 或 n) x y z
  • n: x y 或 n: x y z
  • n, 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 输出格式见数据导入与导出。

画布外观设置
画布外观设置
Robopol Refined 算法设置
Robopol Refined 算法设置
多车辆路线设置
多车辆路线设置

mTSP 使用 LKH-3.0.10,主要面向 AIR 2D 和 ROAD 工作流程。使用 AIR 3D 时,请先验证较小任务,再运行大型计算。

编辑和计算

点击画布添加点。启用删除模式后再点击,可移除单个点。移除连线可清除已绘制的路线,清空操作会移除所有点、路线和背景图。计算至少需要两个坐标不同的点。

添加点时会突出显示第一个输入点。计算后,标记显示路线实际的起点和终点。在删除模式中点击某个点即可将其移除。

TSP 艺术

桌面版可将图像转换为点。在线版可以导入准备好的坐标,并据此计算一条连续路线。

在桌面版的数据集菜单中选择图片并输入点数。快速预览时可先用几千个点。用 LKH 快速计算时,可尝试 DELAUNAY、RUNS = 1、MAX_TRIALS = 1、MOVE_TYPE = 3,并将两个拼接参数设为 0。计算后可调整颜色和线宽,并导出结果。

示例使用 5 万至 10 万个点。运行时间随数据、设置和硬件而异。

约翰·威克:使用 LKH 计算的 100,000 个唯一点的 TSP 艺术作品
约翰·威克:使用 LKH 计算的 100,000 个唯一点的 TSP 艺术作品
老虎:浅色界面中显示的 100,000 个唯一点的 TSP 艺术作品
老虎:浅色界面中显示的 100,000 个唯一点的 TSP 艺术作品
玫瑰:深色界面中显示的 50,000 个唯一点的 TSP 艺术作品
玫瑰:深色界面中显示的 50,000 个唯一点的 TSP 艺术作品

参考图像:约翰·威克 · 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 可查看原始尺寸。

图像背景操作步骤

  1. 打开文件 → 导入图像。
  2. 在图像上添加点,选择算法并点击计算。
  3. 导出图像、点或 SVG,并使用另存为保存项目。

TXT 坐标操作步骤

  1. 使用支持的分隔符准备坐标数据。
  2. 打开数据集 → 导入点,然后计算路线。
  3. 对比唯一点数和路线详情,再导出结果。

道路路线

在多车辆模式下,各车辆都从共同出发点出发,并返回该点。depot_index 从 1 开始,按成功完成地理编码的地址排序;失败的地址会被跳过。地址地理编码和道路路线计算依赖外部服务。

公路模式结合地理编码与真实道路网络上的路线规划。在算法设置 → 路线规划中启用 mTSP,并设置车辆数、目标、车场及停靠点上下限。同一功能也支持 AIR 2D。AIR 3D 应先用较小任务验证。

选择 ROAD,每行输入一个地址,对列表进行地理编码后计算路线。显示地图打开交互式预览。导出至 Google Maps 可用于导航或将路线发送到手机。此功能需要互联网连接,外部路线服务请求可能使计算变慢。

逐行输入道路路线的目的地地址
逐行输入道路路线的目的地地址
地图上计算完成的道路路线
地图上计算完成的道路路线

许可证和版本

各版本在点数上限、导入导出权限及公路路线功能方面有所不同。在信息 → 许可证密钥中激活已购买的功能。Demo 版用于评估,点数和功能有限。Basic 版适合较小项目和出行规划。Professional 版提供完整功能和更高限额。实际可处理的数据规模取决于硬件、内存及所选模式。

浏览器要求

需要现代浏览器和网络连接。三维查看器需要 WebGL。计算在服务器上执行。

在线计算无需安装桌面求解器。

提示

  • 提供街道、门牌号、邮政编码、城市和国家或地区,可提高地理编码的准确率。
  • 对于大型 AIR 数据集,可从 Fast 预设开始,必要时跳过绘制。
  • 如需在矢量图形软件中编辑路线,可导出 SVG。坐标文件使用英文句点表示小数点。

SVG 适合无损缩放及矢量编辑,例如在 Inkscape 或 Illustrator 中进行后期处理。

语言选择器会在当前工作区内切换界面语言,同时保留点、路线、地址、打开的对话框及正在进行的计算。