Tình huống này tối ưu hoá thứ tự điểm dừng được chỉ định cho một xe bằng các thông số chi phí đơn giản. Đây là chế độ đơn giản nhất của hoạt động Tối ưu hoá tuyến đường và đảm bảo rằng tất cả các điểm dừng đều được ghé thăm trong khung thời gian đã chỉ định.
Ví dụ sau đây minh hoạ một tình huống cơ bản với một xe và ba lô hàng, tất cả đều bắt nguồn từ một vị trí duy nhất được gọi là kho.
Xem yêu cầu mẫu
{
"populatePolylines": true,
"populateTransitionPolylines": true,
"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"
}
]
},
{
"deliveries": [
{
"arrivalLocation": {
"latitude": 37.789116,
"longitude": -122.395080
},
"duration": "250s"
}
],
"pickups": [
{
"arrivalLocation": {
"latitude": 37.794465,
"longitude": -122.394839
},
"duration": "150s"
}
]
},
{
"deliveries": [
{
"arrivalLocation": {
"latitude": 37.795242,
"longitude": -122.399347
},
"duration": "250s"
}
],
"pickups": [
{
"arrivalLocation": {
"latitude": 37.794465,
"longitude": -122.394839
},
"duration": "150s"
}
]
}
],
"vehicles": [
{
"endLocation": {
"latitude": 37.794465,
"longitude": -122.394839
},
"startLocation": {
"latitude": 37.794465,
"longitude": -122.394839
},
"costPerKilometer": 10.0,
"costPerHour": 40.0
}
]
}
}
Các trường yêu cầu Tối ưu hoá tuyến đường
Như đã đề cập trong phần Tổng quan, các thuộc tính yêu cầu tối ưu hoá tuyến quan trọng nhất là vehicles và shipments.
Ngoài xe và lô hàng, yêu cầu này còn bao gồm các trường sau:
Đường đa tuyến
populatePolylines và populateTransitionPolylines chỉ định xem tính năng Tối ưu hoá tuyến đường có trả về đa tuyến hay không.
Dịch vụ này mã hoá Polylines bằng bộ mã hoá và giải mã polyline Maps JS, đại diện cho dữ liệu polyline nhị phân bằng các ký tự ASCII có thể in. Bạn có thể sử dụng Tiện ích bộ mã hoá đường đa tuyến tương tác để trực quan hoá các đường dẫn được tính toán bằng tính năng Tối ưu hoá tuyến đường. Ví dụ trong hướng dẫn này đặt populatePolylines và populateTransitionPolylines thành true, nhưng các hướng dẫn khác đặt các giá trị này thành false để giảm kích thước phản hồi.
Xem phần Định dạng thuật toán đường đa tuyến tính được mã hoá để biết nội dung mô tả về định dạng mã hoá.
Giới hạn thời gian chung
model.globalStartTime và model.globalEndTime được đặt thành một khoảng thời gian 24 giờ bất kỳ. Điều này giúp bạn dễ dàng diễn giải dấu thời gian đầu ra.
Tham quan địa điểm
Yêu cầu mẫu chỉ sử dụng model.shipments[].pickups[].arrivalLocation và model.shipments[].deliveries[].arrivalLocation. Ngoài ra, còn có thuộc tính departureLocation cho các trường hợp xe rời khỏi một điểm khác với điểm đến, chẳng hạn như một khu đỗ xe có lối vào ở một bên của toà nhà và lối ra ở bên kia. Trong hướng dẫn này và các hướng dẫn tiếp theo, điểm đến và điểm khởi hành được giả định là giống nhau.
waypoint đến và đi cũng tồn tại như một giải pháp thay thế cho latLng.
Các trường Waypoint hỗ trợ việc sử dụng Mã địa điểm của Google thay cho LatLng, đồng thời cũng có thể chỉ định hướng của xe. Hãy xem tài liệu tham khảo (REST, gRPC) để biết thêm thông tin chi tiết.
Các quy tắc ràng buộc trong ví dụ
Tình huống này ràng buộc trình tối ưu hoá theo một số cách:
- Tất cả hoạt động phải được hoàn tất trong khoảng thời gian bắt đầu và kết thúc chung. Trong trường hợp này, thời gian bắt đầu và kết thúc là một điều kiện ràng buộc rất lỏng lẻo do các lô hàng gần nhau và khung thời gian toàn cầu rộng.
- Tất cả đơn hàng phải được hoàn tất. Đây là hành vi mặc định khi bạn không chỉ định chi phí phạt trên
shipments. costPerKilometervàcostPerHourđược đặt trên xe.
Chi phí được đề cập trong phần Tham số mô hình chi phí.
Thuộc tính phản hồi của tính năng Tối ưu hoá tuyến đường
Xem phản hồi cho yêu cầu mẫu
{
"routes": [
{
"vehicleStartTime": "2023-01-14T00:00:00Z",
"vehicleEndTime": "2023-01-14T00:36:41Z",
"visits": [
{
"shipmentIndex": 2,
"isPickup": true,
"startTime": "2023-01-14T00:00:00Z",
"detour": "0s"
},
{
"shipmentIndex": 1,
"isPickup": true,
"startTime": "2023-01-14T00:02:30Z",
"detour": "150s"
},
{
"isPickup": true,
"startTime": "2023-01-14T00:05:00Z",
"detour": "300s"
},
{
"startTime": "2023-01-14T00:11:25Z",
"detour": "0s"
},
{
"shipmentIndex": 1,
"startTime": "2023-01-14T00:19:29Z",
"detour": "503s"
},
{
"shipmentIndex": 2,
"startTime": "2023-01-14T00:29:02Z",
"detour": "1324s"
}
],
"transitions": [
{
"travelDuration": "0s",
"waitDuration": "0s",
"totalDuration": "0s",
"startTime": "2023-01-14T00:00:00Z",
"routePolyline": {}
},
{
"travelDuration": "0s",
"waitDuration": "0s",
"totalDuration": "0s",
"startTime": "2023-01-14T00:02:30Z",
"routePolyline": {}
},
{
"travelDuration": "0s",
"waitDuration": "0s",
"totalDuration": "0s",
"startTime": "2023-01-14T00:05:00Z",
"routePolyline": {}
},
{
"travelDuration": "235s",
"travelDistanceMeters": 795,
"waitDuration": "0s",
"totalDuration": "235s",
"startTime": "2023-01-14T00:07:30Z",
"routePolyline": {
"points": "kvteFtfjVAA?C?C@C?A?C@AFMj@s@JKb@k@Zc@LSjA}ARWDGdAxAdAvAXa@@k@AsA\\c@FKp@_A\\c@Ze@fA{ALSFGd@o@rAgBB{BZc@"
}
},
{
"travelDuration": "234s",
"travelDistanceMeters": 793,
"waitDuration": "0s",
"totalDuration": "234s",
"startTime": "2023-01-14T00:15:35Z",
"routePolyline": {
"points": "cwseFti_jVRWj@w@x@eAHLNRHJbApAHLX\\V^?@hA~AT\\PVFFDHDFJNp@~@NRLNNTFFUZIJY^Y^g@p@[`@KP{@fAEFSXe@l@c@h@WZY\\?BELk@v@MNa@l@"
}
},
{
"travelDuration": "323s",
"travelDistanceMeters": 1204,
"waitDuration": "0s",
"totalDuration": "323s",
"startTime": "2023-01-14T00:23:39Z",
"routePolyline": {
"points": "cuseFhjVSTY`@Yb@GHEDIJEF]f@IJi@r@oAbBeCfDKLaApAKNQVIPKPCDQJIBIBM@iAJeALqBVC@C?A?QBYDI@C?_@Dc@FO@a@FDp@HfAHvABVDl@Dj@PpCQDiALsALAQASKwAOgBEe@COCYEa@Es@Eg@"
}
},
{
"travelDuration": "209s",
"travelDistanceMeters": 665,
"waitDuration": "0s",
"totalDuration": "209s",
"startTime": "2023-01-14T00:33:12Z",
"routePolyline": {
"points": "{zteFxbajV?CAYEc@AMC_@AOAK?E?CCWAOAKCe@CY?WScDEm@d@EFA\\ENCB?XEVC^E`@EhBUVCNEB?@?\\Er@IMUe@k@k@w@AAMQa@i@SWQWMQi@u@AC?A"
}
}
],
"routePolyline": {
"points": "kvteFtfjVAA?C?C@C?A?C@AFMj@s@JKb@k@Zc@LSjA}ARWDGdAxAdAvAXa@@k@AsA\\c@FKp@_A\\c@Ze@fA{ALSFGd@o@rAgBB{BZc@RWj@w@x@eAHLNRHJbApAHLX\\V^?@hA~AT\\PVFFDHDFJNp@~@NRLNNTFFUZIJY^Y^g@p@[@KP{@fAEFSXe@l@c@h@WZY\\?BELk@v@MNa@l@STY@Yb@GHEDIJEF]f@IJi@r@oAbBeCfDKLaApAKNQVIPKPCDQJIBIBM@iAJeALqBVC@C?A?QBYDI@C?_@Dc@FO@a@FDp@HfAHvABVDl@Dj@PpCQDiALsALAQASKwAOgBEe@COCYEa@Es@Eg@?CAYEc@AMC_@AOAK?E?CCWAOAKCe@CY?WScDEm@d@EFA\\ENCB?XEVC^E`@EhBUVCNEB?@?\\Er@IMUe@k@k@w@AAMQa@i@SWQWMQi@u@AC?A"
},
"metrics": {
"performedShipmentCount": 3,
"travelDuration": "1001s",
"waitDuration": "0s",
"delayDuration": "0s",
"breakDuration": "0s",
"visitDuration": "1200s",
"totalDuration": "2201s",
"travelDistanceMeters": 3457
},
"travelSteps": [
{
"duration": "0s",
"routePolyline": {}
},
{
"duration": "0s",
"routePolyline": {}
},
{
"duration": "0s",
"routePolyline": {}
},
{
"duration": "227s",
"distanceMeters": 794,
"routePolyline": {
"points": "kvteFtfjVAA?C?C@C?A?C@AFMj@s@JKb@k@Zc@LSjA}ARWDGdAxAdAvAXa@@k@AsA\\c@FKp@_A\\c@Ze@fA{ALSFGd@o@rAgBB{BZc@"
}
},
{
"duration": "233s",
"distanceMeters": 791,
"routePolyline": {
"points": "cwseFti_jVRWj@w@x@eAHLNRHJbApAHLX\\V^?@hA~AT\\PVFFDHDFJNp@~@NRLNNTFFUZIJY^Y^g@p@[`@KP{@fAEFSXe@l@c@h@WZY\\?BELk@v@MNa@l@"
}
},
{
"duration": "322s",
"distanceMeters": 1205,
"routePolyline": {
"points": "cuseFhjVSTY`@Yb@GHEDIJEF]f@IJi@r@oAbBeCfDKLaApAKNQVIPKPCDQJIBIBM@iAJeALqBVC@C?A?QBYDI@C?_@Dc@FO@a@FDp@HfAHvABVDl@Dj@PpCQDiALsALAQASKwAOgBEe@COCYEa@Es@Eg@"
}
},
{
"duration": "208s",
"distanceMeters": 666,
"routePolyline": {
"points": "{zteFxbajV?CAYEc@AMC_@AOAK?E?CCWAOAKCe@CY?WScDEm@d@EFA\\ENCB?XEVC^E`@EhBUVCNEB?@?\\Er@IMUe@k@k@w@AAMQa@i@SWQWMQi@u@AC?A"
}
}
],
"vehicleDetour": "2201s",
"routeCosts": {
"model.vehicles.cost_per_hour": 24.455555555555556,
"model.vehicles.cost_per_kilometer": 34.57
},
"routeTotalCost": 59.025555555555556
}
],
"totalCost": 59.025555555555556,
"metrics": {
"aggregatedRouteMetrics": {
"performedShipmentCount": 3,
"travelDuration": "1001s",
"waitDuration": "0s",
"delayDuration": "0s",
"breakDuration": "0s",
"visitDuration": "1200s",
"totalDuration": "2201s",
"travelDistanceMeters": 3457
},
"usedVehicleCount": 1,
"earliestVehicleStartTime": "2023-01-14T00:00:00Z",
"latestVehicleEndTime": "2023-01-14T00:36:41Z",
"totalCost": 59.025555555555556,
"costs": {
"model.vehicles.cost_per_kilometer": 34.57,
"model.vehicles.cost_per_hour": 24.455555555555556
}
}
}
Phản hồi của tính năng Tối ưu hoá tuyến đường bao gồm một trường routes cấp cao nhất đại diện cho các tuyến đường được đề xuất, với mỗi xe là một tuyến đường. Vì yêu cầu mẫu trong hướng dẫn này chỉ chỉ định một xe, nên routes sẽ bao gồm một thông báo ShipmentRoute.
ShipmentRoute cơ sở lưu trú
Hai thuộc tính quan trọng nhất đối với loại thông báo ShipmentRoute là visits và transitions.
Mỗi Visit đại diện cho việc hoàn tất một lượt lấy hàng hoặc giao hàng từ một trong các VisitRequest của thông báo yêu cầu. Một lượt ghé thăm được chỉ định công việc một cách hiệu quả để một xe hoàn thành tại một địa điểm và thời điểm nào đó.
Mỗi Transition đại diện cho một xe di chuyển từ vị trí này đến vị trí tiếp theo. Quá trình chuyển đổi có thể xảy ra giữa một cặp điểm bắt đầu của xe, vị trí truy cập và điểm cuối của xe.
Để tái tạo toàn bộ tuyến đường của xe, bạn phải kết hợp visits và transitions của ShipmentRoute. Việc kết hợp các trường thành một tiến trình của hoạt động của xe sẽ có dạng như sau:
request.vehicles[0].startLocation -> transitions[0] -> visits[0] ->
transitions[1] -> visits[1] -> transitions[2] -> ... -> visits[3] ->
transitions[4] -> request.vehicles[0].endLocation
ShipmentRoute luôn có nhiều transitions hơn visits, vì xe phải di chuyển từ vị trí bắt đầu đến lần truy cập đầu tiên ở đầu tuyến và từ lần truy cập cuối cùng đến vị trí kết thúc ở cuối tuyến. Nếu xe thiếu vị trí bắt đầu hoặc kết thúc, thì transitions sẽ vẫn nhiều hơn visits một lần vì vị trí của lượt truy cập đầu tiên hoặc cuối cùng được dùng làm vị trí bắt đầu hoặc kết thúc của xe tương ứng.
Trong ví dụ này, 3 lượt đến lấy hàng đầu tiên có các lượt chuyển đổi giữa chúng với quãng đường và thời lượng bằng 0 vì cả 3 lượt đến lấy hàng đều có cùng một vị trí trong yêu cầu.
Hãy xem tài liệu tham khảo ShipmentRoute (REST, gRPC) để biết thêm thông tin chi tiết.
Tối ưu hoá thứ tự điểm trung gian đơn giản
Như ví dụ này minh hoạ, tính năng Tối ưu hoá tuyến đường mô hình hoá các lượt truy cập dưới dạng thuộc tính của lô hàng và không có khái niệm về điểm trung gian hoặc điểm dừng dưới dạng một thực thể độc lập. Tuy nhiên, bạn có thể biểu thị các điểm dừng hoặc điểm trung gian dưới dạng lô hàng với đúng một VisitRequest là điểm đến lấy hàng hoặc điểm đến giao hàng. Xe vẫn phải được chỉ định costPerHour hoặc costPerKilometer để trình tối ưu hoá tìm được tuyến đường tối ưu (thay vì tìm bất kỳ tuyến đường khả thi nào).