Optimization in maritime inventory routing

The primary aim of this thesis is to develop effective solution techniques for large-scale maritime inventory routing problems that possess a core substructure common in many real-world applications. We use the term “large-scale” to refer to problems whose standard mixed-integer linear programming (MIP) formulations involve tens of thousands of binary decision variables and tens of thousands of constraints and require days to solve on a personal computer. Although a large body of literature already exists for problems combining vehicle routing and inventory control for road-based applications, relatively little work has been published in the realm of maritime logistics. A major contribution of this research is in the advancement of novel methods for tackling problems orders of magnitude larger than most of those considered in the literature. Coordinating the movement of massive vessels all around the globe to deliver large quantities of high value products is a challenging and important problem within the maritime transportation industry. After introducing a core maritime inventory routing model to aid decision-makers with their coordination efforts, we make three main contributions. First, we present a two-stage algorithm that exploits aggregation and decomposition to produce provably good solutions to complex instances with a 60-period (two-month) planning horizon. Not only is our solution approach different from previous methods discussed in the maritime transportation literature, but computational experience shows that our approach is promising. Second, building on the recent successes of approximate dynamic programming (ADP) for road-based applications, we present an ADP procedure to quickly generate good solutions to maritime inventory routing problems with a long planning horizon of up to 365 periods. For instances with many ports (customers) and many vessels, leading MIP solvers often require hours to produce good solutions even when the planning horizon is limited to 90 periods. Our approach requires minutes. Our algorithm operates by solving many small subproblems and, in so doing, collecting and learning information about how to produce better solutions. Our final research contribution is a polyhedral study of an optimization problem that was motivated by maritime inventory routing, but is applicable to a more general class of problems. Numerous planning models within the chemical, petroleum, and process industries involve coordinating the movement of raw materials in a distribution network so that they can be blended into final products. The uncapacitated fixed-charge transportation problem with blending (FCTPwB) that we study captures a core structure encountered in many of these environments. We model the FCTPwB as a mixed-integer linear program and derive two classes of facets, both exponential in size, for the convex hull of solutions for the problem with a single consumer and show that they can be separated in polynomial time. Finally, a computational study demonstrates that these classes of facets are effective in reducing the integrality gap and solution time for more general instances of the FCTPwB.Ph.D