摘要 |
PROBLEM TO BE SOLVED: To obtain a method for selecting a plurality of different routes without detouring significantly by determining a candidate route, having a link cost within a specified times that of an optimal route and lowest link cost at the part overlapping the optimal route, as a quasi-optimal route. SOLUTION: Links a, c being branched from the starting point O of a first link on an optimal route (links b, i, p) between a start and a goal is specified and then the entire route is searched from the link a, c to a goal link D. In this regard, all routes may be searched simultaneously from the links g, f, k branched from the starting points 4, 6 of links i, p to the link D. Routing cost is then calculated for each candidate route and a candidate route, having a routing cost lower than (1+a) times that of an optimal route (a>0) and the sum of link cost at the part common to the optimal route (e.g. links b, c) is minimum, is determined as a quasi-optimal route. Route information related to an optimal route tree or quasi-optimal route tree is transmitted to each vehicle as required. |