集荷と配達の VRP

• Problem
• Solution

配達会社が、配達ルートに沿って特定の荷物や人をのせ、送り届ける必要がある場合があります。つまり、複数の荷物を特定の集荷場所から別の配達場所に移動する必要があります。 このような場合は、集荷と配達の VRP を使用できます。 このような VRP の目的は、集荷および配達の場所を訪問する車両に最適なルートを見つけることです。 このような VRP の各ジョブは、特定の集荷ポイント、対応する配達ポイント、およびそれらの場所間で輸送される需要によって定義されます。 このタイプの VRP の概念は、集荷需要が配達需要と常に等しいことを意味します。そうでない場合、問題は正しく解決されません。

この種の VRP を実際に実装する例として、 Dial-a-Ride（オンデマンド） サービスがあります。 Dial-a-Ride（オンデマンド） は、高齢者や障害のある方を対象とした、出発地から目的地までの高度な予約サービスです。 Dial-a-Ride（オンデマンド） 車両は、ローカルの固定ルートの特定のエリア内を走行します。 旅程はこのサービスエリアで開始および終了する必要があります。 このようなサービスの考えは、ポイント A からポイント B まで顧客を乗せて送り届けることです。

1 台の車両で 1 つの荷物を集荷して配達する必要がある単純なケースを考えてみましょう。 このような場合の問題は、次のようになります。

Problems

{
  "fleet": {
    "types": [
      {
        "id": "b0130d2f754d",
        "profile": "car_1",
        "costs": {
          "fixed": 5.0,
          "distance": 0.007,
          "time": 0.02
        },
        "shifts": [
          {
            "start": {
              "time": "2021-08-27T08:03:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            },
            "end": {
              "time": "2021-08-27T16:03:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            }
          }
        ],
        "capacity": [
          30
        ],
        "amount": 1
      }
    ],
    "profiles": [
      {
        "type": "car",
        "name": "car_1"
      }
    ]
  },
  "plan": {
    "jobs": [
      {
        "id": "job_1",
        "tasks": {
          "pickups": [
            {
              "places": [
                {
                  "location": {
                    "lat": 52.53090538774364,
                    "lng": 13.384692097156309
                  },
                  "duration": 840
                }
              ],
              "demand": [
                1
              ]
            }
          ],
          "deliveries": [
            {
              "places": [
                {
                  "location": {
                    "lat": 52.58919138279804,
                    "lng": 13.462161100698735
                  },
                  "duration": 1020
                }
              ],
              "demand": [
                1
              ]
            }
          ]
        }
      }
    ]
  }
}

Solution

この問題の解決策は次のとおりです。

{
    "statistic": {
        "cost": 249.22400000000002,
        "distance": 21832,
        "duration": 4570,
        "times": {
            "driving": 2710,
            "serving": 1860,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "b0130d2f754d_1",
            "typeId": "b0130d2f754d",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-08-27T08:03:00Z",
                        "departure": "2021-08-27T08:03:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.53090538774364,
                        "lng": 13.384692097156307
                    },
                    "time": {
                        "arrival": "2021-08-27T08:03:02Z",
                        "departure": "2021-08-27T08:17:02Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.58919138279804,
                        "lng": 13.462161100698737
                    },
                    "time": {
                        "arrival": "2021-08-27T08:39:07Z",
                        "departure": "2021-08-27T08:56:07Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-08-27T09:19:10Z",
                        "departure": "2021-08-27T09:19:10Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 249.22400000000002,
                "distance": 21832,
                "duration": 4570,
                "times": {
                    "driving": 2710,
                    "serving": 1860,
                    "waiting": 0,
                    "break": 0
                }
            }
        }
    ]
}

このソリューションから、総コスト、距離、期間などの問題を解決するためのルーチンの統計情報を確認できます。また、デポ、集荷、配達の場所を考慮して、荷物の集荷と配達のための計算ルートを確認できます。