Hyperpath Formulations of Traffic Assignment Problems

Traditional models of traffic assignment usually assume that flow is distributed along paths of the underlying network. In this presentation, we argue that several models can be enhanced by considering that the physical path travelled by a given user depends on a sequence of events (random or not) that occur at the nodes of the network, and whose outcome is only revealed once the user accesses the given node. These situations call for a more sophisticated behaviour than simply selecting an origin-destination path. Users must behave’ strategically’ and take into account the contingency that a desirable path become unavailable, from a certain node on to their destination. Such behaviour can be represented by means of hyperpaths in generalized graphs known as hypergraphs. These tools have been successfully applied in the realm of transit assignment models involving overlapping lines, where it is unrealistic to assume that all passengers will always follow a single path from their origin to their destination. We review these applications and argue that they could as well provide a good representation of user behaviour in capacitated networks, transit or not. We introduce the concept and notation pertaining to strategies and hyperpaths through the paradigm of equilibrium in transit models, pointing out applications in other domains, such as in production planning, logic programming, And-Or graphs and relational databases. Next we address novel,’ strategic’ formulations of equilibria on capacitated networks (with or without priorities) and mention the theoretical and algorithmical challenges posed by this approach.