Abstract
In this paper, a real-life routing and scheduling problem encountered is addressed. The problem, which consists in optimizing the delivery of fluids by tank trucks on a long-term horizon, is a generalization of the vehicle routing problem with vendor managed inventory replenishment. The particularity of this problem is that the vendor monitors the customers’ inventories, deciding when and how much each inventory should be replenished by routing tank trucks. Thus, the objective of the vendor is to minimize the logistic cost of the inventory replenishment for all customers over the long run. Then, an original local-search heuristic is presented for solving the short-term planning problem. The engineering of this algorithm follows the three-layers methodology for “high-performance local search” recently introduced by some of the authors. A computational study demonstrates that our solution is both effective, efficient and robust, providing long-term savings exceeding 20 % on average, compared to solutions computed by expert planners or even a classical greedy algorithm. The resulting software is now exploited in North America by one of the French industry leaders.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bell, W., Dalberto, L., Fisher, M., Greenfield, A., Jaikumar, R., Kedia, P., Mack, R., Prutzman, P.: Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer. Interfaces 13(6), 4–23 (1983)
Campbell, A., Clarke, L., Kleywegt, A., Savelsbergh, M.: The inventory routing problem. In: Crainic, T., Laporte, G. (eds.) Fleet Management and Logistics, pp. 95–113. Kluwer Academic Publishers, Norwell (1998)
Campbell, A., Clarke, L., Savelsbergh, M.: Inventory routing in practice. In: Toth, P., Viego, D. (eds.) The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, vol. 9, pp. 309–330. Kluwer Academic Publishers, Philadelphia (2002)
Campbell, A., Savelsbergh, M.: A decomposition approach for the inventory-routing problem. Transportation Science 38(4), 488–502 (2004)
Savelsbergh, M., Song, J.-H.: Inventory routing with continuous moves. Computers and Operations Research 34(6), 1744–1763 (2007)
Savelsbergh, M., Song, J.-H.: An optimization algorithm for the inventory routing with continuous moves. Computers and Operations Research 35(7), 2266–2282 (2008)
Campbell, A., Savelsbergh, M.: Efficient insertion heuristics for vehicle routing and scheduling problems. Transportation Science 38(3), 369–378 (2004)
Lau, H., Liu, Q., Ono, H.: Integrating local search and network flow to solve the inventory routing problem. In: Proceedings of AAAI 2002, the 18th National Conference on Artificial Intelligence, pp. 9–14. AAAI Press, Menlo Park (2002)
Estellon, B., Gardi, F., Nouioua, K.: High-performance local search for task scheduling with human resource allocation. In: Stützle, T., Birattari, M., Hoos, H.H. (eds.) SLS 2009, 2nd International Workshop on Engineering Stochastic Local Search Algorithms. LNCS, vol. 5752, pp. 1–15. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Benoist, T., Estellon, B., Gardi, F., Jeanjean, A. (2009). High-Performance Local Search for Solving Real-Life Inventory Routing Problems. In: Stützle, T., Birattari, M., Hoos, H.H. (eds) Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics. SLS 2009. Lecture Notes in Computer Science, vol 5752. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03751-1_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-03751-1_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03750-4
Online ISBN: 978-3-642-03751-1
eBook Packages: Computer ScienceComputer Science (R0)