A major cement producer's maritime inventory routing problem is to satisfy the demand at different ports during the planning horizon. A heterogeneous fleet of bulk ships with undedicated compartments transport multiple non-mixable cement products from production port to consumption ports along across several islands. Inventory constraints are present both at the production and the consumption ports, and there are upper and lower limits for all inventories. Besides, constraints regarding the capacity of the ship's compartment hold, the port's depth, and the fact that different products cannot be mixed must be considered. The problem's objective is to find a minimum transportation cost solution while satisfying several technical and physical constraints within a given planning horizon. To solve this problem, first, a mixed-integer linear programming model is presented considering various scheduling and routing constraints, loading or unloading constraints, and ship selection and capacity constraints. Considering the difficulty of solving large problems and the NP-hard nature of the model, we combine the previously introduced MILP formulation with a metaheuristic approach to solve the problem called Genetic Algorithm. The proposed model is validated against MILP solution using AMPL for several problem instances. Besides, we implement this proposed model to solve the real problem faced by a cement company in Indonesia to satisfy the needs at the consumption ports during the given planning horizon with good quality solutions within reasonable solution time.

A major cement producer's maritime inventory routing problem is to satisfy the demand at different ports during the planning horizon. A heterogeneous fleet of bulk ships with undedicated compartments transport multiple non-mixable cement products from production port to consumption ports along across several islands. Inventory constraints are present both at the production and the consumption ports, and there are upper and lower limits for all inventories. Besides, constraints regarding the capacity of the ship's compartment hold, the port's depth, and the fact that different products cannot be mixed must be considered. The problem's objective is to find a minimum transportation cost solution while satisfying several technical and physical constraints within a given planning horizon. To solve this problem, first, a mixed-integer linear programming model is presented considering various scheduling and routing constraints, loading or unloading constraints, and ship selection and capacity constraints. Considering the difficulty of solving large problems and the NP-hard nature of the model, we combine the previously introduced MILP formulation with a metaheuristic approach to solve the problem called Genetic Algorithm. The proposed model is validated against MILP solution using AMPL for several problem instances. Besides, we implement this proposed model to solve the real problem faced by a cement company in Indonesia to satisfy the needs at the consumption ports during the given planning horizon with good quality solutions within reasonable solution time.

Abdelmaguid, T. F., Dessouky, M. M., & Ordóñez, F. (2009). Heuristic Approaches for The Inventory Routing Problem with Backlogging. Computers and Industrial Engineering, 56(4), 1519–1534. https://doi.org/10.1016/j.cie.2008.09.032
Agra, A., Andersson, H., Christiansen, M., & Wolsey, L. (2013). A Maritime Inventory Routing Problem: Discrete Time Formulations and Valid Inequalities. Networks, 62(4), 297–314. https://doi.org/10.1002/net.21518
Al-Khayyal, F., & Hwang, S.-J. (2007). Discrete Optimization Inventory Constrained Maritime Routing and Scheduling for Multi-Commodity Liquid Bulk, Part I: Applications and Model. European Journal of Operational Research, 176, 106–130. https://doi.org/10.1016/j.ejor.2005.06.047
Alegre, J., Laguna, M., & Pacheco, J. (2007). Optimizing The Periodic Pick-Up of Raw Materials for A Manufacturer of Auto Parts. European Journal of Operational Research, 179(3), 736–746. https://doi.org/10.1016/j.ejor.2005.03.063
Andersson, H., Hoff, A., Christiansen, M., Hasle, G., & Løkketangen, A. (2010). Industrial Aspects and Literature Survey: Combined Inventory Management and Routing. Computers and Operations Research, 37(9), 1515–1536. https://doi.org/10.1016/j.cor.2009.11.009
Archetti, C., Boland, N., & Speranza, M. G. (2017). A Matheuristic for The Multivehicle Inventory Routing Problem. INFORMS Journal on Computing, 29(3), 377–387. https://doi.org/10.1287/ijoc.2016.0737
Azadeh, A., Elahi, S., Farahani, M. H., & Nasirian, B. (2017). A Genetic Algorithm-Taguchi Based Approach to Inventory Routing Problem of A Single Perishable Product with Transshipment. Computers and Industrial Engineering, 104, 124–133. https://doi.org/10.1016/j.cie.2016.12.019
Bell, W. J., Dalberto, L. M., Fisher, M. L., Greenfield, A. J., Jaikumar, R., Kedia, P., Mack, R. G., & Prutzman, P. J. (1983). Improving The Distribution of Industrial Gases with An On-Line Computerized Routing and Scheduling Optimizer. Interfaces (Providence, Rhode Island), 13(6), 4–23. https://doi.org/10.1287/inte.13.6.4
Campbell, A. M., & Savelsbergh, M. W. P. (2004). A Decomposition Approach for The Inventory-Routing Problem. Transportation Science, 38(4), 488–502. https://doi.org/10.1287/trsc.1030.0054
Christiansen, M. (1999). Decomposition of A Combined Inventory and Time Constrained Ship Routing Problem. Transportation Science, 33(1), 3–16. https://doi.org/10.1287/trsc.33.1.3
Christiansen, M., Fagerholt, K., Flatberg, T., Haugen, Ø., Kloster, O., & Lund, E. H. (2011). Maritime Inventory Routing with Multiple Products: A Case Study from The Cement Industry. European Journal of Operational Research, 208(1), 86–94. https://doi.org/10.1016/j.ejor.2010.08.023
Christiansen, M., Fagerholt, K., Nygreen, B., & Ronen, D. (2013). Ship Routing and Scheduling in The New Millennium. European Journal of Operational Research, 228(3), 467–483. https://doi.org/10.1016/j.ejor.2012.12.002
Christiansen, M., & Nygreen, B. (1998). A Method for Solving Ship Routing Problems with Inventory Constraints. Annals of Operations Research, 81(0), 357–378. https://doi.org/10.1023/a:1018921527269
Coelho, L. C., Cordeau, J. F., & Laporte, G. (2014). Thirty Years of Inventory Routing. Transportation Science, 48(1), 1–19. https://doi.org/10.1287/trsc.2013.0472
Dauzère-Pérès, S., Nordli, A., Olstad, A., Haugen, K., Koester, U., Myrstad, P. O., Teistklub, G., & Reistad, A. (2007). Omya Hustadmarmor Optimizes its Supply Chain for Delivering Calcium Carbonate Slurry to European Paper Manufacturers. Interfaces, 37(1), 39–51. https://doi.org/10.1287/inte.1060.0276
Engineer, F. G., Furman, K. C., Nemhauser, G. L., Savelsbergh, M. W. P., & Song, J. H. (2012). A branch-Price-and-Cut Algorithm for Single-Product Maritime Inventory Routing. Operations Research, 60(1), 106–122. https://doi.org/10.1287/opre.1110.0997
Federgruen, A., Prastacos, G., & Zipkin, P. H. (1986). Allocation and Distribution Model for Perishable Products. Operations Research, 34(1), 75–82. https://doi.org/10.1287/opre.34.1.75
Federgruen, A., & Zipkin, P. (1984). Combined Vehicle Routing and Inventory Alloacation Problem. Operations Research, 32(5), 1019–1037. https://doi.org/10.1287/opre.32.5.1019
Goodman, E. D. (2009). Introduction to Genetic Algorithms. 2009 World Summit.
Grønhaug, R., & Christiansen, M. (2010). Supply Chain Optimization for The Liquefied Natural Gas Business. Lecture Notes in Economics and Mathematical Systems, 619, 195–218. https://doi.org/10.1007/978-3-540-92944-4_10
Grønhaug, R., Christiansen, M., Desaulniers, G., & Desrosiers, J. (2010). A Branch-and-Price Method for A Liquefied Natural Gas Inventory Routing Problem. Transportation Science, 44(3), 400–415. https://doi.org/10.1287/trsc.1100.0317
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University of Michigan Press. https://www.amazon.com/Adaptation-Natural-Artificial-Systems-Introductory/dp/0262581116
Moin, N. H. &, & Salhi, S. (2007). Inventory Routing Problems: A Logistical Overview. Journal of the Operational Research Society, 58, 1185–1194. https://doi.org/10.1057/palgrave.jors.2602264
Moin, N. H., Salhi, S., & Aziz, N. A. B. (2011). An Efficient Hybrid Genetic Algorithm for The Multi-Product Multi-Period Inventory Routing Problem. International Journal of Production Economics, 133(1), 334–343. https://doi.org/10.1016/j.ijpe.2010.06.012
Persson, J. A., & Göthe-Lundgren, M. (2005). Shipment Planning at Oil Refineries using Column Generation and Valid Inequalities. European Journal of Operational Research, 163(3), 631–652. https://doi.org/10.1016/j.ejor.2004.02.008
Popović, D., Vidović, M., & Radivojević, G. (2012). Variable Neighborhood Search heuristic for The Inventory Routing Problem in Fuel Delivery. Expert Systems with Applications, 39(18), 13390–13398. https://doi.org/10.1016/j.eswa.2012.05.064
Qu, W. W., Bookbinder, J. H., & Iyogun, P. (1999). Integrated Inventory-Transportation System with Modified Periodic Policy for Multiple Products. European Journal of Operational Research, 115(2), 254–269. https://doi.org/10.1016/S0377-2217(98)00301-4
Ronen, D. (2002). Marine Inventory Routing: Shipments Planning. Journal of the Operational Research Society, 53(1), 108–114. https://doi.org/10.1057/palgrave.jors.2601264
Santosa, B., & Ai, T. J. (2017). Pengantar Metaheuristik Implementasi Dengan Matlab. ITS Teknosains.
Simchi-Levi D., Chen X., & Bramel J. (2005). The Logic of Logistics: Theory, Algorithms, and Application for Logistics and Supply Chain Management. In The Logic of Logistics. Springer. https://doi.org/10.1007/b97669
Siswanto, N., Essam, D., & Sarker, R. (2011). Solving The Ship Inventory Routing and Scheduling Problem with Undedicated Compartments. Computers and Industrial Engineering, 61(2), 289–299. https://doi.org/10.1016/j.cie.2010.06.011
Song, J. H., & Furman, K. C. (2013). A Maritime Inventory Routing Problem: Practical Approach. Computers and Operations Research, 40(3), 657–665. https://doi.org/10.1016/j.cor.2010.10.031
Stacey, J., Natarajarathinam, M., & Sox, C. (2007). The Storage Constrained, Inbound Inventory Routing Problem. International Journal of Physical Distribution and Logistics Management, 37(6), 484–500. https://doi.org/10.1108/09600030710763396
Stålhane, M., Rakke, J. G., Moe, C. R., Andersson, H., Christiansen, M., & Fagerholt, K. (2012). A Construction and Improvement Heuristic for A Liquefied Natural Gas Inventory Routing Problem. Computers and Industrial Engineering, 62(1), 245–255. https://doi.org/10.1016/j.cie.2011.09.011
Uggen, K. T., Fodstad, M., & Nørstebø, V. S. (2013). Using and Extending Fix-and-Relax to Solve Maritime Inventory Routing Problems. TOP, 21(2), 355–377. https://doi.org/10.1007/s11750-011-0174-z
Webb, I. R., & Larson, R. C. (1995). Period and Phase of Customer Replenishment: A New Approach to The Strategic Inventory/Routing Problem. European Journal of Operational Research, 85(1), 132–148. https://doi.org/10.1016/0377-2217(93)E0232-M
Yu, V. F., & Lin, S. Y. (2015). A Simulated Annealing Heuristic for the Open Location-Routing Problem. Computers and Operations Research, 62, 184–196. https://doi.org/10.1016/j.cor.2014.10.009