Decoding the optimal route on transport graph using cellular data
The article presents a novel algorithm for optimal route decoding on transport graph using cellular data which uses probabilistic approach based on hidden Markov model. The distinctive feature of the proposed algorithm is that it can process sequential cellular data that consists of highly sparse call data records (CDR) instead of far more accurate GPS-data. Another feature is that this algorithm is able to cope with incomplete data in case when no path on graph can be found between the consecutive CDRs thanks to the proposed modified Viterbi algorithm. The algorithm was evaluated using anonymized CDRs and corresponding test GPS-data. The evaluation showed that the presented method is 2.5 more accurate than the simple algorithm that connects the coordinates of cell towers in order of their appearance. Also, it was shown that modified Viterbi algorithm allows to cover 30% more of test GPS-data points in comparison with of the standard version. In addition, the experimental data was presented that confirms the choice of hyperparameters used for the algorithm and one of the optimal hyperparameters was calculated with the alternative formula which also agrees with the evaluation data. Further work includes adding signal strength, speed, time, route complexity, road priorities and other factors to probabilistic model which will not only improve the algorithm accuracy but will also allow the transport type classification. The preliminary tests of the new version of algorithm shows that the error can be lowered down to 100 meters.