Métodos Branch-price-and-cut de pontos interiores para variantes do problema de roteamento de veículos

Resumo

Neste projeto, pretende-se desenvolver métodos branch-price-and-cut (BPC) para a resolução de duas variantes práticas do problema de roteamento de veículos. A primeira delas considera o uso de múltiplos entregadores em cada rota e, assim, busca determinar o número de trabalhadores que devem ser alocados a cada veículo, além das decisões usuais de roteamento. O número de entregadores tem influência direta no tempo de serviço em cada cliente e, consequentemente, no número de clientes que podem ser visitados ao dia. A segunda variante a ser abordada envolve requisições de coleta e entrega de produtos e, assim, modela situações urbanas relevantes como a entrega de pedidos e o transporte de pessoas sob demanda. Métodos BPC são atualmente o estado-da-arte na resolução exata de problemas de roteamento de veículos. Entretanto, esses métodos ainda podem levar um tempo razoavelmente alto na prática e, assim, a pesquisa por técnicas para a melhoria desses métodos é bastante ativa. Sendo assim, pretende-se propor um método BPC de pontos interiores para cada variante, o qual usa o algoritmo primal-dual de pontos interiores com o intuito de melhorar a eficiência da geração de colunas e desigualdades válidas. Também, as técnicas de ramificação forte (strong branching) e ramificação antecipada (early branching) deverão ser exploradas neste BPC. Até o momento, não se tem conhecimento do uso destas estratégias na solução dos problemas abordados. Além disso, pretende-se tratar as incertezas sobre dados, uma característica comumente observada em situações reais, mas ainda pouco explorada nos modelos e métodos de solução existentes na literatura de roteamento de veículos. 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. (AU)