Route selection system, method and program

• US 8,930,142 B2
• Filed: 11/08/2011
• Issued: 01/06/2015
• Est. Priority Date: 11/26/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yoshizumi, Takayuki
• Primary Examiner(s): Olszewski, John R
• Assistant Examiner(s): MERLINO, DAVID P
• Application Number:
  US13/989,222
• Publication Number:
  US 20130238242A1
• Time in Patent Office: 1,155 Days
• Field of Search: None
• 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:

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.

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

the computer adding to the set of routes to be processed any route lowering the objective function when added; and

repeating the solving of the objective function.

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

the computer determining one or more route requests of the plurality of requests having a same actual required time as one or more candidate routes, wherein the one or more candidate routes include each route of the second plurality of routes that remains after the removing step;

the computer setting the determined one or more route requests as bottleneckRequests;

the computer setting an edge included with the one or more candidate routes as a bottleneckEdge; and

the computer searching for one or more routes with a cost less than the current best solution, using the cost and not using the bottleneckEdge.

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

the computer searching for one or more routes using the bottleneckEdge in response to not finding a route in the step of searching for one or more routes using the cost and not using the bottleneckEdge.

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

the computer determining a candidate route was not found; and

the computer searching for one or more routes using the cost and not using the bottleneckEdge when there is no route concerning each non-bottleneckEdge worsening a solution to the objective function.

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

the computer searching for one or more routes using the bottleneckEdge in response to not finding a route in the step of searching for one or more routes using the cost and not using the bottleneckEdge.

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

8. The method for selecting a route according to claim 7, wherein each of the plurality of requests further includes a demand level, wherein the demand level is a number of vehicles traveling between each departure point and corresponding destination point, and the solver outputs a percentage of the demand level for a third plurality of routes from the departure point to the corresponding destination point.

9. A computer program product comprising a computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions stored thereon, wherein the computer readable storage medium is hardware, and which, when implemented, cause a computer to carry out the steps of a method for selecting a route comprising:

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;

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;

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;

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;

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;

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;

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

repeating the solving of the objective function with each route of the second plurality of routes that is not removed.

10. The computer program product of claim 9, which when implemented, causes the computer to carry out the steps of the method for selecting a route, further comprising:

adding to the set of routes to be processed any route lowering the objective function when added; and

repeating the solving of the objective function.

11. The computer program product of claim 10, which when implemented, causes the computer to carry out the steps of the method, wherein the adding step to the set of routes to be processed further comprises:

determining one or more route requests of the plurality of requests having a same actual required time as one or more candidate routes, wherein the one or more candidate routes include each route of the second plurality of routes that remains after the removing step;

setting the determined one or more route requests as bottleneckRequests;

setting an edge included with the one or more candidate routes as a bottleneckEdge; and

searching for one or more routes with a cost less than the current best solution, using the cost and not using the bottleneckEdge.

12. The computer program product of claim 11, which when implemented, causes the computer to carry out the steps of the method, further comprising:

searching for one or more routes using the bottleneckEdge in response to not finding a route in the step of searching for one or more routes using the cost and not using the bottleneckEdge.

13. The computer program product of claim 9, which when implemented, causes the computer to carry out the steps of the method for selecting a route, wherein the objective function is solved by a solver.

14. The computer program product of claim 13, which when implemented, causes the computer to carry out the steps of the method for selecting a route, wherein each of the plurality of requests further includes a demand level, wherein the demand level is a number of vehicles traveling between each departure point and corresponding destination point, and the solver outputs a percentage of the demand level for a third plurality of routes from the departure point to the corresponding destination point.

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

one or more processors, one or more computer readable storage mediums, and computer readable program instructions stored on the one or more storage mediums for execution by at least one of the one or more processors, wherein the one or more computer readable storage mediums are hardware, the program instructions comprising program instructions configured to;

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;

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;

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;

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;

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;

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;

responsive to determining the current best solution, 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

repeating the solving of the objective function with each route of the second plurality of routes that is not removed.

16. A system for selecting a route according to claim 15, further comprising program instructions configured to:

adding to the set of routes to be processed any route lowering the objective function when added; and

-repeating the solving of the objective function.

17. A system for selecting a route according to claim 16, wherein the program instructions for adding to the set of routes to be processed further comprises:

determining one or more route requests of the plurality of route requests having a same actual required time as one or more candidate routes, wherein the one or more candidate routes include each route of the second plurality of routes that remains after the removing step;

setting the determined one or more route requests as bottleneckRequests;

setting an edge included with the one or more candidate routes as a bottleneckEdge; and

searching for one or more routes with a cost less than the current best solution, using the cost and not using the bottleneckEdge.

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

searching for one or more routes using the bottleneckEdge in response to not finding a route in the step of searching for one or more routes using the cost and not using the bottleneckEdge.

19. A system for selecting a route according to claim 15, wherein each of the plurality of requests includes a set of a departure point, a corresponding destination point, and a demand level, wherein the demand level is a number of vehicles traveling between each departure point and corresponding destination point, and a solver outputs a percentage of the demand level for a third plurality of routes from the departure point to the corresponding destination point.