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 à l'aide de paramètres de coût simples. Il s'agit du mode d'optimisation d'itinéraire le plus simple, qui garantit que tous les arrêts sont desservis dans le délai spécifié.

L'exemple suivant illustre un scénario de base dans lequel un véhicule et trois livraisons proviennent toutes d'un seul et 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 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 des polylignes binaires à l'aide de caractères ASCII imprimables. Vous pouvez utiliser l'utilitaire Interactive Polyline Encoder pour visualiser les chemins 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 des réponses.

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

Important :L'optimisation des routes convertit les barres obliques inverses (\) dans des polylignes en double barre oblique inverse (\\) conformément aux instructions du format d'algorithme des polylignes encodées. Cependant, l'utilitaire interactif de l'encodeur de polylignes attend une seule barre oblique inverse sans échappement (\) 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 dans le monde

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

Les waypoint d'arrivée et de départ sont également disponibles à la place de latLng. Les champs Waypoint acceptent l'utilisation d'ID de lieu Google à la place de LatLng et peuvent également spécifier des en-têtes de véhicule. Pour en savoir plus, consultez la documentation de référence (REST, gRPC).

Contraintes dans l'exemple

Ce scénario impose des contraintes à l'optimiseur de plusieurs manières:

1. Toute activité doit être terminée entre les heures de début et de fin globales. Dans ce scénario, les heures de début et de fin constituent une contrainte très laxiste, étant donné la proximité des expéditions et la large fenêtre temporelle mondiale.
2. Tous les envois doivent être effectués. Il s'agit du comportement par défaut lorsque les pénalités ne sont pas spécifiées sur shipments.
3. costPerKilometer et costPerHour sont définis sur le véhicule.

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

Avertissement :Veillez à spécifier au moins un paramètre de coût. Si les paramètres de coût ne limitent pas la valeur ShipmentModel, l'optimisation des routes renvoie tout itinéraire pouvant être effectué dans l'intervalle de temps autorisé, 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 itinéraires 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 est effectivement attribuée à un travail à effectuer par un véhicule à un endroit et à une heure spécifiques.

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

Pour reconstituer l'itinéraire complet du véhicule, les valeurs visits et transitions de ShipmentRoute doivent être combinées. 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 son point 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 à la fin de l'itinéraire. Si le véhicule n'a pas de lieu de départ ou d'arrivée, un transitions sera tout de même défini sur visits, car la position de la première ou de la dernière visite est utilisée respectivement comme lieu de départ ou d'arrivée.

Dans cet exemple, les trois premières visites de retrait présentent des transitions dont la distance et la durée sont égales à zéro, car elles partagent le même lieu 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 apparaissait 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 expéditions n'incluent pas les visites en point retrait, l'optimiseur suppose que les colis commencent avec des colis déjà chargés. Dans ce cas, des caractéristiques telles que UnloadingPolicy (FIFO ou LIFO) peuvent ne pas s'appliquer, car il n'y a pas de séquence de prise en charge.

Optimisation simple de l'ordre des points de cheminement

Comme le montre cet exemple, l'optimisation des itinéraires modélise les visites comme des propriétés des livraisons. Elle 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 livraisons avec un seul VisitRequest pour le retrait ou la livraison. Un costPerHour ou un costPerKilometer doit toujours être attribué au véhicule pour que l'optimiseur puisse trouver l'itinéraire optimal (par opposition à un itinéraire réalisable).