Abstract

In several frameworks for travel modeling, travel prediction, route choice, traffic control, and optimization, path-related data structures become a key element that determine the efficacy or even the plausibility of analysis or modeling. Such frameworks have always been developed so as to avoid the well-known combinatorial explosion that results from sub-paths within paths, and the associated computational difficulties. This paper attempts to provide an alternative and explain a way to use certain concepts from string storage data structures to network path and sub-path storage which could potentially be applicable to travel networks of reasonable sizes. Though it alludes to other applications for the data structures, the paper does not enumerate all such possibilities, and focuses on describing it in the context of a specific application which is on predicting individual travel from trip diary databases, where correlation in observed behavior normally exists among sub-path variable level. The motivation for this research is a recent project called Persistent Traffic Cookie (PTC) system that collect individual trip diaries using wireless techniques, which are time stamped sequence data. The identified frequently-visited sub-sequences can also be used as sub-path components in a route choice model to make it more behaviorally sound. The proposed data structures are based on the suffix tree and the suffix array for efficiently storing and querying sequence data. A numerical example is used to illustrate the algorithms and some preliminary results are presented.