Optimierung von Bestellungen zum Abholen und Liefern

In diesem Szenario wird die Reihenfolge der Haltestellen optimiert, die einem Fahrzeug mit einfachen cost-Parameter. Dies ist der einfachste Modus der Routenoptimierung. stellt sicher, dass alle Haltestellen innerhalb der angegebenen Zeitspanne angefahren werden.

Das folgende Beispiel veranschaulicht ein grundlegendes Szenario mit einem Fahrzeug und drei Fahrzeugen. Sendungen, die alle aus einem einzigen, sogenannten Depot, stammen.

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 Routenoptimierung

Wie in der Übersicht erwähnt, ist die wichtigste Anfrage zur Routenoptimierung sind vehicles und shipments.

Neben dem Fahrzeug und den Sendungen umfasst die Anfrage Folgendes: Felder:

Polylinien

populatePolylines und populateTransitionPolylines geben an, ob eine Route Die Optimierung sollte Polylinien zurückgeben.

Der Dienst codiert Polylinien mithilfe des Maps JS-Polyline-Codecs, der die binäre Polyliniendaten mit druckbaren ASCII-Zeichen verwenden. 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 „true“, aber andere Führungslinien setzen sie auf „false“, um die Antwortgröße zu reduzieren.

Eine Beschreibung der Codierung finden Sie unter Format des Algorithmus für codierte Polylinien. Format.

Globale Zeitbeschränkungen

model.globalStartTime und model.globalEndTime sind auf einen beliebigen Wert 24 festgelegt. Stunden. Dadurch sind Ausgabezeitstempel leichter zu interpretieren.

Orte besuchen

In der Beispielanfrage werden nur model.shipments[].pickups[].arrivalLocation und model.shipments[].deliveries[].arrivalLocation. Es gibt auch eine departureLocation, wenn das Fahrzeug aus einer an einem anderen Punkt als dem, an dem er ankommt, z. B. ein Parkplatz mit einer Einfahrt und einem Ausgang auf einer anderen Seite des Gebäudes. In diesem und den nachfolgenden Leitfäden wird davon ausgegangen, dass der Start- und Zielpunkt identisch sind.

Die Ankunfts- und Abfahrtszeiten „waypoint“ sind auch als Alternative zu latLng verfügbar. Waypoint-Felder unterstützen die Verwendung von Google Place-IDs als Alternative zu LatLng, und auch Fahrzeug-Überschriften angeben. Referenzdokumentation ansehen (REST, gRPC) für weitere Informationen.

Einschränkungen im Beispiel

In diesem Szenario wird das Optimierungstool auf mehrere Arten eingeschränkt:

  1. Alle Aktivitäten müssen zwischen der globalen Start- und Endzeit abgeschlossen sein. In diesem Szenario sind Start- und Endzeiten Lieferungen und das weite globale Zeitfenster.
  2. Alle Sendungen müssen abgeschlossen sein. Dies ist die Standardeinstellung, wenn Strafkosten sind in shipments nicht angegeben.
  3. costPerKilometer und costPerHour sind am Fahrzeug eingestellt.

Kosten werden unter Kostenmodellparameter behandelt.

Antwortattribute für die Routenoptimierung

Antwort auf die Beispielanfrage 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 der Routenoptimierung enthält ein routes-Feld der obersten Ebene, das stellt die vorgeschlagenen Routen mit einer Route pro Fahrzeug dar. Da das Beispiel Anfrage in diesem Leitfaden nur ein Fahrzeug angibt, routes enthält ein Fahrzeug ShipmentRoute-Nachricht.

ShipmentRoute Unterkünfte

Die beiden wichtigsten Attribute für den Nachrichtentyp ShipmentRoute sind: visits und transitions

Jedes Visit steht für den Abschluss einer Abholung oder Lieferung an einem der Die VisitRequests der Anfragenachricht. Einem Besuch wird effektiv Arbeit zugewiesen, von einem Fahrzeug an einem bestimmten Ort und zu einer bestimmten Uhrzeit durchgeführt werden muss.

Jeder Transition steht für das Fahrzeug, das von einem Standort zum Zwischen zwei Startpunkten des Fahrzeugs, einem Besuch, Standort und Endpunkt des Fahrzeugs.

Zur Rekonstruktion der gesamten Route des ShipmentRoute visits und transitions müssen kombiniert werden. Die Kombination von Feldern zu einer Abfolge von sehen so aus:

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

Ein ShipmentRoute hat immer ein transitions mehr als visits, da die Fahrzeug muss von seinem Startort bis zu seinem ersten Besuch am Anfang fahren der Route und von ihrem letzten Besuch bis zu ihrem Ziel am Ende der Route Route. Wenn kein Start- oder Zielpunkt für das Fahrzeug angegeben ist, wird trotzdem einer angezeigt mehr transitions als visits, da der Standort des ersten oder letzten Besuchs ist als Start- bzw. Zielpunkt des Fahrzeugs verwendet.

In diesem Beispiel haben die ersten drei Abholbesuche Übergänge. ohne Strecke und Reisezeit, weil alle drei denselben Standort in der Anfrage haben.

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

Einfache Optimierung der Wegpunktreihenfolge

Wie dieses Beispiel zeigt, modelliert die Routenoptimierung Besuche als Eigenschaften von Sendungen und nicht als unabhängige Wegpunkte oder Haltestellen Entität. Es ist jedoch möglich, Haltestellen oder Wegpunkte als Lieferungen darzustellen. mit genau einem VisitRequest für Abholung oder Lieferung. Das Fahrzeug muss costPerHour oder costPerKilometer zugewiesen werden, damit das Optimierungstool (im Gegensatz zum Ermitteln einer praktikablen Route).