Title: A Combinatorial Benders' decomposition for the lock scheduling problem
Authors: Verstichel, Jannes * ×
Kinable, Joris *
De Causmaecker, Patrick
Vanden Berghe, Greet #
Issue Date: Feb-2015
Series Title: Computers & Operations Research vol:54 pages:117-128
Abstract: The Lock Scheduling Problem (LSP) is a combinatorial optimization problem that represents a real challenge for many harbours and waterway operators. The LSP consists of three strongly interconnected sub problems: scheduling lockages, assigning ships to chambers, and positioning the ships inside the chambers. These should be interpreted respectively as a scheduling, an assignment, and a packing problem. By combining the first two problems into a master problem and using the packing problem as a sub problem, a decomposition is achieved that can be solved efficiently by a Combinatorial Benders' approach. The master problem is solved first, thereby sequencing the ships into a number of lockages. Next, for each lockage, a packing sub problem is checked for feasibility, possibly returning a number of combinatorial inequalities (cuts) to the master problem.
The result is an exact approach to the LSP. Experiments are conducted on a set of instances that were generated in correspondence with real world data. The results indicate that the decomposition approach significantly outperforms other exact approaches presented in the literature, in terms of solution quality and computation time.
ISSN: 0305-0548
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Computer Science Technology TC, Technology Campuses Ghent and Aalst
Technologiecluster Computerwetenschappen
Computer Science, Campus Kulak Kortrijk
* (joint) first author
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
lockscheduling_decompositon.pdf Published 464KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science