巡回セールスマンの問題を理解する
巡回セールスマンの問題の解決方法を確認してみましょう。一連の場所を指定して、各場所を訪問する最短ルートを見つけ、元の出発地点に戻ります。
データを収集してリクエストを作成する
リクエストURLは次のようになります。
POST https://tourplanning.hereapi.com/v3/problems結果を計算するには、以下を入力する必要があります。
- 出発地
- 訪問する場所の座標
- 車に関する情報
認証
Tour Planning APIは、API KeyとBearer Tokenの両方を使用した認証をサポートしています。無料で利用を開始するには、アカウントを作成してAPI キーを取得します。その他の認証方法については、Identity and Access Managementの開発者ガイドを参照してください。
訪問する場所の座標
訪問する場所 (ジョブ) は、順不同で下のリストに表示されています。私たちの目標は、以下のすべての場所を訪問する最適な順序を見つけることです。
A: 47.620835, -122.333295
B: 47.623879, -122.335212
C: 47.620571, -122.339785
D: 47.623690, -122.333005
E: 47.622017, -122.336911出発地点 (集配センター) はSでラベル付けされており、その位置は47.623231,-122.340168またはワシントン州シアトルのリパブリカンストリート872です。集配センターの座標は、後で運行管理とともに指定します。
特定の場所が開いている特定の時間帯に到着したい場合があります。この例では、ルートに影響を与える時間的制約を指定していません。ただし、集配センターの可用性を設定する場合はtimesパラメーターを使用します。
この例では探索しないもう1つのパラメーターはdemandです。このパラメーターでは、車両の積載量に対応するフレキシブルユニットの配列を指定できます。たとえば、配達ジョブに[2,1]のdemand配列を指定すると、2人の乗客と1つのスーツケースが降ろされます。別の例として、集荷ジョブに[3]を設定する場合があります。この場合、3つの荷物が集荷されます。ジョブの需要は、運行管理のcapacityに対応します。この例では、出荷と容量の追跡について心配していないため、需要と容量を[0]に設定しています。
{
"jobs": [
{
"id": "A",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.620835,
"lng": -122.333295
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "B",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.623879,
"lng": -122.335212
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "C",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.620571,
"lng": -122.339785
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "D",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.62369,
"lng": -122.333005
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "E",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.622017,
"lng": -122.336911
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
}
]
}車両に関する情報
Tour Planning APIではトラックと通常の乗用車の両方のルートを計算できます。また、車両の詳細に基づいて、ツアーのコストに関する情報も提供されます。このため、リクエストを作成するときは、車両の運行管理に関する情報を事前に入力する必要があります。
運行管理プロファイルを設定する
各プロファイルには名前が必要です。一般的に、2輪以上3500kg未満のすべての車両は、車両またはバンの一部が有料道路を避けていない場合を除き、通常、タイプカーと同じルートプロファイルを共有できます。この場合、複数のプロファイルが必要になります。車両タイプはcar、truck、scooter、bicycle、pedestrian、bus、privateBusのいずれかに設定できます。トラックには走行制限があり、車高、車重、トラックの転回制限などに応じてルートが少し異なる場合があります。
{
"profiles": [
{
"name": "car_1",
"type": "car"
}
]
}車両の詳細を設定する
次に、コスト、プロファイル情報、シフトの空き状況など、車両の詳細を設定する必要があります。profileは、先に定義したプロファイルの名前に関連付けられています。プライバシー上の理由から、車両についての特定の内容を表すものであってはなりません。
shiftsは、車両の空き状況と開始位置と終了位置を設定できます。この例では、元の出発地点に戻したいので、開始位置と終了位置を同じ座標に設定します。
capacityを使用すると、未指定のユニットの配列を定義できます。たとえば、capacity [4,2]を使用すると、その車両は、4名の乗員と2つのスーツケースを積載できることを示します。積載量は、次のステップで設定するdemandに対応しています。たとえば、乗客や荷物を載せる予定がなく積載量を気にする必要がない場合、capacityを[0]に設定します。
運行管理を記述する際、amountは、同じ運用シフトとコストプロファイルに従う車両の数を表します。この例では、車両が1台のみであることを前提としています。そのため、amountを1に設定します。
{
"types": [
{
"id": "car_profile",
"profile": "car_1",
"costs": {
"distance": 0.0001,
"time": 0
},
"shifts": [
{
"start": {
"time": "2021-07-04T09:00:00Z",
"location": {
"lat": 47.623231,
"lng": -122.340168
}
},
"end": {
"time": "2021-07-04T18:00:00Z",
"location": {
"lat": 47.623231,
"lng": -122.340168
}
}
}
],
"capacity": [
0
],
"amount": 1
}
]
}リクエストを作成する
APIをコールしてみましょう。
POST https://tourplanning.hereapi.com/v3/problems?apiKey=YOUR_API_KEYそして、本文で、ジョブおよび運行管理についての情報を提供します。
{
"plan": {
"jobs": [
{
"id": "A",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.620835,
"lng": -122.333295
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "B",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.623879,
"lng": -122.335212
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "C",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.620571,
"lng": -122.339785
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "D",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.62369,
"lng": -122.333005
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "E",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.622017,
"lng": -122.336911
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
}
]
},
"fleet": {
"types": [
{
"id": "car_profile",
"profile": "car_1",
"costs": {
"distance": 0.0001,
"time": 0
},
"shifts": [
{
"start": {
"time": "2021-07-04T10:00:00.000Z",
"location": {
"lat": 47.623231,
"lng": -122.340168
}
},
"end": {
"time": "2021-07-04T12:00:00.000Z",
"location": {
"lat": 47.623231,
"lng": -122.340168
}
}
}
],
"capacity": [
0
],
"amount": 1
}
],
"profiles": [
{
"name": "car_1",
"type": "car"
}
]
}
}レスポンスを評価する
下記のレスポンスは、各停車地を訪問する最適な順序 (C->E->A->D->B)、所要時間 (504秒)、走行距離 (2186メートル) などを示します。
{
"statistic": {
"cost": 0.21860000000000002,
"distance": 2186,
"duration": 504,
"times": {
"driving": 504,
"serving": 0,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "car_profile",
"typeId": "car_profile",
"stops": [
{
"location": {
"lat": 47.623231,
"lng": -122.340168
},
"time": {
"arrival": "2021-07-04T10:00:00Z",
"departure": "2021-07-04T10:00:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 47.620571,
"lng": -122.339785
},
"time": {
"arrival": "2021-07-04T10:00:49Z",
"departure": "2021-07-04T10:00:49Z"
},
"load": [
0
],
"activities": [
{
"jobId": "C",
"type": "delivery"
}
],
"distance": 314
},
{
"location": {
"lat": 47.622017,
"lng": -122.336911
},
"time": {
"arrival": "2021-07-04T10:02:18Z",
"departure": "2021-07-04T10:02:18Z"
},
"load": [
0
],
"activities": [
{
"jobId": "E",
"type": "delivery"
}
],
"distance": 696
},
{
"location": {
"lat": 47.620835,
"lng": -122.333295
},
"time": {
"arrival": "2021-07-04T10:03:44Z",
"departure": "2021-07-04T10:03:44Z"
},
"load": [
0
],
"activities": [
{
"jobId": "A",
"type": "delivery"
}
],
"distance": 1099
},
{
"location": {
"lat": 47.62369,
"lng": -122.333005
},
"time": {
"arrival": "2021-07-04T10:05:01Z",
"departure": "2021-07-04T10:05:01Z"
},
"load": [
0
],
"activities": [
{
"jobId": "D",
"type": "delivery"
}
],
"distance": 1436
},
{
"location": {
"lat": 47.623879,
"lng": -122.335212
},
"time": {
"arrival": "2021-07-04T10:06:33Z",
"departure": "2021-07-04T10:06:33Z"
},
"load": [
0
],
"activities": [
{
"jobId": "B",
"type": "delivery"
}
],
"distance": 1741
},
{
"location": {
"lat": 47.623231,
"lng": -122.340168
},
"time": {
"arrival": "2021-07-04T10:08:24Z",
"departure": "2021-07-04T10:08:24Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 2183
}
],
"statistic": {
"cost": 0.21860000000000002,
"distance": 2186,
"duration": 504,
"times": {
"driving": 504,
"serving": 0,
"waiting": 0,
"break": 0
}
}
}
]
}
次のステップ
詳細については、以下を参照してください。
- Submit a Vehicle Routing Problem to solve it synchronously (車両ルート検索問題を送信して同期的に解決する)
- Submit a Vehicle Routing Problem to solve it asynchronously (車両ルート検索問題を送信して非同期的に解決する)
26 日前の更新