이 가이드에서는 경로 최적화 솔루션에 제공되는 차량 수가 요청 매개변수에 따라 어떻게 달라질 수 있는지 보여줍니다.
Route Optimization API는 배송 완료 순서를 최적화할 뿐만 아니라 관리하는 제약 조건에 따라 비용을 최적화하기 위해 배송을 차량에 할당합니다.
첫 번째 예시에서는 차량 수가 배송 수와 일치하며 모든 차량이 동일한 비용 및 위치 속성을 공유합니다. 각 차량에는 운영 시간당 비용과 이동한 킬로미터당 비용이 있으며, 이를 통해 이동 시간과 거리를 최소화할 수 있습니다. 여러 차량에 배송이 할당될 것으로 예상할 수 있지만 예시 응답에는 지정된 비용 모델 매개변수가 적용된 최소 비용 솔루션이 표시됩니다.
차량이 여러 대인 요청 예시 보기
{ "model": { "globalStartTime": "2023-01-13T16:00:00-08:00", "globalEndTime": "2023-01-14T16:00:00-08:00", "shipments": [ { "deliveries": [ { "arrivalLocation": { "latitude": 37.789456, "longitude": -122.390192 }, "duration": "250s" } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 100.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.789116, "longitude": -122.395080 }, "duration": "250s" } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 5.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.795242, "longitude": -122.399347 }, "duration": "250s" } ], "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": 50.0, "costPerKilometer": 10.0 }, { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerHour": 50.0, "costPerKilometer": 10.0 }, { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerHour": 50.0, "costPerKilometer": 10.0 } ] } }
차량이 여러 대인 요청에 대한 응답을 확인합니다.
{ "routes": [ { "vehicleStartTime": "2023-01-14T00:00:00Z", "vehicleEndTime": "2023-01-14T00:28:22Z", "visits": [ { "isPickup": true, "startTime": "2023-01-14T00:00:00Z", "detour": "0s" }, { "shipmentIndex": 2, "isPickup": true, "startTime": "2023-01-14T00:02:30Z", "detour": "150s" }, { "startTime": "2023-01-14T00:08:55Z", "detour": "150s" }, { "shipmentIndex": 2, "startTime": "2023-01-14T00:21:21Z", "detour": "572s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-14T00:00:00Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-14T00:02:30Z" }, { "travelDuration": "235s", "travelDistanceMeters": 795, "waitDuration": "0s", "totalDuration": "235s", "startTime": "2023-01-14T00:05:00Z" }, { "travelDuration": "496s", "travelDistanceMeters": 1893, "waitDuration": "0s", "totalDuration": "496s", "startTime": "2023-01-14T00:13:05Z" }, { "travelDuration": "171s", "travelDistanceMeters": 665, "waitDuration": "0s", "totalDuration": "171s", "startTime": "2023-01-14T00:25:31Z" } ], "metrics": { "performedShipmentCount": 2, "travelDuration": "902s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "800s", "totalDuration": "1702s", "travelDistanceMeters": 3353 }, "routeCosts": { "model.vehicles.cost_per_kilometer": 33.53, "model.vehicles.cost_per_hour": 23.638888888888889 }, "routeTotalCost": 57.168888888888887 }, { "vehicleIndex": 1 }, { "vehicleIndex": 2 } ], "skippedShipments": [ { "index": 1 } ], "metrics": { "aggregatedRouteMetrics": { "performedShipmentCount": 2, "travelDuration": "902s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "800s", "totalDuration": "1702s", "travelDistanceMeters": 3353 }, "usedVehicleCount": 1, "earliestVehicleStartTime": "2023-01-14T00:00:00Z", "latestVehicleEndTime": "2023-01-14T00:28:22Z", "totalCost": 62.168888888888887, "costs": { "model.vehicles.cost_per_hour": 23.638888888888889, "model.shipments.penalty_cost": 5, "model.vehicles.cost_per_kilometer": 33.53 } } }
솔버가 모든 배송을 하나의 차량에만 할당하여 차량이 충분히 있음에도 불구하고 하나의 배송을 건너뜁니다. 추가 차량을 운영하는 비용이 너무 높아 정당화할 수 없고, 낮은 벌금 비용을 고려할 때 어떤 차량이든 건너뛴 배송을 완료하는 것이 비용 효율적이지 않기 때문입니다.
사용 가능한 차량 용량이 있음에도 불구하고 한 대의 차량이 가장 비용 효율적인 방식으로 할당된 모든 배송을 수행할 수 있습니다. 요청의 차량에 usedIfRouteIsEmpty 속성이 설정되어 있지 않으므로 (자세한 내용은 Vehicle 메시지 문서 (REST, gRPC) 참고) 사용하지 않으면 비용이 발생하지 않습니다.
개별적으로 더 짧은 차량 경로가 아닌 전체적으로 더 짧은 솔루션을 우선시하도록 비용 매개변수를 변경하면 솔루션에 더 많은 차량이 참여하게 됩니다. 다음 예시 요청은 Vehicle.costPerHour를 전역 ShipmentModel.globalDurationCostPerHour로 대체하여 특정 차량의 작동 시간보다 총 시간이 짧은 솔루션에 우선순위를 부여합니다. shipment[1]의 페널티 비용도 건너뛸 가능성을 줄이기 위해 증가합니다.
globalDurationCostPerHour를 사용하는 요청 예시를 참고하세요.
{ "model": { "globalStartTime": "2023-01-13T16:00:00-08:00", "globalEndTime": "2023-01-14T16:00:00-08:00", "globalDurationCostPerHour": 150.0, "shipments": [ { "deliveries": [ { "arrivalLocation": { "latitude": 37.789456, "longitude": -122.390192 }, "duration": "250s" } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 100.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.789116, "longitude": -122.395080 }, "duration": "250s" } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 75.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.795242, "longitude": -122.399347 }, "duration": "250s" } ], "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 }, "costPerKilometer": 10.0 }, { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerKilometer": 10.0 }, { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerKilometer": 10.0 } ] } }
결과를 보면 시간당 전역 비용 매개변수를 사용하면 차량 1대가 아닌 3대가 모두 사용됩니다.
globalDurationCostPerHour를 사용하여 요청에 대한 응답을 확인합니다.
{ "routes": [ { "vehicleStartTime": "2023-01-14T00:00:00Z", "vehicleEndTime": "2023-01-14T00:16:20Z", "visits": [ { "shipmentIndex": 2, "isPickup": true, "startTime": "2023-01-14T00:00:00Z", "detour": "0s" }, { "shipmentIndex": 2, "startTime": "2023-01-14T00:09:19Z", "detour": "0s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-14T00:00:00Z" }, { "travelDuration": "409s", "travelDistanceMeters": 1371, "waitDuration": "0s", "totalDuration": "409s", "startTime": "2023-01-14T00:02:30Z" }, { "travelDuration": "171s", "travelDistanceMeters": 665, "waitDuration": "0s", "totalDuration": "171s", "startTime": "2023-01-14T00:13:29Z" } ], "metrics": { "performedShipmentCount": 1, "travelDuration": "580s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "400s", "totalDuration": "980s", "travelDistanceMeters": 2036 }, "routeCosts": { "model.vehicles.cost_per_kilometer": 20.36 }, "routeTotalCost": 20.36 }, { "vehicleIndex": 1, "vehicleStartTime": "2023-01-14T00:00:00Z", "vehicleEndTime": "2023-01-14T00:18:54Z", "visits": [ { "shipmentIndex": 1, "isPickup": true, "startTime": "2023-01-14T00:00:00Z", "detour": "0s" }, { "shipmentIndex": 1, "startTime": "2023-01-14T00:08:24Z", "detour": "0s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-14T00:00:00Z" }, { "travelDuration": "354s", "travelDistanceMeters": 1192, "waitDuration": "0s", "totalDuration": "354s", "startTime": "2023-01-14T00:02:30Z" }, { "travelDuration": "380s", "travelDistanceMeters": 1190, "waitDuration": "0s", "totalDuration": "380s", "startTime": "2023-01-14T00:12:34Z" } ], "metrics": { "performedShipmentCount": 1, "travelDuration": "734s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "400s", "totalDuration": "1134s", "travelDistanceMeters": 2382 }, "routeCosts": { "model.vehicles.cost_per_kilometer": 23.82 }, "routeTotalCost": 23.82 }, { "vehicleIndex": 2, "vehicleStartTime": "2023-01-14T00:00:00Z", "vehicleEndTime": "2023-01-14T00:16:14Z", "visits": [ { "isPickup": true, "startTime": "2023-01-14T00:00:00Z", "detour": "0s" }, { "startTime": "2023-01-14T00:06:25Z", "detour": "0s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-14T00:00:00Z" }, { "travelDuration": "235s", "travelDistanceMeters": 795, "waitDuration": "0s", "totalDuration": "235s", "startTime": "2023-01-14T00:02:30Z" }, { "travelDuration": "339s", "travelDistanceMeters": 1276, "waitDuration": "0s", "totalDuration": "339s", "startTime": "2023-01-14T00:10:35Z" } ], "metrics": { "performedShipmentCount": 1, "travelDuration": "574s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "400s", "totalDuration": "974s", "travelDistanceMeters": 2071 }, "routeCosts": { "model.vehicles.cost_per_kilometer": 20.71 }, "routeTotalCost": 20.71 } ], "metrics": { "aggregatedRouteMetrics": { "performedShipmentCount": 3, "travelDuration": "1888s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "3088s", "travelDistanceMeters": 6489 }, "usedVehicleCount": 3, "earliestVehicleStartTime": "2023-01-14T00:00:00Z", "latestVehicleEndTime": "2023-01-14T00:18:54Z", "totalCost": 112.14, "costs": { "model.vehicles.cost_per_kilometer": 64.89, "model.global_duration_cost_per_hour": 47.25 } } }
이 응답에서 세 대의 차량은 모두 사용 중이며 (metrics.usedVehicleCount에 따라) 각 차량에는 완료해야 할 배송이 하나씩 할당됩니다. 시작 위치, 종료 위치, costPerKilometer가 동일하므로 세 대의 차량은 사실상 서로 교체할 수 있으므로 어떤 배송이 어떤 차량에 할당되는지는 중요하지 않습니다.
globalDurationCostPerHour로 인해 최적화 프로그램이 전체적으로 더 짧은 솔루션을 찾습니다. earliestVehicleStartTime와 latestVehicleEndTime의 차이는 이전 대답의 28분 22초와 달리 18분 54초에 불과합니다. 하지만 metrics.costs.model.vehicles.cost_per_kilometer는 사용된 세 대의 차량의 총 이동 거리가 늘어난 것을 반영하여 증가했습니다. 이는 비용 모델을 통해 트레이드 오프를 수행할 수 있는 한 가지 방법을 보여줍니다.
- 전역 시간 비용 증가: 차량 활용도를 높여 전체 완료 시간을 최소화합니다. 대신 차량 이동 거리와 이동 시간이 늘어납니다.
- 차량 시간 비용 증가: 전체 솔루션이 길어지는 대신 차량 활용도와 이동 시간을 줄입니다.
이 예에서 globalDurationCostPerHour 값 150.0은 이전 예의 개별 차량 costPerHour 50.0의 3배로 설정됩니다. 이 전역 비용 값은 세 대의 차량이 모두 동시에 작동할 것으로 예상하지만 실제 설정에서는 이러한 가정이 현실을 반영하지 않을 수 있으며 결과 품질에 부정적인 영향을 미칠 수 있습니다.
비용 모델 매개변수에 설명된 대로 모든 비용 매개변수는 동일한 무차원 단위로 표현되지만 의미는 매우 다를 수 있습니다. 일반적으로 비용 모델 매개변수 값은 가능한 한 현실에 기반해야 합니다. 이 예와 같은 인위적인 비용은 API가 의도와 일치하지 않는 목표를 위해 최적화하도록 할 수 있기 때문입니다.