Levenshtein distance for the structural comparison of OD matrices

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).