A transportation model, its development and application to a ship scheduling problem

This paper presents a model for the timetabling of either commercial aircraft or cargo ships. Lagrangian Relaxation is applied to the model to produce a set containing the optimal craft and cargo schedule. A novel refinement of Benders’ Decomposition is then used to choose the optimum schedule from within the set, by avoiding solving an integer LP at each iteration. The method manages to break a difficult integer programming problem into two relatively simple steps which parallel the steps typically taken by schedulers, while maintaining optimality. Results for a multi-vessel multi-product ship scheduling problem are included.