Multi-constraint partitioning

In the ``gotthard'' scenario, 50000 travelers, starting at random locations all over Switzerland, attempt to travel to Lugano as quickly as possible. The scenario is meant for testing the route assignment logic with respect to route equilibration in a single destination scenario. It was also used as a test scenario for parallel computing.

Partitioning in our case refers to the nodes of the road network. Since the work of the queue simulation mostly consists of computing the intersection dynamics, computational load is essentially proportional to the number of intersections. Standard partitioning thus attempts to spread the network nodes equally across all CPUs while maintaining contiguous domains.

Multi-constraint partitioning means that there is more than one weight per node. In our case, this can be best understood by assuming that those weights refer to different time slices. For example, in the gotthard scenario, there is a lot of traffic all over Switzerland initially, but near the end of the simulation, only some nodes process traffic while all others are empty.

The question is if under such circumstances the network can be partitioned so that the load is equally balanced at all times. A counter-example would be a distribution where one CPU has nodes with a lot of traffic initially but no traffic later, and another CPU has no traffic initially, but a lot of traffic later. That simulation would run faster if both CPUs traded approximately half of their nodes: Then both CPUs would always be busy on about half of their nodes. This is exactly what multi-constraint partitioning attempts to achieve.

Abbildung 5: (a) RTR and (b) Speedup curves of a 6-hour run of Gotthard scenario without and with multi-constraint (''MC'') domain decomposition approach.

[] []