Dynamic and stochastic routing; Transshipment; Substitution; Genetic algorithm; deep reinforcement learning
[en] In this paper, we investigate a two-level supply chain consisting of a company which manufactures
a set of products and distributes them via its central warehouse to a set of customers. The problem is modelled as a dynamic and stochastic inventory routing problem (DSIRP) that considers two flexible instruments of transshipment and substitution to mitigate shortages at the customer level. A new resolution approach, based on the hybridisation of mathematical modelling, Genetic Algorithm and Deep Reinforcement Learning is proposed to handle the combinatorial complexity of the problem at hand. Tested on the 150 most commonly used benchmark instances for single-vehicle-product DSIRP, results show that the proposed algorithm outperforms the current best results in the literature for medium and large instances. Moreover, 450 additional instances for multi-products DSIRP are generated. Different demand distributions are examined in these experiments, namely, Normal distribution, Poisson distribution for demand occurrence, combined with demands of constant size; Stuttering Poisson distribution and Negative Binomial distribution. In terms of managerial insights, results show the advantages of promoting inventory sharing and substitutions on the overall supply chain performance.
Abdelmaguid, T. F. 2004. “Heuristic Approaches for The Integrated Inventory Distribution Problem.” PhD thesis, University of Southern California.
Abdelmaguid, T. F., M. M. Dessouky, and F. Ordóñez. 2009. “ Heuristic Approaches for the Inventory-Routing Problem with Backlogging.” Computers & Industrial Engineering 56 (4): 1519–1534.
Achamrah, F. E., F. Riane, and S. Limbourg. 2021. “ Spare Parts Inventory Routing Problem with Transshipment and Substitutions Under Stochastic Demands.” Applied Mathematical Modelling 101: 309–331.
Adams, D., D.-H. Oh, D.-W. Kim, C.-H. Lee, and M. Oh. 2021. “ Deep Reinforcement Learning Optimization Framework for a Power Generation Plant Considering Performance and Environmental Issues.” Journal of Cleaner Production 291: 125915.
Alegre, J., M. Laguna, and J. Pacheco. 2007. “ Optimizing the Periodic Pick-up of Raw Materials for A Manufacturer of Auto Parts.” European Journal of Operational Research 179 (3): 736–746.
Alom, M. Z., T. M. Taha, C. Yakopcic, S. Westberg, P. Sidike, M. S. Nasrin, M. Hasan, B. C. Van Essen, A. A. S. Awwal, and V. K. Asari. 2019. “ A State-of-the-Art Survey on Deep Learning Theory and Architectures.” Electronics 8 (3): 292.
Archetti, C., L. Bertazzi, A. Hertz, and M. G. Speranza. 2012. “ A Hybrid Heuristic for An Inventory Routing Problem.” INFORMS Journal on Computing 24 (1): 101–116.
Archetti, C., L. Bertazzi, G. Laporte, and M. G. Speranza. 2007a. “ A Branch-and-Cut Algorithm for a Vendor-Managed Inventory-Routing Problem.” Transportation Science 41 (3): 382–391.
Archetti, C., L. Bertazzi, G. Laporte, and M. G. Speranza. 2007b. “ A Branch-and-Cut Algorithm for a Vendor-Managed Inventory-Routing Problem.” Transportation Science 41 (3): 382–391.
Baker, B. M., and M. Ayechew. 2003. “ A Genetic Algorithm for the Vehicle Routing Problem.” Computers & Operations Research 30 (5): 787–800.
Bell, W. J., L. M. Dalberto, M. L. Fisher, A. J. Greenfield, R. Jaikumar, P. Kedia, R. G. Mack, and P. J. Prutzman. 1983. “ Improving the Distribution of Industrial Gases with An On-Line Computerized Routing and Scheduling Optimizer.” Interfaces 13 (6): 4–23.
Bertazzi, L., A. Bosco, F. Guerriero, and D. Laganà. 2013. “ A Stochastic Inventory Routing Problem with Stock-Out.” Transportation Research Part C: Emerging Technologies 27: 89–107.
Bertazzi, L., and M. G. Speranza. 2002. “ Continuous and Discrete Shipping Strategies for the Single Link Problem.” Transportation Science 36 (3): 314–325.
Burns, L. D., R. W. Hall, D. E. Blumenfeld, and C. F. Daganzo. 1985. “ Distribution Strategies that Minimize Transportation and Inventory Costs.” Operations Research 33 (3): 469–490.
Christiansen, M. 1999. “ Decomposition of a Combined Inventory and Time Constrained Ship Routing Problem.” Transportation Science 33 (1): 3–16.
Christiansen, M., K. Fagerholt, T. Flatberg, Ø. Haugen, O. Kloster, and E. H. Lund. 2011. “ Maritime Inventory Routing with Multiple Products: A Case Study from the Cement Industry.” European Journal of Operational Research 208 (1): 86–94.
Chrysochoou, E., A. Ziliaskopoulos, and A. Lois. 2015. “An Exact Algorithm for the Stochastic Inventory Routing Problem with Transshipment.”
Coelho, L. C., J. -F. Cordeau, and G. Laporte. 2012a. “ Consistency in Multi-Vehicle Inventory-Routing.” Transportation Research Part C: Emerging Technologies 24: 270–287.
Coelho, L. C., J. -F. Cordeau, and G. Laporte. 2012b. “ The Inventory-Routing Problem with Transshipment.” Computers & Operations Research 39 (11): 2537–2548.
Coelho, L., J.-F. Cordeau, and G. Laporte. 2014a. “ Heuristics for Dynamic and Stochastic Inventory-Routing.” Computers & Operations Research 52: 55–67.
Coelho, L. C., J. -F. Cordeau, and G. Laporte. 2014b. “ Thirty Years of Inventory Routing.” Transportation Science 48 (1): 1–19.
Coelho, L. C., and G. Laporte. 2013. “ A Branch-and-Cut Algorithm for the Multi-Product Multi-Vehicle Inventory-Routing Problem.” International Journal of Production Research 51 (23-24): 7156–7169.
Conceição, S. V., G. L. C. da Silva, D. Lu, N. T. R. Nunes, and G. C. Pedrosa. 2015. “ A Demand Classification Scheme for Spare Part Inventory Model Subject to Stochastic Demand and Lead Time.” Production Planning & Control 26 (16): 1318–1331.
Dehghani, M., B. Abbasi, and F. Oliveira. 2021. “ Proactive Transshipment in the Blood Supply Chain: A Stochastic Programming Approach.” Omega 98: 102112.
Dror, M., and L. Levy. 1986. “ A Vehicle Routing Improvement Algorithm Comparison of A ‘Greedy’ and a Matching Implementation for Inventory Routing.” Computers & Operations Research 13 (1): 33–45.
Grahovac, J., and A. Chakravarty. 2001. “ Sharing and Lateral Transshipment of Inventory in A Supply Chain with Expensive Low-Demand Items.” Management Science 47 (4): 579–594.
Grønhaug, R., M. Christiansen, G. Desaulniers, and J. Desrosiers. 2010. “ A Branch-and-Price Method for a Liquefied Natural Gas Inventory Routing Problem.” Transportation Science 44 (3): 400–415.
Hewitt, M., G. Nemhauser, M. Savelsbergh, and J.-H. Song. 2013. “ A Branch-and-Price Guided Search Approach to Maritime Inventory Routing.” Computers & Operations Research 40 (5): 1410–1419.
Hssini, I., N. Meskens, and F. Riane. 2016. “Blood Products Inventory Pickup and Delivery Problem Under Time Windows Constraints.” In International Conference on Operations Research and Enterprise Systems, Rome, Italy, Vol. 2, 349–356. https://www.scitepress.org/ProceedingsDetails.aspx?ID=+QMdiRu8YnQ=&t=1
Huang, S.-H., and P.-C. Lin. 2010. “ A Modified Ant Colony Optimization Algorithm for Multi-Item Inventory Routing Problems with Demand Uncertainty.” Transportation Research Part E: Logistics and Transportation Review 46 (5): 598–611.
Laporte, G. 2009. “ Fifty Years of Vehicle Routing.” Transportation Science 43 (4): 408–416.
Lefever, W., E.-H. Aghezzaf, K. Hadj-Hamou, and B. Penz. 2018. “ Analysis of An Improved Branch-and-Cut Formulation for the Inventory-Routing Problem with Transshipment.” Computers & Operations Research 98: 137–148.
López-Ibáñez, M., J. Dubois-Lacoste, L. Pérez Cáceres, M. Birattari, and T. Stützle. 2016. “ The Irace Package: Iterated Racing for Automatic Algorithm Configuration.” Operations Research Perspectives 3: 43–58.
Mirzaei, S., and A. Seifi. 2015. “ Considering Lost Sale in Inventory Routing Problems for Perishable Goods.” Computers & Industrial Engineering 87: 213–227.
Mohammed, M. A., M. K. A. Ghani, R. I. Hamed, S. A. Mostafa, D. A. Ibrahim, H. K. Jameel, and A. H. Alallah. 2017. “ Solving Vehicle Routing Problem by Using Improved K-Nearest Neighbor Algorithm for Best Solution.” Journal of Computational Science 21: 232–240.
Paterson, C., G. Kiesmüller, R. Teunter, and K. Glazebrook. 2011. “ Inventory Models with Lateral Transshipments: A Review.” European Journal of Operational Research 210 (2): 125–136.
Peres, I. T., H. M. Repolho, R. Martinelli, and N. J. Monteiro. 2017. “ Optimization in Inventory-Routing Problem with Planned Transshipment: A Case Study in the Retail Industry.” International Journal of Production Economics 193: 748–756.
Roldán, R. F., R. Basagoiti, and L. C. Coelho. 2016. “ Robustness of Inventory Replenishment and Customer Selection Policies for the Dynamic and Stochastic Inventory-Routing Problem.” Computers & Operations Research 74: 14–20.
Ronen, D. 2002. “ Marine Inventory Routing: Shipments Planning.” Journal of the Operational Research Society 53 (1): 108–114.
Sabba, S., and S. Chikhi. 2012. “ Integrating the Best 2-opt Method to Enhance the Genetic Algorithm Execution Time in Solving the Traveler Salesman Problem.” Advances in Intelligent and Soft Computing170: 195–208.
Savelsbergh, M., and J.-H. Song. 2008. “ An Optimization Algorithm for the Inventory Routing Problem with Continuous Moves.” Computers & Operations Research 35 (7): 2266–2282.
Silver, D. 2015. “RL Exploration and Exploitation.”
Solyalı, O., J.-F. Cordeau, and G. Laporte. 2012. “ Robust Inventory Routing Under Demand Uncertainty.” Transportation Science 46: 327–340.
Stålhane, M., H. Andersson, M. Christiansen, J.-F. Cordeau, and G. Desaulniers. 2012. “ A Branch-Price-and-Cut Method for a Ship Routing and Scheduling Problem with Split Loads.” Computers and Operations Research 39: 3361–3375.
Strack, G., B. Fortz, F. Riane, and M. Van Vyve. 2011. “Comparison of Heuristic Procedures for An Integrated Model for Production and Distribution Planning in An Environment of Shared Resources.” LIDAM Discussion Papers CORE 2011016, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
Syntetos, A. A., M. Z. Babai, and N. Altay. 2012. “ On the Demand Distributions of Spare Parts.” International Journal of Production Research 50 (8): 2101–2117.
Talbi, E.-G. 2020. “Machine Learning Into Metaheuristics: A Survey and Taxonomy of Data-Driven Metaheuristics.” Working paper or preprint.
Turrini, L., and J. Meissner. 2019. “ Spare Parts Inventory Management: New Evidence From Distribution Fitting.” European Journal of Operational Research 273 (1): 118–130.
Yu, Y., C. Chu, H. Chen, and F. Chu. 2013. “ Large Scale Stochastic Inventory Routing Problems with Split Delivery and Service Level Constraints.” Annals of Operations Research 197: 135–158.
Zhang, D., Y. Liu, R. M'Hallah, and S. C. Leung. 2010. “ A Simulated Annealing with a New Neighborhood Structure Based Algorithm for High School Timetabling Problems.” European Journal of Operational Research 203 (3): 550–558.
Zhao, Q.-H., S. Chen, and C.-X. Zang. 2008. “ Model and Algorithm for Inventory/Routing Decision in A Three-Echelon Logistics System.” European Journal of Operational Research 191 (3): 623–635.