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.

---

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	#Paletes	Latitude	Longitude
1	BrwnsvllTX	4	25.9000	-97.4333
2	Chicago	7	41.8781	-87.6298
3	DelRio	2	29,3667	-100.7833
4	Detroit	3	42.4167	-83.0167
5	Minneapolis	6	44.9800	-93.2519
6	New York City	9	40.7128	-74.0059
7	Oakland	9	37.7297	-122.2200
8	Phoenix	5	33.4833	-112.0667
9	Pittsburgh	5	40.4406	-79.9959
10	Portland	4	45.5997	-122.5997
11	Salt Lake City	8	40.7500	-111.8833
12	San Diego	4	32.7333	-117.1667
13	Seattle	2	47.6062	-122.3321
14	St Louis	11	38.6270	-90.1994
15	Tucson	6	32.2217	-110.9258
16	Tallahassee	5	30.3833	-84.3667
17	Dallas	0	32.7767	32.7767