OptimizeToursRequest는 다음에 제약 조건을 적용합니다.
- 배송 - 배송이 실행되는 방식에 영향을 미칩니다.
- 차량 경로 계산 방식에 영향을 미치는 차량
- 전 세계적으로 차량과 배송에 모두 영향을 미칩니다.
이 가이드에서는 필수 배송 제약조건인 시간 범위에 중점을 둡니다.
기간은 배송 활동에 시간 기반 제한을 지정하기 위해 OptimizeToursRequest 메시지 (REST, gRPC)에 제공하는 한 가지 유형의 제약 조건입니다. 이러한 유형의 제약 조건은 배송을 진행할 수 있는 시기와 방법과 배송 차량 할당에 모두 영향을 줍니다. 이러한 제약조건을 토대로 최적화 도구는 배송의 시간 제약조건을 가장 잘 충족할 수 있는 차량을 우선시합니다.
배송 제약조건: 기간
다음과 같이 Shipment.VisitRequest 메시지에서 수령 또는 배송이 발생할 수 있는 시점을 지정합니다.
기간 제약 조건이 있는 요청 예
이 예에서는 각각 고유한 배송 기간이 있는 3가지 배송을 보여줍니다. 이 예에서는 편의상 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을 시작 시간으로 사용하면 차량이 방문 시간이 시작될 때까지 방문 위치에서 대기할 필요가 없습니다. 이는 응답에 waitDuration 값 0으로 표시됩니다.
시간대별 예시 요청에 대한 응답 보기
{ "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보다 작습니다. 옵티마이저는 배송을 건너뛰는 것보다 배송을 일찍 처리하는 것이 비용 효율적이라고 판단했습니다.