UN ALGORITMO BASADO EN HEURISTICAS PARA LA RESOLUCIÓN DEL PROBLEMA DE MANEJO DE TRENES EN FERROCARRILES

Abstract

The rolling stock unit management on railway sites problem was proposed by ROADEF group in cooperation with the Association of European Operational Research Societies EURO and Google in their challenge of the year 2014. This problem consists in managing the use of resources of trains between arrivals and departures, with instances that are similar to reality. This research presents the de¿nition of the problem with all its components, its constraints, and the objective function. Then, investigations about similar problems, like train scheduling problem, are presented and how competitors have addressed the problem,where they divide it into two subproblems: DepartureMatchingProblemandRoutingProblem. From this information, we propose an algorithm based on heuristics to solve the ¿rst of the subproblems, and we evaluate its performance in different experiments with random instances and instances of the challenge.El problema de manejo de trenes en ferrocarriles fue propuesto por el grupo ROADEF en cooperación con la Sociedad Europea de Investigación de Operaciones EURO y Google en su desafío del año 2014. Este problema consiste en gestionar el uso de recursos de trenes entre sus llegadas y salidas,con instancias que se asemejan a la realidad.En esta memoria se presenta la de¿nición del problema entregada en el desafío,especi¿cando todas las componentes del problema, sus restricciones y función objetivo.Luego se presentan los estudios realizados hasta el momento sobre problemas relacionados con la gestión de trenes y cómo los competidores del desafío abordaron el problema,donde lo dividen en dos subproblemas: Departure Matching Problem y Routing Problem. A partir de esta información se propone un algoritmo basado en heurísticas que resuelva el primer subproblema mencionado,para luego evaluar su desempeño por medio de diferentes experimentos con instancias aleatorias e instancias de la competencia.