Column generation approaches to ship scheduling with flexible cargo sizes

Geir Brønmo (geir.bronmo@iot.ntnu.no), Bjørn Nygreen (bjorn.nygreen@iot.ntnu.no) 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, http://www.asb.dk/staff/bs/lys.aspx?page=%7B803EFF10-69F7-4C0F-AEE3-F7F410E4B6F2%7D

No L-2006-07, CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies

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 (search for similar items in EconPapers)
Pages: 28 pages
Date: 2006-06-01
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.hha.dk/bs/wp/log/L_2006_07.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to www.hha.dk:80 (No such host is known. )

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhb:aarbls:2006-007

Access Statistics for this paper

More papers in CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies The Aarhus School of Business, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Helle Vinbaek Stenholt (hes@asb.dk this e-mail address is bad, please contact repec@repec.org).