A Branch-and-Price Method for a Liquefied Natural Gas Inventory Routing Problem

Grønhaug, Roar; Christiansen, Marielle; Desaulniers, Guy; Desrosiers, Jacques
August 2010
Transportation Science;Aug2010, Vol. 44 Issue 3, p400
Academic Journal
We consider a maritime inventory routing problem in the liquefied natural gas (LNG) business, called the LNG inventory routing problem (LNG-IRP). Here, an actor is responsible for the routing of the fleet of special purpose ships, and the inventories both at the liquefaction plants and the regasification terminals. Compared to many other maritime inventory routing problems, the LNG-IRP includes some complicating aspects such as (1) a constant rate of the cargo evaporates each day and is used as fuel during transportation; (2) variable production and consumption of LNG, and (3) a variable number of tanks unloaded at the regasification terminals. The problem is solved by a branch-and-price method. In the column generation approach, the master problem handles the inventory management and the port capacity constraints, while the subproblems generate the ship route columns. Different accelerating strategies are implemented. The proposed method is tested on instances inspired from real-world problems faced by a major energy company.


Related Articles

  • Simulated annealing for the vehicle routing problem with two-dimensional loading constraints. Leung, Stephen C. H.; Jiemin Zheng; Defu Zhang; Xiyue Zhou // Flexible Services & Manufacturing Journal;Jun2010, Vol. 22 Issue 1/2, p61 

    This paper addresses the capacitated vehicle routing problem with two-dimensional loading constraints (2L-CVRP). The 2L-CVRP is a combination of the two most important problems in distribution logistics, which are loading of freight into vehicles, and the successive routing of the vehicles to...

  • A Vehicle Routing Problem with Inventory in a Hybrid Uncertain Environment. Malekly, A. // International Journal of Applied Operational Research;Apr2012, Vol. 2 Issue 1, p65 

    Manufacturers, who re-supply a large number of customers, continually struggle with the question of how to formulate a replenishment strategy. The purpose of this paper is to determine the optimal set of routes for a group of vehicles in the transportation network under defined constraints --...

  • Exact Routing in Large Road Networks Using Contraction Hierarchies. Geisberger, Robert; Sanders, Peter; Schultes, Dominik; Vetter, Christian // Transportation Science;Aug2012, Vol. 46 Issue 3, p388 

    Contraction hierarchies are a simple approach for fast routing in road networks. Our algorithm calculates exact shortest paths and handles road networks of whole continents. During a preprocessing step, we exploit the inherent hierarchical structure of road networks by adding shortcut edges. A...

  • AN ANNOTATED BIBLIOGRAPHY OF COMBINED ROUTING AND LOADING PROBLEMS. IORI, Manuel; MARTELLO, Silvano // Yugoslav Journal of Operations Research;2013, Vol. 23 Issue 3, p311 

    Transportation problems involving routing and loading at the same time are currently a hot topic in combinatorial optimization. The interest of researchers and practitioners is motivated by the intrinsic difficulty of this research area, which combines two computationally hard problems, and by...

  • Information in the Traveling Salesman Problem. Barach, Gilad; Fort, Hugo; Mehlman, Yoni; Zypman, Fredy // Applied Mathematics;Aug2012, Vol. 3 Issue 8, p926 

    In the Simulated Annealing algorithm applied to the Traveling Salesman Problem, the total tour length decreases with temperature. Empirical observation shows that the tours become more structured as the temperature decreases. We quantify this fact by proposing the use of the Shannon information...

  • Adapting the traveling salesman problem to an adiabatic quantum computer. Warren, Richard // Quantum Information Processing;Apr2013, Vol. 12 Issue 4, p1781 

    We show how to guide a quantum computer to select an optimal tour for the traveling salesman. This is significant because it opens a rapid solution method for the wide range of applications of the traveling salesman problem, which include vehicle routing, job sequencing and data clustering.

  • Open Vehicle Routing Problem by Ant Colony Optimization. GurpreetSingh; Dhir, Vijay // International Journal of Advanced Computer Science & Application;2014, Vol. 5 Issue 3, p63 

    Vehicle routing problem (VRP) is real-world combinatorial optimization problem which determine the optimal route of a vehicle. Generally, to provide the efficient vehicle serving to the customer through different services by visiting the number of cities or stops, the VRP follows the Travelling...

  • Analysis of Transport Processes Management for a Romanian Food Market. NEAGU, Maria; DUDA, George // Annals of the University Dunarea de Jos of Galati: Fascicle: I, ;2012, Vol. 18 Issue 3, p21 

    This paper presents the study of optimization process for the products transportation for a Romanian food-market. The vehicle routing problem was solves using Lingo 13.0 software and an analysis was conducted in order to determine the optimal routes for the vehicles in the conditions of products...

  • An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem. Baldacci, Roberto; Mingozzi, Aristide; Roberti, Roberto; Calvo, Roberto Wolfler // Operations Research;Mar/Apr2013, Vol. 61 Issue 2, p298 

    In the two-echelon capacitated vehicle routing problem (2E-CVRP), the delivery to customers from a depot uses intermediate depots, called satellites. The 2E-CVRP involves two levels of routing problems. The first level requires a design of the routes for a vehicle fleet located at the depot to...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics