# A heuristic branch-cut-and-price algorithm for the ROADEF/EURO challenge on Inventory Routing

Nabil Absi, Diego Cattaruzza, Dominique Feillet, Maxime Ogier, Frédéric Semet

► To cite this version:

Nabil Absi, Diego Cattaruzza, Dominique Feillet, Maxime Ogier, Frédéric Semet. A heuristic branch-cut-and-price algorithm for the ROADEF/EURO challenge on Inventory Routing. ROADEF 2017 - 18ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2017, Metz, France. pp.1-2. [hal-01629298](https://hal-01629298)

HAL Id: hal-01629298

https://inria.hal.science/hal-01629298

Submitted on 6 Nov 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
A heuristic branch-cut-and-price algorithm for the
ROADEF/EURO challenge on Inventory Routing

Nabil Absi¹, Diego Cattaruzza², Dominique Feillet¹, Maxime Ogier², Frédéric Semet²

¹ Ecole des Mines de Saint-Etienne and LIMOS UMR CNRS 6158, CMP Georges Charpak, F-13541 Gardanne, France.

absi,feillet@emse.fr

² Université Lille, CNRS, Centrale Lille, Inria, UMR 9189 - CRISTAL
Centre de Recherche en Informatique Signal et Automatique de Lille

F-59000 Lille, France

diego.cattaruzza,maxime.ogier,frederic.semet@ec-lille.fr

**Mots-clés :** Inventory Routing Problem, Challenge ROADEF/EURO, Heuristic branch-cut-and-price

# 1 Introduction

In this paper, we propose a heuristic solution method for the Inventory Routing Problem introduced during the 2016 ROADEF/EURO challenge, that we coin as REC-IRP. Inventory routing has attracted researchers for many years due to both its practical and theoretical interests (Coelho et al.; 2013). The REC-IRP proposed for the challenge is original and complex for several reasons : the logistic ratio optimization objective, the hourly time-granularity for inventory constraints, the driver/trailer allocation management. Clearly, designing an exact solution approach is out of reach for large size instances as those proposed during the challenge. However, we decided to address the REC-IRP with a branch-cut-and-price framework : a cut-and-column generation procedure is developed, along with a heuristic pricing algorithm to generate new columns and a heuristic fixing procedure to generate integer solutions.

# 2 Problem definition

Due to space limitation, in this section we provide a reduced definition of the REC-IRP. For a complete and detailed problem definition, the interested reader is referred to the challenge web page (ROADEF/EURO Challenge 2016 : Inventory Routing Problem (2016)). The REC-IRP can be defined on a complete graph $G = (N, A)$, where $N = B \cup S \cup C$. $B$ is the set of bases, where the trailers are located at the beginning of the planning horizon ; $S$ is the set of sources, locations where the trailers can be filled up with the product to be delivered ; $C$ is the set of customers to be served ; $A$ is the set of arcs connecting each couple of nodes in $N$.

The set of customers $C$ is defined as $C = C_1 \cup C_2$ where $C_1$ is the set of Vendor Management Inventory (VMI) customers, while $C_2$ is the set of call-in customers. The latter needs to be delivered by a fixed quantity within a predefined time window. Customers $C_1$ are associated with a hourly consumption pattern, a capacity and minimum delivery quantity. These customers
are not mandatory to be visited unless they are forecast to run out of stock during the horizon planning. However, at each visit, at least the minimum delivery quantity must be delivered.

A set of trailers $\mathcal{T}$ is available at the beginning of the horizon. Each trailer has a proper capacity and can accede a subset of customers.

A set of drivers $\mathcal{D}$ is also available. Each driver can drive a subset of trailers and is associated with a set of time windows during which it is allowed to work. Maximum driving duration and minimum inter-shift duration must be taken into account as well.

The REC-IRP calls for the determination of a set of shifts (elementary pieces of work for a driver accomplished with a trailer), the quantity of product to be delivered to each customer visited in the shift, and an assignment of such shifts to drivers and trailers in order to minimize the *logistic ratio*. The *logistic ratio* is the ratio of the total working cost divided by the total quantity of product that is delivered. This represents the delivery cost of each unit of product. The planning needs to :

- avoid stock-outs at customers in $C_1$ and serve all customers in $C_2$;

- respect capacity constraints on trailers;

- respect capacity and accessibility constraints on customers;

- respect driver time windows and maximum driving duration;

- respect the possible allocations of drivers to trailers;

- the shifts assigned to the same trailer do not overlap in time;

- the shifts assigned to the same driver need to respect the minimum inter-shift duration.

# 3 Solution method and results

This section briefly summarizes the solution method adopted to tackle the REC-IRP. The fractional objective function is managed as proposed by Dinkelbach (1967) by introducing a parameter $Z$ to linearize the objective. We first generate a set of promising time-stamped shifts and solve the restricted master problem based on this set of shifts. When a solution is provided we check if non-zero artificial variables, introduced to guarantee that a feasible solution is found, exist. In this case we generate new shifts with negative reduced cost by means of a heuristic pricing procedure. We then solve again the restricted master problem and iterate until all the artificial variables are null.

Then, until a time limit is reached, we again (1) add shifts with negative reduced costs into the restricted master problem; (2) select shifts (by means of a variable fixing procedure); (3) update the value of $Z$; (4) solve the restricted master problem and possibly call the heuristic pricing heuristic. Finally we solve the MIP formulation of our problem. This solution method allowed our team to qualify to the final phase of the ROADEF/EURO challenge 2016.

# Références

Coelho, L. C., Cordeau, J.-F. and Laporte, G. (2013). Thirty years of inventory routing, *Transportation Science* **48**(1): 1–19.

Dinkelbach, W. (1967). On nonlinear fractional programming, *Management Science* **13**(7): 492–498.

ROADEF/EURO Challenge 2016: Inventory Routing Problem (2016).
URL: http://challenge.roadef.org/