Bulk ship routing and scheduling under uncertainty

Abstract

Bulk shipping contributes to nearly half of the global seaborne transportation volume. In bulk shipping, ships are operated in two different modes: industrial shipping and tramp shipping. In industrial shipping, an industrial corporation owns or controls a fleet of bulk ships and transports cargoes to satisfy its own demand (i.e., the corporation acts as the shipper and the carrier at the same time). In tramp shipping, shipping companies act as carriers that transport cargoes from one port to another by following the orders from the customers (shippers). Seaborne transportation is known for its uncertainties which greatly impact the operations in both industrial and tramp bulk shipping. This thesis focuses on two operations management problems in bulk shipping under uncertainties. Particularly, we consider a bulk ship scheduling problem in industrial shipping in Chapter 2 and a bulk ship routing problem in tramp shipping in Chapter 3. Chapter 2 explores a ship scheduling problem for an industrial corporation that manages a fleet of bulk ships under stochastic environments. The considered problem is an integration of three interconnected sub-problems from different planning levels: the strategic fleet sizing and mix problem, the tactical voyage planning problem, and the operational stochastic backhaul cargo canvassing problem. To obtain the optimal solution of the problem, this chapter provides a two-step algorithmic scheme. In the first step, the stochastic backhaul cargo canvassing problem is solved by a dynamic programming (DP) algorithm, leading to optimal canvassing strategies for all feasible voyages of all ships. In the second step, a mixed-integer programming (MIP) model that jointly solves the fleet sizing and mix problem and the voyage planning problem is formulated using the results from the first step. To efficiently solve the proposed MIP model, this chapter develops a tailored Benders decomposition method. Finally, extensive numerical experiments are conducted to demonstrate the applicability and efficiency of the proposed models and solution methods for practical instances. Chapter 3 presents a robust optimization algorithm to solve a ship routing problem faced by bulk tramp shipping companies. In this problem, the cargo selection behaviors in the settings where a group of cargoes should be treated as a batch are considered. In view of the uncertainties observed in maritime transportation, we formulate the problem in such a way that the solutions are robust against variations in voyage costs. We first provide compact mixed integer linear programming formulations for the problem and then convert them into a strengthened set covering model. A tailored branch-and-price-and-cut algorithm is developed to solve the set covering model. The algorithm is enhanced by a multi-cut generation technique aimed at tightening the lower bounds and a primal heuristic aimed at finding high-quality upper bounds. Extensive computational results show that our algorithm yields optimal or near-optimal solutions to realistic instances within short computing times and that the enhancement techniques significantly improve the efficiency of the algorithm.