巡回セールスマンのProblems

巡回セールスマンのProblemsの解決方法を確認してみましょう。一連の場所を指定して、各場所を訪問する最短ルートを見つけ、元の出発地点に戻ります。

巡回セールスマンのProblems
図 1. 巡回セールスマンのProblems

データを収集してリクエストを作成

リクエスト URL の内容 :

POST https://tourplanning.hereapi.com/v3/problems

結果を計算するには、次の情報を入力する必要があります。

  • 出発地
  • 訪問する場所の座標
  • 車両に関する情報

認証

Tour Planning API は、 API Key と Bearer Token の両方を使用した認証をサポートしています 無料で利用開始するには、アカウントを作成して API キー を取得します。 その他の認証方法については、『 Identity & 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 輪以上 3500 kg 未満のすべての車両は、車両またはバンの一部が有料道路を避けていない場合を除き、通常、car タイプと同じルートプロファイルを共有できます。 その条件が該当する場合、複数のプロファイルが必要になります。 車両タイプは car、 truck、 scooter、 bicycle または pedestrian のいずれかに設定できます。 トラックには運行の制限があり、トラックの高さ、重量、および転回の制限といった事に対応するため、ルートは少し異なった物になる場合もあります。

{
  "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"
            }
          ]
        },
        {
          "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"
            }
          ]
        },
        {
          "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"
            }
          ]
        },
        {
          "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"
            }
          ]
        },
        {
          "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"
            }
          ]
        },
        {
          "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"
            }
          ]
        },
        {
          "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"
            }
          ]
        }
      ],
      "statistic": {
        "cost": 0.21860000000000002,
        "distance": 2186,
        "duration": 504,
        "times": {
          "driving": 504,
          "serving": 0,
          "waiting": 0,
          "break": 0
        }
      }
    }
  ]
}
巡回セールスマンのProblemsへの解決策
図 2. 巡回セールスマンのProblemsへの解決策

「」に一致する結果は 件です

    「」に一致する結果はありません