Routing container ships using Lagrangean relaxation and decomposition

International shipping is a multibillion dollar business and shipping companies may expect large benefits from improving the routing and scheduling processes of their ships. In this paper, the authors describe a container-ship routing scenario in which a shipping company provides services to a network of ports. They formulate a mathematical programming model that maximizes total profit (i.e., revenue minus operating costs) for multiple ships and determines: (a)the optimal sequence of ports of call for each ship, (b)the number of trips each ship makes in a planning horizon, and (c)the amount of cargo transported between any two ports by each ship. The model contains discrete, 0-1 and continuous variables, and nonlinear complicating constraints. The multiple container ship model is quite different from those of vehicle routing and traveling salesman problems. The authors use a decomposition method for the model as well as for the network in order to solve the problem. Several problems on 10- to 20-port networks are solved and the results presented.