 Integer Programming Methods for a Vessel Scheduling ProblemLeif H. Appelgren
Transportation Science, 1971, vol. 5, issue 1, 64-78 Abstract: In a previous paper, Appelgren (Appelgren, L. 1969. A column generation algorithm for a ship scheduling problem. Trans. Sci. 3 53--68.), a decomposition algorithm for a class of vessel scheduling problems was presented. In some problems, the algorithm gives fractional solutions that cannot be interpreted as feasible schedules. This paper treats two integer programming methods that can be used to resolve these cases. The cutting plane method that was first tested was abandoned because it was not able to solve all the test problems. The second method is a branch-and-bound algorithm, where the branching is performed on one of the “essential” fractional variables and where the bounds are obtained by the decomposition algorithm. All fractional problems that have been found by simulation or in regular use of the algorithm have been solved, mostly with one branching only. There are fundamental difficulties in combining these integer programming methods with the Dantzig-Wolfe decomposition, since the constraints generated in the master program have to be taken into account in the solution of the subprograms. The success in this case is due to the simple structure of the master LP problem. Date: 1971 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:5:y:1971:i:1:p:64-78 Access Statistics for this article More articles in Transportation Science from INFORMS Contact information at EDIRC. |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.