The coordination and management of vehicles in a big city with a complex network of roads are critical to reduce traffic jam, which also reduces driving time, pollution, and noise. Because there is no empty space left in a big city to accommodate more transportation infrastructures, the development of an effective navigation system is a low cost option for mitigating traffic jam. Nowadays, an on-board navigation device or a navigation service provider can identify a shortest or fastest route based on the current or history traffic information for a vehicle. Even though each vehicle arrives at its destination along the shortest or fastest route, a traffic jam may still happen because each vehicle does not know the routes of the other vehicles. To plan routes for vehicles, previous works have focused on the traffic assignment problem or the multi-agent routing problem. For example, with a behavioral approach, a dynamic traffic assignment model can be used to represent the interaction between travel choices and traffic flows. Multi-agent based vehicle routing systems focus on how these agents perform communication between them to improve decision making. Regarding a future world where automated driving technologies have become mature and most drivers are willing to transfer the driving control to an automatic driving system that always follows the pre-scheduled route suggested by a navigation system in normal situations, it is likely to predict the traffic jam if the navigation system can know the pre-scheduled route of each vehicle. Recently, a navigation algorithm based on near-future evaluation is proposed to effectively reduce traffic jam for hundreds of thousands of automated driving vehicles. However, the aforementioned algorithm does not consider any kind of uncertainty, for example, traffic accidents or the change of route due to the change of destination or a temporary stop. In this paper, we propose a navigation algorithm to guide vehicles based on the assumption that all the navigating query request are processed by a single system. To get close to the real world, some kinds of uncertainties are allowed, such as abrupt traffic jams caused by vehicle accident and prediction failure caused by changing the destination or a temporary stop. First, for a metropolitan map, we randomly generate traffic accidents on some roads. The frequency of traffic accidents is derived from official statistics. We compare our navigation algorithm with a dynamic-update based conventional navigation algorithm without near-future evaluation capability. Secondly, as a person starts his journey by automatic driving, he may change the destination or temporarily park for something before reaching the destination. For these situations, the navigating system has to identify a new route for the new destination and also needs to update the future traffic flow of the roads on the pre-scheduled route. We download the maps of Kyoto, Osaka, and Taipei cities from OpenStreetMap and utilize the data of traffic flow from official statistics to randomly generate many sets queries with different quantity (a query is issued by a vehicle). Experimental results demonstrate that, compared with dynamically updated navigating system, the total cruising time is improved for each case.