Networks · 2010 · 79 citations · 12 references
ManagementComputer ScienceIndustrial EngineeringSchedulingTransportTransportationClassificationFreight TransportationSorting ProblemsTransport OperationsTransportation ProblemsAlgorithmic Lower BoundsComplexityLower BoundsRailway SchedulingSortingTransportation Scheduling
Abstract In this article, we study the train classification problem. Train classification basically is the process of rearranging the cars of a train in a specified order, which can be regarded as a special sorting problem. This sorting is done in a special railway installation called a classification yard, and a classification process is described by a classification schedule. In this article, we develop a novel encoding of classification schedules, which allows characterizing train classification methods simply as classes of schedules. Applying this efficient encoding, we achieve a simpler, more precise analysis of well‐known classification methods. Furthermore, we elaborate a valuable optimality condition inherent in our encoding, which we succesfully apply to obtain tight lower bounds for the length of schedules in general and to develop new classification methods. Finally, we present complexity results and algorithms to derive optimal schedules for several real‐world settings. Together, our theoretical results provide a solid foundation for improving train classification in practice. © 2010 Wiley Periodicals, Inc. NETWORKS, 2011
12
Approximating Minimum Feedback Sets and Multicuts in Directed Graphs
Guy Even, Joseph Naor, Baruch Schieber et al. · Algorithmica · 1998 · 313 citations
Elias Dahlhaus, Peter Horák, Mirka Miller et al. · Discrete Applied Mathematics · 2000 · 105 citations