OptimizeToursRequest applique des contraintes aux éléments suivants:
- les expéditions, qui ont une incidence sur la façon dont elles sont effectuées ;
- Véhicules, affectant la façon dont les itinéraires des véhicules sont calculés
- À l'échelle mondiale, cela affecte à la fois les véhicules et les envois.
Ce guide se concentre sur une contrainte d'expédition essentielle: les fenêtres temporelles.
Les fenêtres de temps sont un type de contrainte que vous fournissez dans le message OptimizeToursRequest (REST, gRPC) afin de spécifier des limites temporelles pour les activités de livraison. Ce type de contrainte influe à la fois sur le moment et la manière dont une livraison peut être effectuée, ainsi que sur l'attribution du véhicule pour la livraison. Avec ces contraintes, l'optimiseur donne la priorité aux véhicules qui peuvent le mieux répondre aux contraintes temporelles de l'expédition.
Contraintes de livraison: périodes
Vous spécifiez quand un retrait ou une livraison peut avoir lieu dans le message Shipment.VisitRequest comme suit:
- Utilisez la propriété
timeWindowsdans le message (REST, gRPC). - Spécifiez l'heure de début et de fin dans le message
TimeWindow(REST, gRPC).
Exemple de requête avec des contraintes de période
L'exemple ci-dessous illustre trois envois différents, chacun avec sa propre période de livraison. Pour des raisons de simplicité, cet exemple définit des périodes sur deliveries uniquement, mais des périodes peuvent également être appliquées aux collectes. Vous pouvez spécifier plusieurs périodes, mais cet exemple n'en utilise qu'une par VisitRequest de diffusion.
Voir un exemple de requête avec des périodes
{ "populatePolylines": false, "populateTransitionPolylines": false, "model": { "globalStartTime": "2023-01-13T16:00:00Z", "globalEndTime": "2023-01-14T16:00:00Z", "shipments": [ { "deliveries": [ { "arrivalLocation": { "latitude": 37.789456, "longitude": -122.390192 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T18:00:00Z", "endTime": "2023-01-13T19:00:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 100.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.789116, "longitude": -122.395080 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T18:00:00Z", "endTime": "2023-01-13T18:30:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 20.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.795242, "longitude": -122.399347 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T17:30:00Z", "endTime": "2023-01-13T18:00:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 50.0 } ], "vehicles": [ { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerHour": 40.0, "costPerKilometer": 10.0 } ] } }
Exemple de réponse avec des contraintes de période
Dans l'exemple de réponse, les heures de début et de fin du véhicule sont respectivement 17:35:50 et 18:17:24. Ces temps reflètent l'optimiseur qui minimise le temps nécessaire pour exploiter le véhicule spécifié dans la requête en tant que costPerHour tout en respectant toutes les contraintes de période. L'utilisation de l'heure de début 17:35:50 évite au véhicule d'attendre à un emplacement de visite jusqu'au début de la période de visite. Cela apparaît dans la réponse sous la forme de valeurs waitDuration nulles.
Voir une réponse à l'exemple de requête avec des périodes
{ "routes": [ { "vehicleStartTime": "2023-01-13T17:35:50Z", "vehicleEndTime": "2023-01-13T18:17:24Z", "visits": [ { "isPickup": true, "startTime": "2023-01-13T17:35:50Z", "detour": "0s" }, { "shipmentIndex": 1, "isPickup": true, "startTime": "2023-01-13T17:38:20Z", "detour": "150s" }, { "shipmentIndex": 2, "isPickup": true, "startTime": "2023-01-13T17:40:50Z", "detour": "300s" }, { "shipmentIndex": 2, "startTime": "2023-01-13T17:50:09Z", "detour": "0s" }, { "shipmentIndex": 1, "startTime": "2023-01-13T18:00:00Z", "detour": "796s" }, { "startTime": "2023-01-13T18:07:35Z", "detour": "1520s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:35:50Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:38:20Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:40:50Z" }, { "travelDuration": "409s", "travelDistanceMeters": 1371, "waitDuration": "0s", "totalDuration": "409s", "startTime": "2023-01-13T17:43:20Z" }, { "travelDuration": "341s", "travelDistanceMeters": 1312, "waitDuration": "0s", "totalDuration": "341s", "startTime": "2023-01-13T17:54:19Z" }, { "travelDuration": "205s", "travelDistanceMeters": 636, "waitDuration": "0s", "totalDuration": "205s", "startTime": "2023-01-13T18:04:10Z" }, { "travelDuration": "339s", "travelDistanceMeters": 1276, "waitDuration": "0s", "totalDuration": "339s", "startTime": "2023-01-13T18:11:45Z" } ], "metrics": { "performedShipmentCount": 3, "travelDuration": "1294s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "2494s", "travelDistanceMeters": 4595 }, "routeCosts": { "model.vehicles.cost_per_hour": 27.711111111111112, "model.vehicles.cost_per_kilometer": 45.95 }, "routeTotalCost": 73.661111111111111 } ], "metrics": { "aggregatedRouteMetrics": { "performedShipmentCount": 3, "travelDuration": "1294s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "2494s", "travelDistanceMeters": 4595 }, "usedVehicleCount": 1, "earliestVehicleStartTime": "2023-01-13T17:35:50Z", "latestVehicleEndTime": "2023-01-13T18:17:24Z", "totalCost": 73.661111111111111, "costs": { "model.vehicles.cost_per_hour": 27.711111111111112, "model.vehicles.cost_per_kilometer": 45.95 } } }
Les périodes ont classé les visits du véhicule de sorte que les envois avec les périodes les plus courtes soient livrés en premier.
shipments[2]est livré à 17h50shipments[1]est livré à 18hshipments[0]est diffusé à 18h07
L'exemple de requête spécifie des contraintes de périodes difficiles qui nécessitent que les livraisons soient effectuées dans ces fenêtres. Si l'exécution de la VisitRequests d'un envoi dans l'une de ses périodes n'est pas possible ou n'est pas rentable, l'optimiseur ignore l'envoi. Si l'envoi comporte un penaltyCost, l'optimiseur l'ajoute aux coûts indiqués dans la réponse metrics. Sinon, la propriété skippedMandatoryShipmentCount du message OptimizeToursResponse (REST, gRPC) augmente.
Si vous modifiez les fenêtres temporelles en décalant la fenêtre de shipment[1] plusieurs heures plus tard (de 18h à 21h), les résultats seront différents, comme illustré dans les exemples suivants.
Voir un exemple de requête dont les périodes ne peuvent pas être satisfaites
{ "populatePolylines": false, "populateTransitionPolylines": false, "model": { "globalStartTime": "2023-01-13T16:00:00Z", "globalEndTime": "2023-01-14T16:00:00Z", "shipments": [ { "deliveries": [ { "arrivalLocation": { "latitude": 37.789456, "longitude": -122.390192 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T18:00:00Z", "endTime": "2023-01-13T19:00:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 100.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.789116, "longitude": -122.395080 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T21:00:00Z", "endTime": "2023-01-13T21:30:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 20.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.795242, "longitude": -122.399347 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T17:30:00Z", "endTime": "2023-01-13T18:00:00Z" } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 50.0 } ], "vehicles": [ { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerHour": 40.0, "costPerKilometer": 10.0 } ] } }
Consultez une réponse au deuxième exemple de requête avec des fenêtres temporelles, où une livraison est ignorée.
{ "routes": [ { "vehicleStartTime": "2023-01-13T17:37:49Z", "vehicleEndTime": "2023-01-13T18:09:49Z", "visits": [ { "isPickup": true, "startTime": "2023-01-13T17:37:49Z", "detour": "0s" }, { "shipmentIndex": 2, "isPickup": true, "startTime": "2023-01-13T17:40:19Z", "detour": "150s" }, { "shipmentIndex": 2, "startTime": "2023-01-13T17:49:38Z", "detour": "0s" }, { "startTime": "2023-01-13T18:00:00Z", "detour": "946s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:37:49Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:40:19Z" }, { "travelDuration": "409s", "travelDistanceMeters": 1371, "waitDuration": "0s", "totalDuration": "409s", "startTime": "2023-01-13T17:42:49Z" }, { "travelDuration": "372s", "travelDistanceMeters": 1348, "waitDuration": "0s", "totalDuration": "372s", "startTime": "2023-01-13T17:53:48Z" }, { "travelDuration": "339s", "travelDistanceMeters": 1276, "waitDuration": "0s", "totalDuration": "339s", "startTime": "2023-01-13T18:04:10Z" } ], "metrics": { "performedShipmentCount": 2, "travelDuration": "1120s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "800s", "totalDuration": "1920s", "travelDistanceMeters": 3995 }, "routeCosts": { "model.vehicles.cost_per_kilometer": 39.95, "model.vehicles.cost_per_hour": 21.333333333333332 }, "routeTotalCost": 61.283333333333331 } ], "skippedShipments": [ { "index": 1 } ], "metrics": { "aggregatedRouteMetrics": { "performedShipmentCount": 2, "travelDuration": "1120s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "800s", "totalDuration": "1920s", "travelDistanceMeters": 3995 }, "usedVehicleCount": 1, "earliestVehicleStartTime": "2023-01-13T17:37:49Z", "latestVehicleEndTime": "2023-01-13T18:09:49Z", "totalCost": 81.283333333333331, "costs": { "model.shipments.penalty_cost": 20, "model.vehicles.cost_per_hour": 21.333333333333332, "model.vehicles.cost_per_kilometer": 39.95 } } }
Dans cet exemple, la période de livraison ultérieure a entraîné l'exclusion de shipment[1], car le temps de fonctionnement supplémentaire du véhicule requis pour effectuer la livraison de l'envoi dans la période spécifiée dépassait le coût de pénalité de l'envoi.
Le coût de pénalité pour shipment[1] apparaît dans metrics.costs, et son indice apparaît dans skippedShipments.
Contraintes de fenêtre flexible
Comme indiqué brièvement dans la section Paramètres du modèle de coût, les périodes peuvent être appliquées en tant que contraintes souples. Les contraintes souples diffèrent des contraintes strictes comme suit:
- Contraintes strictes: ne peuvent pas être violées, et l'optimiseur n'offre pas de solution qui viole la contrainte, même si cela signifie ignorer un envoi.
- Contraintes souples: peuvent être violées, ce qui signifie que l'optimiseur peut fournir une solution qui ne respecte pas une contrainte souple. Cependant, l'optimiseur applique également un coût à toute violation. Vous fournissez ce coût en tant que propriété supplémentaire dans la période, généralement sous la forme d'un coût par heure pour chaque heure avant ou après la période au cours de laquelle l'activité se produit.
Les fenêtres temporelles sont atténuées en utilisant softStartTime ou softEndTime au lieu de startTime ou endTime, respectivement, et en définissant costPerHourBeforeSoftStartTime ou costPerHourAfterSoftEndTime.
Utilisez des contraintes de période flexibles lorsque les collectes ou les livraisons devraient avoir lieu dans une période spécifiée, mais que la collecte ou la livraison dans cette période n'est pas absolument obligatoire. Vous pouvez utiliser des contraintes de période strictes et flexibles pour exprimer vos objectifs commerciaux. Exemple :
- Plage horaire fixe: indique les horaires d'ouverture d'un client, par exemple de 9h à 17h.
- Plage horaire flexible: indique la période de livraison ou de retrait correspondant à la notification envoyée au client, par exemple de 9h à 13h.
Dans cet exemple, la contrainte d'heure de début de l'envoi précédemment ignoré, car sa période a commencé trop tard, est assouplie. Les délais de livraison des autres commandes ont également été assouplis.
Voir un exemple de requête avec des périodes de validité strictes et flexibles
{ "populatePolylines": false, "populateTransitionPolylines": false, "model": { "globalStartTime": "2023-01-13T16:00:00Z", "globalEndTime": "2023-01-14T16:00:00Z", "shipments": [ { "deliveries": [ { "arrivalLocation": { "latitude": 37.789456, "longitude": -122.390192 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T18:00:00Z", "softEndTime": "2023-01-13T19:00:00Z", "costPerHourAfterSoftEndTime": 2.0 } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 100.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.789116, "longitude": -122.395080 }, "duration": "250s", "timeWindows": [ { "softStartTime": "2023-01-13T21:00:00Z", "endTime": "2023-01-13T21:30:00Z", "costPerHourBeforeSoftStartTime": 2.0 } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 20.0 }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.795242, "longitude": -122.399347 }, "duration": "250s", "timeWindows": [ { "startTime": "2023-01-13T17:30:00Z", "softEndTime": "2023-01-13T18:00:00Z", "costPerHourAfterSoftEndTime": 2.0 } ] } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ], "penaltyCost": 50.0 } ], "vehicles": [ { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerHour": 40.0, "costPerKilometer": 10.0 } ] } }
Voir une réponse à l'exemple de requête avec des délais stricts et flexibles
{ "routes": [ { "vehicleStartTime": "2023-01-13T17:48:35Z", "vehicleEndTime": "2023-01-13T18:24:28Z", "visits": [ { "isPickup": true, "startTime": "2023-01-13T17:48:35Z", "detour": "0s" }, { "shipmentIndex": 1, "isPickup": true, "startTime": "2023-01-13T17:51:05Z", "detour": "150s" }, { "shipmentIndex": 2, "isPickup": true, "startTime": "2023-01-13T17:53:35Z", "detour": "300s" }, { "startTime": "2023-01-13T18:00:00Z", "detour": "300s" }, { "shipmentIndex": 1, "startTime": "2023-01-13T18:07:42Z", "detour": "493s" }, { "shipmentIndex": 2, "startTime": "2023-01-13T18:17:27Z", "detour": "873s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:48:35Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:51:05Z" }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-13T17:53:35Z" }, { "travelDuration": "235s", "travelDistanceMeters": 795, "waitDuration": "0s", "totalDuration": "235s", "startTime": "2023-01-13T17:56:05Z" }, { "travelDuration": "212s", "travelDistanceMeters": 791, "waitDuration": "0s", "totalDuration": "212s", "startTime": "2023-01-13T18:04:10Z" }, { "travelDuration": "335s", "travelDistanceMeters": 1204, "waitDuration": "0s", "totalDuration": "335s", "startTime": "2023-01-13T18:11:52Z" }, { "travelDuration": "171s", "travelDistanceMeters": 665, "waitDuration": "0s", "totalDuration": "171s", "startTime": "2023-01-13T18:21:37Z" } ], "metrics": { "performedShipmentCount": 3, "travelDuration": "953s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "2153s", "travelDistanceMeters": 3455 }, "routeCosts": { "model.shipments.deliveries.time_windows.cost_per_hour_after_soft_end_time": 0.58166666666666667, "model.shipments.deliveries.time_windows.cost_per_hour_before_soft_start_time": 5.7433333333333332, "model.vehicles.cost_per_hour": 23.922222222222221, "model.vehicles.cost_per_kilometer": 34.55 }, "routeTotalCost": 64.797222222222217 } ], "metrics": { "aggregatedRouteMetrics": { "performedShipmentCount": 3, "travelDuration": "953s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "2153s", "travelDistanceMeters": 3455 }, "usedVehicleCount": 1, "earliestVehicleStartTime": "2023-01-13T17:48:35Z", "latestVehicleEndTime": "2023-01-13T18:24:28Z", "totalCost": 64.797222222222217, "costs": { "model.vehicles.cost_per_kilometer": 34.55, "model.shipments.deliveries.time_windows.cost_per_hour_before_soft_start_time": 5.7433333333333332, "model.shipments.deliveries.time_windows.cost_per_hour_after_soft_end_time": 0.58166666666666667, "model.vehicles.cost_per_hour": 23.922222222222221 } } }
Lorsque l'exemple avec uniquement des contraintes de fenêtre temporelle ignorait complètement shipment[1], l'adoucissement de la fenêtre de délai de livraison entraîne sa livraison avant son heure de début. De même, l'assouplissement des heures de fin des autres envois a permis à shipment[2] d'être livré après la fin de sa période.
Dans le même temps, les coûts et le nombre total d'expéditions ont changé:
totalCost: diminution de 81,283 à 64,797- Nombre total d'envois terminés: augmentation de 2 à 3
L'optimiseur a trouvé une solution moins coûteuse, car les contraintes de période ont été assouplies par rapport à l'exemple précédent.
Enfin, la propriété metrics.costs inclut également une nouvelle clé pour indiquer le coût réel en fonction du produit de la contrainte et la durée pendant laquelle la période de livraison a été manquée. Par exemple :
costPerHourBeforeSoftStartTime: 2,0 et- Délai entre la livraison réelle et le début de la période : 2,83583 heures
Résultat :
model.shipments.deliveries.time_windows.cost_per_hour_before_soft_start_time:
5.6716666666666669.
Ces métriques vous permettent d'effectuer une analyse des coûts pour déterminer le compromis entre les contraintes strictes et les contraintes souples, que vous pouvez utiliser pour ajuster vos contraintes afin qu'elles soient mieux adaptées à vos règles métier spécifiques. Dans ce cas, le coût total est inférieur à shipment[1].penalty_cost, soit 20,0. L'optimiseur a déterminé qu'il était plus rentable d'effectuer l'envoi plus tôt que de ne pas l'effectuer.