マルチリロード

場合によっては、車両の容量に制限があるため、1回のツアーですべてのアイテムを配送できないことがあります。 したがって、シフト時間が許せば、より多くの品目を配送できるように、車両を複数回移動させる必要がある場合があります。 reloads この機能により、車両はデポ(またはその他の場所)に戻り、前回のトリップのすべてのタスクが完了した後で、さらに多くのアイテムを受け取ることができます。

この使用例の最も簡単な例は、特定の容量を持つ車両と総需要が容量を超えるジョブがある場合です。 車両の能力に合わないジョブの一部は、ツアーに割り当てられないことが予想されます。 したがって、車両の容量を増やしたり車両を追加したりする機会はないが、それでも既存の車両でツアーを完了する必要がある場合は、車両に対してさらに車両を追加できるようにする問題の制約にリロード オプションを追加する必要があります。 これにより、以前のタスクが完了した後に車両がツアーに追加できるようになります。 リロードは、出発倉庫、配達場所、集荷場所、またはその他の場所で行うことができます。 リロード オプションは、次のようにリロードの location とその durationを含む問題の fleet の部分に追加する必要があります。

"reloads":[
   {
       "location":{
           "lat": 52.530976,
           "lng": 13.384916
       },
       "duration":60
   },
   {
       "location":{
           "lat": 52.530976,
           "lng": 13.384916
       },
       "duration":60
   },
]

車両の容量が総作業需要(キャパシティ3、デマンド5)よりも小さい場合、つまり需要が車両の容量を超えている場合を考えてみましょう。 この場合は、リンクの容量制約を伴う VRPセクションでこのドキュメントを確認できます。 前述の例の車両がツアーを完了できるようにするには、 問題にオプションreloadsを追加します。 次の問題例では 、車両がツアーを開始した場所と同じ場所にreloads を追加しました。

Problems

{
    "fleet": {
        "types": [
            {
                "id": "e429c9c1e6df",
                "profile": "car_bd5be9a38474",
                "costs": {
                    "fixed": 6.0,
                    "distance": 0.002,
                    "time": 0.007
                },
                "shifts": [
                    {
                        "start": {
                            "time": "2022-06-01T08:05:00Z",
                            "location": {
                                "lat": 52.530971,
                                "lng": 13.384915
                            }
                        },
                        "end": {
                            "time": "2022-06-01T18:05:00Z",
                            "location": {
                                "lat": 52.530971,
                                "lng": 13.384915
                            }
                        },
                        "reloads": [
                            {
                                "location": {
                                    "lat": 52.530971,
                                    "lng": 13.384915
                                },
                                "duration": 60
                            }
                        ]
                    }
                ],
                "capacity": [
                    3
                ],
                "amount": 1
            }
        ],
        "profiles": [
            {
                "type": "car",
                "name": "car_bd5be9a38474"
            }
        ]
    },
    "plan": {
        "jobs": [
            {
                "id": "job_1",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T14:05:00Z",
                                            "2022-06-01T18:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.44664947511696,
                                        "lng": 13.484988905387555
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "job_2",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T08:05:00Z",
                                            "2022-06-01T13:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.632489506294235,
                                        "lng": 13.341605471791963
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "job_3",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T08:05:00Z",
                                            "2022-06-01T13:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.5983459422347,
                                        "lng": 13.392007658723308
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "job_4",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T08:05:00Z",
                                            "2022-06-01T12:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.577856866026835,
                                        "lng": 13.423782100910442
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "job_5",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T08:05:00Z",
                                            "2022-06-01T13:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.5983459422347,
                                        "lng": 13.392007658723308
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            }
        ]
    }
}

Solution

以下の解決策から、3つのジョブを提供し、そのすべての容量を使用した後、車両はリロード場所(私たちの場合は出発デポ)に向かい、その後ツアーに残っている最後のジョブを提供することがわかります。

{
    "statistic": {
        "cost": 273.482,
        "distance": 92161,
        "duration": 11880,
        "times": {
            "driving": 9568,
            "serving": 1560,
            "waiting": 752,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "e429c9c1e6df_1",
            "typeId": "e429c9c1e6df",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2022-06-01T08:05:00Z",
                        "departure": "2022-06-01T11:20:56Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ],
                    "distance": 0
                },
                {
                    "location": {
                        "lat": 52.577856866026835,
                        "lng": 13.423782100910442
                    },
                    "time": {
                        "arrival": "2022-06-01T11:38:11Z",
                        "departure": "2022-06-01T11:43:11Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "job_4",
                            "type": "pickup"
                        }
                    ],
                    "distance": 16100
                },
                {
                    "location": {
                        "lat": 52.5983459422347,
                        "lng": 13.392007658723308
                    },
                    "time": {
                        "arrival": "2022-06-01T11:57:43Z",
                        "departure": "2022-06-01T12:07:43Z"
                    },
                    "load": [
                        3
                    ],
                    "activities": [
                        {
                            "jobId": "job_3",
                            "type": "pickup",
                            "location": {
                                "lat": 52.5983459422347,
                                "lng": 13.392007658723308
                            },
                            "time": {
                                "start": "2022-06-01T11:57:43Z",
                                "end": "2022-06-01T12:02:43Z"
                            }
                        },
                        {
                            "jobId": "job_5",
                            "type": "pickup",
                            "location": {
                                "lat": 52.5983459422347,
                                "lng": 13.392007658723308
                            },
                            "time": {
                                "start": "2022-06-01T12:02:43Z",
                                "end": "2022-06-01T12:07:43Z"
                            }
                        }
                    ],
                    "distance": 27415
                },
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2022-06-01T12:32:18Z",
                        "departure": "2022-06-01T12:33:18Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "reload",
                            "type": "reload"
                        }
                    ],
                    "distance": 36817
                },
                {
                    "location": {
                        "lat": 52.632489506294235,
                        "lng": 13.341605471791963
                    },
                    "time": {
                        "arrival": "2022-06-01T13:05:00Z",
                        "departure": "2022-06-01T13:10:00Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "job_2",
                            "type": "pickup"
                        }
                    ],
                    "distance": 44396
                },
                {
                    "location": {
                        "lat": 52.44664947511696,
                        "lng": 13.484988905387556
                    },
                    "time": {
                        "arrival": "2022-06-01T13:52:28Z",
                        "departure": "2022-06-01T14:10:00Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "pickup"
                        }
                    ],
                    "distance": 65595
                },
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2022-06-01T14:38:56Z",
                        "departure": "2022-06-01T14:38:56Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ],
                    "distance": 82587
                }
            ],
            "statistic": {
                "cost": 273.482,
                "distance": 92161,
                "duration": 11880,
                "times": {
                    "driving": 9568,
                    "serving": 1560,
                    "waiting": 752,
                    "break": 0
                }
            },
            "shiftIndex": 0
        }
    ]
}

これが基本的にこのオプションreloadsが機能する方法ですが、場合によっては、リロードを使用するときに他の制約を考慮する必要があります。 以下では、複数のリロードがあり、さらにリロードがデポ以外の場所でも行われる問題の例を作成してみましょう。 さらに、リロード場所は日中の特定の時間に稼働するため、リロードの時間帯も考慮する必要があります。

ツアープランでは 、車両シフトごとにreloadsを最大5つまで追加できます。 それぞれの reloads は、独自の locationduration 、および times を持つことができます (オプション)。

次の例では、需要が容量を超える状況が再び発生しています(容量5と 7ジョブのリクエスト)だけでなく、リロードのための特定の時間帯もあり、車両シフト時間の制約に追加します。 また、リロードの場所を追加できますが、デポだけではありません。 この例では、リロードの1つは車両出発地(デポ)で行われ、もう1つはいずれかの作業場所で行われます。

Problems

{
    "fleet": {
        "types": [
            {
                "id": "e429c9c1e6df",
                "profile": "car_bd5be9a38474",
                "costs": {
                    "fixed": 6.0,
                    "distance": 0.002,
                    "time": 0.007
                },
                "shifts": [
                    {
                        "start": {
                            "time": "2022-06-01T08:05:00Z",
                            "location": {
                                "lat": 52.530971,
                                "lng": 13.384915
                            }
                        },
                        "end": {
                            "time": "2022-06-01T18:05:00Z",
                            "location": {
                                "lat": 52.530971,
                                "lng": 13.384915
                            }
                        },
                        "reloads": [
                            {
                                 "times": [
                                    [
                                         "2022-06-01T09:05:00Z",
                                         "2022-06-01T13:05:00Z"
                                    ]
                                ],
                                "location": {
                                    "lat": 52.530971,
                                    "lng": 13.384915
                                },
                                "duration": 60
                            },
                            {
                                "times": [
                                    [
                                        "2022-06-01T13:05:00Z",
                                        "2022-06-01T18:05:00Z"
                                    ]
                                ],
                                "location": {
                                    "lat": 52.57541509905306,
                                    "lng": 13.409878314747719
                                },
                                "duration": 60
                            }
                        ]
                    }
                ],
                "capacity": [
                    5
                ],
                "amount": 1
            }
        ],
        "profiles": [
            {
                "type": "car",
                "name": "car_bd5be9a38474"
            }
        ]
    },
    "plan": {
        "jobs": [
            {
                "id": "job_1",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T09:05:00Z",
                                            "2022-06-01T13:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.44664947511696,
                                        "lng": 13.484988905387555
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "job_2",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T08:05:00Z",
                                            "2022-06-01T13:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.632489506294235,
                                        "lng": 13.341605471791963
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "job_3",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T08:05:00Z",
                                            "2022-06-01T13:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.5983459422347,
                                        "lng": 13.392007658723308
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "job_4",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T08:05:00Z",
                                            "2022-06-01T12:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.577856866026835,
                                        "lng": 13.423782100910442
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "job_5",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T09:05:00Z",
                                            "2022-06-01T14:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.57541509905306,
                                        "lng": 13.409878314747719
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "job_6",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T09:05:00Z",
                                            "2022-06-01T14:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.486595664301646,
                                        "lng": 13.423728674699783
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            },
            {
                "id": "job_7",
                "tasks": {
                    "pickups": [
                        {
                            "places": [
                                {
                                    "times": [
                                        [
                                            "2022-06-01T08:05:00Z",
                                            "2022-06-01T13:05:00Z"
                                        ]
                                    ],
                                    "location": {
                                        "lat": 52.471783668934606,
                                        "lng": 13.469038314828833
                                    },
                                    "duration": 300
                                }
                            ],
                            "demand": [
                                1
                            ]
                        }
                    ]
                }
            }
        ]
    }
}

Solution

以下の解決策から、車両が job_2job_3job_6job_1、および job_7を処理し、指定された時間内にデポの場所でリロードを行うことがわかります。 その後 job_5job_4が提供されます。

{
    "statistic": {
        "cost": 260.9809999999999,
        "distance": 81441,
        "duration": 13157,
        "times": {
            "driving": 10997,
            "serving": 2160,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "e429c9c1e6df_1",
            "typeId": "e429c9c1e6df",
            "stops": [
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2022-06-01T08:05:00Z",
                        "departure": "2022-06-01T08:05:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ],
                    "distance": 0
                },
                {
                    "location": {
                        "lat": 52.632489506294235,
                        "lng": 13.341605471791963
                    },
                    "time": {
                        "arrival": "2022-06-01T08:36:42Z",
                        "departure": "2022-06-01T08:41:42Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "job_2",
                            "type": "pickup"
                        }
                    ],
                    "distance": 6640
                },
                {
                    "location": {
                        "lat": 52.5983459422347,
                        "lng": 13.392007658723308
                    },
                    "time": {
                        "arrival": "2022-06-01T09:05:56Z",
                        "departure": "2022-06-01T09:10:56Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "job_3",
                            "type": "pickup"
                        }
                    ],
                    "distance": 8022
                },
                {
                    "location": {
                        "lat": 52.486595664301646,
                        "lng": 13.423728674699785
                    },
                    "time": {
                        "arrival": "2022-06-01T09:49:34Z",
                        "departure": "2022-06-01T09:54:34Z"
                    },
                    "load": [
                        3
                    ],
                    "activities": [
                        {
                            "jobId": "job_6",
                            "type": "pickup"
                        }
                    ],
                    "distance": 24199
                },
                {
                    "location": {
                        "lat": 52.44664947511696,
                        "lng": 13.484988905387556
                    },
                    "time": {
                        "arrival": "2022-06-01T10:10:22Z",
                        "departure": "2022-06-01T10:15:22Z"
                    },
                    "load": [
                        4
                    ],
                    "activities": [
                        {
                            "jobId": "job_1",
                            "type": "pickup"
                        }
                    ],
                    "distance": 29363
                },
                {
                    "location": {
                        "lat": 52.471783668934606,
                        "lng": 13.469038314828833
                    },
                    "time": {
                        "arrival": "2022-06-01T10:24:23Z",
                        "departure": "2022-06-01T10:29:23Z"
                    },
                    "load": [
                        5
                    ],
                    "activities": [
                        {
                            "jobId": "job_7",
                            "type": "pickup"
                        }
                    ],
                    "distance": 37457
                },
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2022-06-01T10:56:26Z",
                        "departure": "2022-06-01T10:57:26Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "reload",
                            "type": "reload"
                        }
                    ],
                    "distance": 45849
                },
                {
                    "location": {
                        "lat": 52.57541509905306,
                        "lng": 13.40987831474772
                    },
                    "time": {
                        "arrival": "2022-06-01T11:12:34Z",
                        "departure": "2022-06-01T11:17:34Z"
                    },
                    "load": [
                        1
                    ],
                    "activities": [
                        {
                            "jobId": "job_5",
                            "type": "pickup"
                        }
                    ],
                    "distance": 61949
                },
                {
                    "location": {
                        "lat": 52.577856866026835,
                        "lng": 13.423782100910442
                    },
                    "time": {
                        "arrival": "2022-06-01T11:21:24Z",
                        "departure": "2022-06-01T11:26:24Z"
                    },
                    "load": [
                        2
                    ],
                    "activities": [
                        {
                            "jobId": "job_4",
                            "type": "pickup"
                        }
                    ],
                    "distance": 73264
                },
                {
                    "location": {
                        "lat": 52.530971,
                        "lng": 13.384915
                    },
                    "time": {
                        "arrival": "2022-06-01T11:44:17Z",
                        "departure": "2022-06-01T11:44:17Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ],
                    "distance": 82666
                }
            ],
            "statistic": {
                "cost": 260.9809999999999,
                "distance": 81441,
                "duration": 13157,
                "times": {
                    "driving": 10997,
                    "serving": 2160,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 0
        }
    ]
}

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

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