An Efficient Trip Planner for Time Dependent Road Networks

Abstract

Management of transportation systems has become increasingly important in many real applications such as location-based services, supply chain management, traffic control, and so on. These applications usually involve queries over spatial road networks with dynamically changing and complicated traffic conditions. When we consider road network, route search and optimal path queries are two important types of queries. A path query returns a path that is a set of points that connects the source and destination. The optimal path queries find the optimum path from set information. In the case of road network users give some specification about the travelling with or without constraints. The optimal path queries optimize the possible paths and give the optimal path that satisfies all the constraints. The road network mainly deals with time dependent parameters A spatial road network can be modeled by a large graph in a 2-dimensional geographical space, whose edges correspond to road segments, and are associated with weights related to the traffic information. This paper, mainly focus on finding one of the best path that has minimum travel time. User can select the query points and Candidate plans are generated based on the selected points. To reduce the search space time interval pruning and probabilistic pruning strategies are implemented. Finally the best plan is refined based on a probabilistic threshold.