Marine Inventory-Routing Problem for Liquefied Natural Gas under Travel Time Uncertainty

Document Type : Research Paper


Faculty of Economics, Kharazmi University, Tehran, Iran


In this paper modelling maritimeinventory-routing problem for liquefied natural gas (LNG) under uncertainty of travel time is presented. We consider one hypothetical LNG manufacturer in Iran that sells its products in the form of long-term contracts and spots. The purpose of the study is to examine and compare the shipping costs of split and non-split delivery.The objective function is minimizing the operational costs, contract penalties, and spot fees, and the main constraints are liquefaction port constraints, ship flows, customer and contractual constraints. Considering uncertainty in the problem is one of this paper's contributions which is modeled by assuming vessels speed as a fuzzy parameter. The parameter and related constraints are defuzifided by Jimenez approach and for solving this problem a metaheuristic method is applied and effectiveness of results are compared with a commercial solver. According to the computational results split delivery policy in deterministic problem is cost effective but in the uncertain situation it is more costly comparing to non-split delivery policy, so split delivery is not recommended in maritime transportation with uncertain nature.


Agra, A., Christiansen, M., Hvattum, L. and Rodrigues, F. (2016). A MIP Based Local Search Heuristic for a Stochastic Maritime Inventory-routing Problem. Springer International Publishing Switzerland, pp. 18-34
Agra, A., Andersson, H., Christiansen, M., and Wolsey, L. (2013a). A maritime inventory-routing problem: Discrete time formulations and valid inequalities. Networks, Vol. 62(4), pp. 297–314.
Agra, A., Christiansen, M., and Delgado, A. (2013b). Mixed integer formulations for a short sea fuel oil distribution problem. Transportation Science, Vol. 47(1), pp. 108–124.
Alborzi, M. (2007). Genetic Algorithm, Elmi Press.
Alkaabneh, F.,Diabat, and A.,Gao,H.,(2020). Benders decomposition for the inventory vehicle routing problem with perishable products and environmental costs, Computers & Operations Research, Vol. 113, 104751.
Archetti, C., Grazia Speranza, M., aurizio Boccia,M. Sforza, A., and Claudio Sterle,C. (2020). A branch-and-cut algorithm for the inventory routing problem with pickups and deliveries, European Journal of Operational Research, Vol. 282(3), pp. 886-89
Al-Khayyal, F. and Hwang, S. (2007). Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk, part i: applications and model. European Journal of Operational Research, Vol. 176, pp. 106–130.
Al-Haidous, S., Msakni, M., and Haouari, M. (2016), Optimal planning of liquefied natural gas deliveries, Transportation Research (Part C), Vol. 69, pp. 79 –90
Anderson, H., Christiansen, M., and Fagerholt, K. (2010). Transportation planning and inventory management in the LNG supply chain. In Bjorndal, E., Pardolos, P. M., and Ronnqvist, M., editors, Energy, Natural Resources and Environmental Economics. Springer, Berlin.
Andersson, H., Christiansen, M., and Desaulniers, G. (2016). A new decomposition algorithm for a liquefied natural gas inventory-routing problem. International Journal of Production Research, Vol. 54, No. 2, 564–578.
Andersson, H., Christiansen, M., and Desaulniers, G. and Rakke, J., (2015b). Creating annual delivery programs of liquefied natural gas, Springer Science Business Media New York, Published on line
Argus Global LNG, Vol XII,11, Nov 2016,
BP Statistical Review of World Energy, June 2016, Statistical Review
BP-Outlook 2035of World , 2016, Outlook
Bertazzietal, L.(2019) A matheuristic algorithm for the multi-depot inventory routing problem, Transportation Research (Part E) , Vol.122, pp. 524–544
Chen, T, Yu, O., Hsu, G., Hsu, F. and Sung, W. (2009). Renewable energy technology portfolio planning with scenario analysis: A case study for Tiwan.Energy Policy, Vol. 37, pp. 2900-2906.
Christiansen, M. (1999). Decomposition of a combined inventory and time constrained ship routing problem. Transportation Science, Vol. 33, pp. 3–26.
Christiansen, M. and Fagerholt, K. (2009). Maritime inventory-routing problems. In Floudas, C. A. and Pardalos, P., editors, Encyclopedia of Optimization, pp. 1947–1955. Springer.
Christiansen, M., Fagerholt, K., Flatberg, T., Haugen, Ø. Kloster, O., and Lund, E. H. (2011). Maritime inventory-routing with multiple products: A case study from the cement industry. European Journal of Operational Research, Vol. 208(1), pp. 86–94.
Christiansen, M., Fagerholt, K., Nygreen, B., and Ronen, D. (2013). Ship routing and scheduling in the new millennium. European Journal of Operational Research, Vol. 228(3), pp. 467–483.
Christiansen, M., Fagerholt, K., and Ronen, D. (2004). Ship routing and scheduling: Status and perspectives. Transportation Science, Vol. 38, pp. 1–18.
Chopra S., Meindl P. (2007) Supply Chain Management. Strategy, Planning & Operation. In: Boersch C., Elschen R. (eds) Das Summa Summarum des Management. Gabler
Coelho, L. C., Cordeau, J.-F., and Laporte, G. (2015). Thirty years of inventory-routing . Transportation Science, Vol. 48(1), pp. 1-19.
Davis, T. (1993). Effective supply chain management. Sloan Manage. Rev. Vol. 34, pp. 35 –36
Engineer, F. G., Furman, K. C., Nemhauser, G. L., Savelsbergh, M. W. P., and Song, J. (2012). A branch-price-and-cut algorithm for single product maritime inventory-routing . Operations Research, Vol. 60, pp. 106–122.
COMMISSION OF THE EUROPEAN COMMUNITIES ,“European transport policy for 2010: time to decide: A White Paper”: COM(2001) 370.
Fodstad, M., Urgent, K. T., Rmo, F., Lium, A., and Stremersch, G. (2010).LNG Scheduler: A rich model for coordinating vessel routing, inventories and trade in the liquefied natural gas supply chain. Journal of Energy Markets, Vol. 3(4), pp. 31–64.
Foulds ,L., (1981) Optimization Techniques: An Introduction [Series: Undergraduate Texts in Mathematics] [Edition: 1], Publisher: Springer-Verlag New York Year: Pages: 502 Language: English
Frazelle, E., (2002), Supply chain strategy: the logistics of supply chain management, McGraw-Hill
Furman, K. C., Song, J.-H., Kocis, G. R., McDonald, M. K., and Warrick, P. H. (2011). Feedstock routing in the ExxonMobil downstream sector. Interfaces, Vol. 41(2), pp. 149–163.
Galbraith, J.R. (1973). Designing Complex Organizations, pp. 187–203. Addison-Wesley Longman Publishing Co., Inc.
Ghiami Y., Van Woensel T., Christiansen M., Laporte G. (2015) A Combined Liquefied Natural Gas Routing and Deteriorating Inventory Management Problem. In: Corman F., Voß S., Negenborn R. (eds) Computational Logistics. ICCL 2015. Lecture Notes in Computer Science, Vol. 9335. Springer, Cham.
Ghiami,Y., Demir, E., Woensel,T., Christiansen,M., and Laporte,G.,(2019), A deteriorating inventory routingproblem for an inland liquefied natural gas distribution network, Transportation Research (Part B1), Vol. 26, pp. 45–67
Goel, V., Furman, K. C., Song, J.-H., and El-Bakry, A. S. (2012). Large neighborhood search for LNG inventory-routing . Journal of Heuristics, Vol.18 (6), pp. 821– 848.
Goel, V., Slusky, M., van Hoeve, W.-J., Furman, K., and Shao, Y. (2015). Constraint programming for LNG ship scheduling and inventory management. European Journal of Operational Research, Vol. 241(3), pp. 662–673.
Grønhaug, R., Christiansen, M., Desaulniers, G., and Desrosiers, J. (2010). A branch-and-price method for a liquefied natural gas inventory-routing problem. Transportation Science, Vol. 44(3), pp. 400–415.
Halvorsen-Weare, E. E. and Fagerholt, K. (2013a). Routing and scheduling in a liquefied natural gas shipping problem with inventory and berth constraints. Annals of Operations Research, Vol. 203(1), pp. 167–186.
Halvorsen-Weare, E. E., Fagerholt, K. and Ronnqvist, M., (2013b), Vessel routing and scheduling under uncertainty in the liquefied natural gas business. Computers & Industrial Engineering, Vol.64, pp, 290-301.
Hashemi, M., Javan, A.(2003) ,Energy Encyclopedia,Fuel Conservation organization
Ho, C.J.( 1989). Evaluating the impact of operating environments on MRP system nervousness. Int. J. Prod. Res. Vol. 27(7), pp. 1115–1135.
Hemmati, A., Hvattum, L., Christiansen, M. and Laporte, G., (2016). An iterative two-phase hybrid matheuristic for a multi-product short sea inventory-routing problem, European Journal of Operational Research, Vol. 252, pp. 775–788.
Hemmati, A., Stålhane, M., Hvattum, L.and Andersson, H., (2015). An effective heuristic for solving a combined cargo and inventory-routing problem in tramp shipping, Computers & Operations Research, Vol. 64, pp. 274-282.
Hewitt, M., Nemhauser, G. L., Savelsbergh, M., and Song, J. (2013). A branch and-price guided search approach to maritime inventory-routing . Computers and Operations Research, Vol. 40, pp. 1410–1419.
Hoff, A., Andersson, H., Christiansen, M., Hasle, G., and L kketangen, A. (2010). Industrial aspects and literature survey: Combined inventory management and routing. Computers & Operations Research, Vol. 37(9), pp. 1515–1536
Jones, C., T. and Reily, W., D. (1985).Using Inventory for Competitive Advantage through Supply Chain Management. International Journal of Physical Distribution & Materials Management, Vol. 15(5), pp.16-26
Klibi, W., Martel, A., and Guitouni, A. (2010). The design of robust value-creating supply chain networks: a critical review. Eur. J. Oper. Res. Vol. 203(2), 283–293.
Li, J., Karimi, I., and Srinivasan, R. (2010). Efficient bulk maritime logistics for the supply and delivery of multiple chemicals. Computers & Chemical Engineering, Vol. 34(12), pp. 2118–2128
Glossary of natural gas industry terms and natural gas ,2001,
Fokkema J, Land, C.Coelhoa,C., George,H and B.Huitema (2020), A continuous-time supply-driven inventory-constrained routing problem, Omega, Vol. 92, 102151.
S.M.J.Mirzapour Al-e-hashem,Y.Rekik,E.Mohammadi Hoseinhajlou,(2019) a hybrid L-Shaped method to solve a bi-objective stochastic transshipment-enabled inventory routing problem. International Journal of Production Economics, Vol. 209 , pp. 381–398.
Mokhatab, S., and Perwal, S., (2006). Is LNG a Competitive Source of Natural Gas? Petroleum Science and Technology, Vol. 25(3), pp. 411-413.
Mokhatab, S., (2010). Selecting Technologies for Onshore LNG Production. Petroleum Technology Quarterly, Vol. 15(3), pp. 115-119.
Mokhatab, S., Mac, J., Valappil, J. and Wood, D. (2014), Handbook of Liquefied Natural Gas, Elsevier Inc.
Mutlu, F., Msakni, M., Yildiz, H., Sonmez, E., and Pokhare, S, (2016). A Comprehensive Annual Delivery Program for Upstream Liquefied Natural Gas Supply Chain, European Journal Of Operational Research, Vol. 250(1), pp. 120-130.
Naderi, M., Pishvaee, S. and Torabi, A. (2016), Applications of Fuzzy Mathematical Programming Approaches in Supply Chain Planning Problems, Springer International Publishing Switzerland
Nikhalat-Jahromi, N., Bell, G., Fontes, D, Cochrane, R. and Angeloudis, P, (2016), Spot sale of uncommitted LNG from Middle East: Japan or the UK, Energy Policy, Vol. 96, pp. 717–725
Papageorgiou, D. J., Cheon, M.-S., Nemhauser, G., and Sokol, J. (2014a). Approximate dynamic programming for a class of long-horizon maritime inventory-routing problems. Transportation Science, Vol. 49(4),
Papageorgiou, D. J., Keha, A. B., Nemhauser, G. L., and Sokol, J. (2014b). Two-stage decomposition algorithms for single product maritime inventory-routing . INFORMS Journal on Computing, Vol. 26(4), pp. 825–847.
Papageorgiou, D. J., Nemhauser, G. L., Sokol, J., Cheon, M.-S., and Keha, A. B. (2014c). Mirplib–a library of maritime inventory-routing problem instances: Survey, core model, and benchmark results. European Journal of Operational Research, Vol. 235(2), pp. 350–366.
Peidro, D., Mula, J., Poler, R., and Lario, F.C. (2009). Quantitative models for supply chain planning under uncertainty: a review. Int. J. Adv. Manuf. Technol. Vol. 43(3–4), pp. 400–420.
Peidro, D., Mula, J., Jimenez, M. and Mar Botella, M. (2010). A fuzzy linear programming based approach for tactical supply chain planning in an uncertainty environment, European Journal of Operational Research, Vol. 205, pp. 65–80
Persson, J. A. and Gothe-Lundgren, M. (2005). Shipment planning at oil refineries using column generation and valid inequalities. European Journal of Operational Research, Vol. 163, pp. 631–652.
Popović, D., Bjelić, N. and Radivojević, G., (2011), Simulation Approach to Analyze Deterministic IRP Solution of the Stochastic Fuel Delivery Problem, Procedia Social and Behavioral Sciences, Vol. 20, pp. 273–282
Rakke, J. G., Andersson, H., Christiansen, M., and Desaulniers, G. (2014). A new formulation based on customer delivery patterns for a maritime inventory-routing problem. Transportation Science, Vol. 49(2), pp. 384–401.
Rakke, J. G., Stalhane, M., Moe, C. R., Christiansen, M., Andersson, H., Fagerholt, K., and Norstad, I. (2011). A rolling horizon heuristic for creating a liquefied natural gas annual delivery program. Transportation Research (Part C), Vol. 19, pp. 896–911.
Roberts, P., England, S. and Hong Kong, W., (2008), Gas Sale and Transportation Agreements: Principles and Practices, Second Edition, Sweer & Maxwell, London.
Rocha, R., Grossmann, I. E., and de Arago, M. V. P. (2013). Cascading knapsack inequalities: reformulation of a crude oil distribution problem. Annals of Operations Research, Vol. 203(1), pp. 1–18.
Ronen, D. et al. (2002). Marine inventory-routing : Shipments planning. Journal of the Operational Research Society, Vol. 53(1), pp. 108–114.
Rosenhead, J., Elton, M., and Gupta, S.K.(1972). Robustness and optimality as criteria for strategic decisions. Oper. Res. Q, pp. 413–431.
Shao, Y., Furman, K. C., Goel, V., and Hoda, S. (2015). A hybrid heuristic strategy for liquefied natural gas inventory-routing . Transportation Research (Part C: Emerging Technologies), Vol. 53, pp. 151–171.
Shen, Q., Chu, F., and Chen, H. (2011). A Lagrangian relaxation approach for a multimode inventory-routing problem with transshipment in crude oil transportation. Computers & Chemical Engineering, Vol. 35(10), pp. 2113–2123.
Simangunsong, E., Hendry, L.C., Stevenson, M.( (2012). Supply-chain uncertainty: a review and theoretical foundation for future research. Int. J. Prod. Res. Vol. 50(16), pp. 4493–4523.
Siswanto, N., Essam, D., and Sarker, R. (2011). Multi-heuristics based genetic algorithm for solving maritime inventory-routing problem, 2011 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), pages 116–120. IEEE.
St¨alhane, M., Rakke, J. G., Moe, C. R., Andersson, H., Christiansen, M., and Fagerholt, K. (2012). A construction and improvement heuristic for an lng inventory-routing problem. Computers & Industrial Engineering, Vol. 62, pp. 245– 255.
Song, J. and Furman, K. C. (2013). A maritime inventory-routing problem: Practical approach. Computers and Operations Research, Vol. 40, pp. 657–665.
SteadieSeifi, M., Dellaert, N.P., Nuijten, W., Woensel T. and Raoufi, R., (2014), Multimodal freight transportation planning: A literature review, European Journal of Operational Research, Vol. 233, pp. 1–15
Uggen, K., Fodstad, M., and Nrsteb, V. (2013). Using and extending fix-and-relax to solve maritime inventory-routing problems. TOP, Vol. 21(2), pp. 355–377.
Yadollahi,E.,Aghezzaf,H.,Walraeven,J.,Raa,B. and Claeys,D. (2019). Evaluating approximate solution models for the stochastic periodic inventory routing problem. Journal of Manufacturing Systems, Vol.50, pp. 25–35
Yongheng, J. and Grossmann, I. E. (2015). Alternative mixed-integer linear programming models of a maritime inventory-routing problem. Computers & Chemical Engineering, Vol. 77, pp. 147–161
UNCTAD (2012). Review of maritime transport. United Nations, New York and Geneva.
Wood, D. A., Mokhatab, S., (2008).Gas Monetization Technologies Remain Tentalizingly on the Brink. World Oil, Vol. 229 (1), pp. 103 -108.