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 language | English |
---|---|
Pages (from-to) | 391-397 |
Number of pages | 7 |
Journal | International Journal of Production Economics |
Volume | 155 |
DOIs | |
Publication status | Published - Sept 2014 |
Funding
We thank Guy Desaulniers for his comments on an early version of this paper, as well as Leopoldo Eduardo Cárdenas-Barrón and the anonymous referees for their valuable comments. This work was partly supported by the Canadian Natural Sciences and Engineering Research Council under grant 39682-10 . This support is gratefully acknowledged. We also thank Calcul Québec for providing computing facilities.
Keywords
- Branch-and-cut
- Input order
- Inventory-routing
- Symmetry breaking
- Valid inequalities
ASJC Scopus subject areas
- General Business,Management and Accounting
- Economics and Econometrics
- Management Science and Operations Research
- Industrial and Manufacturing Engineering