Generate a schematic map (“metro map”) for a given (transit) network graph using Mixed Integer Programming.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
docs fancify 🌈 Aug 11, 2018
examples update (fix) bvg example Aug 1, 2018
generate-lp add comment Aug 1, 2018
prepare-graph
revise-solution add `revise` script(s) Jul 24, 2018
.editorconfig init: boilerplate Jul 24, 2018
.gitignore init documentation (german): add problem description Aug 1, 2018
cli.js rename: bin -> cli Jul 24, 2018
index.js
license init: boilerplate Jul 24, 2018
package.json 0.1.0 Jul 24, 2018
readme.md add table of contents Jul 24, 2018

readme.md

transit-map

Generate a schematic map (“metro map”) for a given (transit) network graph using a Mixed Integer Programming approach. Part of the Generating Transit Maps project.

Work in progress, DO NOT USE THIS IN PRODUCTION! See todo.

npm version license chat on gitter

Installation & Requirements

Sadly, for now, you need a valid copy of the commercial Gurobi solver (free academic licenses) in order to run this project. In the near future however, this project will hopefully also support the open CBC solver. Stay tuned.

What you need:

Then, to install the package (for CLI usage), simply run:

npm install -g transit-map

Usage

CLI

You need a JSON graph representation of your transit network that looks like this example for the Berlin Metro (U-Bahn). You can then generate a transit map for the given graph by running:

cat graph.json | transit-map > output.svg

For further information on several CLI options/params, run:

transit-map --help

As a library

The module can be used as a JS library, documentation for this will follow.

Examples

🇩🇪 Berlin (Metro)

Input

Berlin metro network

Output

Berlin metro map

Using this input graph. Running time ≈40sec.

🇦🇹 Vienna (Metro)

Input

Vienna metro network

Output

Vienna metro map

Using this input graph. Running time ≈20sec.

🇸🇪 Stockholm (Metro)

Input

Stockholm metro network

Output

Stockholm metro map

Using this input graph. Running time ≈20sec.

🇵🇹 Lisbon (Metro)

Input

Lisbon metro network

Output

Lisbon metro map

Using this input graph. Running time ≈15sec.

🇫🇷 Nantes (Tram)

Input

Nantes metro network

Output

Nantes metro map

Using this input graph. Running time ≈15sec.

🇫🇷 Montpellier (Tram)

Input

Montpellier tram network

Output

Montpellier tram map

Using this input graph. Running time ≈20sec.

To do

Things I am still working on or someone should work on in the future, roughly in order of perceived importance:

  1. Properly document the current optimization algorithm.
  2. Add an example for full Berlin network (S-Bahn & U-Bahn), debug pre-processing with this (still fails with this network for some reason).
  3. Resolve todo comments in code.
  4. Write tests.
  5. Improve algorithm: “Smoother” edges, higher distance for parallel lines, implement station labels.
  6. Linearize objective function which would allow users to use non-commercial solvers like Cbc.
  7. Enable users to provide an old layout of the same network (or parts of it), the newly generated network should then have as few differences as possible to the older one.
  8. Further explore heuristical approaches to this problem.
  9. Write a paper. 😄

Contributing

If you found a bug or want to propose a feature, feel free to visit the issues page.