O problema multiobjetivo de roteamento de veículos com janela de tempo e com tempo de viagem/serviço estocástico
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Primeiro orientador
Membros da banca
Marcelo Franco Porto
João Antônio de Vasconcelos
Alexandre Xavier Martins
Gilberto de Miranda Junior
João Antônio de Vasconcelos
Alexandre Xavier Martins
Gilberto de Miranda Junior
Resumo
O roteamento de veículos com janela de tempo é particularmente importante
num sistema logístico. Em aplicações reais é comum encontrar problemas que envolvam
uma quantidade muito grande de clientes e que consequentemente fogem do alcance de
métodos exatos, mas que podem ser resolvidos por metaheurísticas. O ambiente real
também possui dados probabilísticos por natureza, como o tempo de viagem entre dois
clientes e o tempo de atendimento de cada cliente. Isto faz com que um modelo de
roteamento que considere as incertezas envolvidas nestes dados seja mais adequado.
Modelos determinísticos podem encontrar soluções que embora viáveis do ponto
de vista do seu modelo matemático, na prática, apresentam casos com baixa probabilidade
do veículo visitar o cliente antes do limite máximo de tempo estabelecido. Modelos
estocásticos que incluem tais incertezas em sua formulação matemática podem assegurar
uma probabilidade mínima de que o veículo visite o cliente dentro do limite de tempo.
Neste contexto, o presente trabalho aborda uma variante do Problema de
Roteamento de Veículos com Janelas de Tempo (PRVJT) no qual o tempo de viagem
entre os clientes e o tempo de serviço em cada cliente são conhecidos apenas
probabilisticamente. Um novo método é desenvolvido não só para estimar o tempo de
chegada aos clientes, mas também para calcular a probabilidade dos veículos atenderem
os clientes dentro de suas respectivas janelas de tempo. O modelo estatístico proposto é
comparado com um benchmark da literatura.
Este trabalho também explora a relação de custo-benefício existente entre
minimizar os custos de transporte e maximizar o nível de serviço (probabilidade do cliente
ser visitado dentro da janela de tempo) criando-se uma versão multiobjetiva do problema.
Conceitos da teoria de otimização multiobjetivo são utilizados para desenvolver um
algoritmo memético, até então inédito na literatura, capaz de encontrar um conjunto de
soluções não dominadas que ofereça informações importantes ao tomador de decisão. Um
método de otimização multicritério é utilizado para permitir a seleção de uma solução a
partir do conjunto de soluções obtido pelo algoritmo.
Abstract
This thesis tackles the vehicle routing problem with hard time windows and
stochastic travel and service times using multiobjective optimization. A new method to
compute the service level (probability of the vehicle visiting the customer before the end
of the time window) is presented. The problem is modeled with two objective functions
using the Pareto ranking technique in which the two objective dimensions are the
operational cost and the service level. The trade-off between the minimization of the
operational cost and the maximization of the service level is explored and the algorithm
returns a set of solutions that fairly consider both of these dimensions. A memetic
multiobjective algorithm is developed to solve all the 56 well know Solomon instances
with 100 customers. It is provided details of the design and implementation of the
algorithm and also a number of computational experiments with comprehensive analysis
of the results. To our knowledge, this method is unprecedented in the literature.
Assunto
Engenharia de produção, Processo estocástico, Veículos
Palavras-chave
Roteamento de veículos, Tempo de viagem estocástico, Janela de tempo, Tempo de serviço estocástico, Otimização multiobjetivo