Dimensions

L'outil de résolution d'itinéraires utilise un objet appelé une dimension pour effectuer le suivi des quantités accumulées sur le trajet d'un véhicule, telles que sa durée ou, si le véhicule effectue des retraits et des livraisons, le poids total qu'il transporte. Si un problème de routage implique une telle quantité, que ce soit dans les contraintes ou la fonction d'objectif, vous devez définir une dimension pour les spécifier.

Cette section explique comment définir et utiliser des dimensions.

Exemples de dimensions

Voici quelques exemples de dimensions des sections précédentes.

  • L'exemple VRPTW crée une dimension pour suivre le temps de trajet cumulé de chaque véhicule. Le résolveur utilise la dimension pour appliquer la contrainte selon laquelle un véhicule ne peut visiter un lieu qu'au cours de la période définie.

  • L'exemple CVC crée une dimension pour les demandes (par exemple, les poids ou les volumes de colis à récupérer), qui suit la charge cumulée du véhicule sur son itinéraire. Le résolveur utilise la dimension pour appliquer la contrainte selon laquelle la charge d'un véhicule ne peut pas dépasser sa capacité.

Les exemples ci-dessous définissent une dimension pour VRPTW à l'aide de la méthode AddDimension.

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

C#

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

La méthode AddDimension comporte les entrées suivantes:

  • callback_index: index du rappel qui renvoie la quantité. L'index, qui est la référence interne du résolveur au rappel, est créé par des méthodes telles que RegisterTransitCallback ou RegisterUnitaryTransitCallback.
  • slack_max: maximum pour le slack, une variable utilisée pour représenter les temps d'attente aux lieux. Consultez les variables Slack ci-dessous pour plus de détails. Si le problème n'implique pas de temps d'attente, vous pouvez généralement définir slack_max sur 0.
  • capacity: quantité maximale cumulée pour chaque itinéraire. Utilisez capacity pour créer des contraintes telles que celles du CVRP. Si votre problème n'est pas soumis à une telle contrainte, vous pouvez définir capacity sur une valeur suffisamment élevée pour n'imposer aucune restriction aux routes (par exemple, la somme de toutes les entrées de la matrice ou du tableau utilisé pour définir le rappel).
  • fix_start_cumulative_to_zero : valeur booléenne. Si la valeur est "true", la valeur cumulative de la quantité commence à 0. Dans la plupart des cas, ce paramètre doit être défini sur True. Toutefois, pour VRPTW ou les problèmes liés aux contraintes de ressources, certains véhicules devront peut-être démarrer après l'heure 0 en raison de contraintes de fenêtre temporelle. Vous devez donc définir fix_start_cumulative_to_zero sur False pour ces problèmes.
  • dimension_name: chaîne correspondant au nom de la dimension, telle que 'Distance', que vous pouvez utiliser pour accéder aux variables ailleurs dans le programme.

Le programme CVRP crée un type de dimension légèrement différent à l'aide de la méthode AddDimensionWithVehicleCapacity. Cette méthode nécessite un tableau des capacités, avec une entrée pour chaque véhicule. En revanche, AddDimension utilise une seule valeur pour capacity. Par conséquent, tous les véhicules ont la même capacité.

Consultez la page de référence RoutingModel pour connaître les autres méthodes permettant de créer des dimensions.

La section Enregistrer les fenêtres temporelles de la solution dans une liste ou un tableau présente des fonctions qui enregistrent les données cumulées dans une dimension d'une liste ou d'un tableau.

Variables Slack

Voici un exemple illustrant les variables Slack pour un problème lié au temps de trajet. Supposons qu'un véhicule part d'un emplacement i à un point j à une étape de son itinéraire, et que:

  • Le temps de trajet cumulé du véhicule à i est de 100 minutes.
  • Le trajet cumulé du véhicule à j est de 200 minutes.
  • Le temps de trajet de i à j est de 75 minutes.

Le véhicule ne peut pas quitter le lieu i immédiatement à son arrivée, ou son temps cumulé à l'emplacement j est 175. Au lieu de cela, le véhicule doit attendre 25 minutes à l'emplacement i avant de partir. En d'autres termes, le relâchement à l'emplacement i est défini sur 25.

Vous devez autoriser le relâchement dans un VRPTW, car les véhicules doivent peut-être attendre avant de se rendre dans un lieu en raison des contraintes de fenêtre temporelle. Dans ce cas, définissez slack_max sur la durée maximale pendant laquelle vous souhaitez autoriser les véhicules à attendre un établissement avant de passer à l'emplacement suivant. Peu importe le temps d'attente, définissez simplement slack_max sur un très grand nombre.

Pour le CVRP, en revanche, la variation de la charge accumulée de i à j est toujours égale à la demande à i. Il n'y a donc pas de décalage. Pour ce type de problème, vous pouvez définir slack_max sur 0.

Nous allons ensuite donner une définition formelle du "slack". En interne, une dimension stocke deux types de variables liés aux quantités cumulées sur les routes:

  • Variables de transports en commun : augmentation ou diminution de la quantité à chaque étape d'un itinéraire. Si i -> j est une étape d'un itinéraire, la variable de transport est l'entrée i de la matrice de transports (j) (pour un rappel de transports en commun) ou simplement la valeur de rappel à l'emplacement i (si le rappel dépend d'un seul emplacement).
  • Variables cumulées : quantité totale cumulée pour chaque établissement. Vous pouvez accéder à la variable cumulée à l'emplacement i d'ici le dimension_name.CumulVar(i). Pour obtenir un exemple, consultez les contraintes de fenêtre temporelle dans l'exemple VRPTW.

En supposant qu'un véhicule part d'un emplacement i à un emplacement j en une seule étape, le décalage est lié à ces variables comme suit : 

slack(i) = cumul(j) - cumul(i) - transit(i, j)

Pour en savoir plus sur les dimensions, consultez RoutingDimension dans la section de référence.