Matheuristics for Inventory Routing Problems

Introduction

The class of Inventory Routing Problems (IRPs) includes a variety of different optimization problems that may have very different characteristics but all simultaneously consider a routing and an inventory management component of an optimization problem. Time may be discrete or continuous, demand may be deterministic or stochastic, specific application-dependent characteristics may be considered, inventory holding costs may be accounted for in the objective function or not. When in an IRP the holding costs are not included in the objective function, a limited inventory capacity at the customers is available and cannot be exceeded. IRPs have received little attention, if compared to plain vehicle routing problems (VRPs). However, the interest in this class of problems has been increasing from the beginning of the eighties. We refer for an overview of the available literature to the surveys Bertazzi et al (2008), Campbell et al (1998), Cordeau et al (2007), Federgruen and Simchi-Levi (1995), Moin and Salhi (2007). In this chapter we will focus on deterministic inventory routing problems.

IRPs model the simultaneous optimization of inventory management and routing that are traditionally optimized separately and independently. Clearly, the traditional separate optimization may lead to a global sub-optimum. The efforts invested in the optimization of the routing side of the problem may be vanished because the optimization ignores the relations between the routing and the inventory management sides of the problem. In VRPs usually the quantities to be delivered to the customers in a specific day by a fleet of capacitated vehicles are given. In a IRP, whereas the demands of the customers are known, the quantities to be delivered have to be decided. An optimal solution of a IRP may suggest that customers located close to each other should be served the same days, that customers close to the factory should be served more frequently, while customers far from the factory should be served more rarely.

Obviously, IRPs are more complex to solve than VRPs. A time dimension is present in the IRPs that is rarely considered in the VRPs. Whereas the value of IRPs in supply chain optimization is widely accepted, the class of the studied IRPs is still quite limited and relatively little is known in terms of solution techniques. The plain VRPs are known to be computationally very hard to solve. The IRPs are even harder. Few attempts to find the optimal solution to IRPs have been proposed in the literature. In most cases heuristic algorithms have been presented.

In this chapter we will illustrate traditional and new ideas for the design of effective heuristics by making use of a simple instance of a basic IRP. We will also review the use of heuristics for IRPs in the literature in a separate section. A set of customers have to be served by a factory (or a warehouse) over a discrete time horizon, measured for example in days, by using a fleet of capacitated vehicles. The factory and the customers have an initial inventory and limited inventory capacity. The production rate of the factory and the consumption rate of the customers are known and are time-dependent. The problem consists in deciding which customers to serve each day of the time horizon and which routes the vehicles travel to serve the customers of each day in such a way that a cost function is minimized. The cost function includes the routing costs and possibly the inventory costs at the factory and/or at the customers. We call this problem the basic IRP.