Logística/Sistemas de distribuição/Escala de veículos

Origem: Wikilivros, livros abertos por um mundo aberto.
Saltar para a navegação Saltar para a pesquisa

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: 0de8.svg Básico: 1de8.svg Criação: 2de8.svg Desenvolvimento: 3de8.svg Maturação: 4de8.svg Revisão: 5de8.svg Desenvolvido: 6de8.svg Finalização: 7de8.svg Abrangente: 8de8.svg
  1. 7de8.svg Formulação e notação básica
  2. 2de8.svg Abordagem exacta (João Gouveia)
    1. 2de8.svg Algoritmos Branch and Bound para CPEV
    2. 2de8.svg Algoritmos Branch and Cut para CPEV
  3. 2de8.svg Heurística
    1. 2de8.svg Heurística clássica para CPEV
      1. 2de8.svg Heurística construtiva
      2. 2de8.svg Heurística de duas fases
        1. 2de8.svg Agrupar-primeiro-e-rotas-depois
        2. 2de8.svg Rotas-primeiro-agrupamento-depois
      3. 2de8.svg Métodos de melhoramento
    2. 2de8.svg Meta-heurística para CPEV
  4. 2de8.svg Janela de Tempo PEV
  5. 2de8.svg Capacidade PEV