An exact method for the two-echelon split-delivery vehicle routing problem for liquefied natural gas delivery with the boil-off phenomenon

Xiaoyun Xiong, Jialin Han, Yunqiang Yin and T.C.E. Cheng

European Journal of Operational Research, 2025, vol. 321, issue 1, 123-146

Abstract: In this paper we investigate a two-echelon vehicle routing problem for liquefied natural gas (LNG) delivery to determine how to transport LNG from an overseas production terminal to a set of import terminals by vessels, and transport the LNG from the import terminals to a set of filling stations either by tanker trucks or bunker barges. Some important features of this problem are that part of LNG will be evaporated during delivery and split deliveries are allowed at both import terminals and filling stations, which render the problem more intractable than those considered in most of the existing two-echelon vehicle routing studies. The objective is to find the optimal first-echelon and second-echelon delivery schemes to minimize the sum of the routing cost and boil-off cost. To solve the problem, we develop a customized branch-and-price-and-cut (BPC) algorithm incorporating a specialized labeling algorithm tailored to address the issues of LNG evaporation and split deliveries in solving the challenging pricing subproblems. To speed up the solution algorithm, we introduce some heuristic pricing strategies to quickly solve the pricing subproblems, and explore the (strong) k-path inequalities and subset-row inequalities to tighten the lower bound obtained by column generation. We conduct extensive numerical studies on simulation instances and a case study of LNG delivery in region along the Yangtze river, China to verify the effectiveness of the model and proposed algorithm. The numerical results demonstrate that our algorithm significantly outperforms CPLEX and the existing BPC algorithm on related topic, confirm the superiority of our integrated two-echelon solution method over its sequential solution counterpart, and illustrate that the locations of the production terminal and import terminals are highly related to the solution performance.

Keywords: Distribution; Two-echelon transportation; Split delivery; Branch-and-cut-and-price; Column generation (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724007434
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:321:y:2025:i:1:p:123-146

DOI: 10.1016/j.ejor.2024.09.040

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().