A Markov Perturbed Utility Model of Route Choice

Abstract

This paper proposes the Markov perturbed utility route choice (M-PURC) model. The model is based on a generalized entropy over link flows, constructed at each node as the perspective of a convex node perturbation with respect to the node outflow. The convex conjugate of the generalized entropy defines a surplus function whose gradient yields the optimal link flows. Lagrangian duality decomposes the surplus maximization into node-level perturbed utility problems coupled through a Bellman equation, yielding a Markovian representation of optimal behavior. The framework accommodates the recursive logit and the NGEV model as special cases. A separable specification, in which the node perturbation is the sum of link perturbations, yields a link-bylink probability-recovery formula and endogenous sparsity: dominated links receive exactly zero probability without choice set specification. We estimate the model via a Fenchel–Young loss that is convex in parameters, remains finite at corner solutions, and reduces to the recursive-logit likelihood as a special case.