Logística/Sistemas de distribuição/Escala de veículos
O problema de escala de veículos (PEV), vehicle routing problem (VRP), consiste na determinação do conjunto óptimo de rotas a serem percorridas por uma frota de veículos para servirem um dado número de clientes. O VRP é um dos problemas de optimização combinatória mais importantes e mais estudados (Toth et al., 2002a, p. xvii).
O VRP foi formulado pela primeira vez, em 1959, por Dantzig e Ramser, quando analisaram a optimização das rotas de distribuição de gasolina aos posto de venda e formularam o primeiro modelo de programação matemática e abordagem algorítmica. Alguns anos mais tarde, em 1964, Clarke e Wright propuseram uma heurística que melhorou a abordagem de Dantzig e Ramser. A estes dois trabalhos iniciais seguiram-se muitos outros modelos e algoritmos para obter soluções óptimas e aproximadas de várias versões do VRP que deram origem a diferentes programas para resolução de casos reais. O interesse deste problema resulta da sua aplicação prática e considerável dificuldade.
Nas últimas décadas do século XX assistiu-se a um aumento no uso de programas de optimização baseados em técnicas de investigação operacional e programação matemática, para uma gestão correcta de sistemas de distribuição (Toth et al., 2002b, p. 1).
O VRP é um problema de programação inteira pertencente à classe de problemas NP-Difícil, NP-Hard, o que significa que o esforço computacional para resolver o problema aumenta exponencialmente com o tamanho do problema. Para encontrar rapidamente soluções adequadas ao fim a que se destinam, é muitas vezes preferível obterem-se soluções aproximadas. Nos casos reais o VRP apresenta, geralmente, restrições adicionais. Algumas das mais importantes são (Dorronsoro, 2007a).
- Todos os veículos têm uma capacidade limitada (CVRP);
- Todos os clientes têm de ser abastecidos dentro de um certo intervalo de tempo (VRPTW);
- O vendedor usa vários armazéns para abastecer os clientes (MDVRP);
- Os clientes podem devolver alguns produtos ao armazém (VRPPD);
- Os clientes podem ser servidos por veículos diferentes (SDVRP);
- Alguns dados, tais como o número de clientes, as suas necessidades e o tempo de serviço ou deslocação, são aleatórios (SVRP);
- As entregas devem ser feitas em certos dias (PVRP).
| Etapas de desenvolvimento - 9 fases | ||||||||
|---|---|---|---|---|---|---|---|---|
Início: 
|
Básico: 
|
Criação: 
|
Desenvolvimento: 
|
Maturação: 
|
Revisão: 
|
Desenvolvido: 
|
Finalização: 
|
Abrangente: 
|