Dimensiones

El solucionador de problemas de enrutamiento usa un objeto llamado dimensión para realizar un seguimiento de cantidades que se acumulan a lo largo de la ruta de un vehículo, como la duración del viaje o Si el vehículo hace retiros y entregas, el peso total que lleva de Google Cloud. Si un problema de enrutamiento involucra esa cantidad, ya sea en las restricciones o la función objetiva, debes definir una dimensión para especificarlos.

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

Ejemplos de dimensiones

Estos son algunos ejemplos de dimensiones de secciones anteriores.

  • El ejemplo de VRPTW crea una dimensión para hacer un seguimiento. el tiempo de viaje acumulado de cada vehículo. La herramienta de resolución usa la dimensión para aplicar la restricción de que un vehículo solo puede visitar una ubicación dentro del durante la ventana de tiempo.

  • El ejemplo de CVRP crea una dimensión para el las demandas (p.ej., pesos o volúmenes de paquetes para recoger), que rastrean la carga acumulativa que lleva el vehículo en su ruta. La herramienta de resolución usa la dimensión para aplicar la restricción de que la carga de un vehículo no supere su capacidad.

En los siguientes ejemplos, se define una dimensión para la VRPTW con el parámetro 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, es creada por métodos, como RegisterTransitCallback o RegisterUnitaryTransitCallback.
  • slack_max: Es el máximo para la variable slack, que se usa para representar la espera. horarios en las ubicaciones. Consulta las variables de Slack a continuación para más detalles. Si el problema no implica tiempo de espera, por lo general, puedes establecer slack_max en 0.
  • capacity: Es el valor máximo de la cantidad total acumulada en cada ruta. Usa capacity para crear restricciones como las del CVRP. Si tu problema no tiene un restricción, puedes establecer capacity en un valor lo suficientemente grande como para no imponen restricciones en las rutas, por ejemplo, la suma de todas las entradas de la matriz o matriz usadas para definir la devolución de llamada.
  • fix_start_cumulative_to_zero: valor booleano. Si es verdadero, el valor acumulado de la cantidad comienza en 0. En la mayoría de los casos, se debe establecer en True. Sin embargo, para la VRPTW o los problemas con restricciones de recursos, algunos vehículos podría tener que empezar después del tiempo 0 debido a limitaciones de tiempo, por lo que establece fix_start_cumulative_to_zero en False para estos problemas.
  • dimension_name: Es una cadena para el nombre de la dimensión, como 'Distance'. que puedes usar para acceder a las variables en otras partes del programa.

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

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

La sección Guarda las ventanas de tiempo de la solución en una lista o un array Presenta funciones que guardan los datos acumulativos de una dimensión en una lista o un array.

Variables de Slack

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

  • El tiempo de viaje acumulado del vehículo en i es de 100 minutos.
  • El tiempo de viaje acumulado del vehículo en j es de 200 minutos.
  • La duración del viaje de i a j es de 75 minutos.

El vehículo no puede salir de la ubicación i inmediatamente al llegar, o bien tiempo en la ubicación j serían 175. En cambio, el vehículo debe esperar 25 minutos en la ubicación i antes de salir; en otras palabras, la distancia en la ubicación i es de 25.

Debes permitir la holgura en un VRPTW porque es posible que los vehículos deban esperar antes visitar una ubicación debido a limitaciones de tiempo. En un problema como este, establece slack_max hasta la cantidad máxima de tiempo en la que deseas permitir que los vehículos esperen una ubicación antes de pasar a la siguiente. Si no importa cuánto tiempo esperan, solo 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 inactividad. Para problemas como puedes configurar slack_max en 0.

A continuación, te daremos la definición formal de slack. Internamente, una dimensión almacena Hay 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 por una ruta. Si i -> j es un paso en una ruta, la variable de transporte público es i. una entrada j de la matriz de transporte público (para una devolución de llamada de transporte público), o simplemente la entrada 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: Es la cantidad total acumulada en cada ubicación. Tú puede acceder a la variable acumulada en la ubicación i dimension_name.CumulVar(i) Para ver un ejemplo, consulta el las limitaciones de las ventanas de tiempo en el ejemplo de VRPTW.

Si suponemos que un vehículo va de la ubicación i a la j en un paso, el slack se relaciona 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.