A local branching algorithm applied to the inventory routing problem with time-windows

Abstract

Resumo: O ininterrupto desenvolvimento de novas tecnologias e ferramentas para o controle e simulação de processos, aliado à constante busca por modelos matemáticos mais precisos e representativos da realidade, tem possibilitado uma aproximação entre teoria e prática inédita na operação de cadeias de suprimentos. Plan ejamentos táticos e operacionais de alta acurácia são essenciais para determinados tipos de operações, como por exemplo em empresas de entrega de bens perecíveis e de distribuição de combustíveis. Além da preocupação com o controle eficiente de seus estoqu es e de suas frotas veiculares, seus clientes devem ser atendidos dentro de intervalos de tempo determinados, de modo a atingir níveis de serviço estabelecidos e até mesmo garantir a viabilidade de seus produtos. Mesmo com os avanços expressivos na área da modelagem de sistemas de roteamento de veículos, alguns desafios na resolução destes problemas ainda persistem. Este trabalho propõe um modelo matemático de Programação Linear Inteira Mista (PLIM) para o Problema de Roteamento de Estoque com Janelas de Tempo (Inventory-Routing Problem with Time-Windows - IRPTW). Um modelo exato é elaborado, sendo testado seu desempenho computacional sob o auxílio de dois conjuntos de desigualdades válidas desenvolvidas para o Problema de Roteamento de Estoque (Inventory-Routing Problem - IRP), variadas técnicas de préprocessamento, heurísticas de melhoria de solução, e um algoritmo de Local branching. Uma configuração utilizando desigualdades válidas referentes a limites melhorados proporciona os melhores resultados dentre todas as avaliadas. Esta configuração é usada como base para o algoritmo de Local Branching, que apresenta modificações específicas para a exploração agressiva e rápida de vizinhanças reduzidas do espaço de busca do problema. Os resultados obtidos são comparados com um grupo de instâncias desenvolvido para o problema, apresentando ganhos consistentes quando comparado aos resultados existentes. Diversas novas melhores soluções são encontradas para o conjunto avaliado e estabelecem-se limites superiores e inferiores (gaps) para diversas outras instâncias. Este trabalho, até onde sabemos, é o primeiro a integrar todas essas ferramentas de otimização para a resolução do IRPTW, e é o primeiro a comparar resultados com um conjunto de instâncias exclusivamente desenvolvido para o IRPTW, ao mesmo tempo que expande este grupo com instâncias ainda mais complexas. A estratégia focada em exploração parcial de vizinhanças do Local Branching também é uma contribuição, podendo ser ainda mais aprofundada e melhorada em trabalhos futuros.

Abstract: The continuous development of new technologies and tools for better process control and simulation, combined with the strive for better and more representative mathematical models, has allowed supply chain models to reach levels of accuracy never seen. Tactical and operational planning are essential to the operation of many logistic chains, such as perishable products delivery and fuel distribution. Not only these companies have to efficiently manage their inventories and vehicle fleets to achieve predetermined levels of service, they must also fulfill their customers' needs in restricted time-windows and guarantee their product's viability during the entire delivery process. Even though many improvements were made in the field of vehicle routing, some challenges remain. This dissertation proposes a mixed-integer programming (MIP) model for the Inventory-Routing Problem with Time-Windows (IRPTW). An exact model is proposed and has its performance, alongside two groups of valid inequalities developed for the Inventory-Routing Problem (IRP), different preprocessing techniques, solution improvement heuristics, and a Local Branching algorithm, analyzed. A configuration with inventory control valid inequalities presented the best results between all analyzed configurations. This configuration is used as a basis for the Local Branching algorithm, which is specifically adapted to explore reduced neighborhoods of the problem's search space quickly and aggressively. The model is tested using a benchmark instance set and is shown to be superior in comparison to the existing results. Several new best-known solutions are determined for the instance set, just as new upper and lower bounds (gaps) are determined for several other instances. The developments presented here are, as far as we know, the first ones to integrate all these tools under one optimization framework for the IRPTW. This dissertation is also the first one to compare results with a benchmark instance set developed specifically for the problem, while also expanding said instance set. The partial neighborhood exploration used by the Local Branching algorithm is also a contribution to the literature since it enables a quick and efficient exploration of the method's tree. This integration of optimization tools can be worked on future papers, having its approach refined to provide even better results.