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:
- 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.
- Alle Sendungen müssen abgeschlossen sein. Das ist das Standardverhalten, wenn in
shipments
keine Strafkosten angegeben sind. costPerKilometer
undcostPerHour
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 VisitRequest
s 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).