A Lagrangian lower bound for the container transshipment problem at a railway hub for a fast branch-and-bound algorithm

Abstract

In this paper, we consider the container transshipment problem at a railway hub. A simple lower bound known for this problem will be improved by a new Lagrangian relaxation lower bound. Computational tests show that this lower bound outperforms the simple one and decreases substantially the run time of the branch-and-bound algorithm.

Keywords:

• lower bounds
• linear programming
• branch-and-bound algorithm
• Lagrangian relaxation

Acknowledgements

This work has been supported by the German Science Foundation (DFG) through the grant ‘Optimierung der Containerabfertigung in Umschlagbahnhöfen’ (BO 3148/1-1 and PE 514/16-1).

Maksim Barketau is partially supported with Φ10ΦΠ−001 project of Belorussian Fund of Fundamental Research and Φ10M−071 project of Belorussian Fund of Fundamental Research.