Dimensões

O solucionador de trajetos usa um objeto chamado dimensão para acompanhar as quantidades acumuladas ao longo do trajeto de um veículo, como o tempo de viagem ou se o veículo faz retiradas e entregas, ou seja, o peso total carregado. Se um problema de roteamento envolver essa quantidade, seja nas restrições ou na função do objetivo, você precisará definir uma dimensão para especificá-los.

Esta seção explica como definir e usar as dimensões.

Exemplos de dimensões

Veja alguns exemplos de dimensões das seções anteriores.

• O exemplo de VRPTW cria uma dimensão para rastrear o tempo cumulativo 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 dentro da janela de tempo dele.

• O exemplo de CVRP cria uma dimensão para as demandas (por exemplo, pesos ou volumes de pacotes a serem coletados), que rastreiam a carga cumulativa do veículo. 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 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)

O método AddDimension tem as seguintes entradas:

• callback_index: o índice do callback que retorna a quantidade. O índice, que é a referência interna do solucionador para o callback, é criado por métodos como RegisterTransitCallback ou RegisterUnitaryTransitCallback.
• slack_max: máximo para slack, uma variável usada para representar tempos de espera nos locais. Consulte as variáveis do Slack abaixo para mais detalhes. Se o problema não envolver o tempo de espera, geralmente é possível definir slack_max como 0.
• capacity: máximo para a quantidade total acumulada em cada trajeto. Use capacity para criar restrições como as da CVRP. Se o problema não tiver essa restrição, defina capacity como um valor que seja grande o suficiente para não impor restrições nas rotas. Por exemplo, a soma de todas as entradas da matriz ou matriz usada para definir o callback.
• fix_start_cumulative_to_zero: valor booleano. Se for verdadeiro, o valor cumulativo da quantidade começará em 0. Na maioria dos casos, isso é definido como True. No entanto, para VRPTW ou problemas com restrições de recursos, alguns veículos precisam iniciar após o tempo 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 no programa.

O programa CVRP cria um tipo de dimensão um pouco diferente usando o método 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 os veículos têm a mesma capacidade.

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

A 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

Confira um exemplo que mostra as variáveis do Slack para um problema que envolve o tempo de viagem. Suponha que um veículo vá do local i ao local j em uma etapa do trajeto e que:

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

O veículo não pode sair do local i imediatamente após a chegada, ou o tempo acumulado dele no local j seria 175. Em vez disso, o veículo precisa aguardar 25 minutos no local i antes da partida. Em outras palavras, o intervalo no local i é 25.

Você precisa permitir a pausa em um VRPTW porque os veículos podem ter que esperar antes de visitar um local, devido a restrições de janela de tempo. Em um problema como esse, defina slack_max como o tempo máximo que você quer permitir que os veículos aguardem em um local antes de prosseguir para o próximo. Não importa quanto tempo ele espera, basta definir slack_max como um número muito grande.

Já para o CVRP, a mudança na carga acumulada de i para j sempre é igual à demanda em i, de modo que não haja atraso. Para problemas como esse, é possível definir slack_max como 0.

A seguir, vamos definir a definição formal de slack. Internamente, uma dimensão armazena dois tipos de variáveis relacionadas às quantidades acumuladas ao longo das rotas:

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

Supondo que um veículo passe do local i para o local j em uma etapa, a frequência está relacionada a essas variáveis da seguinte maneira:

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

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