Navy

Introdução aos Problemas de Roteirização e
Programação
Programação de Veículos
PNV-2450
Prof. Dr. André Bergsten Mendes

Definição
Um problema de roteirização consiste em determinar rotas para uma frota de veículos que partem e retornam para suas bases. As restrições operacionais mais comuns são: atendimento integral da demanda, capacidade (de carga) dos veículos e duração dos roteiros. Busca-se minimizar uma função de mérito que contempla as parcelas de custo variável e custo fixo.

Variações do PRPVs
Característica
Tamanho da Frota Disponível
Tipo da Frota Disponível
Número de Garagens

Alternativas Possíveis
Um Veículo
Diversos Veículos
Homogênea
Heterogênea
Uma Garagem
Várias
Determinística

Natureza da Demanda

Estocástica
Atendimento Parcial é Permitido
Orientada

Rede Associada

Não Orientada
Mista
Nos Nós da Rede

Localização da Demanda

Restrições de Capacidade dos
Veículos

Nos Arcos da Rede
Em Arcos e Nós da Rede
Imposta e Única
Imposta e Múltipla
Não Imposta

Variações do PRPVs
Característica

Alternativas Possíveis
Imposto e Único (para todas as rotas)

Tempo Máximo de Viagem

Imposto e Diversificado (diferente para rotas diferentes)
Não Imposto
Coleta

Tipo de Operação

Entrega
Coleta e Entrega
Custos Variáveis ou de Roteirização

Custos

Custos Fixos
Custo do Transporte Alternativo para a Demanda Não Atendida
Minimizar o Custo Total de Roteirização
Minimizar a Soma de Custos Fixos e Variáveis
Minimizar a Frota Afretada

Objetivos

Minimizar o Número de Veículos Necessários
Minimizar a Função de Utilidade Baseada em Nível de Serviço e
Prioridade dos Clientes
Balanceamento das Rotas

Fonte: Routing and Scheduling of Vehicles and Crews: The State of Art // Bodin, Golden, Assad, Ball

Programação de Veículos
O problema de programação de veículos surge com a incorporação de restrições temporais & restrições de precedência ao problema de roteirização de