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: