An interactive heuristic for generation of paths in graphs with restriction of grades: application to the design of railway systems

The work discusses the design of a metro network through a graph-theoretical model where the vertices correspond to stations and the edges to line sections between stations. A triangulated planar support graph is the universe of possible connection alternatives between the stations and we will look for vertex-set coverings by sets of elementary paths between pairs of peripheral vertices. In a first moment we adopt a constraint of maximum degree 4 for the spanning subgraph thus obtained. The graph is valued by building and passenger demands. An interactive heuristic supported by this theoretical basis is designed to aid metro project developing and criticism. An example based on Rio de Janeiro metro is discussed.