Trường hợp này tối ưu hoá thứ tự các điểm dừng được chỉ định cho một chiếc xe bằng thông số chi phí. Đây là chế độ đơn giản nhất của thao tác Tối ưu hoá tuyến đường, và để đảm bảo tất cả các điểm dừng đều được ghé thăm trong khung thời gian quy định.
Ví dụ sau đây minh hoạ tình huống cơ bản với một chiếc xe và 3 chiếc xe các lô hàng, tất cả đều bắt nguồn từ một địa điểm duy nhất được gọi là kho hàng.
Xem một 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
}
]
}
}
Trường yêu cầu Tối ưu hoá tuyến đường
Như đã đề cập trong phần Tổng quan, yêu cầu tối ưu hóa tuyến đường quan trọng nhất
là vehicles và shipments.
Ngoài phương tiện vận chuyển và lô hàng, yêu cầu bao gồm những thông tin sau trường:
Hình nhiều đường
populatePolylines và populateTransitionPolylines chỉ định liệu Tuyến
Tính năng tối ưu hoá sẽ trả về hình nhiều đường.
Dịch vụ này mã hoá các Polylines bằng cách sử dụng bộ mã hoá và giải mã nhiều dòng JS của Maps, đại diện cho
dữ liệu nhiều đường nhị phân bằng cách sử dụng các ký tự ASCII có thể in được. Bạn có thể sử dụng
Tiện ích bộ mã hoá Polyline tương tác để trực quan hoá các đường dẫn được tính toán bằng
Tối ưu hoá tuyến đường. Ví dụ trong hướng dẫn này sẽ thiết lập populatePolylines và
populateTransitionPolylines thành true nhưng các hướng dẫn khác đặt giá trị thành false thành
giảm kích thước phản hồi.
Xem phần Định dạng thuật toán đa dòng được mã hoá để biết nội dung mô tả về phương thức mã hoá .
Hạn chế về thời gian trên toàn cầu
model.globalStartTime và model.globalEndTime được đặt thành giá trị 24 tuỳ ý
giờ. Điều này giúp dấu thời gian đầu ra dễ diễn giải hơn.
Ghé thăm các vị trí
Yêu cầu mẫu này 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 trường hợp xe rời khỏi
điểm khác với điểm đến, như bãi đỗ xe có lối vào
ở một bên của toà nhà và lối ra ở bên kia. Trong lần này và các năm tiếp theo
hướng dẫn viên, điểm đến và điểm khởi hành được giả định là giống nhau.
waypoint đến và khởi hành cũng tồn tại để thay thế cho latLng.
Các trường Waypoint hỗ trợ bằng cách sử dụng Mã địa điểm của Google thay cho LatLng,
và cũng có thể chỉ định tiêu đề 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 sự ràng buộc rất linh hoạt do khoảng cách gần giao hàng và khung thời gian toàn cầu rộng.
- Tất cả các lô hàng phải được hoàn thành. Đây là chế độ mặc định khi
chi phí phạt chưa được chỉ định vào
shipments. costPerKilometervàcostPerHourđã được đặt trên xe.
Chi phí được đề cập trong bài viết Tham số mô hình chi phí.
Thuộc tính phản hồi 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 Tối ưu hoá tuyến đường bao gồm trường routes cấp cao nhất
thể hiện các tuyến đường được đề xuất, với một tuyến đường cho mỗi xe. Ví dụ
yêu cầu trong hướng dẫn này chỉ nêu rõ một chiếc xe, routes bao gồm một chiếc xe
Tin nhắn ShipmentRoute.
ShipmentRoute cơ sở lưu trú
Hai thuộc tính quan trọng nhất của loại thông báo ShipmentRoute là
visits và transitions.
Mỗi Visit thể hiện việc hoàn tất việc đến lấy hàng hoặc giao hàng từ một trong
VisitRequest của thông báo yêu cầu. Một lượt ghé thăm được giao công việc hiệu quả cho
hoàn thành bởi một chiếc xe tại một số địa điểm và thời gian.
Mỗi Transition đại diện cho chiếc xe đi từ một vị trí đến
tiếp theo. Quá trình chuyển đổi có thể xảy ra giữa một cặp điểm xuất phát của xe, lượt ghé thăm
thông tin vị trí và điểm cuối của xe.
Để xây dựng lại tuyến đường hoàn chỉnh của xe, visits của ShipmentRoute và
Phải kết hợp transitions. Kết hợp các trường thành tiến trình
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ó một transitions nhiều hơn visits, vì
chiếc xe phải đi từ vị trí bắt đầu đến lượt ghé thăm đầu tiên lúc bắt đầu
của tuyến đường và từ lần ghé thăm cuối cùng của nó đến vị trí kết thúc của nó ở cuối
tuyến đường. Nếu xe không có vị trí bắt đầu hoặc kết thúc, thì vẫn sẽ có vị trí đó
nhiều hơn transitions so với visits bởi vì vị trí của lần ghé thăm đầu tiên hoặc lần cuối cùng
được dùng làm vị trí bắt đầu hoặc kết thúc của xe.
Trong ví dụ này, 3 lượt đến lấy hàng đầu tiên sẽ có sự chuyển đổi giữa các lượt chuyển đổi với quãng đường và thời gian bằng 0 vì cả ba lần đến lấy hàng chia sẻ cùng một vị trí trong yêu cầu.
Xem tài liệu tham khảo về ShipmentRoute (REST, gRPC) để biết thêm
chi tiết.
Tối ưu hoá đơn đặt hàng điểm tham chiếu đơn giản
Như ví dụ này minh hoạ, mô hình Tối ưu hoá tuyến đường truy cập dưới dạng thuộc tính của
vận chuyển và không có khái niệm điểm trung gian hoặc điểm dừng như một cơ sở hạ tầng độc lập
thực thể. Tuy nhiên, bạn có thể biểu diễn các điểm dừng hoặc điểm tham chiếu dưới dạng quá trình vận chuyển
với đúng một VisitRequest làm dịch vụ đến lấy hàng hoặc giao hàng. Xe vẫn phải
được gán costPerHour hoặc costPerKilometer để trình tối ưu hoá tìm
tuyến đường tối ưu (trái ngược với việc tìm bất kỳ tuyến đường khả thi nào).