Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/41771| Type: | Tese |
| Title: | O problema multiobjetivo de roteamento de veículos com janela de tempo e com tempo de viagem/serviço estocástico |
| Authors: | Douglas Moura Miranda |
| First Advisor: | Samuel Vieira Conceição |
| First Referee: | Marcelo Franco Porto |
| Second Referee: | João Antônio de Vasconcelos |
| Third Referee: | Alexandre Xavier Martins |
| metadata.dc.contributor.referee4: | Gilberto de Miranda Junior |
| Abstract: | 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. |
| Subject: | Engenharia de produção Processo estocástico Veículos |
| language: | por |
| metadata.dc.publisher.country: | Brasil |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| metadata.dc.publisher.department: | ENG - DEPARTAMENTO DE ENGENHARIA PRODUÇÃO |
| metadata.dc.publisher.program: | Programa de Pós-Graduação em Engenharia de Produção |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/41771 |
| Issue Date: | 24-Aug-2016 |
| Appears in Collections: | Teses de Doutorado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Tese Texto Douglas - Final para publicacao b.pdf | 2.73 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.