Using path decomposition enumeration to enhance route choice models

Abstract

Prediction of realistic routes is essential in travel behavior research that evaluates the effects of infrastructure design alternatives. Most proposed route choice models are based on additive link attributes. This paper investigates the decomposition of a given path in a graph into least cost components. This corresponds to finding the smallest number of intermediate destinations between which the traveler moved using the most efficient path. Minimum path decompositions are not unique and hence a single given path may result in multiple sets of intermediate destinations. This paper presents a technique to enumerate all possible decompositions of revealed paths and shows how to determine which road network nodes are preferentially used as intermediate destinations.

This paper explains the decomposition enumeration process and focuses on a new algorithm to enumerate efficiently all path decompositions. We implement the algorithms on 500k predicted bikers routes in Amsterdam.