javascript - 按距离优化路线

Question

我正在构建一个基于 Here Maps 的 Web 应用程序。 其主要功能包括能够将电子表格文件(.xls、.xlsx)上传到服务器并使用文件中的地址规划路线，最多 500 个航路点。

当然，这些航路点并不是按优化顺序排列的，所以我想让用户点击“优化路线”按钮，这将按距离优化它。

例如，如果文件有这三个地址:

1. 纽约
2. 旧金山
3. 长岛

默认路线是从纽约到旧金山，然后返回李。

应用程序将检查距离并以如下方式重新排序航路点数组:

纽约 -> 李 -> 旧金山

我的问题: Here Maps 是否有内置的路线优化功能，还是我应该自己编写？

Answer 1

你应该看看 Matrix Routing API .这将计算每个 N x M 位置之间的“实际”距离。使用此信息，您已将问题减少到 Travelling Salesman Problem .当然，TSP 是 NP 完全的，因此除非您使用蛮力算法，否则您无法确定您已获得最佳答案。

就我个人而言，我会查看最近邻解决方案 - 快速、非常易于编码并且通常会返回“合理”的解决方案(即使不是最佳解决方案)。您可以根据需要更新到更复杂的算法:

伪代码如下:

1. 从A点开始
2. 到所有剩余点的矩阵路由请求。
3. 找到最近的，这成为下一个 Waypoint
4. 从第 2 步开始重复。