Canonic Route Splitting

Abstract

There are multiple ways to split a path in a directed graph into largest sub-paths of minimal cost. All possible splits constitute path partitions of the same size. By calculating two specific path splittings, it is possible to identify subsets of the vertices (splitVer- texSets) that can be used to generate every possible path splitting by taking one vertex from each such subset and connecting the resulting vertices by a least cost path. This is interesting in transportation science when investigating the hypothesis that people build up their route from least cost components. The splitVertexSets can be easily and efficiently derived from big data (GPS recordings). This allows for statistical analysis of structural route characteristics which in turn can support constrained enumera- tion methods for route choice set building. Furthermore, the boundary vertices separating consecutive route parts, are way points having a particular meaning to their user which constitutes relevant information to the transportation analyst.