| Summary: | Após ter sido introduzido por Dantzig and Ramser, o Problema de Roteamento de Veículos (PRV) se tornou um dos problemas mais estudados em Otimização Combi-natória. Diferentes estratégias de solução foram propostas ao longo do tempo para solucionar o PRV e suas variações. Nesta tese, são discutidos dois problemas resul-tantes da integração do PRV com problemas de distribuição de mercadorias.O primeiro problema a ser discutido surge da integração do PR V com decisões sobre carga/descarga de mercadorias em um Cross-Docking, que é um armazém que permite armazenamento de curta duração e a consolidação das cargas entre sua co-leta e a entrega. O problema resultante desta integração é denominado Problema de Roteamento de Veículos com Cross-Docking (PRVCD). São apresentados dois mode-los de programação inteira para o PRVCD e respectivos algoritmos Branch-and-Price (BP) para solucionar tais modelos. Será discutida também uma abordagem alterna-tiva aos modelos tradicionais do PRVCD, na qual os veículos podem evitar passar pelo Cross-Docking na coleta/engrega de cargas, sem consolidá-las. Denomina-se estanova abordagem de Problema de Coleta e Entrega com Cross-Docking (PCECD). Uma formulação matemática e um novo algoritmo BP são introduzidos para solucionar o PCECD. O segundo problema tratado surge dos sistemas multi-elos. O Problema de Rotea-mento de Veículos Capacitado com 2 Elos (PRVC-2E) se caracteriza por definir o fluxode cargas entre o depósito e seus consumidores finais, usando armazéns intermediários denominados satélites. Estes armazéns são responsáveis por integrar o primeiro elo, que contém o depósito, com o segundo elo, aonde estão dispostos os consumidores. Além do mais, as mercadorias podem ser consolidadas nos satélites a fim de minimizar os custos de entrega. São apresentados um modelo matemático para o PRVC-2E, que possui um número exponencial de variáveis, além de quatro famílias de desigualdades válidas parafortalecê-lo. A solução deste modelo, incluindo a separação das desigualdades válidas, é feita por um algoritmo Branch-and-cut-and-price (BCP). Os resultados obtidos peloBCP mostram que o seu desempenho domina o de outros algoritmos propostos para o PRVC-2E na literatura.
|
|---|