Predictability measurement for the sequence of travel time by combining the Lempel-Ziv compression and the Longest Common Subsequence algorithm

Abstract

It is commonly recognized that reliability in travel time is a significant factor to consider, as it not only wields a significant impact on traveller behaviour, but also substantially impacts the general efficiency of transport systems. Predictability measure for Travel time Sequence is probabilistic approach that depends on historical data. To measure the reliability of travel time sequence from the perspective of predictability, entropy plays an important role. To estimate the entropy of such a travel time sequence Lempel-Ziv data compression algorithm can be used but Lempel-Ziv scanned the whole historical string for the exactly identical substring. So, in entropy estimation process some partially similar substring or subsequence gets overlooked. For deep analysis, longest common subsequence (LCS) algorithm is employed to calculate exactly identical substring and most similar subsequence. LCS algorithm discarded redundant subsequence's which further reduce entropy. This lead to increase in predictability of travel time sequence. Thus, the combination of LZ and LCS give more accurate predictability and easily can be implemented for travel time forecasting in ITS to calculate prediction rate for next travel time based on given travel time sequence.