Meta-heurística de otimização por colônia de formigas para otimizar manobras ferroviárias em pátios de classificação

Abstract

Rail freight transportation relies heavily on the efficiency of classification yards, where trains are broken down and groups of wagons are rearranged to form the new trains that will leave the yard. The repositioning of these groups is carried out through maneuvers, and planning the maneuver sequence that forms all trains with the least operational effort constitutes a highly complex combinatorial optimization problem. This work addresses the Train Formation Problem in Railway Classification Yards, whose goal is to minimize the number of maneuvers required to place each wagon block on the line, in the order, and at the position demanded by its outbound train, subject to accessibility, forbidden zones, physical connections between lines, and time-window constraints. A greedy-stochastic

constructive heuristic is proposed which, at each step, generates candidate maneuvers for the accessible blocks and selects one through a simple random draw among the lowest-

cost candidates, where the cost combines proximity to the departure line, boarding order, urgency, and a repetition penalty. The heuristic is guided by an Ant Colony Optimization metaheuristic (elitist Ant System), in which pheromone reinforces the (block, destination line) decisions associated with the best solutions found. Computational experiments on thirteen instances (four synthetic and nine real-world) show that the proposed approach yields valid solutions for all of them, highlighting the method's potential for the problem considered.