规划最优跑步路线

# 运行一个最优轨迹追踪：https://anishathalye.com/optimal-trace/ 轨迹追踪（历史上被称为“画红线”(https://www.americantrails.org/resources/trail-terms#h:~:text=Redline)）的目标是完成给定区域内的所有小径。这项运动起源于新罕布什尔州的徒步社区，其中“白山追踪”(http://48x12.com/white-mountains-tracing-rules.shtml)需要覆盖超过1450英里的独特小径。受一位朋友在州立公园长跑的启发，我想要在一次跑步中完成对旧金山天使岛的追踪。我很难手动规划一条高效路线，来覆盖岛上密集的19.4英里独特道路/小径网络。为了免于跑一场超级马拉松，我编写了一些软件来规划和执行*最优*轨迹。天使岛最优轨迹。**红色**：已包含的小径。**浅紫色**：独特路段。**深紫色**：重复路段。 在天使岛之前，我进行了三次本地测试跑：苏特罗山(Strava (https://www.strava.com/activities/19516090175), JPG (https://anishathalye.com/_next/static/images/sutro-run-608b62c49867ae9cdb828d079e70f3f2.jpg))、戴维森山(Strava (https://www.strava.com/activities/19660085812), JPG (https://anishathalye.com/_next/static/images/mount-davidson-run-af517390e7d2b06fb0973cb0d74c488e.jpg))和格伦峡谷(Strava (https://www.strava.com/activities/19825018746), JPG (https://anishathalye.com/_next/static/images/glen-canyon-run-c890c14089f29061cb8864953662451b.jpg))。在这些测试跑中，我改进了：勘察地点(https://anishathalye.com/optimal-trace/#scouting-the-location)的技术，使用诸如人气热图和卫星地图来确定包含哪些小径；在我的网页应用中筛选小径(https://anishathalye.com/optimal-trace/#selecting-the-trails)的工具，从API获取小径数据并提供手动添加/移除小径的界面；优化路线(https://anishathalye.com/optimal-trace/#optimizing-the-route)的算法，实现了一个中国邮递员问题求解器；以及遵循路线(https://anishathalye.com/optimal-trace/#following-the-course)的流程，结合使用手表上的实时导航和手机上的地图。 对于天使岛跑步（规划路线(https://anishathalye.com/_next/static/images/angel-island-trace-static-39dc6b46a10d9ea619ac1abfd3bdd591.png), Strava (https://www.strava.com/activities/19872432764), JPG (https://anishathalye.com/_next/static/images/angel-island-run-85ede8d61e301bcc04c1c77240a897a5.jpg)），我的优化目标是最小化总距离；规划路线总长23.8英里，其中4.4英里为重复路段。我们实际跑了24.6英里，包括一些绕道，耗时约五小时。 ## 勘察地点 规划最优轨迹的第一步是决定包含哪些小径。要成为一次“追踪”，必须包含所选区域内的所有小径。但至关重要的是要避免不存在或无法通行的小径。因为路线必须提前规划和优化，在跑步中途发现某段路无法通行，会打乱整个路线。在这种情况下，往往无法在不破坏最优性的情况下临时调整路线。 ## OpenStreetMap 作为基础，我使用OpenStreetMap来识别特定区域的道路和小径。例如，这是Strava使用的主要地图数据库。 ## 人气热图 像Strava和Garmin Connect这样的服务提供人气热图，有助于识别已关闭或不存在的小径。例如，热图有力地证明了苏特罗山上的日落小径已关闭。使用热图有几个挑战：它聚合了长时间跨度的活动数据，因此无法捕捉近期关闭的小径；其算法进行了一些裁剪和归一化处理，因此不会显示非常冷门的小径。在某种程度上，可以通过使用特定运动类型的热图来克服。例如，比较戴维森山上的全运动热图和徒步专用热图，可以揭示一些确实有少量流量的额外小径。 ## 卫星地图 在我对戴维森山的测试跑中，我遗漏了一条未在热图上突出显示的小径，但在跑步过程中，我发现它确实是一条真实的小径。后来我意识到，通过查看卫星地图本可以发现它。 ## 街景视图 当有最新的街景数据可用时，它是确认小径关闭或不可通行区域的好方法。例如，苏特罗日落小径的关闭可以通过这种方式确认。 ## 公园地图 官方地图提供了关于不可通行区域最清晰的指引。例如，天使岛公园地图(https://www.parks.ca.gov/pages/468/files/angelislandsplweblayout2013.pdf)显示了服务道路和海岸警卫队区域是对游客禁区的，尽管它们出现在Strava热图上。 对于天使岛跑步，我花了几小时使用以上所有方法勘察该区域。尽管我尽力而为，但在规划时仍出现了方向相反的小错误：路线遗漏了通往岛屿西南部莱迪亚德炮台的一条折返小径，我们在跑步时看到并添加了；另外，路线在西北部周边公路与日落小径连接处有一条“幽灵”小径，我们在跑步中发现它并非真实存在后舍弃了。幸运的是，这些错误最终并未影响路线的最优性。 ## 筛选小径 我使用了Overpass API (https://dev.overpass-api.de/)来获取给定区域内所有的道路和小径。该API提供了一些基本的筛选功能，但我所有的跑步都要求对获取的数据进行手动编辑。 ## 删除边 通过勘察确定不可通行的路段，或存在噪音的路段（如连接建筑的支线、公交车站分叉或与道路分开的人行道），都需要在路径优化前删除。OpenStreetMap的原始数据包含一个有数千个节点的图，即使对于小区域也是如此。为了获得良好的编辑体验，我构建了一个界面，支持处理与OpenStreetMap原始数据对应的*物理*节点和边，或仅包含小径交叉口的*逻辑*节点，以及将交叉口之间所有物理边组合在一起的逻辑边。 ## 添加边 这种情况很少见，但OpenStreetMap数据偶尔会缺少可通过其他方式（如卫星地图）确认存在的小径。因此，我需要能够向地图添加边。 ## 优化路线 最初，我只考虑针对距离进行优化。在戴维森山进行了一次多山的跑步后，我考虑了最小化海拔或估计行程时间。对于海拔，我使用USGS 3DEP API (https://elevation.nationalmap.gov/)获取细粒度海拔数据；起初，我的软件严重高估了海拔增益，这通过设置最小阈值（2米）来计算海拔变化得以修复。对于估计行程时间，我使用了托布勒徒步函数(https://en.wikipedia.org/wiki/Tobler%27s_hiking_function)来计算坡度调整后的配速；该计算使用移动平均来平滑海拔剖面。 距离和海拔优化目标对应于一个著名的组合优化问题，称为中国邮递员问题(https://en.wikipedia.org/wiki/Chinese_postman_problem)，即找到一条最小化边权重和并覆盖图中每条边的回路。幸运的是，这个问题有一个实际高效的多项式时间解。作为额外优化，我在逻辑图上计算了最优路径（其中逻辑边权重是相应物理边权重之和），然后将解映射回物理图。我发现距离和海拔优化目标产生了相似的解。例如，在戴维森山： | 优化目标 | 距离 | 海拔 | | :--- | :--- | :--- | | **距离** | **5.0 英里** | 1,410 英尺 | | **海拔** | 5.4 英里 | **1,273 英尺** | 不出所料，优化海拔会重复一些更长更平坦的路段，而优化距离会重复一些更短更陡的小径段。不同优化目标下的戴维森山最优轨迹。**浅紫色**：独特路段。**深紫色**：重复路段。 针对时间的优化略有不同：在这种情况下，遍历一条边的成本取决于遍历的方向，因为上坡跑比下坡跑耗时更长。这个问题被称为有风的邮递员问题，是NP难问题。我使用的解法基于整数线性规划，仅适用于小图，因此我没有在实践中使用。在我的跑步中，节省的海拔似乎不值得增加的距离，因此我总是选择最小化距离。 ## 遵循路线 经过多次迭代，我开发出一个在跑步中遵循路线的好流程。我最初的计划是导出一个最优轨迹的GPX文件，将其导入Strava，然后用手机遵循路线。最终的流程变得相当复杂。 ## 3D GPX 软件的第一个版本导出的是扁平的GPX文件，没有海拔数据。将其导入Strava会填充海拔数据。不幸的是，导入过程存在错误，显然错误放置或遗漏了某些节点。在其他软件中打开原始GPX文件显示了正确的路径，但有些软件不支持预览没有海拔数据的路线。一旦我在GPX导出中添加了海拔数据，这些问题就解决了，最初是依赖Open-Meteo海拔API (https://open-meteo.com/en/docs/elevation-api)，它提供90米分辨率的GLO-90 (https://portal.opentopography.org/raster?opentopoID=OTSDEM.032021.4326.1)数据。后来，我改用USGS 3DEP API (https://elevation.nationalmap.gov/)，它动态提供最佳可用数据，最高可达1米分辨率的S1M (https://www.usgs.gov/3d-elevation-program/new-product-3d-elevation-program-seamless-1-meter-digital-elevation-model-s1m)。 ``` 238.2 239.1 239.2 ``` 这修复了Strava的导入问题，也提高了与其他软件的兼容性。 ## Garmin导航 在手机上查看静态Strava路线时，重复路段无法看清，因此我也将路线同步到我的Garmin手表上，以便跑步时进行实时导航。这很有帮助，但在密集区域是一个不完美的解决方案。在1.3英寸、260x260像素的内存像素显示屏上进行导航。 ## Strava路线预览 在我对苏特罗的第一次测试跑中，我同时使用了静态Strava地图和Garmin导航，但一进入小径密集区域我就迷失了。短暂暂停后，我想到了使用Strava的路线预览功能来动画展示路线，我还可以拖动滑块仔细查看路线的特定部分。虽然这不是该功能的预期用途，但它帮助我完成了第一次测试跑。 ## Organic Maps Strava的路线预览功能是为美观目的设计的，而非导航工具。它只支持卫星地图作为底图，无法很好地处理重叠路段，也不显示你的当前位置。在我第二次测试跑时，我改用Organic Maps (https://organicmaps.app/)来可视化我软件导出的GPX文件。这个设置有几个优点：在地图上显示当前位置、拖动时分辨率更高、以及支持点击地图上的点在规划路线上查找。 ## 拆分GPX 在天使岛之前，我最长的测试跑是8.5英里。在为24英里的天使岛跑步做准备时，我发现拖动查看时的分辨率不足以在密集区域导航。我通过实现拆分GPX导出来解决这个问题，将路径分成4英里的片段。这在拖动查看片段时提供了足够的分辨率。对片段进行颜色编码，并在Organic Maps中能够独立显示/隐藏它们，也简化了导航。 结合使用Garmin手表上的实时导航和手机上的Organic Maps，我得以在天使岛跑步过程中成功导航。 ## 自己试试 最优轨迹规划软件完全在浏览器端客户端运行，使用无需身份验证的公开API。你可以在optimal-trace.anish.io (https://optimal-trace.anish.io/)尝试该应用。注意，该网页应用未针对移动端优化。源代码可在github.com/anishathalye/optimal-trace (https://github.com/anishathalye/optimal-trace)获取。