Container vessel scheduling with bi-directional flows

We consider a strongly NP-hard container vessel scheduling problem with bi-directional flows. We show that a special case of it is solvable as a linear program. This property is then used to design a heuristic for the general case.