ラストマイルの配達時間枠を伴う VRP

顧客訪問が特定の時間枠にのみ可能である場合、ラストマイルの配達問題を解決するには、特定の時間を考慮する必要があることがよくあります。このような問題は、時間枠を伴う車両ルーティング問題(VRPTW)と呼ばれ、ほとんどの配送サービスで広く発生している問題です。 この問題を解決するには、該当する問題に含まれる他のすべての制約とともに、タイミング制約も考慮する必要があります。

ジョブごとに 1 つの時間枠

車両が異なる時間枠に 2 つの配達ジョブを実行する必要がある状況を確認してみましょう。

  • job_1 は 9:00 ~ 18:00 の間
  • job_2 は 10:00 ~ 16:00の間

車両のシフト時間が 8 時から 18 時までの 10 時間であると仮定します。

ここで、各作業には 1 つの時間枠があり、車両の総走行時間を最小限に抑えて、指定された時間枠内にその場所に到着することを目標としています。 この場合、極めて重要な条件は、ジョブの時間枠だけでなく、正確なシフトの開始時間と終了時間も指定することです。 shiftTime プロパティは、車両タイプの最大許容作業時間を定義します。 車両に休憩が定義されている場合、休憩時間が shiftTime に追加されます。 今回の場合、車種は休憩なしで10時間のシフトなので、合計shiftTimeは10時間と定義されます。

VehicleShift の プロパティstart.time および end.time は、車両シフトが割り当てられる時間枠の下限および上限を定義します。車両は、start.time の前に作業を開始できません。または、end.time の後で作業を終了できません。 start.time および end.time は、車両が配達を開始および終了する場所であり、ラストマイルの配達シナリオでは通常、荷物が車両に積み込まれる場所であるデポの、開始時間および終了時間であると想像できます。

同時に、start.timeend.time は、定義された shiftTime を上書きできます。つまり、プロパティshiftTime によって定義された時間が start.time ~ end.time の間の時間間隔よりも長い場合、車両の最大作業時間が短縮され、その時間間隔を超えることはありません。

{
  "fleet": {
    "types": [
      {
        "id": "2695492ea0a5",
        "profile": "car_1",
        "costs": {
          "fixed": 5.0,
          "distance": 0.00,
          "time": 0.02
        },
        "shifts": [
          {
            "start": {
              "time": "2021-07-13T08:00:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            },
            "end": {
              "time": "2021-07-13T18:00:00Z",
              "location": {
                "lat": 52.540850339546864,
                "lng": 13.435575785242161
              }
            }
          }
        ],
        "capacity": [
          10
        ],
        "amount": 1
      }
    ],
    "profiles": [
      {
        "type": "car",
        "name": "car_1"
      }
    ]
  },
  "plan": {
    "jobs": [
      {
        "id": "job_1",
        "tasks": {
          "deliveries": [
            {
              "places": [
                {
                  "times": [
                    [
                      "2021-07-13T09:00:00Z",
                      "2021-07-13T18:00:00Z"
                    ]
                  ],
                  "location": {
                    "lat": 52.605284383450964,
                    "lng": 13.293433615477289
                  },
                  "duration": 1140
                }
              ],
              "demand": [
                2
              ]
            }
          ]
        }
      },
      {
        "id": "job_2",
        "tasks": {
          "deliveries": [
            {
              "places": [
                {
                  "times": [
                    [
                      "2021-07-13T10:00:00Z",
                      "2021-07-13T16:00:00Z"
                    ]
                  ],
                  "location": {
                    "lat": 52.48000596392929,
                    "lng": 13.458654687378955
                  },
                  "duration": 1020
                }
              ],
              "demand": [
                2
              ]
            }
          ]
        }
      }
    ]
  }
}

このような問題の解決策は次のようになります。

{
    "statistic": {
        "cost": 144.94,
        "distance": 51941,
        "duration": 6997,
        "times": {
            "driving": 4837,
            "serving": 2160,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "2695492ea0a5_1",
            "typeId": "2695492ea0a5",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-07-13T08:00:00Z",
                        "departure": "2021-07-13T08:43:48Z"
                    },
                    "load": [
                        4
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.60528438345096,
                        "lng": 13.293433615477287
                    },
                    "time": {
                        "arrival": "2021-07-13T09:06:09Z",
                        "departure": "2021-07-13T09:25:09Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.48000596392929,
                        "lng": 13.458654687378957
                    },
                    "time": {
                        "arrival": "2021-07-13T10:00:00Z",
                        "departure": "2021-07-13T10:17:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "job_3",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.540850339546864,
                        "lng": 13.43557578524216
                    },
                    "time": {
                        "arrival": "2021-07-13T10:40:25Z",
                        "departure": "2021-07-13T10:40:25Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 144.94,
                "distance": 51941,
                "duration": 6997,
                "times": {
                    "driving": 4837,
                    "serving": 2160,
                    "waiting": 0,
                    "break": 0
                }
            }
        }
    ]
}

このソリューションでは、総コスト、距離、所要時間、設定した時間枠を考慮したジョブの実行順序など、系統立ったツアーの統計情報を確認できます。

ジョブごとの複数時間枠

クライアントの特定の要件により、 1 日以内に複数の時間枠でジョブを実行できる場合があります。この場合、最適化のための選択肢が増え、ツアーの計画時に考慮する必要があります。この場合、ジョブの時間枠が重複しないようにする必要があり、したがって、時間枠の開始時間と終了時間が別のジョブの時間枠に含まれていてはいけません。

車両が異なる時間に 2 つのジョブを実行する必要がある状況について考えてみましょう。

  • job_1 は 9:00 ~ 11:00 、または 16:00 ~ 19:00 の間
  • Job_2 は 11:00 ~ 14:00 、または 17:00 ~ 19:00 の間

車両のシフト時間が 8 時から 18 時までの 10 時間であると仮定します。 ここで、各ジョブには、2 つの時間枠があります。

この場合、車両のシフト時間は job_1 の両方の時間枠にマッチしますが、job_2 は最初の時間枠にのみ部分的にマッチします。このため、解決策では、これらの制約条件を考慮して、車両のより適切なルートを計算します。

{
  "fleet": {
    "types": [
      {
        "id": "2695492ea0a5",
        "profile": "car_1",
        "costs": {
          "fixed": 5.0,
          "distance": 0.007,
          "time": 0.02
        },
        "shifts": [
          {
            "start": {
              "time": "2021-07-13T08:00:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            },
            "end": {
              "time": "2021-07-13T18:00:00Z",
              "location": {
                "lat": 52.540850339546864,
                "lng": 13.435575785242161
              }
            }
          }
        ],
        "capacity": [
          5
        ],
        "amount": 1
      }
    ],
    "profiles": [
      {
        "type": "car",
        "name": "car_1"
      }
    ]
  },
  "plan": {
    "jobs": [
      {
        "id": "job_1",
        "tasks": {
          "pickups": [
            {
              "places": [
                {
                  "times": [
                    [
                      "2021-07-13T09:00:00Z",
                      "2021-07-13T11:00:00Z"
                    ],
                    [
                      "2021-07-13T16:00:00Z",
                      "2021-07-13T19:00:00Z"
                    ]
                  ],
                  "location": {
                    "lat": 52.605284383450964,
                    "lng": 13.293433615477289
                  },
                  "duration": 1140
                }
              ],
              "demand": [
                2
              ]
            }
          ]
        }
      },
      {
        "id": "job_2",
        "tasks": {
          "pickups": [
            {
              "places": [
                {
                  "times": [
                    [
                      "2021-07-13T11:00:00Z",
                      "2021-07-13T14:00:00Z"
                    ],
                    [
                      "2021-07-13T17:00:00Z",
                      "2021-07-13T19:00:00Z"
                    ]
                  ],
                  "location": {
                    "lat": 52.54217501128922,
                    "lng": 13.31486008054587
                  },
                  "duration": 120
                }
              ],
              "demand": [
                2
              ]
            }
          ]
        }
      }
    ]
  }
}

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

{
    "statistic": {
        "cost": 334.486,
        "distance": 33638,
        "duration": 4701,
        "times": {
            "driving": 3441,
            "serving": 1260,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "2695492ea0a5_1",
            "typeId": "2695492ea0a5",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-07-13T08:00:00Z",
                        "departure": "2021-07-13T10:07:02Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.60528438345096,
                        "lng": 13.293433615477287
                    },
                    "time": {
                        "arrival": "2021-07-13T10:29:23Z",
                        "departure": "2021-07-13T10:48:23Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.54217501128922,
                        "lng": 13.31486008054587
                    },
                    "time": {
                        "arrival": "2021-07-13T11:00:00Z",
                        "departure": "2021-07-13T11:02:00Z"
                    },
                    "load": [
                        4
                    ],
                    "activities": [
                        {
                            "jobId": "job_2",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.540850339546864,
                        "lng": 13.43557578524216
                    },
                    "time": {
                        "arrival": "2021-07-13T11:25:23Z",
                        "departure": "2021-07-13T11:25:23Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 334.486,
                "distance": 33638,
                "duration": 4701,
                "times": {
                    "driving": 3441,
                    "serving": 1260,
                    "waiting": 0,
                    "break": 0
                }
            }
        }
    ]
}

これにより、総コスト、走行距離、所要時間などの定期的なツアーの統計情報、および各ジョブに設定した両方の時間枠を考慮したジョブの実行順序を確認できます。

時間枠がシフト終了に近すぎるため、割り当てられていないジョブ

時間枠が車両シフトの終了時間に近すぎるために、車両にジョブを割り当てることができない状況に遭遇することがあります。 たとえば、作業時間枠が 16:00 ~ 18:00 で、車両シフトの終了時間が 19:00 の場合です。 このような状況では、ジョブは割り当てられず、それぞれのメッセージが通知されます。

車両が異なる時間に 2 つのジョブを実行する必要がある状況について考えてみましょう。

  • job_1 は 9:00 ~ 19:00 の間
  • job_2 は 17:45 ~ 18:30 の間

車両のシフト時間が 8 時から 18 時までの 10 時間であると仮定します。

{
  "fleet": {
    "types": [
      {
        "id": "2695492ea0a5",
        "profile": "car_1",
        "costs": {
          "fixed": 5.0,
          "distance": 0.007,
          "time": 0.02
        },
        "shifts": [
          {
            "start": {
              "time": "2021-07-13T08:00:00Z",
              "location": {
                "lat": 52.530971,
                "lng": 13.384915
              }
            },
            "end": {
              "time": "2021-07-13T18:00:00Z",
              "location": {
                "lat": 52.540850339546864,
                "lng": 13.435575785242161
              }
            }
          }
        ],
        "capacity": [
          5
        ],
        "amount": 1
      }
    ],
    "profiles": [
      {
        "type": "car",
        "name": "car_1"
      }
    ]
  },
  "plan": {
    "jobs": [
      {
        "id": "job_1",
        "tasks": {
          "pickups": [
            {
              "places": [
                {
                  "times": [
                    [
                      "2021-07-13T09:00:00Z",
                      "2021-07-13T19:00:00Z"
                    ]
                  ],
                  "location": {
                    "lat": 52.605284383450964,
                    "lng": 13.293433615477289
                  },
                  "duration": 1140
                }
              ],
              "demand": [
                2
              ]
            }
          ]
        }
      },
      {
        "id": "job_2",
        "tasks": {
          "pickups": [
            {
              "places": [
                {
                  "times": [
                    [
                      "2021-07-13T17:50:00Z",
                      "2021-07-13T18:30:00Z"
                    ]
                  ],
                  "location": {
                    "lat": 52.54217501128922,
                    "lng": 13.31486008054587
                  },
                  "duration": 120
                }
              ],
              "demand": [
                2
              ]
            }
          ]
        }
      }
    ]
  }
}

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

{
    "statistic": {
        "cost": 300.415,
        "distance": 30005,
        "duration": 4269,
        "times": {
            "driving": 3129,
            "serving": 1140,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "2695492ea0a5_1",
            "typeId": "2695492ea0a5",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-07-13T08:00:00Z",
                        "departure": "2021-07-13T08:37:39Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.60528438345096,
                        "lng": 13.293433615477287
                    },
                    "time": {
                        "arrival": "2021-07-13T09:00:00Z",
                        "departure": "2021-07-13T09:19:00Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.540850339546864,
                        "lng": 13.43557578524216
                    },
                    "time": {
                        "arrival": "2021-07-13T09:48:48Z",
                        "departure": "2021-07-13T09:48:48Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 300.415,
                "distance": 30005,
                "duration": 4269,
                "times": {
                    "driving": 3129,
                    "serving": 1140,
                    "waiting": 0,
                    "break": 0
                }
            }
        }
    ],
    "unassigned": [
        {
            "jobId": "job_2",
            "reasons": [
                {
                    "code": "TIME_WINDOW_CONSTRAINT",
                    "description": "cannot be visited within time window"
                }
            ]
        }
    ]
}

このソリューションでは、総コスト、距離、所要時間、時間枠を考慮したジョブの実行順序など、定期的なツアーの統計情報を確認できます。 時間枠が車両シフト終了時間に近いため、ここでは 1 つのジョブを実行できず、また、その旨メッセージが返されます。

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

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