Developing the Inventory Routing Problem with Backhauls, Heterogeneous Fleet and Split Service


Department of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, Iran


One of the most important points in a supply chain is customer-driven modeling, which reduces the bullwhip effect in the supply chain, as well as the costs of investment on the inventory and efficient transshipment of the products. Their homogeneity is reflected in the Inventory Routing Problem, which is a combination of distribution and inventory management. This paper expands the classical Inventory Routing Problem based on the Multiple Delivery Strategy along with one of the functionalities of routing problem, namely, "backhauls", with a priority consideration for linehaul customers.  Then it has been modeled in the form of a problem with Multi-period, multi-product, and multi- vehicle planning horizons in which stock out is not allowed. Moreover, for an optimal use of the vehicle capacity to serve the linehaul and backhaul customers, this study adopted a “split service” problem to the model, which also increases the complexity of the problem. First, considering the above-mentioned assumptions, a new mathematical model is proposed in the form of mixed integer programming for the problem defined in this paper. Then, since the stated problem can be considered among the non-deterministic polynomial-time hard, an efficient meta-heuristic genetic algorithm is provided for solving it. At the end, the numerical results obtained by this algorithm are analyzed using the randomized test problems. The result shows that by adopting a split service approach, 70% of the test problems will demonstrate cost reduction.


1.     Aghezzaf, E.-H., Raa, B. and Van Landeghem, H., "Modeling inventory routing problems in supply chains of high consumption products", European Journal of Operational Research,  Vol. 169, No. 3, (2006), 1048-1063.
2.     Prins, C., "A simple and effective evolutionary algorithm for the vehicle routing problem", Computers & Operations Research,  Vol. 31, No. 12, (2004), 1985-2002.
3.     Bell, W.J., Dalberto, L.M., Fisher, M.L., Greenfield, A.J., Jaikumar, R., Kedia, P., Mack, R.G. and Prutzman, P.J., "Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer", Interfaces,  Vol. 13, No. 6, (1983), 4-23.
4.     Kleywegt, A.J., Nori, V.S. and Savelsbergh, M.W., "The stochastic inventory routing problem with direct deliveries", Transportation Science,  Vol. 36, No. 1, (2002), 94-118.
5.     Andersson, H., Christiansen, M. and Fagerholt, K., Transportation planning and inventory management in the lng supply chain, in Energy, natural resources and environmental economics. 2010, Springer.427-439.
6.     Coelho, L.C., Cordeau, J.-F. and Laporte, G., "Thirty years of inventory routing", Transportation Science,  Vol. 48, No. 1, (2013), 1-19.
7.     Coelho, L.C. and Laporte, G., "A branch-and-cut algorithm for the multi-product multi-vehicle inventory-routing problem", International Journal of Production Research,  Vol. 51, No. 23-24, (2013), 7156-7169.
8.     Adulyasak, Y., Cordeau, J.-F. and Jans, R., "Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems", INFORMS Journal on Computing,  Vol. 26, No. 1, (2013), 103-120.
9.     Coelho, L.C., Laporte, G. and Cordeau, J.-F., "Dynamic and stochastic inventory-routing, CIRRELT,  (2012).
10.   Santos, E., Ochi, L.S., Simonetti, L. and González, P.H., "A hybrid heuristic based on iterated local search for multivehicle inventory routing problem", Electronic Notes in Discrete Mathematics,  Vol. 52, (2016), 197-204.
11.   Moin, N.H., Salhi, S. and Aziz, N., "An efficient hybrid genetic algorithm for the multi-product multi-period inventory routing problem", International Journal of Production Economics,  Vol. 133, No. 1, (2011), 334-343.
12.   Mjirda, A., Jarboui, B., Macedo, R., Hanafi, S. and Mladenović, N., "A two phase variable neighborhood search for the multi-product inventory routing problem", Computers & Operations Research,  Vol. 52, No., (2014), 291-299.
13.   Sindhuchao, S., Romeijn, H.E., Akçali, E. and Boondiskulchok, R., "An integrated inventory-routing system for multi-item joint replenishment with limited vehicle capacity", Journal of Global Optimization,  Vol. 32, No. 1, (2005), 93-118.
14.   Popović, D., Vidović, M. and Radivojević, G., "Variable neighborhood search heuristic for the inventory routing problem in fuel delivery", Expert Systems with Applications,  Vol. 39, No. 18, (2012), 13390-13398.
15.   Coelho, L.C. and Laporte, G., "The exact solution of several classes of inventory-routing problems", Computers & Operations Research,  Vol. 40, No. 2, (2013), 558-565.
16.   Cordeau, J.-F., Laganà, D., Musmanno, R. and Vocaturo, F., "A decomposition-based heuristic for the multiple-product inventory-routing problem", Computers & Operations Research,  Vol. 55, (2015), 153-166.
17.   Cárdenas-Barrón, L.E., González-Velarde, J.L. and Treviño-Garza, G., "A new approach to solve the multi-product multi-period inventory lot sizing with supplier selection problem", Computers & Operations Research,  Vol. 64, (2015), 225-232.
18.   Rabbani, M., Baghersad, M. and Jafari, R., "A new hybrid ga-pso method for solving multi-period inventory routing problem with considering financial decisions", Journal of Industrial Engineering and Management,  Vol. 6, No. 4, (2013), 909-915.
19.   Mirzaei, S. and Seifi, A., "Considering lost sale in inventory routing problems for perishable goods", Computers & Industrial Engineering,  Vol. 87, (2015), 213-227.
20.   Azadeh, A., Elahi, S., Farahani, M.H. and Nasirian, B., "A genetic algorithm-taguchi based approach to inventory routing problem of a single perishable product with transshipment", Computers & Industrial Engineering,  Vol. 104, (2017), 124-133.
21.   Moubed, M. and Mehrjerdi Zare, Y., "A hybrid dynamic programming for inventory routing problem in collaborative reverse supply chains", International Journal of Engineering, TRANSACTIONS A: Basics,  Vol. 29, No. 10, (2016), 1412-1420.
22.   Liu, S.-C., Lu, M.-C. and Chung, C.-H., "A hybrid heuristic method for the periodic inventory routing problem", The International Journal of Advanced Manufacturing Technology,  Vol. 85, No. 9-12, (2016), 2345-2352.
23.   Fattahi, P., Tanhatalab, M. and Bashiri, M., "Bi-objectives approach for a multi-period two echelons perishable product inventory-routing problem with production and lateral transshipment", International Journal of Engineering-Transactions C: Aspects,  Vol. 30, No. 6, (2016), 876-882.
24.   Yu, Y., Chen, H. and Chu, F., "Large scale inventory routing problem with split delivery: A new model and lagrangian relaxation approach", International Journal of Services Operations and Informatics,  Vol. 1, No. 3, (2006), 304-320.
25.   Yu, Y., Chen, H. and Chu, F., "A new model and hybrid approach for large scale inventory routing problems", European Journal of Operational Research,  Vol. 189, No. 3, (2008), 1022-1040.
26.   Yu, Y., Chu, C., Chen, H. and Chu, F., "Large scale stochastic inventory routing problems with split delivery and service level constraints", Annals of Operations Research,  Vol. 197, No. 1, (2012), 135-158.
27.   Koza, J.R., "Genetic programming: On the programming of computers by means of natural selection, Cambridge, Mass., MIT Press,  (1992).