Scandinavian Working Papers in Business Administration
CORAL Working Papers,
University of Aarhus, Aarhus School of Business, Department of Business Studies
No L-2006-07: Column generation approaches to ship scheduling with flexible cargo sizes
Geir Brønmo (), Bjørn Nygreen () and Jens Lysgaard
Additional contact information
Geir Brønmo: Section of Managerial Economics and Operations Research, Postal: Norwegian University of Science and Technology, 7491 Trondheim, Norway
Bjørn Nygreen: Section of Managerial Economics and Operations Research, Postal: Norwegian University of Science and Technology, 7491 Trondheim, Norway
Jens Lysgaard: Department of Accounting, Aarhus School of Business, Postal: The Aarhus School of Business, Fuglesangs Allé 4, 8210 Aarhus V, Denmark
Abstract: 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
Keywords: Transportation; integer programming; dynamic programming
28 pages, June 1, 2006
Full text files
L_2006_07.pdf
- University of Aarhus, Aarhus School of Business, Department of Business Studies
- Home page for this series
Questions (including download problems) about the papers in this series should be directed to Helle Vinbaek Stenholt ()
Report other problems with accessing this service to Sune Karlsson ().
RePEc:hhb:aarbls:2006-007This page generated on 2024-09-13 22:18:12.