• English
  • Deutsch
  • Log In
    Password Login
    Research Outputs
    Fundings & Projects
    Researchers
    Institutes
    Statistics
Repository logo
Fraunhofer-Gesellschaft
  1. Home
  2. Fraunhofer-Gesellschaft
  3. Konferenzschrift
  4. A graph-theoretic approach to the train marshalling problem
 
  • Details
  • Full
Options
2018
Conference Paper
Title

A graph-theoretic approach to the train marshalling problem

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 graph-theoretic approach for this NP-complete problem. The idea is to partition an associated directed graph into what we call pseudochains of minimum length. We describe a greedy-type heuristic to solve the partitioning problem which, on random instances, performs better than the known heuristics for the train marshalling problem.
Author(s)
Dörpinghaus, J.
Schrader, R.
Mainwork
Federated Conference on Computer Science and Information Systems, FedCSIS 2018. Proceedings  
Conference
Federated Conference on Computer Science and Information Systems (FedCSIS) 2018  
Open Access
DOI
10.15439/2018F26
Language
English
Fraunhofer-Institut für Algorithmen und Wissenschaftliches Rechnen SCAI  
  • Cookie settings
  • Imprint
  • Privacy policy
  • Api
  • Contact
© 2024