Randomized Local Search for Real-Life Inventory Routing

Thierry Benoist (), Frédéric Gardi (), Antoine Jeanjean () and Bertrand Estellon ()
Additional contact information
Thierry Benoist: Bouygues e-lab, 75008 Paris, France
Frédéric Gardi: Bouygues e-lab, 75008 Paris, France
Antoine Jeanjean: Bouygues e-lab, 75008 Paris, France
Bertrand Estellon: Laboratoire d'Informatique Fondamentale-CNRS UMR 6166, Faculté des Sciences de Luminy-Université Aix-Marseille II, 13288 Marseille, France

Transportation Science, 2011, vol. 45, issue 3, 381-398

Abstract: In this paper, a new practical solution approach based on randomized local search is presented for tackling a real-life inventory routing problem. Inventory routing refers to the optimization of transportation costs for the replenishment of customers' inventories: based on consumption forecasts, the vendor organizes delivery routes. Our model takes into account pickups, time windows, drivers' safety regulations, orders, and many other real-life constraints. This generalization of the vehicle-routing problem was often handled in two stages in the past: inventory first, routing second. On the contrary, a characteristic of our local search approach is the absence of decomposition, made possible by a fast volume assignment algorithm. Moreover, thanks to a large variety of randomized neighborhoods, a simple first-improvement descent is used instead of tuned, complex metaheuristics. The problem being solved every day with a rolling horizon, the short-term objective needs to be carefully designed to ensure long-term savings. To achieve this goal, we propose a new surrogate objective function for the short-term model, based on long-term lower bounds. An extensive computational study shows that our solution is effective, efficient, and robust, providing long-term savings exceeding 20% on average, compared to solutions built by expert planners or even a classical urgency-based constructive algorithm. Confirming the promised gains in operations, the resulting decision support system is progressively deployed worldwide.

Keywords: logistics; real-life inventory routing; decision support system; randomized local search; high-performance algorithm engineering (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0360 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:45:y:2011:i:3:p:381-398

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().