VEHICLE ROUTER PROCESS

Um importante problema prático é o roteamento de veículos de um depósito central, o chamado Problema de Roteamento de Veículos (VRP). São muitos os exemplos: 

  • Encaminhamento de caminhões de entrega para um serviço de entrega de encomendas, 
  • Encaminhamento de entregas de equipamentos, 
  • Encaminhamento de reparadores etc. 

O VRP é como um problema de vendedor ambulante, mas com vários vendedores com restrições de capacidade para cada vendedor e viagem associada. normalmente, existem duas restrições em uma viagem: 

  • Carga do veículo, por exemplo, um veículo pode transportar no máximo 24 paletes e
  • Restrições na duração da viagem, por exemplo, no máximo oito horas. 

Às vezes, esse problema também é chamado de problema de roteamento LTL ( menos carga de caminhão) porque um destinatário típico recebe menos de uma carga de caminhão de mercadorias.

  • É importante notar que o VRP é muito semelhante a um problema comum de agendamento de tarefas: 
  • Dado um conjunto de tarefas a serem executadas;
  • Um conjunto de máquinas nas quais as tarefas podem ser executadas; 
  • Ou  um limite de tempo, por exemplo, 8 horas; 
  • Ou sobre quanto tempo está disponível em cada máquina;
  • Ou matriz de tempo de alternância entre tarefas;
  • Quais tarefas devem ser atribuídas a quais máquinas e em que ordem as tarefas devem ser executadas em cada máquina.

Um importante problema prático é o roteamento de veículos de um depósito central, o chamado Problema de Roteamento de Veículos (VRP). São muitos os exemplos: 

  • Encaminhamento de caminhões de entrega para um serviço de entrega de encomendas, 
  • Encaminhamento de entregas de equipamentos, 
  • Encaminhamento de reparadores etc. 

O VRP é como um problema de vendedor ambulante, mas com vários vendedores com restrições de capacidade para cada vendedor e viagem associada. normalmente, existem duas restrições em uma viagem: 

  • Carga do veículo, por exemplo, um veículo pode transportar no máximo 24 paletes e
  • Restrições na duração da viagem, por exemplo, no máximo oito horas. 

Às vezes, esse problema também é chamado de problema de roteamento LTL ( menos carga de caminhão) porque um destinatário típico recebe menos de uma carga de caminhão de mercadorias.

VRP 2


O que é LTL?

Já a LTL, de Less than TruckLoad, é utilizada quando a carga a ser despachada não é suficiente para ocupar a capacidade total de um caminhão.

Vantagens e Desvantagens da LTL

O LTL também é conhecido como carga fracionada, uma vez que o valor do transporte é dividido entre interessados em despachar mercadorias para um mesmo local, mas em vários endereços. Esse modelo é muito utilizado por lojas e distribuidoras que necessitam entregar pequenas embalagens.

As vantagens são:

  • Dividir o custo de transporte com outros interessados na mesma rota;
  • Entregar a encomenda no endereço que desejar, independente de volume ou peso.

As desvantagens:

Os riscos de danos e perda são maiores, uma vez que o caminhão possui programação de entregas onde ocorrem paradas e manejos de mercadorias. É importante notar que o VRP é muito semelhante a um problema comum de agendamento de tarefas: 

  • Dado um conjunto de tarefas a serem executadas;
  • Um conjunto de máquinas nas quais as tarefas podem ser executadas;
  • Ou  um limite de tempo, por exemplo, 8 horas; 
  • Ou sobre quanto tempo está disponível em cada máquina;
  • Ou matriz de tempo de alternância entre tarefas;
  • Quais tarefas devem ser atribuídas a quais máquinas e em que ordem as tarefas devem ser executadas em cada máquina.

Algumas outras variações no problema básico estão listadas abaixo:

Múltiplas dimensões em capacidade:

  • Além de uma restrição de capacidade do veículo, por exemplo, no máximo 24 paletes, 
  • Há frequentemente uma restrição de duração da viagem, por exemplo, oito horas. 
  • Pode haver uma restrição de peso, bem como uma restrição de volume, “cubo”.

Tempo de visita diferente de zero: 

  • Se você estiver encaminhando a entrega ou reparador de equipamento,
  • Se houver uma restrição no tempo total da viagem, 
  • Será necessário levar em consideração o tempo gasto em cada parada.
    •  

Times: 

Se houver limites para quando cada cliente pode ser visitado, o problema pode ser muito mais difícil;

Múltiplos tipos de veículos:

  • Um “veículo com 18 rodas” pode fazer entregas em um endereço suburbano, 
  • Mas não pode manobrar em uma área central da cidade, 
  • Portanto, um serviço de entrega pode precisar de vários tipos de veículos de entrega.

Matriz de distância dinâmica: 

  • Para algumas regiões, por exemplo, onde há uma grande movimentação da manhã ou da noite, 
  • O tempo de viagem depende significativamente da hora do dia. 
  • Isso pode ser tratado em parte com janelas de tempo para evitar entregas em determinadas regiões durante o horário de tráfego intenso.

Entregas divididas: 

  • Se a demanda em um cliente for maior que a capacidade do veículo, uma entrega dividida é inevitável. 
  • Mesmo que a demanda de cada cidade seja menor que a capacidade do veículo, permitir entregas divididas pode reduzir a distância total. 
  • Suponha que você tenha 3 cidades próximas uma da outra, mas distantes do depósito, cada uma com demanda 16 e capacidade do veículo = 24. 
  • Se entregas não forem permitidas, você deverá enviar 3 veículos. 
  • Se entregas divididas forem permitidas, você precisará de apenas duas.

Algumas outras variações no problema básico estão listadas abaixo:

Matriz de distância não simétrica: 

  • Se você estiver usando uma transportadora pública, pode ser que você tenha que pagar apenas pela distância até a parada final. 
  • Você não precisa pagar pela etapa final da viagem de volta ao depósito a partir da parada final. 
  • A distância de volta ao depósito é efetivamente zero. 
  • Se você estiver sequenciando tarefas em várias máquinas, a matriz de tempo de troca normalmente não é simétrica.

Vários depósitos: 

  • Normalmente é 1, mas se você estiver agendando capturas. 
  • Pode haver uma opção adicional de qual depósito atende a qual cliente. 
  • Esse recurso pode dificultar o problema.

Incerteza: 

  • Se você está programando pessoal de reparo ou entrega em domicílio, frequentemente não sabe com certeza o horário em cada parada. 
  • Da mesma forma, os tempos de viagem podem ser afetados pelo clima ou congestionamentos inesperados. 
  • Uma abordagem é estimar a variação de cada etapa, somar as variações de uma viagem e restringi-la. 
  • Além disso, na prática, paradas ou pernas de alta variação são colocadas no final da viagem.

Construção de carga: 

  • Há uma interação entre o roteamento do veículo e o carregamento dos veículos. 
  • Caminhões são normalmente descarregados na parte de trás. 
  • O caminhão para entregas, convém carregá-lo na ordem LIFO (Last In First Out). 
  • Para complicar, se os itens forem pesados, convém carregar itens para que o peso seja distribuído uniformemente. 
  • Se houver captadores e entregas, convém fazer entregas no início da viagem.

Exemplo:

  • Precisamos entregar mercadorias para 17 cidades diferentes a partir de um depósito em Dallas. 
  • Temos uma frota de caminhões para fazer as entregas. 
  • Cada caminhão pode transportar até 24 paletes. 
  • As cidades receptoras, juntamente com o número de paletes necessários e a latitude e longitude de cada cidade estão listadas abaixo.
CITY#PaletesLatitudeLongitude
1BrwnsvllTX425.9000-97.4333
2Chicago741.8781-87.6298
3DelRio229,3667-100.7833
4Detroit342.4167-83.0167
5Minneapolis644.9800-93.2519
6New York City940.7128-74.0059
7Oakland937.7297-122.2200
8Phoenix533.4833-112.0667
9Pittsburgh540.4406-79.9959
10Portland445.5997-122.5997
11Salt Lake City840.7500-111.8833
12San Diego432.7333-117.1667
13Seattle247.6062-122.3321
14St Louis1138.6270-90.1994
15Tucson632.2217-110.9258
16Tallahassee530.3833 -84.3667 
17Dallas032.776732.7767
Rota por coordenadas

Click me

CATEGORIAS