Multidimensional sequence alignment methods for activity-travel pattern analysis: A comparison of dynamic programming and genetic algorithms

Quantitative comparisons of space-time activity-travel patterns have been m ade at length in regional science. Traditionally, Euclidean Hamming distanc es have been widely used to measure the similarity between activity-travel patterns that involve several attribute dimensions such as activity type, l ocation, travel mode, accompanying person, etc. Other techniques, such as p attern recognition in signal processing theory, have also been introduced f or this purpose. All these measures, however, lack the ability to capture t he sequential information embedded in activity-travel patterns. Recently, t he sequence alignment methods (SAMs), developed in molecular biology that a re concerned with the distances between DNA strings, have been introduced i n time use research. These SAMs do capture the similarity of activity-trave l patterns, including sequential information, but based on a single attribu te only. Unfortunately, the extension of the unidimensional SAMs to a multi dimensional method induces the problem of combinatorial explosion. To solve this problem, this paper introduces effective heuristic methods for the co mparison of multidimensional activity-travel patterns. First, following a b rief review of existing measures of activity-travel pattern comparison, the problem of multidimensional sequential information comparison and the comb inatorial nature of the method are discussed. The paper then develops alter native multidimensional SAMs employing heuristic based on dynamic programmi ng and genetic algorithms, respectively. These heuristic SAMs are compared using empirical activity-travel pattern data. The paper ends by discussing avenues of future research.