Dimensions

O solucionador de roteamento usa um objeto chamado dimensão para acompanhar quantidades que se acumulam ao longo do trajeto de um veículo, como o tempo de viagem ou Se o veículo está fazendo retiradas e entregas, o peso total que está carregando , Se um problema de roteamento envolver tal quantidade, seja nas restrições ou função objetiva, você precisa definir uma dimensão para especificá-las.

Nesta seção, explicamos como definir e usar dimensões.

Exemplos de dimensões

Aqui estão alguns exemplos de dimensões das seções anteriores.

  • O exemplo de VRPTW cria uma dimensão para rastrear o tempo cumulativo de viagem de cada veículo. O solucionador usa a dimensão para aplicar a restrição de que um veículo só pode visitar um local no janela de tempo.

  • O exemplo de CVRP cria uma dimensão para o exigências (por exemplo, pesos ou volumes de pacotes a serem coletados), que rastreiam a carga cumulativa que o veículo carrega ao longo do trajeto. O solucionador usa a dimensão para aplicar a restrição de que a carga de um veículo não pode exceder a capacidade dele.

Os exemplos abaixo definem uma dimensão para o VRPTW usando o 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)

O método AddDimension tem as seguintes entradas:

  • callback_index: o índice do callback que retorna a quantidade. A índice, que é a referência interna do solucionador para o callback, é criado pelo métodos, como RegisterTransitCallback ou RegisterUnitaryTransitCallback.
  • slack_max: máximo para a folga, uma variável usada para representar a espera vezes nos locais. Consulte as variáveis do Slack abaixo para detalhes. Se o problema não envolver tempo de espera, geralmente é possível definir slack_max como zero.
  • capacity: máximo para a quantidade total acumulada em cada trajeto. Use capacity para criar restrições como as CVRP: Se seu problema não tiver um restrição, é possível definir capacity como um valor que seja grande o suficiente para não impor restrições aos trajetos, por exemplo, a soma de todos entradas da matriz ou matriz usadas para definir o callback.
  • fix_start_cumulative_to_zero: valor booleano. Se verdadeiro, o valor cumulativo da quantidade começa em 0. Na maioria dos casos, ele precisa ser definido como True. No entanto, para VRPTW ou problemas com restrições de recursos, alguns veículos pode ter que iniciar depois de 0 devido a restrições de janela de tempo, portanto defina fix_start_cumulative_to_zero como False para esses problemas.
  • dimension_name: string do nome da dimensão, como 'Distance'. que pode ser usada para acessar as variáveis em outro lugar do programa.

O programa CVRP cria um tipo um pouco diferente de dimensão usando o AddDimensionWithVehicleCapacity . Esse método usa uma matriz de capacidades, com uma entrada para cada veículo. Por outro lado, AddDimension usa um único valor para capacity, então todos presume-se que veículos tenham a mesma capacidade.)

Consulte o RoutingModel página de referência para outros métodos que criam dimensões.

Seção Salvar as janelas de tempo da solução em uma lista ou matriz apresenta funções que salvam os dados cumulativos em uma dimensão em uma lista ou matriz.

Variáveis do Slack

Aqui está um exemplo que ilustra as variáveis de folga para um problema que envolve o tempo de viagem. Suponha que um veículo vai do local i para o local j em uma etapa do trajeto, e que:

  • O tempo cumulativo de viagem do veículo em i é de 100 minutos.
  • O tempo cumulativo de viagem do veículo em j é de 200 minutos.
  • O tempo de viagem de i para j é de 75 minutos.

O veículo não pode sair do local i imediatamente após a chegada nem o valor acumulado no local j seria 175. Em vez disso, o veículo deve aguardar 25 minutos location i antes da partida; em outras palavras, a folga no local i é 25.

É preciso permitir a folga em um VRPTW porque os veículos podem ter que esperar até visitar um local devido a restrições de janela de tempo. Em um problema como esse, defina slack_max para o tempo máximo de espera dos veículos local antes de prosseguir para o próximo. Se não importa quanto tempo eles esperam, basta definir slack_max como um número muito alto.

Para o CVRP, por outro lado, a mudança na carga acumulada de i para j sempre é igual à demanda em i, então não há folga. Para problemas como defina slack_max como 0.

A seguir, daremos a definição formal de folga. Internamente, uma dimensão armazena dois tipos de variáveis relacionadas às quantidades acumuladas ao longo dos trajetos:

  • Variáveis de transporte público: o aumento ou a diminuição da quantidade em cada etapa do um trajeto. Se i -> j for uma etapa do trajeto, a variável de transporte público será i, entrada j da matriz de transporte público (para um callback de transporte público), ou simplesmente o valor do callback no local i (se o callback depender de apenas um local).
  • Variáveis cumulativas: quantidade total acumulada em cada local. Você pode acessar a variável cumulativa no local i ao dimension_name.CumulVar(i): Para ver um exemplo, consulte restrições de janela de tempo no exemplo VRPTW.

Supondo que um veículo vá do local i ao local j em uma etapa, o O slack está relacionado a essas variáveis da seguinte maneira: 

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

Para mais detalhes sobre as dimensões, consulte RoutingDimension na seção de referência.