A generalized partite-graph method for transportation data association. (March 2017)

• Record Type: Journal Article
• Authors: Anderson, Paul; Farooq, Bilal
• Is Part Of: Transportation research. Volume 76(2017)
• Page Start: 150
• Page End: 169
• Publication Date: 2017-03
• Subjects: Associations generation -- k-partite graphs -- Vehicle trajectory -- Population synthesis; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2017.01.004
• Languages: English
• ISSNs: 0968-090X

Abstract

Highlights: Propose a generalized k-partite method for transportation data association problems. Show that k-partite graphs yield better results than pair-wise matching. Show that groups of agents can be linked in a single step. Show that proposed k-partite method has sufficient performance for practical use. Abstract: There are many problems in transportation which involve reconstructing the associations between different entities. For example, data points related to a vehicle from different sensors could be matched to reconstruct the trajectories of vehicles. Or, in population synthesis for microsimulation, lists of persons, dwellings, and vehicles could be generated individually from source data and then matched into synthetic households. There are numerous other examples. The unifying theme is a desire to construct realistic unit-level associations from aggregate or anonymized data. The problem demands a method that is behaviorally consistent and operationally efficient to handle large datasets. We adapt concepts from graph theory to formulate this class of problems as a k-partite graph. This approach is generic and can incorporate expectations of behavior in the form of edge weights. A Dijkstra algorithm based solution is proposed for a subset of k-partite graphs which permits a direct comparison with pair-wise matching and applied to a case study of bicycle tracklets. We then propose an iterative improvement algorithm as a generic method and apply it to a complete k-partite graph in a population synthesis case study. The first case study shows that the k-partite algorithm outperforms the previously used pair-wise matching algorithms. The second case study demonstrates the generality of the proposed algorithm to all k-partite graphs and shows that the generic method is fast and scalable to large problems. As a whole, this paper aims to show that k-partite methods are behaviorally consistent, efficient, and potentially applicable to a wide variety of transportation data association problems.