×

Analysis of an improved branch-and-cut formulation for the inventory-routing problem with transshipment. (English) Zbl 1391.90017

Summary: The inventory-routing problem with transshipment (IRPT) is an extension of the inventory-routing problem (IRP), in which not only the supplier can deliver goods to the retailers, but also transshipments between retailers or between the supplier and a retailer are possible. In this paper, we investigate the branch-and-cut (B&C) formulation of the IRPT and propose four different types of improvements for it. We first develop two new sets of valid inequalities for the problem which greatly strengthen the linear relaxation of the problem. We then improve the bounds on the continuous delivery variables and use these improved bounds to tighten the inventory management constraints. Next, we reformulate the routing component of the problem by exploiting the possible presence of direct shipments in the optimal solution. Finally, we prove that some integer and continuous variables can be eliminated out of the mathematical formulation. Experimental results demonstrate that these improvements drastically reduce the computational burden for solving the IRPT to optimality. On a large set of benchmark instances our proposed branch-and-cut algorithm, which integrates these improvements, outperforms the current best results in the literature. In addition, we are able to find the optimal solutions for two instances whose optimal solution was not known until now.

MSC:

90B05 Inventory, storage, reservoirs
90B06 Transportation, logistics and supply chain management
90B20 Traffic problems in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achabal, D. D.; McIntyre, S. H.; Smith, S. A.; Kalyanam, K., A decision support system for vendor managed inventory, J. Retail., 76, 4, 430-454, (2000)
[2] Andersson, H.; Hoff, A.; Christiansen, M.; Hasle, G.; Løkketangen, A., Industrial aspects and literature survey: combined inventory management and routing, Comput. Oper. Res., 37, 9, 1515-1536, (2010) · Zbl 1190.90012
[3] Archetti, C.; Bertazzi, L.; Laporte, G.; Speranza, M. G., A branch-and-cut algorithm for a vendor-managed inventory-routing problem, Transp. Sci., 41, 3, 382-391, (2007)
[4] Avella, P.; Boccia, M.; Wolsey, L. A., Single-item reformulations for a vendor managed inventory routing problem: computational experience with benchmark instances, Networks, 65, 2, 129-138, (2015) · Zbl 1390.90011
[5] Bell, W. J.; Dalberto, L. M.; Fisher, M. L.; Greenfield, A. J.; Jaikumar, R.; Kedia, P.; Mack, R. G.; Prutzman, P. J., Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer, Interfaces, 13, 6, 4-23, (1983)
[6] Bertazzi, L.; Paletta, G.; Speranza, M. G., Deterministic order-up-to level policies in an inventory routing problem, Transp. Sci., 36, 1, 119-132, (2002) · Zbl 1065.90500
[7] Çetinkaya, S.; Lee, C. Y., Stock replenishment and shipment scheduling for vendor-managed inventory systems, Manag. Sci., 46, 2, 217-232, (2000) · Zbl 1231.90016
[8] Coelho, L. C.; Cordeau, J. F.; Laporte, G., The inventory-routing problem with transshipment, Comput. Oper. Res., 39, 11, 2537-2548, (2012) · Zbl 1251.90030
[9] Coelho, L. C.; Cordeau, J. F.; Laporte, G., Thirty years of inventory routing, Transp. Sci., 48, 1, 1-19, (2013)
[10] Coelho, L. C.; Cordeau, J. F.; Laporte, G., Heuristics for dynamic and stochastic inventory-routing, Comput. Oper. Res., 52, 55-67, (2014) · Zbl 1348.90024
[11] Coelho, L. C.; Laporte, G., The exact solution of several classes of inventory-routing problems, Comput. Oper. Res., 40, 2, 558-565, (2013) · Zbl 1349.90016
[12] Coelho, L. C.; Laporte, G., Single-item reformulations for a vendor managed inventory routing problem: computational experience with benchmark instances, Int. J. Prod. Econ., 155, 391-397, (2014)
[13] Desaulniers, G.; Rakke, J. G.; Coelho, L. C., A branch-price-and-cut algorithm for the inventory-routing problem, Transp. Sci., 50, 3, 1060-1076, (2015)
[14] Mirzapour Al-e-hashem, S.; Rekik, Y., Multi-product multi-period inventory routing problem with a transshipment option: a Green approach, Int. J. Prod. Econ., 157, 80-88, (2014)
[15] Peres, I. T.; Repolho, H. M.; Martinelli, R.; Monteiro, N. J., Optimization in inventory-routing problem with planned transshipment: a case study in the retail industry, Int. J. Prod. Econ., 193, 748-756, (2017)
[16] Pisinger, D.; Ropke, S., A general heuristic for vehicle routing problems, Comput. Oper. Res., 34, 8, 2403-2435, (2007) · Zbl 1144.90318
[17] Timajchi, A.; Mirzapour Al-e-Hashem, S. M.; Rekik, Y., Inventory routing problem for hazardous and deteriorating items in the presence of accident risk with transshipment option, Int. J. Prod. Econ, (2018)
[18] Waller, M.; Johnson, M. E.; Davis, T., Vendor-managed inventory in the retail supply chain, J. Bus. Logist., 20, 1, 183, (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.