Research Of Dynamic Vehicle Navigation Algorithm

Currently, real-time traffic system based on floating car data has been covered almost first-tier or second-tier cities in China mainland. Traffic navigation using real-time traffic information can not only mitigate jams in road network but also provide guidance services to prevent congestions propagating under traffic confidents. However, it provides shortest path or fastest path normally without considering effects on human cognition ability of complexity of route instruction. Many researches on human cognition manifested that the complexity of route instruction may be as important as its length and travel time in navigation. Comparing to shortest or fastest path, people prefer suboptimal routes that were potentially easier to describe or follow although these routes may not be the optimal one in length and travel time. Those suboptimal routes can eliminate more cognitive barriers. Therefore, it makes sense on practical significance to take route complexity into consideration and study tactics of vehicle dynamic navigation using real-time traffic.By using the number of turns to quantify route complexity, this paper proposed a fewest-turn path algorithm based on breadth-first search to get routes with low complexity. Then, we extracted four road networks of OpenStreetMap in different cities and computed historical traffic of Nanjing using floating car data. Finally, we proved that tactics of vehicle dynamic navigation considering complexity factor is applicable in both static and dynamic road network. The main works and achievements are listed as followed.(1) Adapting to characters of features in open source map data of OpenStreetMap, we constructed a workflow to extract and organize city road network preparing for map matching and fewest-turn path searching. It includes non-network features filtering, road segment parting and road segment identifier assigning.(2) To cover noise samples generated by traffic jams and waiting in traffic lights, we proposed a method to remove parking samples based on driving pattern in pre-processing of floating car data. This method defines a GPS trajectory as parking pattern by three parameters, maximum distance between two neighbour samples rp, minimum duration ΔTp and maximum movement radius Rp.(3) Using a map matching algorithm considering both geometry and topology information, we constructed a workflow for pre-processing of floating car data and traffic computing in OpenStreet Map network. It can solve the problem of speed limit lacking in OpenStreetMap data.(4) Inspired by the description of turns in navigation instruction, a fewest-turn path algorithm based on breadth-first search is proposed. Using static road networks of four cities and dynamic traffic network in Nanjing, we compared two kinds of navigation tactics, distance or travel time minimization with condition of fewest-turns and only distance or travel time minimization. This job carried out by using two kinds of ratio, ratio of distance/travel time and ratio of the number of turns, and proved that there two superiorities existed in navigation tactics with fewest-turn. First, the solution of fewest-turn path obtained a simpler path while the length/travel time was nearly as short as the shortest/fastest path, when the OD distance is greater than 45 km. Second, for shorter OD distance, there are still considerable paths keeping this superiority.