从GPS数据中找到最佳匹配路线

Question

我正在开发一个应用程序，用户可以保存他们日常行程中从手机获取的GPS数据到服务器上。例如，他们从家到工作地点。GPS数据被存储在数据库中。

现在，用户想知道是否有更多人也走这条路线。我想比较不同用户的路线，并向用户提供来自其他用户路线的3-5个最佳匹配项。

重要的是比较整个行程，因为用户可以加入他们的路线，一起从某个点开始上班，而不仅仅是从起点和终点。此外，我认为对于搜索其他用户路线的用户来说，目的地点也很重要。其他用户的路线必须靠近搜索者的路线结束点。

有两个因素需要考虑 - 时间和位置。一个用户开车，另一个步行并乘公交车。步行的人早些时候开始行程，另一个晚些时候开始，因为他走得更快。在某个时间点，他们的路线匹配。

如何比较路线？是否有算法可用？我需要比较路线上的每个点吗？

- evilone

---

不确定答案是什么，但这是一个非常有趣的问题 - 我喜欢这样的挑战...首先的想法是你可能需要以某种方式抽象数据，并对结果进行某种模式匹配。另一个想法是，旅程本身重要还是只有起点和终点位置真正重要？例如，如果这是为了一个拼车应用程序，您是否正在寻找包括您的起点和终点的另一条路线？ - Richard Baxter

@Richard Baxter 修改了我的问题。 - evilone

Answer 1

本质上，您正在谈论路由算法和旅行推销员的组合。

最常见的路由算法是由Dijkstra在大约50年前发明的，它计算从点a到点b的最佳路径，在路由应用程序中，这意味着每条道路都表示为网络中的一条边，每个边缘都与一个“成本”相关联，即通过该道路所需的时间、平均速度或在您的情况下，它将是通过该路线旅行的人数。

旅行推销员问题略有不同，但也相关，试图优化访问的节点数量 - 在您的情况下，它可能解决相反的问题，因为它试图最大化城市（边缘交叉节点）的数量，同时最小化前往所有节点的成本 - 如果您想解决此问题，值得理解。

- Soren

Answer 2

看看GIS - 这是一个（巨大的）研究领域 - 非常有趣但也非常紧张

- KevinDTimm

Answer 3

我认为你需要做的是将手机获取的GPS坐标转换成路线。可以看看Open Route Service，它是Open Street Map项目的一部分。

一旦你将每个人的纬度和经度转换为共同的路线，那么比较他们的路径就会更容易，以查看是否有共同点。你还可以进行其他操作，例如搜索备选路线。也许一个人通过多走几英里/公里可以与另外一组4-5个人一起前往基本相同的方向。类似这样的事情。

- arunkumar