Googleマップを使用した最適な地図ルーティング
https://stackoverflow.com/questions/337607
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
Google Maps APIを使用して「最適化」を取得する方法はありますかウェイポイントのセットが与えられたルート（言い換えると、巡回セールスマン問題の「十分な」解決策）、または常に指定された順序でポイントを含むルートを返しますか？
解決
常にそれらを順番に提供します。
だから、ポイントの各ペア間の距離（または時間）を一度に1つずつ見つけて、巡回セールスマンの問題を自分で解決する必要があると思います。ただし、Googleマップにその機能を追加するよう説得することもできます。何が「十分に良い」を構成するのかと思います。解決策は、あなたが何をしているのか、それがどれくらいの速さであるのかに依存します。
他のヒント
Google Maps API DirectionsRequestには、optimizeWaypointsと呼ばれるオプションがあります。ただし、これは最大8つのウェイポイントしか処理できません。
別の方法として、Google Maps APIで使用できる最適な（最大15箇所）または最適に近い（最大100箇所）ルートを取得できるオープンソース（MITライセンス）ライブラリがあります。
でライブラリの動作を確認できます典型的なTSP問題では、任意の2つのポイント間を直接移動できることが前提です。路面の道路では、これは当てはまりません。 Googleが2つのポイント間のルートを計算すると、ヒューリスティックなスパニングツリーの最適化が行われ、通常、最適なパスにかなり近いパスが作成されます。
TSPルートを計算するには、まずグラフの各ノード間のペアワイズ距離を計算するようGoogleに依頼する必要があります。これにはn *（n-1）/ 2計算が必要だと思います。その後、それらの距離を取り、それらに対してTSP最適化を実行できます。
OpenStreetMaps.orgには、必要な処理を実行できる Java WebStart アプリケーションがあります。もちろん、計算はクライアント側で実行されています。このプロジェクトはオープンソースであり、一見の価値があります。
場所間の最適な直線経路、または最適な運転ルートを見つけようとしていますか？ポイントを注文するだけで、GPS座標を取得できる場合は、非常に簡単な問題になります。
見つかった http://gebweb.net/optimap/ 見た目は簡単です。 Googleマップを使用したオンラインバージョン。
Googleには、Travel Salesman Problemの解決策が用意されています。 OR-Tools（GoogleのOperations Researchツール）がここにあります： https：// developers .google.com / optimization / routing / tsp
基本的に必要なことは2つのことです：
-
Google Maps APIを使用して、各2点間の距離を取得します。 https://developers.google.com/maps/documentation/distance-matrix/start
-
次に、配列の距離を ORツールに渡します a>そして、あなたにとって非常に良い解決策を見つけます（数百万のノードがある特定のインスタンスでは、解決策は最適なツアーの1％以内であることが保証されています）。
次の点にも注意してください：
従来の巡回セールスマンの解決策を見つけることに加えて 問題、OR-Toolsは、より一般的なタイプの 以下を含むTSP：
-
非対称コストの問題＆＃8212;従来のTSPは対称です。ポイントAからポイントBまでの距離は、ポイントBから ポイントA。ただし、ポイントAからポイントBに商品を配送するコスト それらをポイントBからポイントAに配送するコストと等しくない場合があります。 OR-Toolsは、非対称コストの問題も処理できます。
-
ノードを訪問することで利益が発生するTSPを収集する
-
タイムウィンドウ付きのTSP
追加リンク：
