OptimizeToursRequest áp dụng các điều kiện ràng buộc trên những mục sau:
- Lô hàng, ảnh hưởng đến cách thực hiện các lô hàng
- Phương tiện di chuyển, ảnh hưởng đến cách tính toán tuyến đường của phương tiện
- Ảnh hưởng trên toàn cầu, ảnh hưởng đến cả phương tiện vận chuyển và quá trình vận chuyển.
Hướng dẫn này tập trung vào một quy tắc ràng buộc thiết yếu đối với việc vận chuyển: khoảng thời gian.
Cửa sổ thời gian là một loại ràng buộc mà bạn cung cấp trong
OptimizeToursRequest thông báo (REST, gRPC) để chỉ định
các giới hạn dựa trên thời gian đối với hoạt động vận chuyển. Loại quy tắc ràng buộc này ảnh hưởng đến
cả thời điểm và cách thức vận chuyển cũng như việc chỉ định xe
cho lô hàng. Với những hạn chế này, trình tối ưu hoá ưu tiên
những phương tiện có thể đáp ứng tốt nhất những hạn chế về thời gian vận chuyển.
Giới hạn vận chuyển: khung thời gian
Bạn chỉ định thời điểm có thể đến lấy hàng hoặc giao hàng trong Shipment.VisitRequest
thông báo như sau:
- Sử dụng thuộc tính
timeWindowstrong thông báo (REST, gRPC) - Chỉ định thời gian bắt đầu và kết thúc trong thông báo
TimeWindow(REST, gRPC).
Yêu cầu mẫu có giới hạn về khoảng thời gian
Ví dụ ở đây minh hoạ ba gói hàng khác nhau, mỗi gói hàng có
khung thời gian phân phối. Để đơn giản, ví dụ này đặt khoảng thời gian trên deliveries
nhưng cũng có thể áp dụng khung thời gian cho hàng đến lấy hàng. Bạn có thể tạo nhiều cửa sổ thời gian
được chỉ định, mặc dù ví dụ này chỉ sử dụng một lần cho mỗi VisitRequest phân phối.
Xem một yêu cầu mẫu có khoảng thời gian
{
"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
}
]
}
}
Ví dụ về phản hồi có giới hạn về khoảng thời gian
Trong phản hồi ví dụ, thời gian bắt đầu và kết thúc của xe là 17:35:50 và
18:17:24. Những thời gian này phản ánh việc trình tối ưu hoá giảm thiểu thời gian
phải vận hành chiếc xe được chỉ định trong yêu cầu bằng costPerHour khi
đáp ứng mọi giới hạn về khoảng thời gian. Sử dụng 17:35:50 làm thời gian bắt đầu
giúp loại bỏ việc xe phải chờ tại vị trí ghé thăm cho đến khi
khoảng thời gian của lượt truy cập bắt đầu. Giá trị này xuất hiện trong câu trả lời là 0 waitDuration
giá trị.
Xem phản hồi cho yêu cầu mẫu với khung thời gian
{
"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
}
}
}
Khoảng thời gian đã đặt hàng visits của xe để các lô hàng có
các cửa sổ thời điểm sớm nhất được phân phối trước.
shipments[2]được giao lúc 17:50shipments[1]được giao lúc 18:00shipments[0]được giao lúc 18:07
Yêu cầu mẫu chỉ định các quy tắc ràng buộc về cửa sổ thời gian cứng, đòi hỏi
phân phối được hoàn tất trong các cửa sổ đó. Nếu bạn hoàn tất
VisitRequests trong bất kỳ khoảng thời gian nào là không khả thi hoặc
tiết kiệm chi phí, thì trình tối ưu hoá sẽ bỏ qua việc chuyển hàng. Nếu lô hàng có
penaltyCost, trình tối ưu hoá sẽ thêm phương thức này vào các chi phí được báo cáo theo phản hồi
metrics. Nếu không, thuộc tính skippedMandatoryShipmentCount của
OptimizeToursResponse thông báo (REST, gRPC) tăng lên.
Nếu bạn thay đổi khoảng thời gian bằng cách dịch chuyển cửa sổ của shipment[1] vài giờ
(đến 21:00 từ 18:00), kết quả sẽ khác nhau như được minh hoạ trong
các ví dụ sau.
Xem một yêu cầu mẫu có khoảng thời gian không thể hài lòng
{
"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
}
]
}
}
Xem phản hồi cho yêu cầu mẫu thứ hai với khoảng thời gian, trong đó một lô hàng được bỏ qua
{
"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
}
}
}
Trong ví dụ này, khoảng thời gian trễ hơn khiến shipment[1] bị bỏ qua,
vì cần thêm thời gian vận hành xe để hoàn thành việc vận chuyển
việc giao hàng trong khung thời gian quy định đã vượt quá chi phí phạt của lô hàng.
Chi phí phạt cho shipment[1] xuất hiện trong metrics.costs và chỉ mục của nó
xuất hiện trong skippedShipments.
Giới hạn về khoảng thời gian tạm thời
Như đã đề cập ngắn gọn trong Tham số mô hình chi phí, khoảng thời gian có thể được áp dụng dưới dạng quy tắc ràng buộc mềm. Quy tắc ràng buộc mềm khác với quy tắc ràng buộc cứng như sau:
- Những ràng buộc cứng: Không thể bị vi phạm và trình tối ưu hoá không cung cấp một giải pháp vi phạm quy tắc ràng buộc, ngay cả khi điều đó có nghĩa là bỏ qua một chuyển hàng.
- Hạn chế mềm: Có thể bị vi phạm, có nghĩa là trình tối ưu hóa có thể đưa ra một giải pháp vi phạm quy tắc ràng buộc mềm. Tuy nhiên, trình tối ưu hoá cũng áp dụng chi phí cho mọi lỗi vi phạm. Bạn cung cấp chi phí này dưới dạng tài sản bổ sung trong khoảng thời gian, thường là chi phí mỗi giờ cho mỗi giờ trước hoặc sau khoảng thời gian diễn ra hoạt động.
Làm mềm cửa sổ thời gian bằng cách sử dụng softStartTime hoặc softEndTime thay vì
startTime hoặc endTime tương ứng và bằng cách đặt
costPerHourBeforeSoftStartTime hoặc costPerHourAfterSoftEndTime.
Sử dụng các giới hạn về khoảng thời gian mềm khi nên đến lấy hàng hoặc giao hàng trong khoảng thời gian đã chỉ định, nhưng đến lấy hàng hoặc giao hàng trong khung thời gian đó không được là hoàn toàn bắt buộc. Bạn có thể sử dụng các quy tắc ràng buộc về khoảng thời gian cố định và tạm thời để thể hiện mục tiêu kinh doanh. Ví dụ:
- Khoảng thời gian cố định: Cho biết giờ làm việc của khách hàng, chẳng hạn như từ Từ 9:00 đến 17:00.
- Khoảng thời gian tạm thời: Cho biết khung thời gian giao hàng hoặc đến lấy hàng khớp với thông báo đã gửi cho khách hàng, chẳng hạn như 9:00 đến 13:00.
Trong ví dụ này, lô hàng trước đó đã bị bỏ qua do thời gian vận chuyển cửa sổ bắt đầu quá muộn do giới hạn thời gian bắt đầu bị giảm bớt. Khác gói hàng đã được điều chỉnh theo khung thời gian thời gian kết thúc cũng giảm xuống.
Xem một yêu cầu mẫu có thời gian cứng và thời gian tạm thời cửa sổ
{
"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
}
]
}
}
Xem phản hồi cho yêu cầu mẫu với phần cứng và khung thời gian ưu đãi
{
"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
}
}
}
Trường hợp ví dụ chỉ có giới hạn về khoảng thời gian cố định bị bỏ qua hoàn toàn
shipment[1], việc rút ngắn khoảng thời gian giao hàng để khiến thư được gửi
trước thời gian bắt đầu khoảng thời gian. Tương tự, làm mềm thời gian kết thúc của
các lô hàng khác cho phép giao shipment[2] sau khoảng thời gian giao hàng
kết thúc.
Đồng thời, cả chi phí và tổng số vận chuyển đều thay đổi:
totalCost: giảm từ 81,283 xuống 64,797- tổng số lô hàng đã hoàn tất: tăng từ 2 lên 3
Trình tối ưu hoá đã tìm thấy giải pháp ít tốn kém hơn do khoảng thời gian được nới lỏng hơn so với ví dụ trước.
Cuối cùng, thuộc tính metrics.costs cũng bao gồm một khoá mới để cho biết
chi phí thực tế phát sinh dựa trên sản phẩm của điều kiện ràng buộc và thời lượng
thời gian giao hàng bị lỡ. Đó là:
costPerHourBeforeSoftStartTime/2 và- khoảng thời gian từ thời điểm phân phối thực tế đến thời điểm bắt đầu khoảng thời gian: 2,83583 giờ
Kết quả:
model.shipments.deliveries.time_windows.cost_per_hour_before_soft_start_time:
5,6716666666666669.
Các chỉ số này cho phép bạn phân tích chi phí để xem sự đánh đổi giữa
các ràng buộc và ràng buộc mềm mà bạn có thể sử dụng để điều chỉnh các ràng buộc của mình để
phù hợp hơn với quy tắc kinh doanh cụ thể của bạn. Trong trường hợp này, tổng chi phí là
nhỏ hơn shipment[1].penalty_cost/20.0. Trình tối ưu hoá đã xác định
việc giao hàng sớm sẽ tiết kiệm chi phí hơn so với việc giao hàng
bỏ qua bước vận chuyển.