Method and system for mobile vehicle re-routing

• US 6,587,785 B2
• Filed: 09/21/2001
• Issued: 07/01/2003
• Est. Priority Date: 09/21/2001
• Status: Active Grant

• Current Assignee: General Motors LLC (General Motors Company)
• Original Assignee: General Motors Corporation (Motors Liquidation Co. GUC Trust)
• Inventors: Stefan, Jeffrey M., Jijina, Jasmin
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US09/960,438
• Publication Number:
  US 20030060977A1
• Time in Patent Office: 648 Days
• Field of Search: 701/201, 701/209, 701/210, 701/211, 701/117, 340/995, 340/989
• US Class Current: 701/210
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• 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/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/09685 where the complete route is computed only once and not updated
• CPC Class Codes: G08G 1/096861 where the immediate route instructions are output to the driver, e.g. arrow signs for next turn

Abstract

The invention provides a method for routing a mobile vehicle around a traffic incident site. A traffic incident location and an intended vehicle route are provided to a route generation algorithm. A polygon based on the traffic incident location and the intended vehicle route is determined. At least one route exit point and at least one route re-entry point are determined. A plurality of intersections within the polygon is determined, and link weights between the intersections are assigned based on at least one condition factor. At least one alternative route between the route exit point and the route re-entry point is determined, based on the assigned link weights. Another aspect of the invention provides an algorithm for re-distributing traffic around a traffic incident site.

Claims

1. Method of routing a mobile vehicle around a traffic incident comprising:

receiving a traffic incident location;

receiving an intended vehicle route;

determining a polygon based on the traffic incident location and the intended vehicle route;

determining at least one route exit point and at least one route re-entry point;

determining a plurality of intersections within the polygon;

assigning link weights between the intersections based on at least one condition factor; and

determining at least one alternative route between the route exit point and the route re-entry point based on the assigned link weights.

2. The method of claim 1 wherein the link weights are based on a condition factor comprising a distance between intersections.

3. The method of claim 1 wherein the link weights are substantially equal to the distance between the intersections.

4. The method of claim 2 further comprising:

selecting the alternative route having at least one link weight corresponding to a greatest distance.

5. The method of claim 1 wherein the link weights are based on at least one condition factor from a set consisting of distance, travel time, number of traffic lights, duration of traffic lights, synchronization of traffic lights, speed limits, number of stop signs, number of left turns, number of lanes, number of cross streets, number of driveways, time of day, road conditions, weather, traffic backup, angle of link with respect to intended vehicle route, fuel requirements, vehicle wear-and-tear, personal profile, personal preferences, other desired stops, statistical information, dynamic information and real-time information between intersections.

6. The method of claim 1 further comprising:

labeling each alternative route.

7. The method of claim 6 further comprising:

assigning a mobile vehicle one of the labeled routes based on a traffic distribution algorithm.

8. The method of claim 7 wherein the traffic distribution algorithm is a round-robin algorithm.

9. A computer usable medium including a program for determining mobile vehicle routing around a traffic incident, comprising:

computer program code for receiving a traffic incident location;

computer program code for receiving an intended vehicle route;

computer program code for determining a polygon based on the traffic incident location and the intended vehicle route;

computer program code for determining at least one route exit point and at least one route re-entry point;

computer program code for determining a plurality of intersections within the polygon;

computer program code for assigning link weights between the intersections based on at least one condition factor; and

computer program code for determining at least one alternative route between the route exit point and the route re-entry point based on the assigned link weights.

10. The computer usable medium of claim 9, further comprising:

computer program code for selecting the alternative route having at least one link weight corresponding to a greatest distance.

11. The computer usable medium of claim 9, further comprising:

computer program code for labeling each alternative route.

12. The computer usable medium of claim 11, further comprising:

computer program code for assigning one of the labeled routes to a mobile vehicle based on a traffic distribution algorithm.

13. A mobile vehicle re-routing system comprising:

means for receiving a traffic incident location;

means for receiving an intended vehicle route;

means for determining a polygon based on the traffic incident location and the intended vehicle route;

means for determining at least one route exit point and at least one route re-entry point;

means for determining a plurality of intersections within the polygon;

means for assigning link weights between the intersections based on at least one condition factor; and

means for determining at least one alternative route between the route exit point and the route re-entry point based on the assigned link weights.

14. The system of claim 13 further comprising:

means for selecting the alternative route having at least one link weight corresponding to a greatest distance.

15. The system of claim 13 further comprising:

means for labeling each alternative route.

16. The system of claim 15 further comprising:

means for assigning a mobile vehicle one of the labeled routes based on a traffic distribution algorithm.