Patent ID: 9057619
Filing Date: 2015-06-16
Classification: G01C

Abstract:
1. An optimal path search system, which optimizes a travel path of a moving object moved using a moving means among a plurality of moving means, and the moving means moving the object is changed to a different moving means among the plurality of moving means, comprising: a path information database; a path search unit that searches for an optimal path that exhibits a minimum travel cost borne by the moving object, from among travel paths of the moving object; and an output unit that outputs information regarding the optimal path from the path search unit, wherein the path information database stores: path network management information for managing a path network that is structured of a plurality of nodes indicating points through which the moving object is able to travel and a plurality of links that connect the plurality of nodes; and travel cost management information for managing travel costs, which are necessary to travel along each of the plurality of links by using each of the plurality of moving means which can be used to travel along each of the plurality of links; the plurality of nodes include a plurality of intersection nodes that can be reached by traveling along the plurality of links by using either a particular moving means or another moving means among the plurality of moving means, wherein the path search unit is configured to: determine a plurality of destination points which can be reached only by using the particular moving means on the path network, the destination points are nodes within the path network; reference the path information database to search for first travel paths, each for traveling from each of the destination points to each of the intersection nodes, and calculate a first travel cost that is necessary for the moving object to travel along each of the retrieved first travel paths; search for a nearest intersection node to each of the destination points, the nearest intersection node being one of the intersection nodes corresponding to the first travel path having the lowest calculated first travel cost; generate pairs, each being obtained by associating each of the destination points with the nearest intersection node thereof; generate a plurality of groups, each being a partial set of the path network including at least one destination point and one or two of the generated pairs of the destination point and the nearest intersection node thereof; reference the path information database to search for second travel paths within each of the groups along each of which the moving object travels through all of the destination points included in the group and one or two nearest intersection nodes included in the group, and calculate second travel costs, each being necessary for the moving object to travel along each of the retrieved second travel paths; determine one of the second travel paths for which the calculated second travel cost is minimum as an intra-group optimal path; reference the path information database to search for third travel paths between groups along which the moving object travels between the groups, and calculate third travel costs, each being necessary for the moving object to travel along each of the retrieved third travel paths; determine one of the third travel paths for which the calculated third travel cost is minimum as an inter-group optimal path; and determine the optimal path based on the intra-group optimal path and the inter-group optimal path; and the output unit outputs data for displaying information regarding the optimal path and the travel paths of each of the plurality of moving means.