Perturbed utility Markovian traffic equilibrium: theory and computation

Abstract

This paper proposes the perturbed utility Markovian equilibrium (PUME) framework for stochastic traffic assignment. The demand side, the perturbed utility Markovian choice model (PUMCM), characterizes route choice as an undiscounted infinite-horizon Markov decision process in which a convex surplus function at each state replaces the additive random utility shock; its gradient yields link choice probabilities on the full simplex, and corner solutions arise endogenously at dominated actions. Fenchel–Young duality links the state-wise surplus on the policy space to a flow-space perturbation, and strict stage negativity ensures every Bellman-consistent policy proper, so policy evaluation is well posed without the need for discounting. The framework accommodates recursive logit and network GEV as special cases, and extends to α-entmax and sparsemax, which assign zero probability to dominated actions. The equilibrium is formulated as a monotone variational inequality (VI) in cost space, which accommodates asymmetric supply and reduces to the classical Beckmann-type characterization when the supply is integrable. A modified policy iteration solves the inner network loading with a global convergence guarantee; and an accelerated VI algorithm solves the outer equilibrium problem. Numerical experiments illustrate endogenous corner solutions and approximately linear runtime scaling in network size.