Tramp ship routing and scheduling with voyage separation requirements

This presentation addresses a tramp routing and scheduling problem. Tramp ships operate like taxies by following the available demand, as opposed to liner ships that operate like busses on a fixed route network according to a published timetable. Tramp operators determine some of the demand in advance by ensuring long-term contracts. The rest of the demand comes from optional voyages found in the spot market. Routing and scheduling a tramp feet to best utilize feet capacity according to the current demand is therefore an ongoing and complicated problem. We add further complexity by incorporating voyage separation requirements that enforce a minimum time spread between some voyages. We developed a new and exact Branch-and-Price procedure for this problem. A dynamic programming algorithm generates columns, while a novel time window branching scheme is used to enforce the voyage separation requirements. Computational results show that the algorithm finds optimal solutions very quickly for the vast majority of test instances. We compare the results with two earlier published methods and show that our Branch-and-Price approach outperforms both an a priori path generation method and an Adaptive Large Neighbourhood Search heuristic.