Multistage route optimization with vessel repositioning and cargo flows under uncertainty

Abstract

This thesis focuses on one critical issue faced in the operations management of ship fleets under uncertainty in maritime transportation by using quantitative decision methodologies. Vessels operated by a shipping company are located around the world to transport goods. The liner company, therefore, needs to regularly adjust its shipping network by repositioning vessels to respond to uncertain container transport demand. During the adjustment, vessels are added, removed or moved between services in the shipping network. Few studies investigate a multistage route optimization problem with vessel repositioning and cargo flows under uncertainty. Hence, this thesis formulates an MILP model capturing mentioned characteristics to decide the number of vessels of different types moved to each route, the number of vessels of different types chartered in and out, the vessel type selected for each round trip on each route, and the numbers of accepted, delayed, and shipped containers of all O-D pairs in each time period throughout the planning horizon. This thesis proves NP-completeness of the decision version of this problem, and subsequently designs an improved exact algorithm based on Benders decomposition for this problem. Several types of acceleration strategies including the Pareto-optimal cut, upper bound tightening inequalities, warm start, and local branching algorithm, are applied to enhance the performance of the designed approach. Numerous computational instances are conducted to verify that the designed algorithm significantly outperforms the CPLEX method and the classical Benders decomposition with callback functions in solving the problem. Besides, some managerial insights are concluded to guide the operations of vessels under uncertainty for the liner company based on the sensitive analysis.