GPSデータから最も一致するルートを見つける

Question

私は日常のルートを旅行するときにユーザーが携帯電話からサーバーにGPSデータを保存できるアプリケーションを作成しています。たとえば、彼らは自宅から仕事に向かいます。 GPSデータはデータベースに格納されます。

ここで、このルートを旅行する人が増えている可能性があります。私は、さまざまなユーザーのルートを比較し、他のユーザーのルートから3-5のベストマッチなどをユーザーに伝えたいと考えています。

重要なのは、ユーザーがルートに参加し、開始時と終了時だけでなく、ある時点で開始することができるためです。また、重要なのは、他のユーザーのルートを検索しているユーザービューからの宛先ポイントだと思います。他のユーザールートは、検索者ルートの端に近くなければなりません。

時間と場所の2つの要素があります。 1人のユーザーが車で運転し、もう1人が歩き、例えばバスを利用します。歩いている人は、早くこのルートを旅するので、早く、もう1つ後で出発します。ある時点では、そのルートは一致しています。

どのように経路を比較できますか？そのためのアルゴリズムはありますか？ルート内のすべてのポイントを比較する必要がありますか？

Answer 1

基本的にあなたは、ルーティングアルゴリズムの組み合わせの話、旅行販売人いる

最も一般的なルーティングアルゴリズム約50年前にDijkstraによって考案され、有向ネットワークのポイントaからポイントbに至る最善の方法を計算します。つまり、各道路がネットワーク内のエッジとして表され、各エッジが「コスト」すなわち道路を降りるのにかかる時間、または平均速度に関連するか、またはあなたのケースでは、それは釣人の数になりますそのルートを旅しています。

tは少し違っていますが、訪問したノードの数を最適化しようとしています - あなたのケースでは、都市の数を最大にしようとしているように、 ）すべてのノードへの移動コストを最小限に抑えながら - この問題を解決したい場合には理解できる価値がある

Answer 2

GISを参照してください - それは、研究の（巨大な）フィールドだ - 非常に興味深いが、非常に激しい

Answer 3

私はあなたが電話から得たGPS座標をルート。 Open Street Mapプロジェクトの一部であるOpen Route Serviceをご覧ください。

各人の緯度と経度を共通のルートに変換すると、パスを比較して共通点があるかどうかが簡単になります。また、代替ルートの検索などの操作を行うこともできます。おそらく1人の人が2マイルの余分なマイルを移動することによって、4-5人の別のグループと一緒に基本的に同じ方向に進むことができます。そういうもの。