Aplicação de uma heurística de melhoria em um problema de roteirização com restrição de janela de tempo

Abstract

RESUMO: Este trabalho objetiva melhorar a elaboração de rotas de entrega em uma cadeia de suprimento que apresenta um problema de roteirização com restrição de janela de tempo, denominado Vehicle Routing Problem with Time Windows (VRPTW) com a aplicação de uma heurística de melhoria, o Adaptive Large Neighborhood Search (ALNS). Buscando estabelecer um número mínimo de frota de entregadores capazes de suprirem a demanda, bem como um mínimo de quilometragem rodada. A heurística foi implementada no VBA do Excel e possibilitou a criação de uma nova roteirização das entregas. A nova roteirização apresentou uma diminuição na quilometragem percorrida pela frota de 420,31 km para 248,14 km, uma redução de 40%, que representa uma redução nos custos variáveis de R$764,41 por mês. Além disso, indicou uma possível redução de frota, de sete para seis veículos, e uma diminuição no tempo total de trabalho de 2365 minutos por dia para 1919 minutos por dia, uma redução de 19%. O solver utilizado mostrou-se capaz de lidar com possíveis alterações no curto prazo, sendo elas: a) mudança na demanda dos clientes; b) mudança na capacidade dos veículos; c) manutenção de uma quantidade de entregadores diferente daquela recomendada pela solução; e d) ausência de entregadores. Contudo não é muito interessante para lidar com problemas cuja alteração do pool de clientes acontece de forma acelerada.

ABSTRACT: This paper aims to improve the elaboration of delivery routes in a supply chain that presents a time-constrained routing problem, known as Vehicle Routing Problem with Time Windows (VRPTW) by using an Adaptive Large Neighborhood Search (ALNS) heuristic. The object function is to minimize the number of fleet, as well as the total mileage traveled. The chosen heuristics was implemented with Excel’s VBA and it made possible to criate a new delivery routes. The new delivery routes shown to be possible to reduce the total travelled distance from 420,31 km to 248,14 km, a reduction of 40%, that reduction represents a R$ 764,41 reductions in the variable cost per month. Moreover, it shown a possible reduction in the number of vehicles from seven to six, and a decrease in total work time from 2365 minutes per day to 1919 minutes per day, a reduction of 19%. The solving tool is able to deal with possible short-term alteration. Those being: a) change in client demand; b) change in the vehicle capacity; c) set a fixed number of vehicles even if the algorithm suggests a different number; d) employees day-off. That being said the solver is not well equipped to deal with problems in which the client pool changes in a fast pace.