ROUTE SELECTION SYSTEM, METHOD AND PROGRAM

• US 20130238242A1
• Filed: 11/08/2011
• Published: 09/12/2013
• Est. Priority Date: 11/26/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yoshizumi, Takayuki
• Granted Patent: US 8,930,142 B2
• Time in Patent Office: Days
• US Class Current: 701/533
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

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.

Claims

1. A computer implemented method for selecting a route, the method comprising the steps of:

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 in response to a plurality of requests being sets of departure points and destination points;

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.

2. The method for selecting a route according to claim 1, wherein the weighting is the traveling time of the route.

3. The method for selecting a route according to claim 2, further comprising:

adding to the set of routes to be processed any route lowering the objective function when added while repeating the solving of the objective function.

4. The method for selecting a route according to claim 3, wherein adding to the set of routes further comprises:

searching for any route using the current cost and not using the bottleneckEdge when the “

actual required time/shortest required time”

is maximized, a request having the same actual required time as all candidate routes is a bottleneckRequest, and an edge included in the candidate route set for these is a bottleneckEdge.

5. The method for selecting a route according to claim 4, further comprising:

including and searching for any route using the bottleneckEdge in response to not finding a route in the step of searching for any route using the current cost and not using the bottleneckEdge.

6. The method for selecting a route according to claim 5, further comprising:

searching for any route using the current cost and not using the bottleneckEdge when there is no route concerning each non-bottleneckEdge worsening the solution at the time and increasing the flow in response to not finding a route in the step of searching for any route using the current cost and not using the bottleneckEdge.

7. The method for selecting a route according to claim 6, further comprising:

including and searching for any route using the bottleneckEdge in response to not finding a route in the step of searching for any route using the current cost and not using the bottleneckEdge.

8. The method for selecting a route according to claim 1, wherein the objective function is solved by a solver.

9. The method for selecting a route according to claim 8, wherein the request is a set of a departure point, a destination point, and a demand level, and the solver outputs the percentage of the demand level for a plurality of routes from the departure point to the destination point.

10. A computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions which, when implemented, cause a computer to carry out the steps of a method for selecting a route comprising:

preparing a graph expressing routes as edges and route intersections as nodes, the weight of each route being approximated by a monotonically increased piecewise linear function;

searching the graph for the shortest routes in response to a plurality of requests being sets of departure points and destination points;

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

repeating the solving of the objective function while removing as an unpromising route from the set of routes to be processed any route having a minimum cost greater than the best solution at the time, and any unused route added in the previous iteration.

11. The method for selecting a route according to claim 10, wherein the weighting is the transit time of the route.

12. The method for selecting a route according to claim 11, further comprising:

adding to the set of routes to be processed any route lowering the objective function when added while repeating the solving of the objective function.

13. The method for selecting a route according to claim 12, wherein the adding step to the set of routes further comprises:

searching for any route using the current cost and not using the bottleneckEdge when the “

actual required time/shortest required time”

is maximized, a request having the same actual required time as all candidate routes is a bottleneckRequest, and an edge included in the candidate route set for these is a bottleneckEdge.

14. The method for selecting a route according to claim 13, further comprising:

including and searching for any route using the bottleneckEdge in response to not finding a route in the step of searching for any route using the current cost and not using the bottleneckEdge.

15. The method for selecting a route according to claim 10, wherein the objective function is solved by a solver.

16. The method for selecting a route according to claim 15, wherein the request is a set of a departure point, a destination point, and a demand level, and the solver outputs the percentage of the demand level for a plurality of routes from the departure point to the destination point.

17. A computer implemented system for selecting a route, the system comprising:

storage means; and

, stored in the storage means,

means for 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;

means for searching the graph for the shortest routes in response to a plurality of requests being sets of departure points and destination points, and establishing the obtained routes as a set of routes to be processed;

a solver for 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

means for 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.

18. A system for selecting a route according to claim 17, further comprising:

means for adding to the set of routes to be processed any route lowering the objective function when added while repeating the solving of the objective function.

19. A system for selecting a route according to claim 18, wherein the means for adding to the set of routes further comprises:

means for searching for any route using the current cost and not using the bottleneckEdge when the “

actual required time/shortest required time”

is maximized, a request having the same actual required time as all candidate routes is a bottleneckRequest, and an edge included in the candidate route set for these is a bottleneckEdge.

20. A system for selecting a route according to claim 19, further comprising:

means for including and searching for any route using the bottleneckEdge in response to not finding a route in the step of searching for any route using the current cost and not using the bottleneckEdge.

21. A system for selecting a route according to claim 20, wherein the request is a set of a departure point, a destination point, and a demand level, and the solver outputs the percentage of the demand level for a plurality of routes from the departure point to the destination point.