13.1.3 巡回セールスマン(TSP)ルート・リクエスト

巡回セールスマン(TSP)ルート・リクエストには、少なくとも3つの場所が必要です。単純マルチアドレス・ルート・リクエストとは異なり、<start_location>要素はオプションです。

TSPルート・リクエストは、optimize_route属性が存在し、TRUEに設定されたマルチアドレス・リクエストです。TSPルート・リクエストは、リクエスト内の固定されていない場所を並べ替えて全体的なルートの最適化を試みます。

TSPリクエスト内のすべての場所は、非固定または固定として分類されます。

• 非固定の場所: 場所が<location>要素で指定されている場合は、非固定の場所とみなされ、ルート計算時に並替えの対象となります。

• 固定の場所: 場所が<start_location>または<end_location>要素で指定されている場合は、固定の場所とみなされ、ルート計算時に並替えの対象になりません。

  中間地を固定する必要がある場合は、TSPルート・リクエストのかわりに単純マルチアドレス・ルート・リクエストを使用する必要があります。

TSPルート・リクエストでは、route_type属性を使用して、ルートを開いた行程または閉じた行程として分類します。

• 開いた行程: ルートは出発地に戻りません。

• 閉じた行程: ルートは出発地に戻ります。

  TSPの閉じた行程ルートがリクエストされた場合は、<start_location>要素を指定する必要があります。この出発地はルート計算中に目的地としても使用されます。TSPの閉じた行程ルート・リクエストで<end_location>要素が指定されている場合は、エラーが戻されます。定義では、TSPの閉じた行程ルートは単一の固定の出発および目的地を使用しますが、中間地は並替えの対象となります。

例: TSPの開いた行程ルート・リクエスト

職場から運転し、顧客A、B、Cを訪問する場合は、次のようになります。

• ルートには固定の出発地として職場があります。

• ルートには、非固定の中間地として顧客A、B、Cがあります。これらの場所が並べ替えられて、全体的なルートが最適化されます。

• 戻されるルートは、職場から最初の並べ替えられた場所、さらに2番目の並べ替えられた場所を通過して最終目的地に到達する、最適化された開いた行程ルートです。

例: TSPの閉じた行程ルート・リクエスト

職場から運転し、顧客A、B、Cを訪問し、職場に戻る場合は、次のようになります。

• ルートには固定の出発地として職場があります。職場は固定の目的地としても使用されます。<end_location>要素はルート・リクエストで指定しないでください。ルーティング・エンジンは、閉じた行程のリクエストを検出すると、最後の非固定の場所から職場までのサブルートを自動的に追加します。

• ルートには、非固定の中間地として顧客A、B、Cがあります。これらの場所が並べ替えられて、全体的なルートが最適化されます。

• 戻されるルートは、職場から最初の並べ替えられた場所、さらに2番目と3番目の並べ替えられた場所を通過して最終的に出発地に戻る、最適化された閉じた行程ルートです。

TSPルート・リクエストには、各サブルートに固有の複数の属性を含めることができます。これらの属性には、return_subroutes、return_subroute_edge_idsおよびreturn_subroute_geometryが含まれます。これらの属性については、「ルート・リクエストXMLスキーマ定義」で説明しています。