direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Nash Flow Computation

Lupe

This tool can compute thin flows with resetting and consequently Nash flows over time and is embedded in a graphical user-interface framework. This allows not only quick and easy creation of networks but also the analysis of, e.g., earliest arrival time functions, thin flows with resetting, and inflow functions in a dynamic equilibrium.

The Nash Flow Computation (short: NFC) tool, has been written in Python 2.7.12 and consists of over 4000 lines of code. It has been designed to work on Linux-based operating systems but can be easily extended to work on other operating systems as Windows and macOS, given that they allow the installation of the third-party software and modules needed for NFC to run. NetworkX 2.1 provides the necessary data structures and algorithms for directed graphs. The computation of Nash flows over time heavily relies on the solving of mixed 0-1 linear programs. 

NFC currently supports only one solver, namely SCIP 4.0.0, together with the non-commercial LP-solver SoPlex 3.0.0. Furthermore, we used the modeling language ZIMPL to formulate templates for optimization problems. Last but not least, the entire GUI has been coded in PyQT4 and designed using QT-Designer.

A lot of effort has been put in the development of an adequate class structure, allowing the creation of directed graphs, while using the features of Matplotlib to display the graphs in a visually appealing manner. The graph creation canvas of NFC makes it possible to easily add and remove nodes and edges as well as to assign capacity or transit-time values. Furthermore, zooming in and out as well as moving the display area are included features. Although NetworkX provides methods to plot directed graphs using Matplotlib, these are not sufficient in order to display edges with queues. These methods have been re-designed from scratch.

Requirements

We list required third party software and modules and give brief explanations if necessary as well as links to said software.

  • Python 2.7.12
  • SCIP Optimization Suite - Includes:

    • SCIP 4.0.0
    • SoPlex 3.0.0
    • ZIMPL 3.3.4

  • PyQT 4.12.1
  • NetworkX 2.1
  • Numpy 1.11 - Python scientific computing library including data structures and methods for arrays, matrices and vectors.
  • Matplotlib 1.5.1 - Python plotting library. Used to display the networks and to handle most of the user input as well as the animation of Nash flows over time.

 

Download

The current version is available for download as a compressed zip-archive.

Nash Flow Computation (18.07.18)

Nash Flow Cmputation Manual (18.07.18)

Disclamer

This software is part of the Dynamic Models and Algorithms for Equilibria in Traffic Networks (MI12) project carried out in the framework of Matheon supported by Einstein Foundation Berlin.

Zusatzinformationen / Extras

Direktzugang:

Schnellnavigation zur Seite über Nummerneingabe