A route search apparatus configured to search a route from a set place of departure to a set destination, the route search apparatus comprising: a storage part configured to store network data (24; NW1; NW2) that include nodes (N1-N4; N6-N11, N30) and links (L1-L4; L5-L14) representing a road network, an average cost value indicating an average of travel time of each of the links, and a variance value indicating a degree of variance of the travel time; and a route searcher configured to determine the route from the place of departure to the destination as a recommended route, based on an overall cost value calculated according to a function including the average cost value, the variance value and a weight coefficient of the variance value, wherein the route searcher is configured to determine a route from the place of departure to a node corresponding to a specific point in the middle of the route from the place of departure to the destination, as a halfway route of the recommended route, said halfway route being iteratively calculated using a route search algorithm, based on a candidate overall cost value that is provided as a sum of a first term representing an integrated value of the average cost values corresponding to links that are passed through from the place of departure to the node corresponding to the specific point in the middle of the route from the place of departure to the destination and a second term representing a correction value calculated based on the weight coefficient and an integrated value of the variance values corresponding to the links that are passed through, the halfway route being set to determine the recommended route, characterized in that when there are a plurality of the candidate overall cost values that are different from each other by at most a predetermined value, out of the candidate overall cost values of a plurality of halfway route candidates that are candidates of the halfway route, the route searcher is configured to determine the halfway route, based on one of the first term and the second term that is selected according to the weight coefficient. a storage part configured to store network data (24; NW1; NW2) that include nodes (N1-N4; N6-N11, N30) and links (L1-L4; L5-L14) representing a road network, an average cost value indicating an average of travel time of each of the links, and a variance value indicating a degree of variance of the travel time; and a route searcher configured to determine the route from the place of departure to the destination as a recommended route, based on an overall cost value calculated according to a function including the average cost value, the variance value and a weight coefficient of the variance value, wherein the route searcher is configured to determine a route from the place of departure to a node corresponding to a specific point in the middle of the route from the place of departure to the destination, as a halfway route of the recommended route, said halfway route being iteratively calculated using a route search algorithm, based on a candidate overall cost value that is provided as a sum of a first term representing an integrated value of the average cost values corresponding to links that are passed through from the place of departure to the node corresponding to the specific point in the middle of the route from the place of departure to the destination and a second term representing a correction value calculated based on the weight coefficient and an integrated value of the variance values corresponding to the links that are passed through, the halfway route being set to determine the recommended route, characterized in that when there are a plurality of the candidate overall cost values that are different from each other by at most a predetermined value, out of the candidate overall cost values of a plurality of halfway route candidates that are candidates of the halfway route, the route searcher is configured to determine the halfway route, based on one of the first term and the second term that is selected according to the weight coefficient.