A Combinatorial Benders' decomposition for the lock scheduling problem
A Combinatorial Benders' decomposition for the lock scheduling problem
复制标题
DOI：
10.1016/j.cor.2014.09.007
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
Jannes Verstichel;Joris Kinable;P. D. Causmaecker;G. V. Berghe
中科院分区：
文献类型：
--
作者：
Jannes Verstichel;Joris Kinable;P. D. Causmaecker;G. V. Berghe
船闸调度问题(LSP)是一个组合优化问题，对许多港口和航道运营商来说是一个真正的挑战。LSP由三个紧密相连的子问题组成：船闸调度、船舶舱室分配和船舶在舱室内的定位。这些问题应分别解释为调度问题、作业问题和布局问题。通过将前两个问题合并为主问题，并将布局问题作为子问题，得到了一个可以用组合弯曲׳方法有效求解的分解。首先解决主问题，从而将船只排序到多个船闸。接下来，对于每个锁，检查打包子问题的可行性，可能将一些组合不等式(割)返回到主问题。其结果是一种精确的LSP方法。实验是在一组实例上进行的，这些实例是根据真实世界数据生成的。结果表明，该分解方法在解质量和计算时间方面明显优于文献中提出的其他精确方法。
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 subproblems: 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 subproblem, 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 subproblem 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.