Optimization strategies for the integrated routing and inventory management problem

Overview & Synopsis

Inventory management and vehicle routing problems are logistic challenges that can significantly influence the efficiency and effectiveness of supply chain operations and should be well-coordinated and aligned. Handling both jointly is even more challenging when considering the number of customers to be served and the length of the time horizon. In the literature, this problem is known as the Inventory Routing Problem (IRP) and aims to find a minimum-cost solution that addresses both inventory and transportation problems simultaneously. The IRP was first introduced in 1983 by Bell et al. and have received a lot of attention from the OR community so far, which has introduced numerous extensions and provided datasets to favor research and fair comparisons.In research, some gaps exist, and the IRP is not an exception. Most works in the literature so far assume that the fleet of vehicles used for the deliveries is homogeneous and that the costs associated with product storage and customer needs are constant and equal over the entire time horizon, which is not in accordance with a real scenario. Also, a single-item delivery per period is often considered by the formulation, which is clearly not cost-effective.This thesis addresses the IRP and introduces a new variant that is closer to a real logistic scenario by incorporating a heterogeneous vehicle fleet, customer demands, and inventory holding costs that are period-dependent. Additionally, it considers that customers may prefer receiving products in batches rather than in single units. For that, a new set of instances is introduced to handle these new features. This novel variant, named the Heterogeneous Inventory Routing Problem with Batch Size (HIRP-BS), is studied using three approaches. The first one is a mathematical formulation that extends a flow formulation initially designed to handle the HIRP-BS characteristics. New variables and constraints are then required to consider the new incorporated features. Not surprisingly, the formulation is not capable of handling large-scale instances and even the medium-scale ones are hard to solve in a timely manner. The second method is an iterative algorithm which decomposes the original IRP into as many sub-problems as periods of time are considered. The idea is to solve the sub-problems in chronological order such that at each iteration (except for the first, which corresponds to the first period), it uses the solution obtained in the previous as a starting point for the current one. The changes are limited by an input parameter to accelerate convergence. The overall idea is that for a given period, the following iterations should require smart modification of the previous solutions of the partial problem already solved and that the number of changes should decrease once it approaches the end of the time horizon.The third method is a split-based metaheuristic that decomposes a multi-period sequence of customers, called a giant tour, into routes that are assigned to a period and a vehicle type. The contribution leads to a new multi-period Split algorithm. It starts with the computation of the estimated quantities and periods for the replenishment, assuming the delivery operations at the latest possible moment. It allows the definition of a giant tour that is evaluated through a Split algorithm responsible for defining feasible solutions for the problem. Then, a local search mechanism dedicated to the routing problem takes advantage of classical route-based operators. Lastly, a post-optimization phase is considered, and slightly improve solution quality in terms of inventory and routing aspects based on a solution distance notion. Results are promising in terms of convergence and can provide valid upper bounds in a reasonable time even for the large-scale instances proposed.