Levenshtein distance for the structural comparison of OD matrices

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

Research output: Unpublished conference presentation (presented paper, abstract, poster)Conference presentation (not published in journal/proceeding/book)Academic researchpeer-review


The spatial distribution of Origin-Destination (OD) demands between different OD pairs reveals the structural information of OD matrices. Generally, OD pairs from geographical zones sharing similar activities, travel cost, and destination choices have a similar distribution of trips. Most of the traditional statistical measures are based on a cell by cell comparison and do not account for the additional structural knowledge in terms of similarity of trip distribution while comparing OD matrices. Thus, there is a need for new comparative measures to account for the structural information by computing statistics on the group of OD pairs. In this light, the paper adopts and extends an existing metric – Levenshtein distance for structural comparison of OD matrices. The proposed Mean Normalized Levenshtein distance for OD matrices comparison (MNLdOD) is an optimization-based metric and is computationally better than another popular metric – Wasserstein distance proposed by Ruiz de Villa et al. (2014).

Original languageEnglish
Publication statusPublished - 1 Jan 2018
Event40th Australasian Transport Research Forum, ATRF 2018 - Darwin, Australia
Duration: 30 Oct 20181 Nov 2018


Conference40th Australasian Transport Research Forum, ATRF 2018


  • Bluetooth OD
  • Levenshtein distance
  • OD matrices comparison
  • OD matrix structure
  • Statistical measures
  • Wasserstein distance

ASJC Scopus subject areas

  • Transportation


Dive into the research topics of 'Levenshtein distance for the structural comparison of OD matrices'. Together they form a unique fingerprint.

Cite this