Dimensions

Le résolveur de routage utilise un objet appelé dimension pour suivre les quantités accumulées sur l'itinéraire d'un véhicule, telles que le temps de trajet le poids total qu'il supporte si le véhicule effectue des retraits et des livraisons ; pour en savoir plus. Si un problème de routage implique une telle quantité, soit dans les contraintes, soit la fonction 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 provenant des sections précédentes.

  • L'exemple VRPTW crée une dimension à suivre la durée de trajet cumulée de chaque véhicule. Le résolveur utilise la dimension pour appliquer la contrainte selon laquelle un véhicule ne peut se rendre période.

  • L'exemple CVRP crée une dimension pour le demandes (par exemple, poids ou volumes de colis à retirer), qui permet de suivre la charge cumulée que le véhicule supporte sur son trajet ; 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 le VRPTW en utilisant le 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é. La "index", qui est la référence interne du résolveur au rappel, est créé par comme RegisterTransitCallback ou RegisterUnitaryTransitCallback.
  • slack_max: valeur maximale pour la zone d'attente, une variable utilisée pour représenter le temps d'attente fois sur les sites. Consultez les variables Slack ci-dessous pour en savoir plus plus de détails. Si le problème n'implique pas de temps d'attente, vous pouvez généralement définir slack_max à 0.
  • capacity: quantité maximale pour la quantité totale cumulée sur chaque itinéraire. Utilisez capacity pour créer des contraintes semblables à celles de la CVRP : Si votre problème n'est pas associé vous pouvez définir capacity sur une valeur suffisamment grande pour n'imposent aucune restriction sur les routes, par exemple la somme de toutes 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 cumulée de la quantité commence à 0. Dans la plupart des cas, il doit être défini sur True. Toutefois, pour le VRPTW ou les problèmes liés contraintes liées aux ressources, certains véhicules peut devoir démarrer après l'heure 0 en raison de contraintes de période, vous devez donc définissez fix_start_cumulative_to_zero sur False pour ces problèmes.
  • dimension_name: chaîne du nom de la dimension, par exemple '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 du AddDimensionWithVehicleCapacity . Cette méthode nécessite un tableau des capacités, avec une entrée pour chaque véhicule. (En revanche, AddDimension n'accepte qu'une seule valeur pour capacity. Par conséquent, les véhicules sont supposés avoir la même capacité.

Consultez le RoutingModel de référence pour les autres méthodes de création de dimensions.

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

Variables Slack

Voici un exemple illustrant les variables de marge pour un problème impliquant le temps de trajet. Supposons que un véhicule se déplace d'un point i à un point j sur son itinéraire, et que:

  • Le temps de trajet cumulé du véhicule à i est de 100 minutes.
  • Le temps de 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 à l'arrivée, ou ses données cumulées l'heure à l'emplacement j serait de 175. Le véhicule doit attendre 25 minutes à lieu i avant le départ ; en d'autres termes, le mou à l'emplacement i est de 25.

Vous devez laisser du jeu dans un VRPTW, car les véhicules peuvent devoir attendre avant se rendre dans un lieu, en raison de contraintes horaires. Dans un problème comme celui-ci, définissez slack_max à la durée maximale d'attente des véhicules un lieu avant de passer au lieu suivant. Si ce n'est pas important, combien de temps il suffit de définir slack_max sur un très grand nombre.

Pour le CVRP, en revanche, la variation de la charge cumulée de i à j est toujours égal à la demande à i, il n'y a donc pas de marge. Pour des problèmes tels que vous pouvez définir slack_max sur 0.

Ensuite, nous donnerons la définition formelle de la marge. En interne, une dimension stocke deux types de variables liées aux quantités qui s'accumulent tout au long des itinéraires:

  • Variables relatives aux transports en commun: l'augmentation ou la diminution de la quantité à chaque étape de un itinéraire. Si i -> j correspond à une étape d'un itinéraire, la variable de transports en commun est i, Entrée j de la matrice des transports en commun (pour un rappel de transports en commun), ou simplement valeur de rappel à l'emplacement i (si le rappel dépend d'un seul lieu).
  • Variables cumulatives: quantité totale cumulée dans chaque établissement. Toi peuvent accéder à la variable cumulée à l'emplacement i en dimension_name.CumulVar(i) Pour voir un exemple, consultez la contraintes liées aux fenêtres temporelles dans l'exemple VRPTW.

En supposant qu'un véhicule se déplace de l'emplacement i à l'emplacement j en une seule étape, Slack 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 des références.