Introducing HERMES

posted by Dan Graur, Rodrigo Bruno and Joschka Bischoff on 30 October, 2020

1. Introduction

As means of transportation evolve, as the preferences of individuals change, and as the population increases, we need to understand what changes are required to our transportation networks in order to provide optimal service. One key element towards delivering this is large-scale simulation. However, the state-of-the-art tools we currently have at hand are unable to support such magnitudes (e.g. country-wide level such as Switzerland). For instance, using its default simulator, QSim, MATSim is expected to require roughly 116 days to carry out 1000 simulation iterations of Switzerland at 100% population. It is obvious that such execution times make large-scale scenarios impractical.

After analyzing MATSim, we have found that the main scalability inhibitors are the data structures and algorithms in the simulation core, QSim. To this extent, we propose a novel, high-performance, scalable simulator for MATSim called Hermes.

2. Hermes Overview

Hermes is a high-performance simulator which supports large-scale scenarios and repetitive what-if runs. It focuses on efficiently implementing the concepts behind transport simulation, and functions as an alternative to QSim. Figure 1 shows the new MATSim architecture with Hermes as its simulation core.

Fig. 1: MATSim Architecture with the Hermes Simulator

Hermes is built around one critical observation: in large-scale simulations, at every iteration, events are concentrated around a sparse set of areas in the graph. Hence, traversing the entire graph is wasteful. Hermes capitalizes on this point by exploiting an event-driven execution, where only the events taking place at a specific iteration are processed. This is in opposition to QSim's approach of processing each link and agent at each iteration.

Hermes also introduces additional improvements, such as: optimized code paths for common events, optimized data structures, pre-computation and memoization, as well as efficient code which makes extensive use of primitive types. These features, together with the event-driven approach, enable Hermes to deliver efficient, large-scale simulations.

It should be noted that Hermes does not compromise on extensibility, and allows users to plug in experimental events into the simulation. To the best of our knowledge, this is the only extension in the MATSim ecosystem which is both scalable and abides to the ecosystem's principles of extensibility and community-driven development.

Quite notably, Hermes does not provide all the functionality that QSim has to offer, but focuses on the core, "standard" functionality. Different vehicle types and both private and public transport can be simulated in a similar way as with QSim. Special extensions such as dynamic vehicle routing, within-day replanning or traffic signals are however not supported. Nevertheless, a dual use of Hermes and QSim is in theory possible, where Hermes is used for some iterations and Qsim for others.

3. Hermes Architecture and Workflow

Hermes' architecture consists of three main stages: Scenario Importer, Simulation Core, and Event Manager, as shown in Figure 1. We further describe what each stage does.

Scenario Setup: Prepares the data structures used by the Simulation Core. These structures refer to the links that form the network, the agents that participate in the simulation, as well as other helpful data structures. Considering that an event defines what, when and how something happens in the network, and that we can readily extract the what and how from an agent plan, it follows that we can pre-compute all the events during the simulation by initially omitting the when. This latter piece of information is added at simulation time.

Simulation Core: Performs the simulation itself using an event-driven algorithm. In its implementation, this stage employs a set of optimizations, which refer to: Avoiding Objectification, Avoiding Non-Contiguous Data Structures, Avoiding Polymorphism, and striving for Compact Hot-Code Paths.

Event Processor: Processes events generated by the Simulation Core, and converts them to MATSim compatible structures.

4. Results

Hermes has already been adopted by the SBB where it is being used in production. Here, we perform a simulation of Switzerland with 10% population (roughly 1M agents and 1.5M network links) over 301 iterations. We use a machine equipped with a Xeon Platinum 8168 (48 cores in total) at 2.70GHz, and 768GBs of RAM. Hermes uses 48 threads, while QSim uses 18 threads during simulation. Both simulations only use 130GBs of RAM.

The average iteration time in Hermes is 3:33 minutes, while in QSim it is 8:45 minutes. This is a 2.5x speedup. The total simulation runtime is reduced by 40% , and is now dominated by MATSim's Replanning Step.

Due to the differences in Hermes' and QSim's logic, the simulation results are not identical. These discrepancies are however very slight, and do not affect the overall quality of the results. For instance, transfer times and road congestion times in Hermes are marginally higher. Transportation mode distributions can also be subject to small differences, such as lower car usage in Hermes (around 1%), as can be seen in Figure 2.

5. Usage

Hermes is part of the current MATSim snapshots and weekly releases and can be used out of the box by setting the "mobsim" parameter in the Controller Config-Group to "hermes".

There is an additional Hermes Config Group, where some parameters should be set, many of them are similar to those in QSim:

<module name="hermes" >

<!– Simulation End Time –>

<param name="endTime" value="32:00:00" />

<param name="flowCapacityFactor" value="0.25" />

<param name="mainMode" value="car" />

<param name="storageCapacityFactor" value="0.25" />

<!– time in seconds. Time after which the frontmost vehicle on a link is called `stuck' if it does not move. Set to Integer.MAX_VALUE to disable this behavior –>

<param name="stuckTime" value="30" />

<!– treats PT as deterministic. PT vehicles will run with a steady speed according to their timetable. –>

<param name="useDeterministicPt" value="true" />

</module>

In addition to that, the event handling needs to be set to oneThreadPerHandler

<module name="parallelEventHandling" >

<param name="oneThreadPerHandler" value="true" />

</module>

Note: The FlowCapacityFactor setting should be set in accordance with the population sample size. The storageCapacityFactor might be set a little bit higher for small sample sizes (=< 10%).

Hermes supports different vehicle types and PCUs. If PT is used on a congested network, the PCU equivalent for the transit vehicles should be defined in accordance with the sample size (i.e., for a 10% sample, a PT vehicle's PCUe should be set to 10%). For all other vehicles, an automatic scaling is performed.

6. Conclusions

We have presented Hermes, a novel simulator for MATSim, which delivers high-performance and scalability using an event-driven design and numerous optimizations to the code and the data structures. We have shown Hermes' improved efficiency over QSim through production-level results. Moreover, Hermes is currently being successfully used in production by the SBB to simulate transportation networks within Switzerland. The simulator is currently integrated in MATSim, and is available via the latest weekly releases of MATSim 13 (https://matsim.org/downloads/).

7. Acknowledgements

We would like to thank the SBB for their generous support towards funding the project as part of the Mobility Initiative, and for the many fruitful discussions we have had the SBB Planning team. We would also like to thank Dr. Michel Müller (ETH), Dr. Marcel Rieser (SBB/Simunto), Prof. Gustavo Alonso (ETH), Prof. Torsten Hoefler (ETH) and Wolfgang Scherr (SBB) for their many contributions and ideas on this project.