TITLE: Robust Optimization with Applications in Maritime Inventory Routing

STUDENT: Chengliang Zhang

ABSTRACT:

In recent years, the importance of incorporating uncertainty into planning models for logistics and transportation systems has been widely recognized in the Operations Research (OR) and transportation science communities. Maritime transportation, as a major mode of transport in the world, is subject to a wide range of disruptions at the strategic, tactical and operational levels. This thesis is mainly concerned with the development of robustness planning strategies that can mitigate the effects of some major types of disruptions for an important class of optimization problems in the shipping industry.

The problem is motivated by an application in the design and negotiation of an Annual Delivery Plan (ADP) involving a single vendor and multiple customers in the Liquefied Natural Gas (LNG) business. The overall ADP planning activity is to develop contractual agreements of delivery plans that specify delivery dates (or time windows) and the corresponding delivery quantities over a long-term horizon. In the first part of the thesis, we study a maritime inventory routing problem with given time windows for deliveries with uncertain disruptions. We propose a Lagrangian heuristic scheme to obtain robust solutions by incorporating soft constraints, whose satisfaction can aid robustness, into the objective function with Lagrange multipliers. By simulating random disruption events, we show that the actual operational costs in case of disruptions can be significantly reduced when robust plans are implemented. In addition, the simulator enables us to determine the cost of achieving the robustness and to generate recovery solutions under various disruption events with different lead times.

In the second part, we study a more general robust maritime inventory routing problem with time windows, where the length and placement of the time windows are also decision variables. The vendor must simultaneously decide routes for all the vessels and time windows at all the customers. We formulate the problem as a two-stage stochastic mixed-integer program and propose a two-phase solution approach that considers a sample set of disruptions as well as their recovery solutions. In the first phase, we introduce two planning strategies to generate robust routes, and in the second phase, we propose a multi-scenario construction heuristic to obtain good feasible solutions. We also investigate an iterative procedure between updating the routes and re-optimizing the time windows by coupling the Lagrangian heuristic approach proposed in the first part.

Finally, we study a robust single-item uncapacitated lot-sizing problem with backlogging and random machine breakdowns. The objective is to optimize the costs of production, inventory and backlogging against the worst-case scenario. By identifying the solution characteristics of the worst-case disruptions, we show that the optimal solutions to the robust model can be characterized by a set of stationary production plans.