In this paper we present a fastest path algorithm that contains multiple unique destinations, which is a specialization of the Traveling Salesman Problem (TSP) with intermediate cities [1]. This algorithm can be used with Intelligent Transportation System (ITS) applications for determining the fastest route to travel to a set of destinations, such as required by delivery companies. The dynamic behavior of the algorithm is necessary for ITS applications since the amount of time to traverse a roadway in a vehicular network can change constantly. Assuming that all of the potential paths between all nodes in the transportation graph is known, the algorithm will determine the fastest route to a set of nodes in O(n3), where n is the number of nodes to visit. The algorithm was executed on theoretical and actual transportation graphs in FreeSim (http://www.freewaysimulator.com) [2], and an analysis of the running time and a proof of the correctness of the algorithm are included in this paper.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Dynamic fastest paths with multiple unique destinations (DynFast-MUD) — A specialized traveling salesman problem with intermediate cities


    Contributors:


    Publication date :

    2009-10-01


    Size :

    370549 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English




    Probabilistic Traveling Salesman Problem with Deadlines

    Campbell, Ann M. | Online Contents | 2008


    Probabilistic Traveling Salesman Problem with Deadlines

    Campbell, A.M. / Thomas, B.W. | British Library Online Contents | 2008


    Modeling the Flying Sidekick Traveling Salesman Problem with Multiple Drones

    Mauro Dell'Amico / Roberto Montemanni / Stefano Novellani | BASE | 2021

    Free access

    A Dynamic Colored Traveling Salesman Problem With Varying Edge Weights

    Meng, Xianghu / Li, Jun / Zhou, Mengchu et al. | IEEE | 2022