Navigating a Greener Horizon: Route Optimization of LNG Shipping
Main Article Content
This research addresses a critical gap in maritime logistics optimization by developing the first comprehensive Capacitated Vehicle Routing Problem (CVRP) framework specifically designed for Japan's domestic Liquified Natural Gas (LNG) terminal distribution network. Despite Japan being the world's second-largest LNG consumer with 37 operational terminals, no prior academic research has systematically optimized inter-terminal routing within this strategically important market. The study develops solutions using Mixed Integer Linear Programming (MILP) and Clarke-Wright Savings Algorithm to minimize operational costs while incorporating Boil-Off Gas (BOG) losses as a novel constraint in maritime CVRP formulations. Through analysis of five vessel capacity configurations (125,000-180,000 m³) across eight representative Japanese terminals, this research demonstrates that 180,000 m³ vessels achieve optimal performance with 3-vessel fleet deployment and 80.2% average utilization. When operational consistency constraints require minimum 80% target utilization, the optimal configuration shifts to 170,000 m³ vessels, achieving 84.9% average utilization with significantly reduced variability (3.6% standard deviation versus 15.8% unconstrained). The research validates MILP optimality for medium-scale instances while establishing metaheuristic alternatives for larger operational deployments.
Christiansen, M., & Nygreen, B. (1998). A method for solving ship routing problems with inventory constraints. Annals of Operations Research, 81, 357-378.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91.
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.
International Energy Agency. (2024). Japan Natural Gas Security Policy -- Analysis. IEA.
Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43(4), 408-416.
Lenstra, J. K., & Rinnooy Kan, A. H. G. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221-227.
Mokhatab, S., Mak, J. Y., Valappil, J. V., & Wood, D. A. (2014). Handbook of liquefied natural gas. Gulf Professional Publishing.
Rakke, J. G., Stålhane, M., Moe, C. R., Christiansen, M., Andersson, H., Fagerholt, K., & Norstad, I. (2011). A rolling horizon heuristic for creating a liquefied natural gas annual delivery program. Transportation Research Part C: Emerging Technologies, 19(5), 896-911.
Reynolds, S., & Doleman, C. (2024). Japan's largest LNG buyers have a surplus problem. Institute for Energy Economics and Financial Analysis.
Shao, Y., Furman, K. C., Goel, V., & Hoda, S. (2014). Bound improvement for LNG inventory routing. Optimization Online.
Toth, P., & Vigo, D. (2014). Vehicle routing: problems, methods, and applications (2nd ed.). Society for Industrial and Applied Mathematics.
Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., & Rei, W. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611-624.
Zhao, H., Feng, Y., & Deng, W. (2022). Fleet deployment optimization for LNG shipping vessels considering the influence of mixed factors. Journal of Marine Science and Engineering, 10(12), 2034.
