The lockmaster's problem

S. Coene, F.C.R. Spieksma

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)

Samenvatting

Inland waterways form a natural network that is an existing, congestion free infrastructure with capacity for more traffic. The European commission promotes the transportation of goods by ship as it is a reliable, efficient and environmental friendly way of transport. A bottleneck for transportation over water are the locks that manage the water level. The lockmaster's problem concerns the optimal strategy for operating such a lock. In the lockmaster's problem we are given a lock, a set of ships coming from downstream that want to go upstream, and another set of ships coming from upstream that want to go downstream. We are given the arrival times of the ships and a constant lockage time; the goal is to minimize total waiting time of the ships. In this paper a dynamic programming algorithm (DP) is proposed that solves the lockmaster's problem in polynomial time. We extend this DP to different generalizations that consider weights, water usage, capacity, and (a fixed number of) multiple chambers. Finally, we prove that the problem becomes strongly NP-hard when the number of chambers is part of the input.

Originele taal-2Engels
Titel11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2011
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's27-37
Aantal pagina's11
Volume20
ISBN van geprinte versie978-3-939897-33-0
DOI's
StatusGepubliceerd - 2011
Extern gepubliceerdJa
Evenement11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2011) - Saarbrucken, Duitsland
Duur: 8 sep 20118 sep 2011
Congresnummer: 11
http://atmos2011.mpi-inf.mpg.de/

Publicatie series

NaamOpenAccess Series in Informatics (OASIcs)
Volume20

Congres

Congres11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2011)
Verkorte titelATMOS 2011
LandDuitsland
StadSaarbrucken
Periode8/09/118/09/11
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'The lockmaster's problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit