容量制約を伴う VRP

HERE では、需要、積載量の相互関係、追加の積載量パラメータなどの特定の制約を使用して、ラストマイル配送の問題を解決する方法を模索しています。

需要とキャパシティの相関関係

容量制約を伴う車両の取り回しの問題を解決するには、車両の取り回し時に車両の積載量を考慮する必要があります。 作業の需要と車両の積載量を考慮して、複数の場所を訪問する複数の車両に最適なルートを見つける必要がある状況を考えてみましょう。 すべての作業の総需要がすべての車両の総積載量を超えない場合、この特定の問題を解決できるものと想定する必要があります。

4 つの場所と 2 台の車両があるとします。 各場所には、集荷または配達するアイテムの数量に対応するジョブの特定の需要があります (5,4,2,3) 。 また、各車両の最大積載量は 10 です。 車両の積載量は、車両が保持できる最大積載量です。 車両が運搬できる荷物の合計量が、その積載量を超えることはありません。

ここで解決する必要のある問題は、車両の総走行距離が最短となり、車両が運搬している総量がその車両の積載量に適しているルートの車両への割り当てを見つけることです。私たちは、需要や積載量に対する単位を指定しません。単位は、事業毎、組織毎に定義されるものです。(集荷または配達される品目の重量や量など)。したがって、需要及び積載量には正の数のみを入力する必要があります。

この問題の解決策を計算するには、次の情報を提供する必要があります。

  • 車両に関する情報(開始地点と終了地点、コスト、シフト、積載量)

  • ジョブに関する情報 ( 場所、期間、および需要 )

この例では、次の主な制約があります。

Location : 4.

各場所での需要 : 5 、 4 、 2 、 3

車両 : 2.

各車両の積載量 : 10 、 10.

車両情報の設定

この例では、運行管理 プロファイル、各車両コスト、シフトフィールドの開始時間と終了時間、それらの積載量と数を指定しました。 積載量については 10、数は 2 を指定しています。つまり、このソリューションでは同じ積載量の車両を最大 2 台使用できます。 以下の例では、特に車両タイプについて、距離と時間の両方で 0 より大きいコストを指定しています。 その結果、このアルゴリズムによって、指定した 2 台の車両の走行距離とツアー時間の両方が最適化されることが予想されます。

{ 
  "fleet": { 
    "types": [ 
      { 
        "id": "069ea42ae3e9", 
        "profile": "car_1", 
        "costs": { 
          "fixed": 5.0, 
          "distance": 0.007, 
          "time": 0.002
        }, 
        "shifts": [ 
          { 
            "start": { 
              "time": "2021-07-10T08:37:00Z", 
              "location": { 
                "lat": 52.530971, 
                "lng": 13.384915 
              } 
            }, 
            "end": { 
              "time": "2021-07-10T17:37:00Z", 
              "location": { 
                "lat": 52.5281430596138, 
                "lng": 13.36381375834569 
              } 
            } 
          } 
        ], 
        "capacity": [ 
          10 
        ], 
        "amount": 2 
      } 
    ], 
    "profiles": [ 
      { 
        "type": "car", 
        "name": "car_1" 
      }

ジョブ情報の設定

前述のように、 4 つのジョブを実行します。 ジョブごとに、そのタイプ ( 集荷または配達 ) 、場所、期間、需要を指定します。 この特定のケースで重要なパラメータは、上記車両に指定した積載量と直接関連するので、「需要」です。

"plan": { 
    "jobs": [ 
      { 
        "id": "job_1", 
        "tasks": { 
          "pickups": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.484104043903585, 
                    "lng": 13.386732295521801 
                  }, 
                  "duration": 840 
                } 
              ], 
              "demand": [ 
                5 
              ] 
            } 
          ] 
        } 
      },

Problems

上記の4 つの配達ジョブを伴う例について、問題を設定しましょう。

{ 
  "fleet": { 
    "types": [ 
      { 
        "id": "d3e7bb8d20c5", 
        "profile": "car_1", 
        "costs": { 
          "fixed": 5.0, 
          "distance": 0.007, 
          "time": 0.05
        }, 
        "shifts": [ 
          { 
            "start": { 
              "time": "2021-08-27T08:03:00Z", 
              "location": { 
                "lat": 52.530971, 
                "lng": 13.384915 
              } 
            }, 
            "end": { 
              "time": "2021-08-27T19:03:00Z", 
              "location": { 
                "lat": 52.43119084052164, 
                "lng": 13.39255783460401 
              } 
            } 
          } 
        ], 
        "capacity": [ 
          10 
        ], 
        "amount": 2 
      } 
    ], 
    "profiles": [ 
      { 
        "type": "car", 
        "name": "car_1" 
      } 
    ] 
  }, 
  "plan": { 
    "jobs": [ 
      { 
        "id": "job_1", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.484104043903585, 
                    "lng": 13.386732295521801 
                  }, 
                  "duration": 840 
                } 
              ], 
              "demand": [ 
                5 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_2", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.463735398833514, 
                    "lng": 13.303616544747735 
                  }, 
                  "duration": 600 
                } 
              ], 
              "demand": [ 
                4 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_3", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.542308727849075, 
                    "lng": 13.350779211496564 
                  }, 
                  "duration": 60 
                } 
              ], 
              "demand": [ 
                2 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_4", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.48460493700661, 
                    "lng": 13.315372249087625 
                  }, 
                  "duration": 1140 
                } 
              ], 
              "demand": [ 
                3 
              ] 
            } 
          ] 
        } 
      } 
    ] 
  } 
}

Solution

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

{
    "statistic": {
        "cost": 679.9580000000001,
        "distance": 39944,
        "duration": 7807,
        "times": {
            "driving": 5167,
            "serving": 2640,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "d3e7bb8d20c5_2",
            "typeId": "d3e7bb8d20c5",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-08-27T08:03:00Z",
                        "departure": "2021-08-27T08:03:00Z"
                    },
                    "load": [
                        7
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.48460493700661,
                        "lng": 13.315372249087623
                    },
                    "time": {
                        "arrival": "2021-08-27T08:21:09Z",
                        "departure": "2021-08-27T08:40:09Z"
                    },
                    "load": [
                        4
                    ],
                    "activities": [
                        {
                            "jobId": "job_4",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.463735398833514,
                        "lng": 13.303616544747737
                    },
                    "time": {
                        "arrival": "2021-08-27T08:46:35Z",
                        "departure": "2021-08-27T08:56:35Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "job_2",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.43119084052164,
                        "lng": 13.39255783460401
                    },
                    "time": {
                        "arrival": "2021-08-27T09:14:16Z",
                        "departure": "2021-08-27T09:14:16Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 364.68,
                "distance": 20840,
                "duration": 4276,
                "times": {
                    "driving": 2536,
                    "serving": 1740,
                    "waiting": 0,
                    "break": 0
                }
            }
        },
        {
            "vehicleId": "d3e7bb8d20c5_1",
            "typeId": "d3e7bb8d20c5",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-08-27T08:03:00Z",
                        "departure": "2021-08-27T08:03:00Z"
                    },
                    "load": [
                        7
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.542308727849075,
                        "lng": 13.350779211496564
                    },
                    "time": {
                        "arrival": "2021-08-27T08:12:53Z",
                        "departure": "2021-08-27T08:13:53Z"
                    },
                    "load": [
                        5
                    ],
                    "activities": [
                        {
                            "jobId": "job_3",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.484104043903585,
                        "lng": 13.3867322955218
                    },
                    "time": {
                        "arrival": "2021-08-27T08:32:38Z",
                        "departure": "2021-08-27T08:46:38Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.43119084052164,
                        "lng": 13.39255783460401
                    },
                    "time": {
                        "arrival": "2021-08-27T09:01:51Z",
                        "departure": "2021-08-27T09:01:51Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 315.278,
                "distance": 19104,
                "duration": 3531,
                "times": {
                    "driving": 2631,
                    "serving": 900,
                    "waiting": 0,
                    "break": 0
                }
            }
        }
    ]
}

このレスポンスから、各場所を最も適切な車両で訪問する最も適切な順序と、走行距離と、個々のジョブを実行する車両の積載量に適合する車両総積載量と、運転、サービス、待ち、シフト休憩に対する正確なタイミングを含む総運行時間を確認できます。

異なるジョブタイプを含む問題

1 つの問題で複数のジョブの種類 ( 集荷と配達 ) を設定する場合は、次のように問題を設定する必要があります。

{ 
  "fleet": { 
    "types": [ 
      { 
        "id": "d3e7bb8d20c5", 
        "profile": "car_1", 
        "costs": { 
          "fixed": 5.0, 
          "distance": 0.007, 
          "time": 0.05
        }, 
        "shifts": [ 
          { 
            "start": { 
              "time": "2021-08-27T08:03:00Z", 
              "location": { 
                "lat": 52.530971, 
                "lng": 13.384915 
              } 
            }, 
            "end": { 
              "time": "2021-08-27T19:03:00Z", 
              "location": { 
                "lat": 52.43119084052164, 
                "lng": 13.39255783460401 
              } 
            } 
          } 
        ], 
        "capacity": [ 
          10 
        ], 
        "amount": 2 
      } 
    ], 
    "profiles": [ 
      { 
        "type": "car", 
        "name": "car_1" 
      } 
    ] 
  }, 
  "plan": { 
    "jobs": [ 
      { 
        "id": "job_1", 
        "tasks": { 
          "pickups": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.484104043903585, 
                    "lng": 13.386732295521801 
                  }, 
                  "duration": 840 
                } 
              ], 
              "demand": [ 
                5 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_2", 
        "tasks": { 
          "pickups": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.463735398833514, 
                    "lng": 13.303616544747735 
                  }, 
                  "duration": 600 
                } 
              ], 
              "demand": [ 
                4 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_3", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.542308727849075, 
                    "lng": 13.350779211496564 
                  }, 
                  "duration": 60 
                } 
              ], 
              "demand": [ 
                2 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_4", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.48460493700661, 
                    "lng": 13.315372249087625 
                  }, 
                  "duration": 1140 
                } 
              ], 
              "demand": [ 
                3 
              ] 
            } 
          ] 
        } 
      } 
    ] 
  } 
}

Solution

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

{
    "statistic": {
        "cost": 552.719,
        "distance": 31667,
        "duration": 6521,
        "times": {
            "driving": 3881,
            "serving": 2640,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "d3e7bb8d20c5_1",
            "typeId": "d3e7bb8d20c5",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-08-27T08:03:00Z",
                        "departure": "2021-08-27T08:03:00Z"
                    },
                    "load": [
                        5
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.542308727849075,
                        "lng": 13.350779211496564
                    },
                    "time": {
                        "arrival": "2021-08-27T08:12:53Z",
                        "departure": "2021-08-27T08:13:53Z"
                    },
                    "load": [
                        3
                    ],
                    "activities": [
                        {
                            "jobId": "job_3",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.484104043903585,
                        "lng": 13.3867322955218
                    },
                    "time": {
                        "arrival": "2021-08-27T08:32:38Z",
                        "departure": "2021-08-27T08:46:38Z"
                    },
                    "load": [
                        8
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.48460493700661,
                        "lng": 13.315372249087623
                    },
                    "time": {
                        "arrival": "2021-08-27T08:58:34Z",
                        "departure": "2021-08-27T09:17:34Z"
                    },
                    "load": [
                        5
                    ],
                    "activities": [
                        {
                            "jobId": "job_4",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.463735398833514,
                        "lng": 13.303616544747737
                    },
                    "time": {
                        "arrival": "2021-08-27T09:24:00Z",
                        "departure": "2021-08-27T09:34:00Z"
                    },
                    "load": [
                        9
                    ],
                    "activities": [
                        {
                            "jobId": "job_2",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.43119084052164,
                        "lng": 13.39255783460401
                    },
                    "time": {
                        "arrival": "2021-08-27T09:51:41Z",
                        "departure": "2021-08-27T09:51:41Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 552.719,
                "distance": 31667,
                "duration": 6521,
                "times": {
                    "driving": 3881,
                    "serving": 2640,
                    "waiting": 0,
                    "break": 0
                }
            }
        }
    ]
}

このソリューションで、最も適切な車両で集荷・配達ジョブを実行する最も適切な順序と、走行距離と、個々のジョブを実行する車両の積載量に適合する車両総積載量と、運転、サービス、待ち、シフト休憩に対する正確なタイミングを含む総運行時間を確認できます。

複数の次元

車両の積載量は複数の次元で指定できます。 この機能は、たとえば、パレット数と重量の両面でトラックが過積載になっていないことを確認する必要がある、ミドルマイルのロジスティクス企業で使用できます。 このようにして、希望する単位で表現されたアイテム数だけでなく、サイズや重量なども指定できます たとえば、トラックを使用する場合は、パレット数とその重量を指定できます。 積載量の単位は累積する必要があります。つまり、長さや高さなどの寸法は指定できませんが、ユニットの重量などを使用できます。 ジョブの需要は同じ次元で指定され、容量データを考慮して計算されます。 このような制約を設定するには、車両の積載量とジョブの需要の両方を、コンマで区切って正確に同じ順序で指定する必要があります。

以下では、積載量がそれぞれ 50 ユニットと 20 ユニットの 2 台の車両で、経路指定の問題に対する制約を指定する方法を説明します。 この問題では、 2 つの集荷ジョブと 2 つの配達ジョブを実行する必要があります。ジョブの需要( 50 、 20 )は、車両の積載量と同じ順序で指定されます。

{ 
  "fleet": { 
    "types": [ 
      { 
        "id": "069ea42ae3e9", 
        "profile": "car_1", 
        "costs": { 
          "fixed": 10.0, 
          "distance": 0.07, 
          "time": 0.1 
        }, 
        "shifts": [ 
          { 
            "start": { 
              "time": "2021-07-10T08:37:00Z", 
              "location": { 
                "lat": 52.530971, 
                "lng": 13.384915 
              } 
            }, 
            "end": { 
              "time": "2021-07-10T17:37:00Z", 
              "location": { 
                "lat": 52.5281430596138, 
                "lng": 13.36381375834569 
              } 
            } 
          } 
        ], 
        "capacity": [ 
          50,20 
        ], 
        "amount": 2 
      } 
    ], 
    "profiles": [ 
      { 
        "type": "car", 
        "name": "car_1" 
      } 
    ] 
  }, 
  "plan": { 
    "jobs": [ 
      { 
        "id": "job_1", 
        "tasks": { 
          "pickups": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.484104043903585, 
                    "lng": 13.386732295521801 
                  }, 
                  "duration": 840 
                } 
              ], 
              "demand": [ 
                50, 20 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_2", 
        "tasks": { 
          "pickups": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.463735398833514, 
                    "lng": 13.303616544747735 
                  }, 
                  "duration": 600 
                } 
              ], 
              "demand": [ 
                50, 20 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_3", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.542308727849075, 
                    "lng": 13.350779211496564 
                  }, 
                  "duration": 60 
                } 
              ], 
              "demand": [ 
                50, 20 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_4", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.48460493700661, 
                    "lng": 13.315372249087625 
                  }, 
                  "duration": 1140 
                } 
              ], 
              "demand": [ 
                50, 20 
              ] 
            } 
          ] 
        } 
      } 
    ] 
  } 
}

このような問題の解決策を確認すると、 2 台の車両が、その積載量と 2 つのディメンションで指定された作業要求に基づいて集荷と配達の作業を行うことがわかります。

{
    "statistic": {
        "cost": 3663.9000000000005,
        "distance": 41390,
        "duration": 7466,
        "times": {
            "driving": 4826,
            "serving": 2640,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "069ea42ae3e9_2",
            "typeId": "069ea42ae3e9",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-07-10T08:37:00Z",
                        "departure": "2021-07-10T08:37:00Z"
                    },
                    "load": [
                        50,
                        20
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.542308727849075,
                        "lng": 13.350779211496564
                    },
                    "time": {
                        "arrival": "2021-07-10T08:46:29Z",
                        "departure": "2021-07-10T08:47:29Z"
                    },
                    "load": [
                        0,
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "job_3",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.484104043903585,
                        "lng": 13.3867322955218
                    },
                    "time": {
                        "arrival": "2021-07-10T09:04:35Z",
                        "departure": "2021-07-10T09:18:35Z"
                    },
                    "load": [
                        50,
                        20
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.5281430596138,
                        "lng": 13.36381375834569
                    },
                    "time": {
                        "arrival": "2021-07-10T09:30:33Z",
                        "departure": "2021-07-10T09:30:33Z"
                    },
                    "load": [
                        0,
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 1642.0500000000002,
                "distance": 18725,
                "duration": 3213,
                "times": {
                    "driving": 2313,
                    "serving": 900,
                    "waiting": 0,
                    "break": 0
                }
            }
        },
        {
            "vehicleId": "069ea42ae3e9_1",
            "typeId": "069ea42ae3e9",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-07-10T08:37:00Z",
                        "departure": "2021-07-10T08:37:00Z"
                    },
                    "load": [
                        50,
                        20
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.48460493700661,
                        "lng": 13.315372249087623
                    },
                    "time": {
                        "arrival": "2021-07-10T08:54:30Z",
                        "departure": "2021-07-10T09:13:30Z"
                    },
                    "load": [
                        0,
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "job_4",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.463735398833514,
                        "lng": 13.303616544747737
                    },
                    "time": {
                        "arrival": "2021-07-10T09:19:48Z",
                        "departure": "2021-07-10T09:29:48Z"
                    },
                    "load": [
                        50,
                        20
                    ],
                    "activities": [
                        {
                            "jobId": "job_2",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.5281430596138,
                        "lng": 13.36381375834569
                    },
                    "time": {
                        "arrival": "2021-07-10T09:47:53Z",
                        "departure": "2021-07-10T09:47:53Z"
                    },
                    "load": [
                        0,
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 2021.8500000000001,
                "distance": 22665,
                "duration": 4253,
                "times": {
                    "driving": 2513,
                    "serving": 1740,
                    "waiting": 0,
                    "break": 0
                }
            }
        }
    ]
}

需要が積載量を超えている場合

輸送しようとする荷物の合計量 ( 需要 ) が利用可能な車両の総積載量を超える状況を考えてみましょう。 この状況では、優先度が指定されている場合、解決策は主にジョブの優先度に基づきます。 ジョブに優先度が指定されていない場合、すべての優先度が等しいことを意味します。そのため、最適化は挿入コスト ( 場所間の距離、待機時間、処理時間 ) に基づいて行われます。

3 ユニット分の積載量の車両を保有しているが、すべての作業の合計需要は 4 ユニットであるとします。 これらのすべてのジョブの場所が異なり、各ジョブの需要が 1 を超えていません。 このようなシナリオの問題リクエストは、次のようになります。

{ 
  "fleet": { 
    "types": [ 
      { 
        "id": "d3e7bb8d20c5", 
        "profile": "car_1", 
        "costs": { 
          "fixed": 10.0, 
          "distance": 0.005, 
          "time": 0.07 
        }, 
        "shifts": [ 
          { 
            "start": { 
              "time": "2021-08-27T08:03:00Z", 
              "location": { 
                "lat": 52.530971, 
                "lng": 13.384915 
              } 
            }, 
            "end": { 
              "time": "2021-08-27T19:03:00Z", 
              "location": { 
                "lat": 52.43119084052164, 
                "lng": 13.39255783460401 
              } 
            } 
          } 
        ], 
        "capacity": [ 
          5 
        ], 
        "amount": 1 
      } 
    ], 
    "profiles": [ 
      { 
        "type": "car", 
        "name": "car_1" 
      } 
    ] 
  }, 
  "plan": { 
    "jobs": [ 
      { 
        "id": "job_1", 
        "tasks": { 
          "pickups": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.484104043903585, 
                    "lng": 13.386732295521801 
                  }, 
                  "duration": 840 
                } 
              ], 
              "demand": [ 
                1 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_2", 
        "tasks": { 
          "pickups": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.463735398833514, 
                    "lng": 13.303616544747735 
                  }, 
                  "duration": 600 
                } 
              ], 
              "demand": [ 
                1 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_3", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.542308727849075, 
                    "lng": 13.350779211496564 
                  }, 
                  "duration": 60 
                } 
              ], 
              "demand": [ 
                1 
              ] 
            } 
          ] 
        } 
      }, 
      { 
        "id": "job_4", 
        "tasks": { 
          "deliveries": [ 
            { 
              "places": [ 
                { 
                  "location": { 
                    "lat": 52.48460493700661, 
                    "lng": 13.315372249087625 
                  }, 
                  "duration": 1140 
                } 
              ], 
              "demand": [ 
                1 
              ] 
            } 
          ] 
        } 
      } 
    ] 
  }
}

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

{
    "statistic": {
        "cost": 624.8050000000001,
        "distance": 31667,
        "duration": 6521,
        "times": {
            "driving": 3881,
            "serving": 2640,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "d3e7bb8d20c5_1",
            "typeId": "d3e7bb8d20c5",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2021-08-27T08:03:00Z",
                        "departure": "2021-08-27T08:03:00Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.542308727849075,
                        "lng": 13.350779211496564
                    },
                    "time": {
                        "arrival": "2021-08-27T08:12:53Z",
                        "departure": "2021-08-27T08:13:53Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "job_3",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.484104043903585,
                        "lng": 13.3867322955218
                    },
                    "time": {
                        "arrival": "2021-08-27T08:32:38Z",
                        "departure": "2021-08-27T08:46:38Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.48460493700661,
                        "lng": 13.315372249087623
                    },
                    "time": {
                        "arrival": "2021-08-27T08:58:34Z",
                        "departure": "2021-08-27T09:17:34Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "job_4",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.463735398833514,
                        "lng": 13.303616544747737
                    },
                    "time": {
                        "arrival": "2021-08-27T09:24:00Z",
                        "departure": "2021-08-27T09:34:00Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "job_2",
                            "type": "pickup"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 52.43119084052164,
                        "lng": 13.39255783460401
                    },
                    "time": {
                        "arrival": "2021-08-27T09:51:41Z",
                        "departure": "2021-08-27T09:51:41Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 624.8050000000001,
                "distance": 31667,
                "duration": 6521,
                "times": {
                    "driving": 3881,
                    "serving": 2640,
                    "waiting": 0,
                    "break": 0
                }
            }
        }
    ]
}

このソリューションでは、車両の総コスト、所要時間、走行距離に関する情報を、各場所で最適なルートで取得できます。 同時に、超過需要のために現在のツアー内の車両が実行できなかった作業については、以下の説明とともに記載されます。 "capacity_constraint- does not fit any vehicle due to capacity" (容量の制約により、どの車両にも積載できません)

この状況では、問題の定義を再確認する必要があります。車両を追加するか、または需要に対応する積載量の車両を変更して、問題を解決してください。

高度なヒント

車両が受け取る荷物の数の制限など、他の目的にも積載量 - 需要の相互関係を使用できます。 ジョブの需要を 1 、車両の積載量を 10 などに指定すると、車両は積載量で指定された量( 10 など)を超える荷物を受け取れません。

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

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