In diesem Szenario wird die Reihenfolge der Haltestellen optimiert, die einem Fahrzeug mit einfachen Kostenparametern zugewiesen sind. Dies ist die einfachste Methode der Routenoptimierung. Sie sorgt dafür, dass alle Haltestellen innerhalb des angegebenen Zeitraums erreicht werden.
Das folgende Beispiel veranschaulicht ein grundlegendes Szenario mit einem Fahrzeug und drei Sendungen, die alle von einem einzigen Standort ausgehen, 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 Eigenschaften der Anfragen zur Routenoptimierung.
Neben einem Fahrzeug und den Sendungen umfasst die Anfrage die folgenden Felder:
Polylinien
populatePolylines
und populateTransitionPolylines
geben an, ob bei der Routenoptimierung Polylinien zurückgegeben werden sollen.
Der Dienst codiert Polylinien mit dem Google 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 durch die Routenoptimierung berechneten Pfade visualisieren. Im Beispiel in diesem Leitfaden werden populatePolylines
und populateTransitionPolylines
auf „true“ gesetzt, in anderen aber auf „false“, um die Antwortgröße zu reduzieren.
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. Dies vereinfacht die Interpretation der Ausgabezeitstempel.
Besuchsorte
In der Beispielanfrage werden nur model.shipments[].pickups[].arrivalLocation
und model.shipments[].deliveries[].arrivalLocation
verwendet. Es gibt auch die Eigenschaft departureLocation
für Situationen, in denen das Fahrzeug an einem anderen Punkt als an seinem Ankunftsort abfährt, z. B. bei einer Parkanlage mit einem Eingang auf einer Seite des Gebäudes und einem Ausgang auf einer anderen. In dieser und in den nachfolgenden Leitfäden wird davon ausgegangen, dass die Ankunfts- und Abfahrtspunkte identisch sind.
Die Ankunfts- und Abfahrtszeiten waypoint
sind eine Alternative zu latLng
.
Waypoint
-Felder unterstützen die Verwendung von Google Place IDs als Alternative zu LatLng
und können auch Fahrzeugüberschriften angeben. Weitere Informationen finden Sie in der Referenzdokumentation (REST, gRPC).
Einschränkungen im Beispiel
In diesem Szenario wird die Optimierung auf verschiedene Arten eingeschränkt:
- Alle Aktivitäten müssen zwischen der globalen Start- und Endzeit abgeschlossen sein. In diesem Szenario sind Start- und Endzeiten aufgrund der unmittelbaren Nähe der Lieferungen und des großen globalen Zeitfensters eine sehr laxe Einschränkung.
- Alle Sendungen müssen abgeschlossen sein. Das ist die Standardeinstellung, wenn unter
shipments
keine Strafkosten angegeben sind. costPerKilometer
undcostPerHour
sind für das Fahrzeug festgelegt.
Die Kosten werden unter Kostenmodellparameter behandelt.
Antwortattribute der 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 zur Routenoptimierung enthält das übergeordnete Feld routes
, das die vorgeschlagenen Routen mit einer Route pro Fahrzeug darstellt. Da die Beispielanfrage in diesem Leitfaden nur ein Fahrzeug angibt, enthält routes
genau eine ShipmentRoute
-Nachricht.
ShipmentRoute
Unterkünfte
Die beiden wichtigsten Eigenschaften für den Nachrichtentyp ShipmentRoute
sind visits
und transitions
.
Jedes Visit
steht für den Abschluss einer Abholung oder Lieferung von einem VisitRequest
der Anfragenachricht. Bei einem Besuch werden Aufgaben zugewiesen,
die von einem Fahrzeug an einem bestimmten Ort und zu einer bestimmten Zeit erledigt werden sollen.
Jedes Transition
steht für ein Fahrzeug, das von einem Standort zum nächsten fährt. Es können Übergänge zwischen zwei Startpunkten des Fahrzeugs, einem Ort des Besuchs und dem Endpunkt des Fahrzeugs erfolgen.
Damit die vollständige Route des Fahrzeugs rekonstruiert werden kann, müssen die visits
und transitions
der 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
Ein ShipmentRoute
hat immer ein transitions
-Element mehr als visits
, da sich das Fahrzeug am Anfang der Route von seinem Startort zum ersten Durchgang und von seinem letzten Besuch bis zu seinem Endpunkt am Ende der Route bewegen muss. Wenn das Fahrzeug keinen Start- oder Endpunkt hat, ist trotzdem eine transitions
mehr als visits
vorhanden, da der Standort des ersten oder letzten Besuchs als Start- oder Endpunkt des Fahrzeugs verwendet wird.
In diesem Beispiel haben die ersten drei Abholorte Übergänge zwischen ihnen ohne Entfernung und Dauer, da alle drei Abholorte denselben Standort in der Anfrage teilen.
Weitere Informationen finden Sie in der ShipmentRoute
-Referenzdokumentation (REST, gRPC).
Einfache Optimierung der Wegpunktreihenfolge
Wie in diesem Beispiel gezeigt, modelliert die Routenoptimierung Besuche als Eigenschaften von Schiffen und hat keine Vorstellung von Wegpunkten oder Haltestellen als unabhängige Einheit. Es ist jedoch möglich, Haltestellen oder Wegpunkte als Lieferungen mit genau einer VisitRequest
als Abholung oder Lieferung darzustellen. Dem Fahrzeug muss weiterhin ein costPerHour
oder costPerKilometer
zugewiesen werden, damit die Optimierung eine optimale Route und keine durchführbare Route finden kann.