Analysis of the Traveling Salesman Problem with a subset of intermediate cities and dynamic edge weights used with intelligent transportation systems

In this paper a specialized routing problem for vehicles in a transportation network that need to visit multiple destinations before returning to the starting location in the minimum time is presented. Although this problem is similar to the Traveling Salesman Problem (TSP), it differs because the edge weights can change constantly and the vehicle only needs to visit a subset of the nodes in the graph. The Dynamic Fastest Paths with Multiple Unique Destinations (DynFast-MUD) algorithm provides a solution to this problem which is tested in a live environment in this study. There are currently 50 vehicles in Anchorage, Alaska that contain devices that report the speed, location, and direction to a central server through a vehicle-to-infrastructure (V2I) architecture. Using this data, the shortest route to a predefined set of destinations was compared to the path identified by the DynFast-MUD algorithm once a day for a two week period. The results show that with this relatively limited number of vehicles contributing to the dynamic changing edge weights, the DynFast-MUD algorithm always provides a route that is at least as fast as the shortest route. It is hypothesized that with more vehicles reporting speed and location data, the DynFast-MUD algorithm will produce even better results.