A Two-Phase Hybrid Heuristic Method for a Multi-Depot Inventory-Routing Problem

Document Type : Research Paper


1 MSc. Student, School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

2 Assistant Professor, School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

3 Ph.D. Candidate, School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran


In this study, a two phase hybrid heuristic approach was proposed to solve the multi-depot multi-vehicle inventory routing problem (MDMVIRP). Inventory routing problem (IRP) is one of the major issues in the supply chain networks that arise in the context of vendor managed systems (VMI) The MDMVIRP combines inventory management and routing decision. We are given on input a fleet of homogeneous vehicles, in which any of these vehicles have a capacity and a fixed cost. Also, a set of distribution centers with restricted capacities are responsible to serve the customer’s demands, which are known for distributer at beginning of each period. The problem consists of determining the delivery quantity to the customers at each period and the routes to be performed to satisfy the demand of the customers. The objective function of this problem is to minimize sum of the holding cost at distributer centers and the customers, and of the transportation costs associated to the preformed routes. In the proposed hybrid heuristic method, after a Construction phase (first phase) a modified variable neighborhood search algorithm (VNS), with distinct neighborhood structures, is used during the improvement phase (second phase). Moreover, we use simulated annealing (SA) concept to avoid that the solution remains in a local optimum for a given number of iterations. Computational results on benchmark instances that adopt from the literature of IRP indicate that the proposed algorithm is capable to find, within reasonable computing time, several solutions gained by the approaches that applied in the previous published studies.


-Adulyasak, Y., Cordeau, J. F. and Jans, R. (2013) "Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems", INFORMS Journal on Computing, Vol.26, No.1, pp.103-120.
-Andersson, H., Hoff, A., Christiansen, M., Hasle, G. and Løkketangen, A. (2010) "Industrial aspects and literature survey: Combined inventory management and routing", Computers and Operations Research, Vol.37, No.9, pp.1515–1536. Available at: http://dx.doi.org/10.1016/j.
-Archetti, C., Bertazzi, L., Laporte, G. and Speranza, M. G. (2007) "A branch-and-cut algorithm for a vendor-managed inventory-routing problem", Transportation Science, Vol.41, No.3, pp.382–391. Available at: http://pubsonline.informs.org/doi/abs/10.1287/trsc.1060.0188.
-Archetti, C., Bertazzi, L. and Speranza, M. G. (2012) "A hybrid heuristic for an inventory routing problem". , INFORMS Journal on Computing, Vol.24, No.1, pp.101–116.
-Bell, W.J., Dalberto, L. M., Fisher, M.L., Greenfield, A.J., Jaikumar, R., Kedia, P., Mack, R.G. and Prutzman, P.J. (1983). "Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer", Interfaces, Vol.13, No.6, pp.4–23.
- Cheraghi, S.and Hossein-Motlagh, S.M. (2017) "Optimal Blood Transportation in Disaster Relief Considering Facility Disruption and Rout Reliability under Uncertainly", International Journal of Trnasportation Engineering, Vol.4, No. 3, pp. 225-254.
-Coelho, L.C., Cordeau, J.F. and Laporte, G. (2012) "Consistency in multi-vehicle inventory-routing", Transportation Research Part C: Emerging Technologies, Vol.24, pp.270–287. Available at: http://dx.doi.org/10.1016/j.trc.2012.03.007.
-Coelho, L.C. and Laporte, G. (2013) "The exact solution of several classes of inventory-routing problems", Computers and Operations Research, Vol.40,No.2, pp.558–565. Available at: http://dx.doi.org/10.1016/j.cor.2012.08.012.
-Cordeau, J. F., Laganà, D., Musmanno, R., and Vocaturo, F. (2014) " A decomposition-based heuristic for the multiple-product inventory-routing problem", Computers and Operations Research, Vol.55, pp.153–166. Available at: htt p://dx.doi.org/10.1016/j.cor.2014.06.007.
-Hosseini-Motlagh, S.-M., Ahadpour, P. and Haeri, A. (2015) "Proposing an approach to calculate headway intervals to improve bus fleet scheduling using a data mining algorithm", Journal of Industrial and Systems Engineering, Vol.8, No.4, pp.72–86.
Hosseini-Motlagh, S. M., Majidi, S., Yaghoubi, S., & Jokar, A. (2017) "Fuzzy green vehicle routing problem with simultaneous pickup-delivery and time windows". RAIRO-Operations Research. Available at: https://doi.org/10.1051/ro/2017007
-Huang, S.-H. and Lin, P.-C. (2010) "A modified ant colony optimization algorithm for multi-item inventory routing problems with demand uncertainty", Transportation Research Part E: Logistics and Transportation Review, Vol.46, No.5, pp.598–611. Available at: http://dx.doi.org/10.1016/j.tre.2010.01.006.
-Jokar, A. and Hosseini-Motlagh, S.-M. (2015) "Impact of capacity of mobile units on blood supply chain performance: Results from a robust analysis", International Journal of Hospital Research, Vol.4, No.3, pp.101–105.
-Jokar, A., and Sahraeian, R. (2012) "A heuristic based approach to solve a capacitated location-routing problem". Journal of Management and Sustainability, Vol.2, No.2, pp.219.
-Liu, S. C. and Lee, S. B. (2003) "A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into consideration", International Journal of Advanced Manufacturing Technology, Vol.22, No.(11–12), pp. 941–950.
-Majidi, S., Hosseini-Motlagh, S.-M., Yaghubi,S., Jokar, A. (2015). "An adaptive large neighborhood search heuristic for the green vehicle routing problem with simultaneously pickup and delivery and hard time windows", Journal Of Industrial Engeeniring Research in Production Systems, Vol.3, No.6, pp.149–165.
-Majidi, S., Hosseini-Motlagh, S.-M., Ignatius, J. (2017). "Adaptive Large Neighborhood Search heuristic for Pollution Routing Problem with simultaneous pickup and delivery", Soft Computing, Available at: 10.1007/s00500-017-2535-5
-Mirzaei, S. and Seifi, A. (2015). "Considering lost sale in inventory routing problems for perishable goods", Computers and Industrial Engineering, Vol.87 (May),  pp.213–227. Available at: http://dx.doi.org/10.1016/j.cie.2015.05.010.
-Mirzapour Al-e-hashem, S.M.J. and Rekik, Y. (2014) "Multi-product multi-period inventory routing problem with a transshipment option: a green approach", International Journal of Production Economics, Vol.157, pp.80–88.
-Mladenović, N. and Hansen, P. (1997) "Variable neighborhood search", Computers & Operations Research, Vol.24, No.11, pp.1097–1100.
-Park, Y.-B., Yoo, J.-S. and Park, H.-S. (2016) "A genetic algorithm for the vendor-managed inventory routing problem with lost sales", Expert Systems with Applications, Vol.53, pp.149–159.
-Poorjafari, V., Long Yue, W., and Holyoak, N. (2016) "A novel method for measuring the quality of temporal integration in public transport systems", International Journal of Transportation Engineereing , Vol.4, No.1, pp.53-59.
-Riahi N., Hosseini-Motlagh, S.-M., Teimourpour, B., (2013) " Three-phase Hybrid Times Series Modeling Framework for Improved Hospital Inventory Demand Forecast", International Journal of Hospital Research Vol. 2, No. 3, pp.130-138
-Saremi, S., Hosseini-Motlagh, S.-M.,S. and Sadjadi, S.J. (2016) "A reschedule design for disrupted liner ships considering ports demand and CO2 emissions : the case study of islamic republic of Iran shipping lines (IRISL)", Journal of Industrial and Systems Engineering, Vol.9, No.1, pp.126–148.
-Shaabani, H. and Kamalabadi, I. N. (2016) "An efficient population-based simulated annealing algorithm for the multi-product multi-retailer perishable inventory routing problem", Computers and Industrial Engineering, Vol.99, pp.189–201. Available at: http://dx.doi.org/10.1016/j.cie.2016.07.022.
-Solyali, Ǒguz and Süral, H. (2011) "A branch-and-cut algorithm using a strong formulation and an a priori tour-based heuristic for an inventory-routing problem", Transportation Science,Vol.45, No.3, pp.335–345.
-Soysal, M., Bloemhof-Ruwaard, J. M., Haijema, R. and van der Vorst, J. G. (2015) "Modeling an inventory routing problem for perishable products with environmental considerations and demand uncertainty", International Journal of Production Economics, Vol.164, pp.118–133.