Column Generation based Solution for a Tactical Inventory Routing Problem

Abstract : The inventory routing problem combines the issue of organizing product delivery or pick-up, and managing the inventory at each customer site. Our application deals with planning product pick-ups, customer inventory being emptied on each visit. We assume a deterministic production rate. The inventory costs are limited to those resulting from the transportation model. In this tactical model, the objective is to minimize the fleet size and to ensure that routes are geographically clustered. The planning must be repeated over the time horizon with constrained periodicity. We develop a truncated branch-and-price algorithm combined with rounding and local search heuristics that yield both primal solutions and dual bounds. On a large scale test problem coming from industry, we obtain a solution within 6.5\% deviation of the optimal. A rough comparison with the industrial practice shows a 10\% decrease in number of vehicles as well as in travel distance. The key to the success of the approach is the use of a state-space relaxation technique in formulating the master program to avoid the symmetry in time. The paper also includes a short review of column generation based heuristics.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00169311
Contributor : François Vanderbeck <>
Submitted on : Monday, September 3, 2007 - 4:43:29 PM
Last modification on : Thursday, January 11, 2018 - 6:21:22 AM
Long-term archiving on : Tuesday, September 21, 2010 - 1:44:34 PM

File

RRinria-00169311.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00169311, version 2

Citation

Sophie Michel, François Vanderbeck. Column Generation based Solution for a Tactical Inventory Routing Problem. [Research Report] 2007. ⟨inria-00169311v2⟩

Share

Metrics

Record views

32

Files downloads

8