이 가이드에서는 경로 최적화 솔루션에 제공되는 차량 수가 요청 매개변수에 따라 어떻게 달라질 수 있는지 보여줍니다.
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를 사용하면 최적화 도구가 전반적으로 더 짧은 솔루션을 찾습니다. 이전 응답의 28분 22초와 달리 earliestVehicleStartTime와 latestVehicleEndTime의 차이는 18분 54초에 불과합니다. 하지만 metrics.costs.model.vehicles.cost_per_kilometer는 증가하여 중고 차량 3대의 총 주행 거리가 더 많이 반영되었습니다. 다음은 비용 모델을 사용하여 절충하는 한 가지 방법을 보여줍니다.
- 전 세계 시간 비용 증가: 차량 활용도를 높여 전체 완료 시간을 최소화하면 차량 거리와 이동 시간은 늘어납니다.
- 차량 시간 비용 증가: 차량 활용도와 이동 시간은 줄이지만 전반적인 솔루션이 더 길어집니다.
이 예에서 globalDurationCostPerHour 값 150.0은 이전 예의 개별 차량 costPerHour 50.0의 세 배로 설정됩니다. 이 전역 비용 값은 세 대의 차량이 모두 동시에 작동한다고 가정하지만 실제 환경에서는 이러한 가정이 현실을 반영하지 못할 수 있으며 실제로 결과 품질에 부정적인 영향을 미칠 수 있습니다.
비용 모델 매개변수에 설명된 대로 모든 비용 매개변수는 동일한 무차원 단위로 표현되지만 의미는 매우 다를 수 있습니다. 일반적으로 비용 모델 매개변수 값은 최대한 현실에 기반해야 합니다. 이 예와 같은 인위적인 비용으로 인해 API가 의도와 일치하지 않는 목표에 최적화될 수 있기 때문입니다.