Automatic vehicle routing and recommendation system

• US 6,496,774 B1
• Filed: 05/24/2001
• Issued: 12/17/2002
• Est. Priority Date: 05/24/2001
• Status: Expired due to Fees

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: PRC, Inc. (Arthur D. Little, Inc.)
• Inventors: Davies, F. Bryan
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Hernandez, Olga
• Application Number:
  US09/863,874
• Publication Number:
  US 20020177945A1
• Time in Patent Office: 572 Days
• Field of Search: 701/200, 731/78.R, 340/990, 340/995
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching
• CPC Class Codes: G08G 1/205 Indicating the location of the monitored vehicles as destination, e.g. accidents, stolen, rental

Abstract

The present invention relates generally to automatic vehicle navigational systems, and more particularly, to an automatic vehicle routing and recommendation system. Even more particularly, the present invention is directed to a system for choosing one of a plurality of potential vehicles in a fleet for routing the fleet vehicle over the shortest distance and/or time from a current location to a target point such as a fire or a passenger for a taxicab.

Claims

1. A method of recommending which of a plurality of vehicles should be routed from a present location to a target location on a tessellated map plane, the tessellated map plane overlaying a street network and being divided into a plurality of tessellation'"'"'s, comprising:

continuously storing a plurality of dynamically changing vehicle locations representing a location of a vehicle with each of the vehicle locations being a present location and being within one of the plurality of tessellations;

for each of the plurality of vehicles determining a next tessellation adjacent the tessellation within which the vehicle is located;

if the second location is not located within the next tessellation, determining a further tessellation until a tessellation is determined including the target location;

selecting which of the plurality of vehicles would travel the shortest distance from the present location to the target location.

2. The method of claim 1, wherein each of the tessellation includes a plurality of boundaries with adjacent tessellations sharing a common boundary.

3. The method of claim 1, comprising recommending the shortest route from the first location to the second location.

4. The method of claim 1, wherein each of the tessellations is a triangle.

5. The method of claim 2, wherein each of the plurality of boundaries has an impedance value associated therewith.

6. The method of claim 5, comprising calculating the shortest distance by adding each of the distances for each of boundaries and multiplying each of the distances by the impedance associated with the boundary.

7. The method of claim 5, wherein the impedance may be different depending on the direction of travel of the vehicle.

8. The method of claim 1, wherein the impedance for a barrier is infinite wherein the barrier is a river, railroad track.

9. The method of claim 1, wherein the method is performed in real time.

10. The method of claim 1, wherein each tessellation is evaluated in a clockwise manner.

11. The method of claim 5, wherein there is four impedance values for different times of the day.