A General Purpose Lagrangian Heuristic Applied to the Train Loading Problem

In this paper we face the train loading problem (TLP) at seaport terminals by proposing a general purpose Lagrangian heuristic. The TLP consists of assigning import containers to the trains departing from the terminal, maximizing the utilization of trains, minimizing the distance travelled by containers from their locations in the storage area to the wagons, as well as the number of needed unproductive movements of containers (re-handles). We define a 0-1 LP formulation consisting of a network flow model complicated by additional constraints. We design a Lagrangian heuristic, which exploits a mixed integer programming (MIP) heuristic to find a first feasible solution in an acceptable time and then to improve it. We show the effectiveness of this approach by comparing the obtained results with the ones provided by a state-of-the-art MIP solver.