Dimensiones

La herramienta de resolución de enrutamiento usa un objeto llamado dimensión para realizar un seguimiento de las cantidades que se acumulan en la ruta de un vehículo, como el tiempo de viaje o, si el vehículo está haciendo retiros y entregas, el peso total que lleva. Si un problema de enrutamiento implica tal cantidad, ya sea en las restricciones o en la función objetiva, debes definir una dimensión para especificarlas.

En esta sección, se explica cómo definir y usar las dimensiones.

Ejemplos de dimensiones

Estos son algunos ejemplos de dimensiones de secciones anteriores.

• El ejemplo de VRPTW crea una dimensión para realizar un seguimiento del tiempo de viaje acumulado de cada vehículo. El agente de resolución usa la dimensión para aplicar de forma forzosa la restricción de que un vehículo solo puede visitar una ubicación dentro del período establecido en la ubicación.

• En el ejemplo de CVRP, se crea una dimensión para las demandas (p.ej., pesos o volúmenes de paquetes que se retirarán), que hace un seguimiento de la carga acumulativa que el vehículo transporta en su ruta. El solucionador usa la dimensión para aplicar la restricción que indica que la carga de un vehículo no puede exceder su capacidad.

En los siguientes ejemplos, se define una dimensión para el VRPTW con el método 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)

El método AddDimension tiene las siguientes entradas:

• callback_index: Es el índice de la devolución de llamada que muestra la cantidad. El índice, que es la referencia interna del solucionador a la devolución de llamada, se crea mediante métodos como RegisterTransitCallback o RegisterUnitaryTransitCallback.
• slack_max: Máximo para el slack, una variable que se usa a fin de representar los tiempos de espera en las ubicaciones. Consulta las variables de Slack a continuación para obtener más detalles. Si el problema no involucra el tiempo de espera, puedes establecer slack_max en 0.
• capacity: Es el máximo para la cantidad total acumulada a lo largo de cada ruta. Usa capacity para crear restricciones como las de la CVRP. Si tu problema no tiene esa restricción, puedes establecer capacity en un valor que sea lo suficientemente grande como para no imponer restricciones en las rutas, por ejemplo, la suma de todas las entradas de la matriz o el arreglo que se usa a fin de definir la devolución de llamada.
• fix_start_cumulative_to_zero: Valor booleano. Si es verdadero, el valor acumulativo de la cantidad comienza en 0. En la mayoría de los casos, debe establecerse en True. Sin embargo, para la VRPTW o los problemas con restricciones de recursos, es posible que algunos vehículos tengan que comenzar después del tiempo 0 debido a restricciones de período, por lo que debes establecer fix_start_cumulative_to_zero en False para estos problemas.
• dimension_name: Es la string del nombre de la dimensión, como 'Distance', que puedes usar a fin de acceder a las variables en otras partes del programa.

El programa CVRP crea un tipo de dimensión ligeramente diferente mediante el método AddDimensionWithVehicleCapacity. Este método toma un arreglo de capacidades, con una entrada para cada vehículo. (En cambio, AddDimension toma un solo valor para capacity, por lo que se supone que todos los vehículos tienen la misma capacidad).

Consulta la página de referencia de RoutingModel para conocer otros métodos que crean dimensiones.

En la sección Guardar los períodos de la solución en una lista o arreglo, se presentan las funciones que guardan los datos acumulativos en una dimensión en una lista o arreglo.

Variables de Slack

Este es un ejemplo que ilustra las variables de Slack para un problema relacionado con el tiempo de viaje. Supongamos que un vehículo va de la ubicación i a la ubicación j en un paso de su ruta y que:

• El tiempo de viaje total acumulado del vehículo es de 100 minutos.
• El tiempo de viaje acumulado del vehículo a j es de 200 minutos.
• El tiempo de viaje desde i hasta j es de 75 minutos.

El vehículo no puede abandonar la ubicación i inmediatamente después de su llegada o su tiempo acumulado en la ubicación j sería de 175. En cambio, el vehículo debe esperar 25 minutos en la ubicación i antes de irse. En otras palabras, la holgura de la ubicación i es de 25.

Debes permitir una holgura en un VRPTW porque es posible que los vehículos tengan que esperar antes de visitar una ubicación, debido a las limitaciones de tiempo. En un problema como este, configura slack_max en el tiempo máximo que deseas permitir que los vehículos esperen en una ubicación antes de pasar a la siguiente. Si no importa cuánto esperen, simplemente configura slack_max en un número muy grande.

Para el CVRP, por otro lado, el cambio en la carga acumulada de i a j siempre es igual a la demanda en i, por lo que no hay demora. Para problemas como este, puedes establecer slack_max en 0.

A continuación, daremos la definición formal de Slack. A nivel interno, una dimensión almacena dos tipos de variables relacionadas con las cantidades que se acumulan en las rutas:

• Variables de transporte público: El aumento o la disminución de la cantidad en cada paso de una ruta. Si i -> j es un paso en una ruta, la variable de transporte público será la entrada i o j de la matriz de transporte público (para una devolución de llamada de transporte público) o, simplemente, el valor de devolución de llamada en la ubicación i (si la devolución de llamada depende de una sola ubicación).
• Variables acumulativas: la cantidad total acumulada en cada ubicación. Puedes acceder a la variable acumulativa en la ubicación i mediante dimension_name.CumulVar(i). Para ver un ejemplo, consulta las restricciones de período en el ejemplo de VRPTW.

Si suponemos que un vehículo va de la ubicación i a la j en un solo paso, la falta está relacionada con estas variables de la siguiente manera:

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

Para obtener más detalles sobre las dimensiones, consulta RoutingDimension en la sección de referencia.