Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. A graphtheoretic approach to the train marshalling problem
 Ganzha, M. ; Institute of Electrical and Electronics Engineers IEEE: Federated Conference on Computer Science and Information Systems, FedCSIS 2018. Proceedings : Poznań, Poland, September 912, 2018 Piscataway, NJ: IEEE, 2018 (Annals of Computer Science and Information Systems 15) ISBN: 9788394941956 ISBN: 9788394941963 ISBN: 9788394941970 S.227231 
 Federated Conference on Computer Science and Information Systems (FedCSIS) <2018, Poznan> 

 Englisch 
 Konferenzbeitrag 
 Fraunhofer SCAI () 
Abstract
Rearranging cars of an incoming train in a hump yard is a widely discussed topic. We focus on the train marshalling problem where the incoming cars of a train are distributed to a certain number of sorting tracks. When pulled out again to build the outgoing train, cars sharing the same destination should appear consecutively. The goal is to minimize the number of sorting tracks. We suggest a graphtheoretic approach for this NPcomplete problem. The idea is to partition an associated directed graph into what we call pseudochains of minimum length. We describe a greedytype heuristic to solve the partitioning problem which, on random instances, performs better than the known heuristics for the train marshalling problem.