Pengoptimalan pesanan perhentian dasar untuk pengambilan dan pengiriman

Skenario ini mengoptimalkan urutan perhentian yang ditetapkan ke kendaraan dengan parameter biaya sederhana. Ini adalah mode operasi Pengoptimalan Rute yang paling sederhana, dan memastikan bahwa semua perhentian dikunjungi dalam jangka waktu yang ditentukan.

Contoh berikut mengilustrasikan skenario dasar dengan satu kendaraan dan tiga pengiriman, yang semuanya berasal dari satu lokasi yang disebut depot.

Lihat contoh permintaan

      {
        "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
            }
          ]
        }
      }

Kolom permintaan Route Optimization

Seperti yang disebutkan dalam Ringkasan, properti permintaan Route Optimization yang paling penting adalah vehicles dan shipments.

Selain kendaraan dan pengiriman, permintaan ini menyertakan kolom berikut:

Polyline

populatePolylines dan populateTransitionPolylines menentukan apakah Route Optimization harus menampilkan polyline.

Layanan ini mengenkode Polyline menggunakan codec polyline Maps JS, yang mewakili data polyline biner menggunakan karakter ASCII yang dapat dicetak. Anda dapat menggunakan Utilitas Encoder Polyline Interaktif untuk memvisualisasikan jalur yang dihitung oleh Route Optimization. Contoh dalam panduan ini menetapkan populatePolylines dan populateTransitionPolylines ke benar, tetapi panduan lain menetapkannya ke salah untuk mengurangi ukuran respons.

Lihat Format Algoritme Polyline yang Dienkodekan untuk deskripsi format enkode.

Batasan waktu global

model.globalStartTime dan model.globalEndTime ditetapkan ke periode 24 jam arbitrer. Hal ini membuat stempel waktu output lebih mudah ditafsirkan.

Kunjungi lokasi

Contoh permintaan hanya menggunakan model.shipments[].pickups[].arrivalLocation dan model.shipments[].deliveries[].arrivalLocation. Ada juga properti departureLocation untuk situasi saat kendaraan berangkat dari titik yang berbeda dengan titik kedatangannya, seperti kompleks parkir dengan pintu masuk di satu sisi bangunan dan pintu keluar di sisi lain. Dalam panduan ini dan panduan berikutnya, titik kedatangan dan keberangkatan diasumsikan sama.

Kedatangan dan keberangkatan waypoint juga ada sebagai alternatif untuk latLng. Kolom Waypoint mendukung penggunaan ID Tempat Google sebagai alternatif untuk LatLng, dan juga dapat menentukan arah kendaraan. Lihat dokumentasi referensi (REST, gRPC) untuk mengetahui detail selengkapnya.

Batasan dalam contoh

Skenario ini membatasi pengoptimal dengan beberapa cara:

  1. Semua aktivitas harus diselesaikan antara waktu mulai dan waktu berakhir global. Dalam skenario ini, waktu mulai dan waktu berakhir adalah batasan yang sangat longgar mengingat kedekatan pengiriman dan periode waktu global yang luas.
  2. Semua pengiriman harus selesai. Ini adalah perilaku default jika biaya penalti tidak ditentukan di shipments.
  3. costPerKilometer dan costPerHour ditetapkan pada kendaraan.

Biaya ditangani di Parameter Model Biaya.

Properti respons Pengoptimalan Rute

Melihat respons terhadap contoh permintaan

    {
      "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
        }
      }
    }

Respons Pengoptimalan Rute menyertakan kolom routes tingkat atas yang mewakili rute yang diusulkan, dengan satu rute per kendaraan. Karena contoh permintaan dalam panduan ini hanya menentukan satu kendaraan, routes menyertakan satu pesan ShipmentRoute.

ShipmentRoute properti

Dua properti terpenting untuk jenis pesan ShipmentRoute adalah visits dan transitions.

Setiap Visit mewakili penyelesaian pengambilan atau pengiriman dari salah satu VisitRequest pesan permintaan. Kunjungan secara efektif diberi tugas untuk selesai oleh kendaraan di suatu tempat dan waktu.

Setiap Transition mewakili kendaraan yang melakukan perjalanan dari satu lokasi ke lokasi berikutnya. Transisi dapat terjadi antara sepasang titik awal kendaraan, lokasi kunjungan, dan endpoint kendaraan.

Untuk merekonstruksi rute lengkap kendaraan, visits dan transitions ShipmentRoute harus digabungkan. Kombinasi kolom ke dalam progres aktivitas kendaraan terlihat seperti berikut:

request.vehicles[0].startLocation -> transitions[0] -> visits[0] ->
transitions[1] -> visits[1] -> transitions[2] -> ... -> visits[3] ->
transitions[4] -> request.vehicles[0].endLocation

ShipmentRoute selalu memiliki satu transitions lebih banyak daripada visits, karena kendaraan harus melakukan perjalanan dari lokasi awal ke kunjungan pertamanya di awal rute dan dari kunjungan terakhirnya ke lokasi akhirnya di akhir rute. Jika kendaraan tidak memiliki lokasi awal atau akhir, akan tetap ada satu transitions lebih banyak daripada visits karena lokasi kunjungan pertama atau terakhir digunakan sebagai lokasi awal atau akhir kendaraan.

Dalam contoh ini, tiga kunjungan pengambilan pertama memiliki transisi di antara mereka dengan jarak dan durasi nol karena ketiga pengambilan tersebut berbagi lokasi yang sama dalam permintaan.

Lihat dokumentasi referensi ShipmentRoute (REST, gRPC) untuk mengetahui detail selengkapnya.

Pengoptimalan urutan titik jalan yang sederhana

Seperti yang ditunjukkan contoh ini, Route Optimization memodelkan kunjungan sebagai properti pengiriman dan tidak memiliki konsep titik perhentian atau perhentian sebagai entitas independen. Namun, Anda dapat merepresentasikan perhentian atau titik jalan sebagai pengiriman dengan tepat satu VisitRequest sebagai pengambilan atau pengiriman. Kendaraan masih harus diberi costPerHour atau costPerKilometer agar pengoptimal dapat menemukan rute yang optimal (bukan menemukan rute yang memungkinkan).