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 der 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 eine sehr lockere Einschränkung.
- Alle Sendungen müssen abgeschlossen sein. Das ist das Standardverhalten, wenn in
shipmentskeine Strafkosten angegeben sind. costPerKilometerundcostPerHoursind 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 Endstandort angegeben ist, ist transitions immer noch größer als visits, da der Standort des ersten oder letzten Besuchs als Start- bzw. Endstandort 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).