Abstract
Liquefied Natural Gas (LNG) is steadily becoming a common mode for commercializing natural gas. Due to the capital intensive nature of LNG projects, the optimal design of LNG supply chains is extremely important from a profitability perspective. Motivated by the need for a model that can assist in the design analysis of LNG supply chains, we address an LNG inventory routing problem where optimized ship schedules have to be developed for an LNG project. In this paper, we present an arc-flow formulation based on the MIP model of Song and Furman (Comput. Oper. Res., 2010). We also present a set of construction and improvement heuristics to solve this model efficiently. The heuristics are evaluated based on a set of realistic test instances that are very large relative to the problem instances seen in recent literature related to this problem. Extensive computational results indicate that the proposed methods are computationally efficient in finding optimal or near optimal solutions and are substantially faster than state-of-the-art commercial optimization software.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja, R.K., Ergun, Ö., Orlin, J.B., Punnen, A.P.: A survey of very large-scale neighborhood search techniques. Discrete Appl. Math. 123, 75–102 (2002)
Andersson, H., Christiansen, M., Fagerholt, K.: Transportation planning and inventory management in the LNG supply chain. Energy Syst. 3, 427–439 (2010a)
Andersson, H., Hoff, A., Christiansen, M., Hasle, G., Løkketangen, A.: Industrial aspects and literature survey: Combined inventory management and routing. Comput. Oper. Res. 37(9), 1515–1536 (2010b)
Christiansen, M., Fagerholt, K.: Maritime inventory routing problems. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 1947–1955. Springer, Berlin (2009)
Christiansen, M., Fagerholt, K., Ronen, D.: Ship routing and scheduling: Status and perspectives. Transp. Sci. 38(1), 1–18 (2004)
Christiansen, M., Fagerholt, K., Nygreen, B., Ronen, D.: Maritime transportation. In: Barnhart, C., Laporte, G. (eds.) Transportation. Handbooks in Operations Research and Management Science, pp. 189–284. Elsevier, Amsterdam (2007). Chapter 4
Christiansen, M., Fagerholt, K., Flatberg, T., Haugen, Ø., Kloster, O., Lund, E.H.: Maritime inventory routing with multiple products: A case study from the cement industry. Eur. J. Oper. Res. 208, 86–94 (2011)
Fodstad, M., Uggen, K.T., Rømo, F., Lium, A.-G., Stremersch, G., Hecq, S.: Profit maximization in the LNG-value chain by combining market prices and ship routing. In: APIEMS 2008—the 9th Asia Pacific Industrial Engineering & Management Systems Conference, pp. 2782–2793 (2008)
Fodstad, M., Uggen, K.T., Rømo, F., Lium, A.-G., Stremersch, G., Hecq, S.: Lngscheduler: A rich model for coordinating vessel routing, inventories and trade in the liquefied natural gas supply chain. J. Energy Mark. 3(4), 31–64 (2011)
Furman, K.C., Song, J.-H., Kocis, G.R., McDonald, M.K., Warrick, P.H.: Feedstock routing in the Exxonmobil downstream sector. Interfaces 41(2), 149–163 (2011)
Grønhaug, R., Christiansen, M.: Supply chain optimization for the liquefied natural gas business. In: Bertazzi, L., van Nunen, J., Speranza, M.G. (eds.) Innovation in Distribution Logistics. Lecture Notes in Economics and Mathematical Systems, vol. 619, pp. 195–218. Springer, Berlin (2009)
Grønhaug, R., Christiansen, M., Desaulniers, G., Desrosiers, J.: A branch-and-price method for a liquefied natural gas inventory routing problem. Transp. Sci. 44(3), 400–415 (2010)
Halvorsen-Weare, E.E., Fagerholt, K.: Routing and scheduling in a liquefied natural gas shipping problem with inventory and berth constraints. Ann. Oper. Res. (2011, to appear)
Rakke, J.G., Stålhane, M., Moe, C.R., Christiansen, M., Andersson, H., Fagerholt, K., Norstad, I.: A rolling horizon heuristic for creating a liquefied natural gas annual delivery program. Transp. Res., Part C, Emerg. Technol. (2011, to appear)
Savelsbergh, M.W.P., Song, J.-H.: An optimization algorithm for the inventory routing problem with continuous moves. Comput. Oper. Res. 35(7), 2266–2282 (2008)
Song, J.-H., Furman, K.C.: A maritime inventory routing problem: Practical approach. Comput. Oper. Res. (2010, in press). Corrected Proof
Stremersch, G., Michalek, J., Hecq, S.: Decision Support Software Tools for LNG Supply Chain Management. Gastech, Richmansworth (2008)
Tusiana, M.D., Shearer, G.: LNG: a Nontechnical Guide. PennWell, Tulsa (2007)
US Energy Information Administration. International energy outlook 2011. http://www.eia.gov/forecasts/ieo/nat_gas.cfm (2011)
van de Broecke, A., Adams, D.: Optimising the LNG supply chain. Pet. Rev. 61(725), 30–32, 48 (2007)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Goel, V., Furman, K.C., Song, JH. et al. Large neighborhood search for LNG inventory routing. J Heuristics 18, 821–848 (2012). https://doi.org/10.1007/s10732-012-9206-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-012-9206-6