Improved solutions for inventory-routing problems through valid inequalities and input ordering

Leandro C. Coelho, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

79 Citations (Scopus)

Abstract

Inventory-routing problems (IRP) combine inventory control and vehicle routing, effectively optimizing inventory and replenishment decisions over several periods at a centralized level. In this paper we provide an exact formulation which includes several well-known valid inequalities for some classes of IRPs. We then propose three new valid inequalities based on the relation between demand and available capacities. Then, following an idea proposed for the binary clustering and for the job scheduling problems, we also show how the order of the input data can have a major effect on the linear relaxation of the proposed model for the IRP. Extensive computational experiments confirm the success of our algorithm. We have used two available datasets with new solutions identified as recently as 2013. On one set of benchmark instances with 249 open instances, we have improved 98 lower bounds, we have computed 96 new best known solutions, and we have proved optimality for 11 instances. On the other dataset composed of larger instances, of which were 63 open, we have improved 32 lower bounds, we have obtained 20 new best known solutions, and we proved optimality for three instances.

Original languageEnglish
Pages (from-to)391-397
Number of pages7
JournalInternational Journal of Production Economics
Volume155
DOIs
Publication statusPublished - Sep 2014

Keywords

  • Branch-and-cut
  • Input order
  • Inventory-routing
  • Symmetry breaking
  • Valid inequalities

ASJC Scopus subject areas

  • Business, Management and Accounting(all)
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Fingerprint

Dive into the research topics of 'Improved solutions for inventory-routing problems through valid inequalities and input ordering'. Together they form a unique fingerprint.

Cite this