A k-shortest paths based algorithm for multimodal time-dependent networks to compute alternative routes

2015 
Usual computations of alternative routes and the measure of their similarities and/or dierences do not embrace the variability of networks specics and user preferences. Indeed, the denition and evaluation of the dierence between paths is often embedded into algorithm internals and thus does not take into account that similar or dissimilar paths may vary depending on the user and/or the network. In this article, a generic method to generate alternative routes on FIFO time-dependent multimodal graphs with regular language constraints is presented. It relies on the computation, in a rst stage, of the k-shortest paths before the enforcement of a distinction criteria based on word metrics and comparison procedures in a second stage. We rst present a variant of a k-shortest paths algorithm taking into account both the multimodality and the time-dependency inherent to transportation networks. Then, we propose several methods for evaluating the dierences between routes. Experiments are conducted in realistic cases of transportation networks and associated results show the relative eciency and interest of the approach.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    11
    References
    0
    Citations
    NaN
    KQI
    []