Optimierung von Bestellungen zum Abholen und Liefern

In diesem Szenario wird die Reihenfolge der Haltestellen, die einem Fahrzeug zugewiesen sind, mit einfachen Kostenparametern optimiert. Dies ist der einfachste Modus der Routenoptimierung. Er sorgt dafür, dass alle Haltestellen innerhalb des angegebenen Zeitraums angefahren werden.

Das folgende Beispiel zeigt ein einfaches Szenario mit einem Fahrzeug und drei Lieferungen, die alle von einem einzigen Standort stammen, dem sogenannten Depot.

Beispielanfrage ansehen

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

Anfragefelder für die Routenoptimierung

Wie in der Übersicht erwähnt, sind vehicles und shipments die wichtigsten Anfrageeigenschaften für die Routenoptimierung.

Neben einem Fahrzeug und den Sendungen enthält die Anfrage die folgenden Felder:

Polylinien

Mit populatePolylines und populateTransitionPolylines wird angegeben, ob bei der Routenoptimierung Polylinien zurückgegeben werden sollen.

Der Dienst codiert Polylinien mit dem Maps JS-Polylinien-Codec, der binäre Polyliniendaten mit druckbaren ASCII-Zeichen darstellt. Mit dem Interaktiven Dienstprogramm für die Codierung von Polylinien können Sie die von der Routenoptimierung berechneten Pfade visualisieren. Im Beispiel in diesem Leitfaden werden populatePolylines und populateTransitionPolylines auf „wahr“ gesetzt. In anderen Leitfäden werden sie jedoch auf „falsch“ gesetzt, um die Antwortgröße zu verringern.

Eine Beschreibung des Codierungsformats finden Sie unter Algorithmusformat für codierte Polylinien.

Globale Zeitbeschränkungen

model.globalStartTime und model.globalEndTime sind auf einen beliebigen 24-Stunden-Zeitraum festgelegt. So lassen sich die Zeitstempel der Ausgabe leichter interpretieren.

Orte besuchen

In der Beispielanfrage werden nur model.shipments[].pickups[].arrivalLocation und model.shipments[].deliveries[].arrivalLocation verwendet. Es gibt auch ein departureLocation-Attribut für Situationen, in denen das Fahrzeug von einem anderen Punkt als dem ankommt, an dem es ankommt, z. B. ein Parkplatzkomplex mit einem Eingang auf der einen Seite des Gebäudes und einem Ausgang auf der anderen. In diesem und den nachfolgenden Leitfäden wird davon ausgegangen, dass der Start- und Zielpunkt identisch sind.

Ankunft und Abfahrt waypoint sind auch als Alternative zu latLng verfügbar. In Waypoint-Feldern können Google-Orts-IDs als Alternative zu LatLng verwendet und Fahrzeugrichtungen angegeben werden. Weitere Informationen finden Sie in der Referenzdokumentation (REST, gRPC).

Einschränkungen im Beispiel

Dieses Szenario schränkt den Optimierer auf verschiedene Weise ein:

  1. Alle Aktivitäten müssen zwischen den globalen Start- und Endzeiten abgeschlossen sein. In diesem Szenario sind Start- und Endzeiten aufgrund der Nähe der Sendungen und des großen globalen Zeitfensters sehr lockere Einschränkungen.
  2. Alle Sendungen müssen abgeschlossen sein. Das ist das Standardverhalten, wenn in shipments keine Strafkosten angegeben sind.
  3. costPerKilometer und costPerHour sind im Fahrzeug festgelegt.

Kosten werden unter Kostenmodellparameter behandelt.

Antworteigenschaften der Routenoptimierung

Beispiel für eine Antwort auf eine Anfrage ansehen

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

Die Antwort zur Routenoptimierung enthält ein übergeordnetes Feld routes, das die vorgeschlagenen Routen darstellt, eine Route pro Fahrzeug. Da in der Beispielanfrage in diesem Leitfaden nur ein Fahrzeug angegeben ist, enthält routes eine ShipmentRoute-Nachricht.

ShipmentRoute Unterkünfte

Die beiden wichtigsten Eigenschaften für den Nachrichtentyp ShipmentRoute sind visits und transitions.

Jede Visit steht für den Abschluss einer Abholung oder Zustellung von einem der VisitRequests der Anfragenachricht. Einem Besuch wird eine Aufgabe zugewiesen, die von einem Fahrzeug an einem bestimmten Ort und zu einer bestimmten Zeit ausgeführt werden soll.

Jede Transition steht für das Fahrzeug, das von einem Ort zum nächsten fährt. Übergänge können zwischen dem Startpunkt des Fahrzeugs, einem Besuchsort und dem Endpunkt des Fahrzeugs erfolgen.

Um die vollständige Route des Fahrzeugs zu rekonstruieren, müssen die visits und transitions des ShipmentRoute kombiniert werden. Die Kombination der Felder zu einer Abfolge von Fahrzeugaktivitäten sieht so aus:

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

Eine ShipmentRoute hat immer eine transitions mehr als eine visits, da das Fahrzeug vom Startort zum ersten Besuch am Anfang der Route und vom letzten Besuch zum Endort am Ende der Route fahren muss. Wenn für das Fahrzeug kein Start- oder Zielort angegeben ist, ist transitions immer noch größer als visits, da der Standort des ersten oder letzten Besuchs als Start- bzw. Zielort des Fahrzeugs verwendet wird.

In diesem Beispiel haben die ersten drei Abholvorgänge Übergänge ohne Entfernung und Dauer, da sich alle drei Abholvorgänge in der Anfrage am selben Ort befinden.

Weitere Informationen finden Sie in der ShipmentRoute-Referenzdokumentation (REST, gRPC).

Einfache Optimierung der Wegpunktreihenfolge

Wie dieses Beispiel zeigt, werden bei der Routenoptimierung Besuche als Eigenschaften von Lieferungen modelliert. Wegpunkte oder Haltestellen werden nicht als eigenständige Entität betrachtet. Es ist jedoch möglich, Haltestellen oder Wegpunkte als Sendungen mit genau einer VisitRequest als Abhol- oder Zustelladresse darzustellen. Dem Fahrzeug muss weiterhin eine costPerHour oder costPerKilometer zugewiesen werden, damit der Optimierer eine optimale Route finden kann (anstatt eine beliebige mögliche Route).