Load sequencing for double-stack trains

Abstract

Les trains à empilement double sont une composante majeure du réseau de transport ferroviaire pour les conteneurs intermodaux dans certains marchés comme celui de l’Amérique du Nord. Le séquençage du chargement représente un problème opérationnel auquel font face les opérateurs de grues dans les cours de chargement lorsqu’ils ont pour tâche de placer les conteneurs sur un train. Le séquençage du chargement consiste à trouver une séquence de mouvements permettant d’extraire les conteneurs des piles dans lesquels ils sont entreposés afin de les placer sur le train. Le séquençage du chargement est interrelié avec la planification du chargement, processus dans lequel des conteneurs sont assignés à des placements spécifiques sur les wagons, afin de former un plan de chargement pour guider le séquençage. Le travail dans ce mémoire s’articule autour d’un article scientifique sur l’optimisation du séquençage du chargement pour les trains à empilement double. Dans cet article sont présentés des algorithmes basés sur la programmation dynamique, ainsi qu’une stratégie tirant avantage de plans de chargement développés afin de solutionner le séquençage pour des instances de chargement réalistes. Les résultats montrent que les heuristiques suggérées fonctionnent bien même pour des instances de grande taille. Ces dernières présentent une légère perte en qualité des solutions mais un temps d’exécution nettement inférieur aux méthodes exactes faisant défaut pour des instances de grande taille. L’analyse démontre également que l’utilisation de plans de chargement plus flexibles permet d’améliorer la qualité des solutions avec toutes les méthodes, ceci se faisant au coût d’un temps d’éxecution supérieur et l’absence d’une garantie de solution pour les heuristiques. Finalement, la planification et le séquençage simultané sont comparés avec l’approche successive utilisant les algorithmes developpés afin d’évaluer la performance relative des deux approches.

Double-stack trains are an important component of the railroad transport network for containerized cargo in specific markets such as the North American one. The load sequencing is an operational problem commonly faced in rail terminals by crane operators when tasked with loading containers on the railcars of a train. The load sequencing problem aims to find an efficient sequence of container retrievals in the storage yard, where containers are stored in piles while awaiting departure by train. Load sequencing is interrelated with load planning, the assignment of containers to specific locations on the train, forming a load plan which guides the load sequencing. The work in this thesis is centered around a scientific paper on the optimization of load sequencing for double-stack trains. This paper proposes algorithms based on dynamic programming and a strategy leveraging the load plans, and assesses their performance in terms of computing time, tractability and solution quality on realistic instance sizes. The results show that the heuristics suggested to solve the load sequencing scale well for realistic instance size, managing to achieve a significantly reduced computing time with a small loss in solution quality compared to exact methods, which would often falter for larger instances. The analysis also illustrates how using a flexible load plan in the load sequencing significantly improves solution quality at the cost of greater computing requirements and lack of guaranteed solution for the heuristics. Finally, the paper compares the performance resulting from the successive application of load planning and sequencing with jointly performing the load planning and sequencing.