Routing system and method

• US 20060161335A1
• Filed: 01/14/2005
• Published: 07/20/2006
• Est. Priority Date: 01/14/2005
• Status: Abandoned Application

• Current Assignee: Ross Beinhaker
• Original Assignee: Ross Beinhaker
• Inventors: Beinhaker, Ross
• Application Number:
  US11/034,874
• Publication Number:
  US 20060161335A1
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• 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

The routing system and method find efficient routings among destinations in a traffic network. A starting point and at least one destination point are identified in the traffic network. The identified points are ordered into at least one tour. Traffic conditions for the traffic network are forecast for a time period of interest, and for each tour, a routing is generated using the forecast traffic conditions. A routing system implementing the method described in a computer or Internet environment includes a database storing a representation of the traffic network. A computer program provides means for selecting a starting point and at least one destination point in the traffic network, means for ordering the points into at least one tour, means for forecasting traffic conditions for the roads in the traffic network, and means for generating a routing for each tour using based on the forecast traffic conditions.

Claims

1. A routing method to find efficient routings to reach destinations in a traffic network, the traffic network having a plurality of nodes interconnected by a plurality of roads, the routing method comprising the steps of:

(a) selecting a starting point and at least one destination point in the traffic network;

(b) ordering the starting point and at least one destination point into at least one tour, wherein the tour begins at the starting point and includes at least one destination point;

(c) forecasting traffic conditions for the roads in the traffic network; and

(d) for each tour, generating a routing using the forecast traffic conditions.

2. The routing method according to claim 1, wherein at least one tour is generated by adding destination points to a tour until a capacity constraint is met.

3. The routing method according to claim 1, wherein at least one destination point is subject to a time-window constraint.

4. The routing method according to claim 1, wherein at least one tour is served by at least one vehicle.

5. The routing method according to claim 1, wherein each tour begins and ends at the starting point.

6. The routing method according to claim 1, wherein step (b) includes the steps of:

generating an initial random order of destination points, and

generating an initial set of tours by allocating the destination points in the initial random order to one or more tours, wherein each tour is limited by a capacity constraint.

7. The routing method according to claim 6, further comprising the step of calculating an objective function to assess a quality of the initial set of tours.

8. The routing method according to claim 6, further comprising the step of making improvements to the initial set of tours to generate an improved set of tours.

9. The routing method according to claim 8, wherein step (b) utilizes an n-opt exchange algorithm within a tabu search algorithm to generate an ordering.

10. The routing method according to claim 1, wherein step (b) utilizes a tabu search algorithm to generate an ordering.

11. The routing method according to claim 1, wherein step (b) utilizes a branch and bound technique to generate an ordering.

12. The routing method according to claim 1, wherein step (b) utilizes a branch and cut technique to generate an ordering.

13. The routing method according to claim 1, wherein step (b) utilizes an ant algorithm to generate an ordering.

14. The routing method according to claim 1, wherein step (b) utilizes a constraint programming technique to generate an ordering.

15. The routing method according to claim 1, wherein step (b) utilizes an annealing technique to generate an ordering.

16. The routing method according to claim 1, wherein step (b) utilizes a genetic algorithm to generate an ordering.

17. The routing method according to claim 1, wherein step (c) comprises the steps of:

collecting current real-time traffic information, and

using the current real-time traffic information to generate a traffic conditions forecast of traffic conditions for a future time interval.

18. The routing method according to claim 17, wherein step (c) further comprises the steps of:

providing previous traffic condition information, and

performing a time-series analysis using the previous traffic condition information along with the current real-time traffic information to generate the traffic conditions forecast.

19. The routing method according to claim 17, wherein the previous traffic condition information comprises a previous traffic conditions forecast.

20. The routing method according to claim 1, wherein step (c) further comprises the steps of:

collecting historical traffic information,

collecting real-time traffic information,

modeling traveler behavior, and

performing a dynamic traffic assignment using the historical traffic information, real-time traffic information, and traveler behavior models to generate the traffic conditions forecast.

21. The routing method according to claim 1, wherein step (d) utilizes a label correcting algorithm to generate the routing.

22. The routing method according to claim 1, wherein step (d) utilizes a label setting algorithm to generate the routing.

23. The routing method according to claim 1, wherein step (d) utilizes an A* algorithm to generate the routing.

24. The routing method according to claim 1, wherein step (d) utilizes a label correcting algorithm to generate the routing, further wherein the label correcting algorithm considers the cost of traversing each arc in the traffic network to determine the routing.

25. The routing method according to claim 24, wherein the cost is a function of an arc length and a traffic condition.

26. The routing method according to claim 25, wherein the traffic condition is the travel speed for a vehicle on an arc.

27. A routing system for finding efficient routings to reach multiple destinations in a traffic network, said traffic network having a plurality of nodes interconnected by a plurality of roads, said system comprising:

a database storing a representation of said traffic network;

means for selecting a starting point and at least one destination point in said traffic network;

means for ordering said starting point and at least one destination point into at least one tour, wherein said tour begins at said starting point and includes at least one destination point;

means for forecasting traffic conditions for the roads in said traffic network; and

means for generating a routing for each tour using said forecast traffic conditions.

28. The routing system of claim 27, further comprising means for receiving current real-time traffic information for said traffic network.

29. The routing system of claim 27, further comprising a database storing historical traffic information for said traffic network.

30. The routing system of claim 27, further comprising at least one remote terminal operable for user entry of said starting point and at least one destination point.