A novel approach for the structural comparison of origin-destination matrices: Levenshtein distance. (February 2020)

• Record Type: Journal Article
• Authors: Behara, Krishna N.S.; Bhaskar, Ashish; Chung, Edward
• Is Part Of: Transportation research. Volume 111(2020)
• Page Start: 513
• Page End: 530
• Publication Date: 2020-02
• Subjects: OD matrix structure -- Structural comparison -- Levenshtein distance -- Destination choices -- Trip distribution -- Bluetooth OD matrices -- Brisbane; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2020.01.005
• Languages: English
• ISSNs: 0968-090X

Abstract

Highlights: OD matrix 'structure' is defined as its skeletal framework. The OD flows corresponding to the skeleton is termed as mass. A holistic comparison of OD matrices should include its structure and mass. Normalised Levenshtein distance for OD matrices (NLOD) is proposed for the structural comparison. NLOD satisfies the mathematical properties of a distance measure. Abstract: Origin-Destination (OD) matrix is a tableau of travel demand distributed between different zonal pairs. Essentially, OD matrix provides two types of information: (a) the individual cell value represents travel demand between a specific OD pair; and (b) group of OD pairs provides insights into structural information in terms of distribution pattern of OD flows. Comparison of OD matrices should account both types of information. Limited studies in the past developed structural similarity measures, and most studies still depend on traditional measures for OD matrices comparison. Traditional performance measures are based on cell by cell comparison, and often neglect OD matrix structural information within their formulations. We propose a methodology that adopts the fundamentals of Levenshtein distance, traditionally used to compare sequences of strings, and extends it to quantify the structural comparison of OD matrices. The novel performance measure is named as normalised Levenshtein distance for OD matrices (NLOD). The results of sensitivity analysis support NLOD to be a robust statistical measure for holistic comparison of OD matrices. The study demonstrates the practicality of the approach with a case study application on real Bluetooth based OD matrices from the Brisbane City Council (BCC) region, Australia.