Série Pesquisa Operacional – Problema de Roteamento de Veículos

Em mais um artigo da série Pesquisa Operacional (confira a introdução da série e o artigo sobre o Problema do Caixeiro Viajante), hoje discutiremos o Problema do Roteamento de Veículos (Vehicle Routing Problem).

Este problema consiste em atender um conjunto de clientes que precisam receber mercadorias a partir de um depósito central. A idéia é visitar todos os clientes, entregar as quantidades necessárias, respeitando algumas restrições como o tempo da viagem dos veículos e a capacidade de carga dos mesmos, e garantindo que tudo seja feito ao menor custo possível. Se o Problema do Caixeiro Viajante (PCV) já era um problema difícil do ponto de vista de resolução computacional, o Problema de Roteamento de Veículos é ainda mais difícil, pois o trajeto de cada um dos veículos requer a resolução de um PCV, e ainda é preciso escolher quais clientes serão designados a cada um dos veículos, garantindo custo mínimo e eficiência máxima.

Este é um problema com alta ligação à área logística, pois a diminuição de custos de transportes é uma pressão constante nas cadeias de suprimentos. Além disso, possuem alto grau de aplicabilidade pois as diferentes versões do problema refletem de maneira muito real as decisões que precisam ser tomadas diariamente por transportadoras:

– roteamento com coletas e entregas (pickup and delivery): apresenta um desafio extra, pois a coleta precisa ser coordenada antes das respectivas entregas, a capacidade do veículo precisa ser ajustada dinamicamente para mais e para menos à medida em que entram e saem mercadorias;

– roteamento com janelas de tempo: cada cliente pode definir um intervalo de tempo limitado para que se dê início a coleta/entrega dos produtos;

– roteamento com múltiplos depósitos: como o nome diz, trata-se do caso em que há mais de um depósito para servir os clientes, e o sistema deve escolher quais veículos partem de quais depósitos para servir quais clientes, a fim de atingir o menor custo possível;

Existem muitas outras variações do problema, mas estas citadas representam boa parte das pesquisas e dos casos práticos utilizados. Assim como no Problema do Caixeiro Viajante, o roteamento de veículos também é solucionado através de heurísticas, os métodos “inteligentes” que geram boas soluções em um tempo reduzido (veja o primeiro artigo da Série Pesquisa Operacional para uma melhor explicação sobre heurísticas).

Na sua empresa, como você faz o roteamento? Que softwares são utilizados?

Depois da introdução, da matéria sobre o Problema do Caixeiro Viajante e deste artigo sobre o Problema de Roteamento de Veículos, na semana que vem veremos um artigo ainda mais complexo, que mistura as decisões de roteamento com o controle de estoques.

Na próxima 4ª feira, dia 10 de março, a matéria sobre o Problema de Estoques e Roteamento.

Fique ligado e não perca os exemplos que serão citados! Assine nosso newsleter (no começo da página à esquerda).