A novel approach for the structural comparison of origin-destination matrices: Levenshtein distance

Krishna N.S. Behara, Ashish Bhaskar, Edward Chung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

36 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)513-530
Number of pages18
JournalTransportation Research Part C: Emerging Technologies
Publication statusPublished - Feb 2020


  • Bluetooth OD matrices
  • Brisbane
  • Destination choices
  • Levenshtein distance
  • OD matrix structure
  • Structural comparison
  • Trip distribution

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Automotive Engineering
  • Transportation
  • Computer Science Applications


Dive into the research topics of 'A novel approach for the structural comparison of origin-destination matrices: Levenshtein distance'. Together they form a unique fingerprint.

Cite this