Optimization of inland shipping: A polynomial time algorithm for the single-ship single-lock optimization problem

摘要

In this paper, we explore problems and algorithms related to the optimisation of locks, as used in inland shipping. We define several optimisation problems associated with inland shipping. We prove that the problem of scheduling a lock is NP-hard if one allows multiple ships to go through in the same lock operation. The single-ship lock optimization problem can, however, be solved in polynomial time and a novel deterministic scheduling algorithm for solving this problem is presented in this paper.