Optimisation de base des commandes stop pour les retraits et les livraisons

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'opération d'optimisation d'itinéraire le plus simple. Il garantit que tous les arrêts sont desservis dans les délais impartis.

L'exemple suivant illustre un scénario de base avec un véhicule et trois expéditions, tous provenant d'un même lieu 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 de la requête d'optimisation des routes

Comme indiqué dans la présentation, les propriétés de requête d'optimisation des routes les plus importantes sont vehicles et shipments.

En plus du véhicule et des livraisons, la requête inclut les champs suivants:

Polylignes

populatePolylines et populateTransitionPolylines spécifient si l'optimisation des routes doit renvoyer des polylignes.

Le service encode les polylignes à l'aide du codec de polyligne Maps JS, qui représente les données de polylignes binaires à l'aide de caractères ASCII imprimables. Vous pouvez utiliser l'utilitaire d'encodage interactif des polylignes pour visualiser les chemins calculés par l'optimisation des routes. L'exemple de ce guide définit populatePolylines et populateTransitionPolylines sur "true", mais d'autres guides les définissent sur "false" afin de réduire la taille de la réponse.

Consultez la section Format d'algorithme des polylignes encodées pour obtenir une description du format d'encodage.

Important :Route Optimization convertit les barres obliques inverses (\) des polylignes en double barre oblique inverse (\\) conformément aux instructions du format d'algorithme des polylignes encodées. En revanche, l'outil d'encodage interactif des polylignes s'attend à recevoir des barres obliques inverses uniques non échappées (\) dans son entrée de polyligne encodée. Avant de décoder une polyligne renvoyée par l'optimisation des routes, remplacez les doubles barres obliques inverses par des barres obliques inverses simples.

Contraintes de temps globales

model.globalStartTime et model.globalEndTime sont définis sur une période arbitraire de 24 heures. Cela facilite l'interprétation des horodatages de sortie.

Visiter des lieux

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 cas où le véhicule part d'un point différent de celui où il arrive, par exemple un parking avec une entrée d'un côté du bâtiment et une sortie sur un autre. Dans ce guide et les suivants, les points d'arrivée et de départ sont supposés être identiques.

Les lieux d'arrivée et de départ waypoint peuvent également servir d'alternative à latLng. Les champs Waypoint acceptent l'utilisation des ID de lieu Google au lieu de LatLng, et peuvent également spécifier des en-têtes de véhicules. 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:

1. Toutes les activités doivent être terminées 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 laxiste étant donné la proximité des expéditions et la grande période mondiale.
2. Tous les envois doivent être finalisés. Il s'agit du comportement par défaut lorsque les coûts des pénalités ne sont pas spécifiés dans shipments.
3. costPerKilometer et costPerHour sont définis sur le véhicule.

Les coûts sont abordés dans la section Paramètres du modèle de coût.

Avertissement :Veillez à spécifier au moins un paramètre "cost". Si les paramètres de coût ne contraignent pas ShipmentModel, Route Optimization renvoie n'importe quelle route pouvant être réalisée dans la fenêtre de temps autorisée, indépendamment de la durée ou de la durée.

Propriétés de la réponse d'optimisation des routes

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 d'optimisation des routes inclut un champ routes de premier niveau 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 de propriétés

Les deux propriétés les plus importantes pour le type de message ShipmentRoute sont visits et transitions.

Chaque Visit représente l'achèvement d'un retrait ou d'une livraison à partir de l'un des VisitRequest du message de requête. Une visite se voit attribuer des tâches à effectuer par un véhicule à un endroit et à un moment précis.

Chaque Transition représente le véhicule se déplaçant d'un emplacement à un autre. Des transitions peuvent se produire entre deux points de départ du véhicule, un lieu de visite et l'arrivée du véhicule.

Pour reconstituer l'itinéraire complet du véhicule, les champs visits et transitions de ShipmentRoute doivent être combinés. La combinaison de 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 a toujours un transitions de plus que visits, car le véhicule doit voyager de sa position de départ à sa première visite au début de l'itinéraire, et de sa dernière visite à son point d'arrivée en fin d'itinéraire. Si le véhicule n'a pas de lieu de départ ou d'arrivée, il y aura toujours un transitions de plus que visits, car le lieu de la première ou de la dernière visite est utilisé respectivement comme lieu de départ ou d'arrivée du véhicule.

Dans cet exemple, les trois premières visites de prise en charge présentent des transitions entre elles avec une distance et une durée nulles, car elles partagent le même emplacement dans la requête.

Pour en savoir plus, consultez la documentation de référence sur ShipmentRoute (REST, gRPC).

Remarque :Les champs qui se terminent par Index reflètent la position d'un message correspondant tel qu'il est apparu dans la requête. Lorsque la valeur d'un champ Index est égale à zéro, l'API l'omet de la réponse. Dans l'exemple de réponse, la première entrée visits est un retrait qui correspond à shipments[0] dans le message de requête.

Remarque :Si les envois omettent de recevoir des visites, l'optimiseur part du principe que les véhicules commencent par des colis déjà chargés. Dans ce cas, les fonctionnalités comme UnloadingPolicy (FIFO ou LIFO) peuvent ne pas s'appliquer, car il n'y a pas de séquence de récupération.

Optimisation simple de l'ordre des points de cheminement

Comme le montre cet exemple, Route Optimization modélise les visites en tant que propriétés des expéditions et n'intègre pas la notion de point de cheminement ou d'arrêt en tant qu'entité indépendante. Toutefois, il est possible de représenter des arrêts ou des points de cheminement comme des colis avec exactement un seul VisitRequest pour les retraits ou les livraisons. Le véhicule doit toujours se voir attribuer un costPerHour ou un costPerKilometer pour que l'optimiseur puisse trouver un itinéraire optimal (au lieu de trouver un itinéraire réalisable).