OptimizeToursRequest
는 다음에 제약 조건을 적용합니다.
- 배송 - 배송이 실행되는 방식에 영향을 미칩니다.
- 차량 경로 계산 방식에 영향을 미치는 차량
- 전 세계적으로 차량과 배송에 모두 영향을 미칩니다.
이 가이드에서는 중요한 배송 제약조건인 시간 범위에 중점을 둡니다.
기간은 배송 활동에 시간 기반 제한을 지정하기 위해 OptimizeToursRequest
메시지 (REST, gRPC)에 제공하는 한 가지 유형의 제약 조건입니다. 이 유형의 제약조건은 배송이 실행될 수 있는 시기와 방법뿐만 아니라 배송의 차량 할당에도 영향을 미칩니다. 이러한 제약조건을 토대로 최적화 도구는 배송의 시간 제약조건을 가장 잘 충족할 수 있는 차량을 우선시합니다.
배송 제약조건: 기간
다음과 같이 Shipment.VisitRequest
메시지에서 수령 또는 배송이 발생할 수 있는 시점을 지정합니다.
시간 제한이 있는 요청 예시
이 예에서는 각각 배송 기간이 다른 세 가지 배송을 보여줍니다. 이 예에서는 편의상 deliveries
에만 시간대를 설정하지만 시간대는 픽업에도 적용할 수 있습니다. 여러 시간대를 지정할 수 있지만 이 예에서는 전송 VisitRequest
당 하나만 사용합니다.
시간대가 포함된 요청 예 보기
{ "populatePolylines": false, "populateTransitionPolylines": false, "model": { "globalStartTime": "2023-01-13T16:00:00Z", "globalEndTime": "2023-01-14T16:00:00Z", "shipments": [ { "deliveries": [ { "arrivalLocation": { "latitude": 37.789456, "longitude": -122.390192 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T18:00:00Z", "endTime": "2023-01-13T19:00:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 100.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.789116, "longitude": -122.395080 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T18:00:00Z", "endTime": "2023-01-13T18:30:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 20.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.795242, "longitude": -122.399347 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T17:30:00Z", "endTime": "2023-01-13T18:00:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 50.0 } ], "vehicles": [ { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerHour": 40.0, "costPerKilometer": 10.0 } ] } }
시간 제약 조건이 있는 응답 예시
응답 예시에서 차량의 시작 시간과 종료 시간은 각각 17:35:50 및 18:17:24입니다. 이 시간은 모든 시간 간격 제약조건을 충족하면서 요청에 지정된 차량을 운전하는 데 필요한 시간을 최소화하는 최적화 도구를 반영합니다.costPerHour
17:35:50을 시작 시간으로 사용하면 방문 시간대가 시작될 때까지 차량이 방문 위치에서 기다릴 필요가 없습니다. 이는 응답에 0 waitDuration
값으로 표시됩니다.
시간 범위가 있는 예시 요청에 대한 응답 보기
{ "routes": [ { "vehicleStartTime": "2023-01-13T17:35:50Z", "vehicleEndTime": "2023-01-13T18:17:24Z", "visits": [ { "isPickup": true, "startTime": "2023-01-13T17:35:50Z", "detour": "0s" }, { "shipmentIndex": 1, "isPickup": true, "startTime": "2023-01-13T17:38:20Z", "detour": "150s" }, { "shipmentIndex": 2, "isPickup": true, "startTime": "2023-01-13T17:40:50Z", "detour": "300s" }, { "shipmentIndex": 2, "startTime": "2023-01-13T17:50:09Z", "detour": "0s" }, { "shipmentIndex": 1, "startTime": "2023-01-13T18:00:00Z", "detour": "796s" }, { "startTime": "2023-01-13T18:07:35Z", "detour": "1520s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:35:50Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:38:20Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:40:50Z" }, { "travelDuration": "409s", "travelDistanceMeters": 1371, "waitDuration": "0s", "totalDuration": "409s", "startTime": "2023-01-13T17:43:20Z" }, { "travelDuration": "341s", "travelDistanceMeters": 1312, "waitDuration": "0s", "totalDuration": "341s", "startTime": "2023-01-13T17:54:19Z" }, { "travelDuration": "205s", "travelDistanceMeters": 636, "waitDuration": "0s", "totalDuration": "205s", "startTime": "2023-01-13T18:04:10Z" }, { "travelDuration": "339s", "travelDistanceMeters": 1276, "waitDuration": "0s", "totalDuration": "339s", "startTime": "2023-01-13T18:11:45Z" } ], "metrics": { "performedShipmentCount": 3, "travelDuration": "1294s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "2494s", "travelDistanceMeters": 4595 }, "routeCosts": { "model.vehicles.cost_per_hour": 27.711111111111112, "model.vehicles.cost_per_kilometer": 45.95 }, "routeTotalCost": 73.661111111111111 } ], "metrics": { "aggregatedRouteMetrics": { "performedShipmentCount": 3, "travelDuration": "1294s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "2494s", "travelDistanceMeters": 4595 }, "usedVehicleCount": 1, "earliestVehicleStartTime": "2023-01-13T17:35:50Z", "latestVehicleEndTime": "2023-01-13T18:17:24Z", "totalCost": 73.661111111111111, "costs": { "model.vehicles.cost_per_hour": 27.711111111111112, "model.vehicles.cost_per_kilometer": 45.95 } } }
가장 빠른 기간이 있는 배송이 먼저 배송되도록 기간이 차량의 visits
를 정렬했습니다.
shipments[2]
은 17:50에 배송됩니다.shipments[1]
은 18:00에 배송됩니다.shipments[0]
이 18:07에 전송됨
이 요청 예에서는 엄격한 시간 제한을 지정하여 해당 기간 내에 전송을 완료해야 합니다. 시간 범위 내에 배송의 VisitRequests
를 완료하는 것이 실행 가능하지 않거나 비용 효율적이지 않은 경우 최적화 도구는 배송을 건너뜁니다. 배송에 penaltyCost
가 있는 경우 최적화 도구는 metrics
응답에 보고된 비용에 이를 추가합니다. 그렇지 않으면 OptimizeToursResponse
메시지 (REST, gRPC)의 skippedMandatoryShipmentCount
속성이 증가합니다.
shipment[1]
의 기간을 몇 시간 후에 변경하여 시간 범위를 변경하면 (18:00에서 21:00으로) 다음 예와 같이 결과가 달라집니다.
충족할 수 없는 시간 기간이 있는 요청 예시 보기
{ "populatePolylines": false, "populateTransitionPolylines": false, "model": { "globalStartTime": "2023-01-13T16:00:00Z", "globalEndTime": "2023-01-14T16:00:00Z", "shipments": [ { "deliveries": [ { "arrivalLocation": { "latitude": 37.789456, "longitude": -122.390192 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T18:00:00Z", "endTime": "2023-01-13T19:00:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 100.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.789116, "longitude": -122.395080 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T21:00:00Z", "endTime": "2023-01-13T21:30:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 20.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.795242, "longitude": -122.399347 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T17:30:00Z", "endTime": "2023-01-13T18:00:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 50.0 } ], "vehicles": [ { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerHour": 40.0, "costPerKilometer": 10.0 } ] } }
배송이 건너뛰어진 시간 범위가 있는 두 번째 요청 예시의 응답 보기
{ "routes": [ { "vehicleStartTime": "2023-01-13T17:37:49Z", "vehicleEndTime": "2023-01-13T18:09:49Z", "visits": [ { "isPickup": true, "startTime": "2023-01-13T17:37:49Z", "detour": "0s" }, { "shipmentIndex": 2, "isPickup": true, "startTime": "2023-01-13T17:40:19Z", "detour": "150s" }, { "shipmentIndex": 2, "startTime": "2023-01-13T17:49:38Z", "detour": "0s" }, { "startTime": "2023-01-13T18:00:00Z", "detour": "946s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:37:49Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:40:19Z" }, { "travelDuration": "409s", "travelDistanceMeters": 1371, "waitDuration": "0s", "totalDuration": "409s", "startTime": "2023-01-13T17:42:49Z" }, { "travelDuration": "372s", "travelDistanceMeters": 1348, "waitDuration": "0s", "totalDuration": "372s", "startTime": "2023-01-13T17:53:48Z" }, { "travelDuration": "339s", "travelDistanceMeters": 1276, "waitDuration": "0s", "totalDuration": "339s", "startTime": "2023-01-13T18:04:10Z" } ], "metrics": { "performedShipmentCount": 2, "travelDuration": "1120s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "800s", "totalDuration": "1920s", "travelDistanceMeters": 3995 }, "routeCosts": { "model.vehicles.cost_per_kilometer": 39.95, "model.vehicles.cost_per_hour": 21.333333333333332 }, "routeTotalCost": 61.283333333333331 } ], "skippedShipments": [ { "index": 1 } ], "metrics": { "aggregatedRouteMetrics": { "performedShipmentCount": 2, "travelDuration": "1120s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "800s", "totalDuration": "1920s", "travelDistanceMeters": 3995 }, "usedVehicleCount": 1, "earliestVehicleStartTime": "2023-01-13T17:37:49Z", "latestVehicleEndTime": "2023-01-13T18:09:49Z", "totalCost": 81.283333333333331, "costs": { "model.shipments.penalty_cost": 20, "model.vehicles.cost_per_hour": 21.333333333333332, "model.vehicles.cost_per_kilometer": 39.95 } } }
이 예에서는 지정된 시간 범위 내에 배송을 완료하는 데 필요한 추가 차량 운행 시간이 배송의 위약금 비용을 초과했기 때문에 나중에 시작된 시간 범위로 인해 shipment[1]
가 건너뛰어졌습니다.
shipment[1]
의 패널티 비용은 metrics.costs
에 표시되고 색인은 skippedShipments
에 표시됩니다.
유연한 시간 윈도우 제약조건
비용 모델 매개변수에서 간단히 언급한 대로 시간 창은 소프트 제약조건으로 적용할 수 있습니다. 유연한 제약 조건은 다음과 같이 엄격한 제약 조건과 다릅니다.
- 엄격한 제약조건: 위반할 수 없으며 최적화 도구는 전송을 건너뛰더라도 제약조건을 위반하는 솔루션을 제공하지 않습니다.
- 조건부 제약조건: 위반될 수 있습니다. 즉, 최적화 도구가 조건부 제약조건을 위반하는 솔루션을 제공할 수 있습니다. 그러나 최적화 도구는 위반사항에 비용도 적용합니다. 이 비용은 시간 범위의 추가 속성으로 제공되며 일반적으로 활동이 발생하는 시간 범위 전후에 각 시간의 시간당 비용으로 제공됩니다.
startTime
또는 endTime
대신 softStartTime
또는 softEndTime
를 사용하고 costPerHourBeforeSoftStartTime
또는 costPerHourAfterSoftEndTime
를 설정하면 시간 범위가 완화됩니다.
지정된 시간 범위 내에 수령 또는 배송이 해야 하지만 해당 시간 범위 내에 수령 또는 배송이 반드시 필요한 것은 아닌 경우 유연한 시간 범위 제약조건을 사용하세요. 하드 타임 윈도우 제약 조건과 소프트 타임 윈도우 제약 조건을 함께 사용하여 비즈니스 목표를 표현할 수 있습니다. 예를 들면 다음과 같습니다.
- 고정 시간 범위: 오전 9시~오후 5시와 같이 고객의 영업시간을 나타냅니다.
- 유연한 시간대: 고객에게 전송된 알림과 일치하는 배송 또는 수령 기간(예: 오전 9시~오후 1시)을 나타냅니다.
이 예에서는 시간 창이 너무 늦게 시작되어 이전에 건너뛴 배송의 시작 시간 제약 조건이 완화되었습니다. 다른 배송의 경우에도 기간 종료 시간이 완화되었습니다.
명확한 시간대와 유연한 시간대의 요청 예 보기
{ "populatePolylines": false, "populateTransitionPolylines": false, "model": { "globalStartTime": "2023-01-13T16:00:00Z", "globalEndTime": "2023-01-14T16:00:00Z", "shipments": [ { "deliveries": [ { "arrivalLocation": { "latitude": 37.789456, "longitude": -122.390192 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T18:00:00Z", "softEndTime": "2023-01-13T19:00:00Z", "costPerHourAfterSoftEndTime": 2.0 } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 100.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.789116, "longitude": -122.395080 }, "duration": "250s", "timeWindows": [ { "softStartTime": "2023-01-13T21:00:00Z", "endTime": "2023-01-13T21:30:00Z", "costPerHourBeforeSoftStartTime": 2.0 } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 20.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.795242, "longitude": -122.399347 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T17:30:00Z", "softEndTime": "2023-01-13T18:00:00Z", "costPerHourAfterSoftEndTime": 2.0 } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 50.0 } ], "vehicles": [ { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerHour": 40.0, "costPerKilometer": 10.0 } ] } }
명확한 시간대와 유연한 시간대를 포함한 요청 예시의 응답 보기
{ "routes": [ { "vehicleStartTime": "2023-01-13T17:48:35Z", "vehicleEndTime": "2023-01-13T18:24:28Z", "visits": [ { "isPickup": true, "startTime": "2023-01-13T17:48:35Z", "detour": "0s" }, { "shipmentIndex": 1, "isPickup": true, "startTime": "2023-01-13T17:51:05Z", "detour": "150s" }, { "shipmentIndex": 2, "isPickup": true, "startTime": "2023-01-13T17:53:35Z", "detour": "300s" }, { "startTime": "2023-01-13T18:00:00Z", "detour": "300s" }, { "shipmentIndex": 1, "startTime": "2023-01-13T18:07:42Z", "detour": "493s" }, { "shipmentIndex": 2, "startTime": "2023-01-13T18:17:27Z", "detour": "873s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:48:35Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:51:05Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:53:35Z" }, { "travelDuration": "235s", "travelDistanceMeters": 795, "waitDuration": "0s", "totalDuration": "235s", "startTime": "2023-01-13T17:56:05Z" }, { "travelDuration": "212s", "travelDistanceMeters": 791, "waitDuration": "0s", "totalDuration": "212s", "startTime": "2023-01-13T18:04:10Z" }, { "travelDuration": "335s", "travelDistanceMeters": 1204, "waitDuration": "0s", "totalDuration": "335s", "startTime": "2023-01-13T18:11:52Z" }, { "travelDuration": "171s", "travelDistanceMeters": 665, "waitDuration": "0s", "totalDuration": "171s", "startTime": "2023-01-13T18:21:37Z" } ], "metrics": { "performedShipmentCount": 3, "travelDuration": "953s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "2153s", "travelDistanceMeters": 3455 }, "routeCosts": { "model.shipments.deliveries.time_windows.cost_per_hour_after_soft_end_time": 0.58166666666666667, "model.shipments.deliveries.time_windows.cost_per_hour_before_soft_start_time": 5.7433333333333332, "model.vehicles.cost_per_hour": 23.922222222222221, "model.vehicles.cost_per_kilometer": 34.55 }, "routeTotalCost": 64.797222222222217 } ], "metrics": { "aggregatedRouteMetrics": { "performedShipmentCount": 3, "travelDuration": "953s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "2153s", "travelDistanceMeters": 3455 }, "usedVehicleCount": 1, "earliestVehicleStartTime": "2023-01-13T17:48:35Z", "latestVehicleEndTime": "2023-01-13T18:24:28Z", "totalCost": 64.797222222222217, "costs": { "model.vehicles.cost_per_kilometer": 34.55, "model.shipments.deliveries.time_windows.cost_per_hour_before_soft_start_time": 5.7433333333333332, "model.shipments.deliveries.time_windows.cost_per_hour_after_soft_end_time": 0.58166666666666667, "model.vehicles.cost_per_hour": 23.922222222222221 } } }
엄격한 시간 제약 조건만 있는 예에서는 shipment[1]
가 완전히 건너뛰었지만, 전송 시간 제한을 완화하면 시간 제한 시작 시간 전에 전송됩니다. 마찬가지로 다른 배송의 종료 시간을 완화하여 shipment[2]
가 시간 범위가 종료된 후에 배송되도록 허용했습니다.
동시에 비용과 총 배송도 변경되었습니다.
totalCost
: 81.283에서 64.797로 감소함- 총 완료된 배송: 2에서 3으로 증가함
이전 예시와 비교하여 시간 제약 조건이 완화되었기 때문에 최적화 도구가 더 저렴한 솔루션을 찾았습니다.
마지막으로 metrics.costs
속성에는 제약 조건과 전송 기간 누락 시간의 곱을 기반으로 발생한 실제 비용을 나타내는 새 키도 포함되어 있습니다. 이는 다음과 같은 의미입니다.
- 2.0의
costPerHourBeforeSoftStartTime
및 - 실제 전송과 시간 범위 시작 사이의 시간: 2.83583시간
결과:
model.shipments.deliveries.time_windows.cost_per_hour_before_soft_start_time
:
5.6716666666666669.
이러한 측정항목을 사용하면 비용 분석을 통해 하드 제약조건과 소프트 제약조건 간의 균형을 확인할 수 있으며, 이를 사용하여 특정 비즈니스 규칙에 더 적합하도록 제약조건을 조정할 수 있습니다. 이 경우 총 비용은 shipment[1].penalty_cost
20.0보다 작습니다. 옵티마이저는 배송을 건너뛰는 것보다 배송을 일찍 처리하는 것이 비용 효율적이라고 판단했습니다.