5

A、B、C、Dなどのポイントをドライブするための最適な方法を見つけようとしています

いくつかの追加の制約があります - 特定のポイントは他のポイントより先に到達する必要があります。Bの前にDに到達する必要があるとします。つまり、いくつかのポイントの順序付けです。

追加の制約がない場合、Google マップ API はこの問題の解決に役立ちます。この問題を解決するのに役立つ別のサービスはありますか? 私が逃したGoogleマップAPIでこれを行う方法はありますか?

4

5 に答える 5

1

あなたは、GoogleにはAPI関数があると言い、名前を付けましょうbestWay(point a, point b)：

ポイントが{A,B,C,D}あり、次の順序でアクセスする必要があります。

A,C,D,B

(A,C) の bestWay を見つけ、(C,D) と (D,B) から、自分のやり方を構築します。

すべての順列をチェックする必要があるC前に、そのような制約しかない場合:D

A->C->B->D
A->B->C->D
...
B->A->C->D
于 2013-02-20T22:08:30.747 に答える
1

巡回セールスマン問題は、整数計画問題(このリンクは定式化を提供します) または制約計画問題として定式化できるため、 CBCやGecodeなどの MIP または CP ソルバーを使用して、必要な追加の制約を使用して TSP 問題を解くことができます。たす。ただし、結果を Google マップにプロットする必要がある場合は、Google Maps API を使用して手動で行う必要があります。

Web ベースのソリューションを好む場合は、XML-RPC APIを介してさまざまなソルバーへのアクセスを提供する最適化のために NEOS サーバーを使用できます。追加の利点として、この方法では、低レベルのソルバー API を直接処理するのではなく、AMPLなどの高レベルのモデリング言語で問題を送信できます。

于 2013-02-20T22:34:01.770 に答える
0

Javascriptの正確なソルバーは次のとおりです：http ：//www.iaindunning.com/？page_id=39 。ここhttp://www.tsp.gatech.edu/methods/dfj/index.htmlのような線形計画法と切断面法を使用します。

于 2013-02-20T23:03:34.757 に答える
0

巡回セールスマン問題のオープンソース実装がhttp://www.openopt.org/TSPで入手できますが、Python で書かれています。

上記の OpenOpt TSP と Google ルート案内を組み合わせて、必要なことを実行する Web サイト (順序の制約を除く) を提供します。http://www.speedyroute.co.uk/で入手できます。

于 2013-03-07T13:34:02.353 に答える
0

これをチェックしてくださいhttp://xsolve.info/TSP.html これはJAVAのプログラムです.これを変更して独自の制約を追加できます

于 2013-08-04T08:03:46.197 に答える