A Two-Model Solution Approach for the Monthly Coal Train Reservations Planning Problem

The monthly coal train reservations planning problem arises in the unit train business of North American railroads. It involves a variety of operational and tactical decisions such as train formation, routing, and scheduling. As a result of the extensive scope of coal transportation in the United States, models for this problem grow quickly to a size unmanageable by state-of-the-art optimization software. Therefore, we propose a two-model heuristic solution methodology that is time-efficient and produces good quality solutions. The first model is developed under simplifying assumptions and yields an upper bound on the number of reservations to be accepted during the month. It also assigns car consists to reservations based on aggregate supply and demand of resources. This model also provides a tentative schedule for trains, and sets precedence relations between reservations. These being given, a second procedure is used to construct a detailed monthly schedule through the solution of network flow models and through the solution of a job-shop scheduling problem. The resulting solution is then improved through a large-scale neighborhood search. We evaluate our approach computationally, both on randomly generated and practical instances. We show numerically that our approach outperforms current practice.