Ce scénario optimise l'ordre des arrêts attribués à un véhicule avec des paramètres de coût simples. Il s'agit du mode d'optimisation des itinéraires le plus simple. Il garantit que tous les arrêts sont desservis dans le délai spécifié.
L'exemple suivant illustre un scénario de base avec un véhicule et trois envois, tous provenant d'un seul emplacement appelé dépôt.
Voir un exemple de requête
{
"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
}
]
}
}
Champs d'une requête d'optimisation des itinéraires
Comme indiqué dans la présentation, les propriétés de requête d'optimisation de parcours les plus importantes sont vehicles et shipments.
En plus d'un véhicule et d'envois, la requête inclut les champs suivants:
Polylignes
populatePolylines et populateTransitionPolylines indiquent si l'optimisation de l'itinéraire doit renvoyer des polylignes.
Le service encode les polylignes à l'aide du codec de polyligne Maps JS, qui représente les données de polyligne binaires à l'aide de caractères ASCII imprimables. Vous pouvez utiliser l'utilitaire d'encodage interactif des polylignes pour visualiser les parcours calculés par l'optimisation des itinéraires. L'exemple de ce guide définit populatePolylines et populateTransitionPolylines sur "true", mais d'autres guides les définissent sur "false" pour réduire la taille de la réponse.
Pour obtenir une description du format d'encodage, consultez la section Format d'algorithme des polylignes encodées.
Contraintes temporelles globales
model.globalStartTime et model.globalEndTime sont définis sur une période de 24 heures arbitraire. Cela facilite l'interprétation des codes temporels de sortie.
Lieux visités
L'exemple de requête n'utilise que model.shipments[].pickups[].arrivalLocation et model.shipments[].deliveries[].arrivalLocation. Il existe également une propriété departureLocation pour les situations où le véhicule part d'un point différent de celui où il arrive, comme un parking avec une entrée d'un côté du bâtiment et une sortie de l'autre. Dans ce guide et les suivants, nous partons du principe que les points d'arrivée et de départ sont identiques.
Les waypoint d'arrivée et de départ existent également en remplacement de latLng.
Les champs Waypoint permettent d'utiliser des ID de lieu Google au lieu de LatLng et peuvent également spécifier les directions du véhicule. Pour en savoir plus, consultez la documentation de référence (REST, gRPC).
Contraintes de l'exemple
Ce scénario contraint l'optimiseur de plusieurs manières:
- Toute activité doit être effectuée entre les heures de début et de fin globales. Dans ce scénario, les heures de début et de fin sont une contrainte très souple compte tenu de la proximité des envois et de la large fenêtre temporelle globale.
- Toutes les livraisons doivent être effectuées. Il s'agit du comportement par défaut lorsque les coûts de pénalité ne sont pas spécifiés dans
shipments. costPerKilometeretcostPerHoursont définis sur le véhicule.
Les coûts sont abordés dans la section Paramètres du modèle de coûts.
Propriétés de réponse de Route Optimization
Afficher une réponse à l'exemple de requête
{
"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
}
}
}
La réponse de l'optimisation des itinéraires inclut un champ routes de niveau supérieur qui représente les itinéraires proposés, avec un itinéraire par véhicule. Étant donné que l'exemple de requête de ce guide ne spécifie qu'un seul véhicule, routes inclut un message ShipmentRoute.
ShipmentRoute établissements
Les deux propriétés les plus importantes pour le type de message ShipmentRoute sont visits et transitions.
Chaque Visit représente la fin d'une collecte ou d'une livraison à partir de l'un des VisitRequest du message de requête. Une visite est une tâche attribuée à un véhicule à un endroit et à un moment donnés.
Chaque Transition représente le véhicule se déplaçant d'un emplacement à un autre. Des transitions peuvent se produire entre un point de départ et un point d'arrivée du véhicule, ainsi qu'entre un lieu visité et un point d'arrivée du véhicule.
Pour reconstruire l'itinéraire complet du véhicule, les visits et transitions de ShipmentRoute doivent être combinés. La combinaison des champs dans une progression de l'activité du véhicule se présente comme suit:
request.vehicles[0].startLocation -> transitions[0] -> visits[0] ->
transitions[1] -> visits[1] -> transitions[2] -> ... -> visits[3] ->
transitions[4] -> request.vehicles[0].endLocation
Un ShipmentRoute comporte toujours un transitions de plus qu'un visits, car le véhicule doit se déplacer de son emplacement de départ à sa première visite au début de l'itinéraire et de sa dernière visite à son emplacement d'arrivée à la fin de l'itinéraire. Si le véhicule ne comporte pas de lieu de départ ou d'arrivée, il y aura toujours un transitions de plus que visits, car l'emplacement de la première ou de la dernière visite est utilisé comme lieu de départ ou d'arrivée du véhicule, respectivement.
Dans cet exemple, les trois premières visites de ramassage ont des transitions entre elles avec une distance et une durée nulles, car les trois ramassages partagent le même emplacement dans la requête.
Pour en savoir plus, consultez la documentation de référence ShipmentRoute (REST, gRPC).
Optimisation simple de l'ordre des points de cheminement
Comme le montre cet exemple, l'optimisation de l'itinéraire modélise les visites en tant que propriétés des envois et ne dispose pas de la notion de points de cheminement ou d'arrêts en tant qu'entité indépendante. Toutefois, il est possible de représenter des arrêts ou des points de repère en tant qu'envois avec exactement un VisitRequest en tant que ramassage ou livraison. Le véhicule doit toujours être associé à un costPerHour ou à un costPerKilometer pour que l'optimiseur trouve un itinéraire optimal (plutôt que de trouver un itinéraire réalisable).