Optimization Models for Train Routing in Railyard Networks

In this document, I will explain three research topics that comprise my dissertation. The three topics presented in three separate chapters correspond to problems that arise in the railway industry, in the areas of freight train repositioning operations, routing, and scheduling. The first research subject deals with a single train routing problem within a railyard network. A railyard, sometimes called a rail hub, is a large set of connected rail tracks that function as a station for freight trains. These facilities are where the main operations of assembly and disassembly of railcars occur in order to create outbound trains, as well as load and unload railcars. A fundamental problem is to determine the shortest route for a train given its desired initial and final locations on the railyard network. This network has geometrical limitations imposed by switch nodes, as well as constraints imposed by track and train lengths. In other words, depending on train length and the geometrical structure of the railyard network, we wish to find the shortest path for a predetermined start and end location. To address this problem, we propose two related approaches that transform the railyard network into an expanded graph. A shortest path algorithm can be applied on the expanded graph to find the shortest route for a single train from an initial to a final location. Our polynomial-time algorithms are able to deal with the unique geometric structure of the railyard networks. They also account for locomotive orientation (i.e., whether the locomotive is pulling or pushing the train during each move). In addition, our approach does not restrict the route to start from a specific node, rather it allows a train to span multiple nodes. This problem and our proposed algorithms provide a foundation for the subsequent research topic. The second research topic considers the simultaneous movement of multiple trains over the railyard network. As discussed, the main operation within railyards is the assembly and disassembly of railcars to form the outbound trains. Such operations can sometimes be performed simultaneously, especially if there are multiple trains being prepared for departure in the upcoming hours. In this case, multiple movements of the railcars over different tracks of the railyard network are necessary. If these repositionings are done simultaneously, this will save time compared to performing single train routing one at a time. In presenting this problem, we propose an integer programming model and a heuristic approach for solving a routing problem involving multiple trains. The key is to generate collision-free routes while accounting for the unique structure of railyard networks. Our constructive heuristic approach works based on the assumption of having a ranked list of trains that are going to be repositioned. We relax the requirement of having to strictly prioritize trains by using a GRASP metaheuristic over the constructive heuristic we propose. Our integer programming model generates an optimal solution for many smaller-size instances of the problem. However, for practical size problems, the heuristic approach is favorable because of its fast solution time. The third topic addresses train departure scheduling over a finite time horizon. In this problem, a set of containers is given with their predetermined destinations. We consider these containers as units that must be loaded on trains to get shipped to their destinations. Therefore, units assigned to the same train should have a common destination. However, the departure time of the train depends on the units assigned to the train because each unit has a time interval within which it must be shipped. The unit's shipping interval is predetermined along with its destination. The interval of each unit is different from the other units, although they may overlap. This enables a train to load a batch of units that have the same destination and share a specific departure time that lies within each of their shipping intervals. Therefore, scheduling departures of outbound trains requires determining train departure times and destinations, along with the assignment of individual units to trains. We call this the Train Assignment Planning problem. The objective is to build an outbound train schedule that satisfies restrictions imposed by units' destinations and shipping intervals. Different performance measures such as the degree of on-time performance, as well as schedule workload balance are investigated. We provide mixed integer programming models and constructive heuristic approaches for distinct objective functions. We also propose a Lagrangian Relaxation approach for maximizing on-time performance and we use it to provide a solution upper bound and a means to evaluate the quality of the approaches. Comparing the solution time for the integer programming approach and the heuristic approach, we show that the heuristic performs much faster and provides a solution within seconds without sacrificing solution quality. The three topics briefly explained above are related as they all provide useful tools for railyard facility systems, whether it is necessary to find the shortest route, investigate the possibility of simultaneous repositioning of trains, or scheduling and assigning shipment units to outbound trains. In this document that I present as my dissertation, I present these three topics in detail