Inhalt des Dokuments
Nash Flow Computation
- © Nash Flow Computation
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. It can handle networks with spillback.
The Nash Flow Computation (short: NFC) tool, has been written in Python 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 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, together with the non-commercial LP-solver SoPlex. Furthermore, we used the modeling language ZIMPL to formulate templates for optimization problems. Last but not least, the entire GUI has been coded in PyQT 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.
We list required third party software and modules and give brief explanations if necessary as well as links to said softwar
- Python  >= 3.7
- SCIP Optimization Suite  >= 7.0
- PyQT  5
- NetworkX  >= 2.4
- Numpy  >= 1.17 - Python scientific computing library including data structures and methods for arrays, matrices and vectors.
- Matplotlib  >= 3.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.
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 .