| 摘要 |
A method for obtaining a many-to-many route searching process with a reasonable amount of computation. The method includes preparing a graph expressing road segments as edges and route intersections as nodes, the weight of each road segment being approximated by a monotonically increased piecewise linear function, searching the graph for the shortest routes, establishing the obtained routes as a set of routes to be processed, solving an objective function so as to minimize the maximum value obtained by dividing the required time from each departure point to each destination point by the shortest required time with respect to the set of a plurality of departure points and destination points, and removing those routes whose minimum cost is greater than or equal to that of the current best solution, and any unused routes added in the previous iteration, while repeating the solving of the objective function. |
| 主权项 |
1. A computer implemented method for selecting a route, the method comprising the steps of:
a computer preparing a graph expressing road segments as edges and route intersections as nodes, the road segments and the route intersections combining to form a first plurality of routes, and each road segment including a weight, the weight equal to a traveling time of each road segment; the computer searching the graph for a second plurality of routes in response to each of a plurality of requests, each request including a set of points, each set including a departure point and a corresponding destination point; the computer determining a minimum cost of each of the second plurality of routes, the minimum cost equal to a cost when traffic volume is zero, wherein the cost is equal to a sum of the weights of each road segment; the computer establishing the second plurality of routes as a set of routes to be processed, each of the second plurality of routes including at least one set of points, and one or more road segments and one or more route intersections connecting the departure point and the corresponding destination point of the at least one set of points; the computer solving an objective function, where the function iterates to minimize a maximum value obtained by dividing an actual required time of each of the second plurality of routes from each departure point to the corresponding destination point by the minimum cost of each of the second plurality of routes, wherein the actual required time is equal to the cost of each of the second plurality of routes; the computer determining, based on the objective function, a current best solution, wherein the current best solution is one route of the second plurality of routes with a lowest value obtained by solving the objective function; the computer determining the cost of the current best solution; responsive to determining the current best solution, the computer removing (a) each of the routes whose minimum cost is greater than the cost of the current best solution, and (b) each of an unused route added in a previous iteration, wherein each unused route is a route of the first plurality of routes not contained in the second plurality of routes; and the computer repeating the solving of the objective function with each route of the second plurality of routes that is not removed. |
