Aarhus University Seal / Aarhus Universitets segl

Column generation approaches to ship scheduling with flexible cargo sizes

Research output: Working paperResearch

  • Department of Business Studies
  • CORAL - Centre for Operations Research Applications in Logistics
We present a Dantzig-Wolfe procedure for the ship scheduling problem with flexible cargo sizes. This problem is similar to the well-known pickup and delivery problem with time windows, but the cargo sizes are defined by an interval instead of a fixed value. We show that the introduction of flexible cargo sizes to the column generation framework is not straightforward, and we handle the flexible cargo sizes heuristically when solving the subproblems. This leads to convergence issues in the branch-and-price search tree, and the optimal solution cannot be guaranteed. Hence we have introduced a method that generates an upper bound on the optimal objective. We have compared our method with an a priori column generation approach, and our computational experiments on real world cases show that the Dantzig-Wolfe approach is faster than the a priori generation of columns, and we are able to deal with larger or more loosely constrained instances. By using the techniques introduced in this paper, a more extensive set of real world cases can be solved either to optimality or within a small deviation from optimality.
Original languageEnglish
PublisherAarhus School of Business, Department of Business Studies
ISBN (Electronic)87-7882-132-0
Publication statusPublished - 2006

    Research areas

  • Transportation, integer programming, dynamic programming.

See relations at Aarhus University Citationformats

ID: 32346267