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.