Tối ưu hoá đơn hàng dừng cơ bản cho hoạt động đến lấy hàng và giao hàng

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, các thuộc tính yêu cầu tối ưu hoá tuyến quan trọng nhất là vehiclesshipments.

Ngoài xe và lô hàng, yêu cầu này còn bao gồm các trường sau:

Hình nhiều đường

populatePolylinespopulateTransitionPolylines 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á đườ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 sẽ thiết lập populatePolylinespopulateTransitionPolylines 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 đường đa tuyến tính được mã hoá để biết nội dung mô tả về định dạng mã hoá.

Hạn chế về thời gian trên toàn cầu

model.globalStartTimemodel.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[].arrivalLocationmodel.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:

  1. 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 với các lô hàng và khoảng thời gian toàn cầu rộng.
  2. 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.
  3. costPerKilometercostPerHour đã đượ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 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 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 ShipmentRoutevisitstransitions.

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 bắt đầu của xe, vị trí truy cập 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 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 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).