부산대학교 도서관

This paper considers the simultaneous movement of multiple trains within a railyard network, where each of a number of trains has an origin location and destination location on the network. We wish to minimize the total time required to move all trains from their origin to destination locations, while ensuring that at most one train occupies each track segment at any given time. We propose an integer programming model that is able to solve small problem instances exactly, as well as a heuristic solution method for solving problems of realistic size in acceptable computing time. Our constructive heuristic approach uses a ranked priority list of trains that require repositioning, and sequentially determines a route on the network for each train in priority order. We then relax the strict priority ordering rule by applying a Greedy Randomized Adaptive Search Procedure (GRASP) based on the underlying constructive heuristic. As we demonstrate via a set of computational tests, this heuristic approach is able to find good quality feasible solutions in fast computing time, drastically reducing the labor hours typically dedicated to routinely solving this problem in practice.