Logic-based Benders decomposition for gantry crane scheduling with transferring position constraints in a rail–road container terminal

ABSTRACT

Rail–road container terminals can be seen as buffers within a large logistics network encompassing hinterland distribution systems. They are used as temporary storage points for containers such that unloading operations from a train and loading operations onto a truck need not be synchronized. Container transferring operation implemented by gantry cranes is one of the most important issues to ensure efficient logistics. To enable efficient container transfer, this article considers the special features of container movement, and integrates the starting position and the ending position of container movement into the gantry crane scheduling problem. In order to solve the proposed problem, this article develops two models: first using mixed integer programming, and secondly using constraint programming (CP). Since the problem is computationally intractable for realistic sizes, this article also proposes a logic-based Benders decomposition (LBBD) methodology to solve it. This method exploits a natural decomposition of the studied problem into a relaxed master problem (RMP) solved by mixed integer programming (MIP), and a series of sub-problems, solved separately by MIP and CP. Computational experiments are performed on generated instances, the structures of which are designed to follow the practical application. The computational results show that the CP approach is better suited to solve the proposed problem with small-sized and medium-sized instances compared with MIP and LBBD. In addition, the LBBD framework is far superior to mixed integer programming on all but a few small instances, and it is highly effective in finding good-quality solutions for larger cases with up to 100 tasks within a reasonable runtime. Moreover, the results find that LBBD using constraint programming to solve the sub-problems usually outperforms LBBD with mixed integer programming on the instances tested.

Keywords:

• Rail–road container terminal
• crane scheduling
• Benders decomposition
• constraint programming
• mixed integer programming

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by the National Natural Science Foundation of China [No. 51405403]; the Fundamental Research Funds for the Central Universities [No. 2682018CX09]; China Postdoctoral Science Foundation funded project [No. 2015M582566].