從GPS數據中尋找最佳匹配路線

Question

我正在製作一個應用程序，用戶可以在他們旅行日常路線時從手機到服務器保存GPS數據。例如，他們正在從家到工作。 GPS數據存儲在數據庫中。

現在，用戶想知道也許有更多的人旅行這條路線。我想比較不同的用戶路由，並給用戶例如其他用戶路由的3-5個最佳匹配。

重要的是比較整個行程，因爲用戶可以加入他們的路線，從一開始就一起工作，不僅從開始和結束。另外我認爲重要的是來自用戶視圖的目標點，他正在搜索其他用戶的路線。其他用戶路由必須靠近搜索者路由端。

有兩個因素 - 時間和地點。一個用戶用汽車行駛，另一個用戶例如走路並乘坐公共汽車。那個走路的人早些時候開始他的旅程，後來他開始旅行，因爲他更快地旅行這條路線。在某一時刻，他們的路線是匹配的。

如何才能比較路線？有算法嗎？我需要比較路線中的每個點嗎？

Answer 1

基本上你正在談論的路由算法的組合和旅遊銷售人

最常見的路由算法是在50年前由Dijkstra發明的，並且計算在有向網絡中從點a到點b的最佳方式 - 在路由應用中，這意味着每條道路在網絡中被表示爲邊緣，並且每條邊是與「成本」相關聯，即沿着道路行駛所花費的時間，或平均速度，或者在您的情況下，這將是人數在這條路上旅行。

經t raveling sales man是略有不同，但也有關係，努力優化訪問節點的數量 - 在你的情況下，它可能是解決，因爲它正試圖最大化的城市數量相對（邊緣相交節點），同時最小化前往所有節點的成本 - 值得理解，如果你想解決這個問題

Answer 2

見GIS - 這是研究的一個（巨大）場 - 很有趣，但非常激烈

Answer 3

我認爲你將不得不做的是將你從手機獲得的GPS座標轉換成路線。看看Open Route Service這是Open Street Map項目的一部分。

一旦將每個人的經緯度轉換爲一組通用路線，那麼比較他們的路徑以查看他們是否有共同點，將會更容易。你也可以做一些事情，比如搜索替代路線。也許一個人乘坐幾英里/公里的速度可以與另一組4-5人一起前進，基本上是一樣的方向。像這樣的東西。