dc.contributor.author | De La Vega Martinez, Jonathan Justen | |
dc.date.accessioned | 2019-05-06T19:27:39Z | |
dc.date.available | 2019-05-06T19:27:39Z | |
dc.date.issued | 2019-03-29 | |
dc.identifier.citation | DE LA VEGA MARTINEZ, Jonathan Justen. Otimização robusta e programação estocástica para o problema de roteamento de veículos com múltiplos entregadores: formulações e métodos exatos. 2019. Tese (Doutorado em Engenharia de Produção) – Universidade Federal de São Carlos, São Carlos, 2019. Disponível em: https://repositorio.ufscar.br/handle/ufscar/11374. | * |
dc.identifier.uri | https://repositorio.ufscar.br/handle/ufscar/11374 | |
dc.description.abstract | In this thesis, we study the vehicle routing problem with time windows and multiple deliverymen with uncertainty. In addition to routing and scheduling decisions, this problem involves deliverymen allocation decisions on each route to reduce costs and service times. Parameters such as customer demands, travel and service times are considered uncertain. Thus, we propose new models of static robust optimization, which incorporate measures to effectively deal with the cost-risk trade-off, and new models of two stage stochastic programming with recourse to address this problem. Usually, when applying the concepts of robust optimization and stochastic programming, the number of decision variables and constraints grow significantly in terms of instance size. Consequently, the larger the instances, the greater is the computational effort required to solve the resulting models with general purpose solvers. However, computational effort can be significantly reduced if appropriate exact methods are developed that take advantage of the resulting robust and stochastic models’ structure. For this reason, we propose exact methods based on branch-and-cut and branch-price-and-cut, which are effective to solve literature instances. Numerical experiments based on these instances and risk analysis based on Monte Carlo simulation indicate the potential of static robust optimization to address the trade-off between cost and risk. These experiments also reveal that this approach provides good results, even without complete knowledge of some probabilistic measure of the uncertain parameters. Regarding stochastic programming, the numerical experiments show that it is possible to save important resources by solving the two stage stochastic programming model with recourse rather than adopting simpler strategies based on the expected value. To the best of our knowledge, there is no studies in the literature that have addressed the problem under study in this thesis, with uncertainty in demands, as well as in travel and service times. We believe that developing models and effective solution methods to address the vehicle routing problem with time windows and multiple deliverymen are original and relevant contributions to the state-of-the-art literature, opening up new fields for future research not only for the problem under study, but also for other variants of vehicle routing problem. | eng |
dc.description.sponsorship | Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) | por |
dc.language.iso | por | por |
dc.publisher | Universidade Federal de São Carlos | por |
dc.rights.uri | Acesso aberto | por |
dc.subject | Roteamento de veículos | por |
dc.subject | Múltiplos entregadores | por |
dc.subject | Otimização robusta | por |
dc.subject | Programação estocástica | por |
dc.subject | Métodos de decomposição | por |
dc.subject | Vehicle routing | eng |
dc.subject | Multiple deliverymen | eng |
dc.subject | Robust optimization | eng |
dc.subject | Stochastic programming | eng |
dc.subject | Decomposition methods | eng |
dc.title | Otimização robusta e programação estocástica para o problema de roteamento de veículos com múltiplos entregadores: formulações e métodos exatos | por |
dc.type | Tese | por |
dc.contributor.advisor1 | Morabito Neto, Reinaldo | |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/4194801952934254 | por |
dc.contributor.advisor-co1 | Munari Junior, Pedro Augusto | |
dc.contributor.advisor-co1Lattes | http://lattes.cnpq.br/1328868140869976 | por |
dc.description.resumo | Nesta tese, estuda-se o problema de roteamento de veículos com janelas de tempo e múltiplos entregadores com incerteza. Esse problema, além das decisões de roteamento e sequenciamento, também envolve decisões de alocação de entregadores a cada uma das rotas, visando reduzir os tempos de serviços e custos. Parâmetros como a demanda de clientes, tempos de viagens e tempos de serviços são aqui considerados incertos. Assim, nesta tese são propostos novos modelos de otimização robusta estática, que incorporam medidas para lidar efetivamente com o trade-off custo-risco, e novos modelos de programação estocástica de dois estágios com recurso, para abordar esse problema. Tipicamente, para tratar incertezas aplicando os conceitos das abordagens de otimização robusta e programação estocástica, os números de variáveis de decisão e de restrições do problema crescem significativamente em termos do tamanho da instância. Consequentemente, quanto maior for o tamanho da instância, maior é o esforço computacional requerido para resolver os modelos resultantes com solvers de propósito gerais. No entanto, o esforço computacional pode ser reduzido significativamente se métodos exatos apropriados forem desenvolvidos, de modo a aproveitarem bem a estrutura particular dos modelos robustos e estocásticos resultantes. Por essa razão, nesta tese, também desenvolvem-se métodos exatos customizados para esse problema, baseados em branch-and-cut e branch-price-and-cut, que são efetivos para resolver instâncias da literatura. Os experimentos numéricos baseados nestas instâncias e a análise de risco baseada na simulação de Monte-Carlo revelam o potencial da abordagem de otimização robusta estática para lidar com o compromisso existente entre custo e risco. Esses experimentos também revelam que essa abordagem oferece bons resultados, mesmo sem ter conhecimento exato de alguma medida probabilística dos parâmetros incertos. Em relação à programação estocástica, os resultados dos experimentos numéricos mostram que é possível poupar recursos importantes com a resolução do modelo de programação estocástica dois estágios com recurso, em vez de adotar estratégias mais simples baseadas no valor esperado. Até o presente momento, não se tem conhecimento de trabalhos na literatura que tenham abordado o problema objeto de estudo desta tese, com incertezas na demanda, bem como nos tempos de viagens e tempos de serviços. Acredita-se que desenvolver modelos e métodos de solução efetivos para tratar esse problema de roteamento de veículos com múltiplos entregadores sejam contribuições originais e relevantes para o estado da arte da literatura, abrindo novos campos para trabalhos futuros, não apenas para esse problema em estudo, mas também para outras variantes de problemas de roteamento de veículos. | por |
dc.publisher.initials | UFSCar | por |
dc.publisher.program | Programa de Pós-Graduação em Engenharia de Produção - PPGEP | por |
dc.subject.cnpq | ENGENHARIAS::ENGENHARIA DE PRODUCAO::PESQUISA OPERACIONAL | por |
dc.subject.cnpq | ENGENHARIAS::ENGENHARIA DE TRANSPORTES::PLANEJAMENTO DE TRANSPORTES | por |
dc.description.sponsorshipId | FAPESP: 2015/14582-7 | por |
dc.ufscar.embargo | Online | por |
dc.publisher.address | Câmpus São Carlos | por |
dc.contributor.authorlattes | http://lattes.cnpq.br/6363035402235765 | por |