Patent ID: 8600721

Claim:
A route cost calculation method of calculating a cost on an arbitrary route in a graph including a plurality of nodes and links connecting the plurality of nodes by using a parameter associated with each link in the graph by processing of a computer on the basis of a plurality of training data sets that each include an origin, a destination, and a route cost value between the origin and the destination on the graph, the method comprising: initializing, by a central processing unit in the computer, a value of the parameter associated with each link in the graph; recalculating, by the central processing unit, route cost values of the plurality of training data sets by calculating a minimum cost route among all routes from each origin to each destination by using the plurality of training data sets; recalculating, by the central processing unit, the value of the parameter associated with each link in the graph by solving an optimization problem of an objective function including the recalculated route cost values of the plurality of training data sets, wherein the objective function is defined by the mathematical expression: Ψ α , β ⁡ ( f | λ ) = ∑ n = 1 N ⁢ ⁢  y ( n ) - ∑ c ∈ x ( n ) ⁢ ⁢ c e ⁡ ( f e )  α + λ ⁢ ∑ e = 1 M ⁢ ⁢ ∑ e ′ = 1 M ⁢ ⁢ S e , e ′ ⁢  f e - f e ′  β where f is a column vector whose entries are {f e }, N is the number of the plurality of training data sets, y (n) is a recorded route cost value from the origin to the destination, f e is a parameter associated with a particular link e, c e (f e ) is a function of transforming the parameter associated with each link in the graph to a route cost value, α and β are integer values, and λ is a determined positive value between 0 and 1, M is a total number of links on the graph, S ee′ is a similarity matrix S identifying a similarity between a link e another link e′; and obtaining, by the central processing unit, the value of the parameter associated with each link in the graph in response to an amount of change in the value of the parameter associated with each link in the graph between before and after the recalculation is equal to or less than a predetermined threshold.