Programação Estocástica e Otimização Robusta para Variantes do Problema de Roteamento de Veículos: Formulações e Métodos Exatos

Resumo

Neste trabalho de doutorado, pretende-se abordar duas variantes do problema de roteamento de veículos com janelas de tempo. Na primeira delas, os clientes podem demandarserviços de coleta e entrega de mercadorias ao mesmo tempo e, dessa maneira, modela situaçõesurbanas relevantes como a distribuição de bebidas, sistema de transporte público e de logística reversa. A segunda variante considera o uso de múltiplos entregadores em cada rota e, assim, além de envolver as decisões clássicas de roteamento, a tripulação de cada veículo também deve ser decidida. Em ambientes práticos, um aspecto bastante relevante a ser considerado é a incerteza. Negligenciar a incerteza pode levar a soluções nãoo implementáveis na prática ou ineficientes. Por exemplo, se em algum momento, for constatada uma diferença significativa entre a demanda estimada e a que de fato se materializou, ou o tempo de viagem e serviço seja diferente daquele estipulado, uma visita adicional ao cliente pode ser necessária, ou visitas a outros clientes subsequentes na rota podem não ser mais possíveis, incorrendo em custos adicionais que podem aumentar em demasia o custo operacional total. Por esta razão, abordagens para lidar com as incertezas inerentes do problema devem ser contempladas, sendo a programação estocástica com recurso e a otimização robusta as que têm sido mais usadas atualmente em programação matemática. Desta forma, essas abordagens serão usadas para formular de modo mais realista os problemas a serem tratados neste trabalho. Usar estes abordagens pode levar a que o número de variáveis de decisão e de restrições do problema cresça significativamente,o qual indica que um maior esforço computacional para a resolução do mesmo é requerido. Contudo, estas formulações resultantes apresentam estruturas particulares que podem ser aproveitadas pelos métodos de decomposição e planos de corte. Assim, pretende-se também neste trabalho usar estes métodos para resolver as duas variantes do problema. Recentemente, alguns trabalhos na literatura têm usado estes métodos para resolver outras variantes do problema deroteamento de veículos estocástico, obtendo resultados promissores. Por essa razão, acredita-se que estes métodos forneçam bons resultados neste estudo também. Os métodos propostos serão implementados e avaliados usando exemplares de teste da literatura, bem como pretende-se usar dados reais coletados de empresas.