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
shipmentskeine Strafkosten angegeben sind. costPerKilometerundcostPerHoursind 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.