PROBLEM TO BE SOLVED: To shorten a time required for searching a passing minimum cost route from a starting point to an end point via a passing point without overlapping route.;SOLUTION: A route search network comprised of arcs wherein a cost is set and a plurality of nodes are used to search the minimum cost routes of a first section between a starting point node and a passing point node, and a second section between the passing point node and an arrival point node, respectively, and to join them together (S1-S3). When any overlapping node is present in a joint route, an arc entering the overlapping node nearest to the passing point node of the minimum cost route in the first section is cut, and a first arc cut route search network is constructed, and an arc going out from the overlapping node nearest to the passing node of the minimum cost route in the second section is cut, and a second arc cut route search network is constructed, and then a joint route without overlapping node is searched in each of the first and second arc cut route search networks, and it is determined as a passing minimum cost route candidate (S4-S6, S1-S3). The candidate with the minimum cost among the candidates is selected as the passing minimum cost route (S7-S9).;COPYRIGHT: (C)2011,JPO&INPIT
展开▼