Matching stored routes to a required route

Details Matching stored routes to a required route Matching stored routes to a required route

2001-11-20

2004-06-15

Zanelli, Michael J. (Department: 3661)

Data processing: vehicles, navigation, and relative location

Navigation

Determination of travel data based on the start point and...

C701S209000

Reexamination Certificate

active

06751548

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to computerized mapping software programs, and more specifically, to computerized mapping software programs that match stored routes to a given route by calculating indicators of similarity between the given route and each stored route and identifying the best stored route or routes by ordering the stored routes by a selected indicator of similarity.
BACKGROUND OF THE INVENTION
The widespread use of single-occupancy vehicles (SOVs) in modern industrialized societies is known to be a significant cause of several major economic, social and environmental problems including the inefficient use of energy resources, higher than necessary traffic congestion and higher than necessary levels of air pollution.
The alternatives of mass transportation, telecommuting or non-congesting
on-polluting modes of transportation are only available to limited segments of the population. A universal alternative to the use of SOVs is the use of high-occupancy vehicles (HOVs), where multiple individuals share a single vehicle. The efficient sharing of vehicles can only occur when the savings of the shared trip are greater than the costs of the individuals coming together to share the single vehicle. A system to determine which individuals should share a vehicle must analyze the locations of the origins (homes) and destinations (places of work) of all the individuals within its scope and group people together based on how close together they live and how close together they work. Alternatively, people can also be grouped to share a vehicle based on the extent to which all of their origins and destinations lie on a straight line.
Several existing products, primarily Internet websites, provide ride-matching services. None of the existing products, however, other than those identified herein as implementations of the present invention, include all four key elements of a complete and maximally efficient ride-matching process, those four elements being full computerization to provide instant automatic results without requiring Human intervention, the capability to match routes with a degree of precision necessary to quantify preferability between matches within short walking distances (less than 100 yards), the capability to function anywhere on the planet using existing global locating references, and the ability to perform efficiently independent of the quantity of stored routes.
Accordingly, the present invention is the first method and system that is fully automatic, precise within short walking distances (less than 100 yards), applicable anywhere on Earth using existing global locating references, and efficient at all levels of quantity of stored routes.
The invention is currently implemented both as the operating Internet website www.carpoolworld.com and as a downloadable software application available at that website.
SUMMARY OF THE INVENTION
The present invention achieves all of the objectives described above by providing a computer-implementable method of storing routes and matching stored routes to a given route that is computationally-efficient.
To make the system precise and globally-applicable, it is based on the direct use of standard latitude and longitude coordinates. Several free publicly available resources, including the Internet websites of the United States Geological Survey and the United States Census Bureau, provide latitude and longitude information. Some websites provide geographic information for specific street addresses in the United States, Canada and several European countries, providing latitude and longitude coordinates to a precision of approximately 6 inches. Some websites provide a graphical point-and-click capability to obtain the latitude and longitude coordinates for any point on the planet's surface. Additionally, Global Positioning System (GPS) devices can be obtained by the public that provide latitude and longitude information readings wherever they are used on the planet to a precision of about 30 feet. Additional resources are available in various printed reference resources.
To make the system computationally-efficient, routes are stored in a standard relational database management system (RDBMS) using multiple indexes that automatically order the routes simultaneously by origin latitude, origin longitude, destination latitude and destination longitude. When a required route is specified, the system uses configurable radii to establish target ranges for each of the four locating numbers, allowing the extraction process to efficiently identify the subset of best matches before making the computational effort to access the full set of data for each route and before computing all the distances.
Once the subset of best matches is identified, the system uses an efficient mathematical equation to calculate the distances. The selection, computation and ordering of the routes is done using a standard SQL (Structured Query Language) statement.
Although it will be apparent to all those skilled in the art that the straight-line calculations do not take into consideration actual road network layouts, in point of fact, for the purposes of the intended application, the layout of actual road networks is not relevant. For example, in the cases of two neighbors residing on back-to-back properties or at opposite ends of a neighborhood park, the direct-line distance between their homes is more important than the street-wise path from one driveway to the other. Similarly, the precise length of the navigational distance between each origin and its destination is not relevant to the objective of matching the origins to eachother and matching the destinations to eachother.
Also, it will be apparent to those skilled in the art that the mathematical formulae employed in the present invention provide mathematical approximations and are subject to various problems resulting from the exact geometry of the planet. In fact, many variables, such as topographical variations, unpredictable road-work situations and the general complexities of the planetary shape adversely affect the ability to calculate precise distances. However, since the necessary objective of the formulae used in the present invention is to distinguish between closely-placed (less than a 100 yards) locations, the formula used is accurate and consistent and efficient.


REFERENCES:
patent: 5523950 (1996-06-01), Peterson
patent: 5799263 (1998-08-01), Culbertson et al.
patent: 5835716 (1998-11-01), Hunt et al.
patent: 5845228 (1998-12-01), Uekawa et al.
patent: 5880958 (1999-03-01), Helms et al.
patent: 5922040 (1999-07-01), Prabhakaran et al.
patent: 6014607 (2000-01-01), Yagyu et al.
patent: 6088648 (2000-07-01), Shah et al.
patent: 6182008 (2001-01-01), Nikiel et al.
patent: 6192314 (2001-02-01), Khavakh et al.
patent: 6253146 (2001-06-01), Hanson et al.
patent: 2001/0037174 (2001-11-01), Dickerson
patent: 2001/0056363 (2001-12-01), Gantz et al.
Carpool Matching Website Can Be Used By Any Commuter, Worldwide; The Urban Transportation Monitor; Jul. 20, 2001; vol. 15, No. 14.*
Carpoolworld.com Revolutionizes Carpool Matching; Press Release; Jul. 12, 2001; Datasphere Corporation; www.carpoolworld.com.*
Prasuna DVG Reddy GIS Based Real-Time Rideshare Matching 1994, 7 pages Academic Paper ITS, Uni. of California, Davis, CA-95616. internet url: www.odyssey.maine.edu/gisweb/spatdb/gis-lis/gi94082.html.
Meridian World Data (web page) Distance Calculations Last updated: Mar. 30, 2001, 4 pages internet url: www.meridianworlddata.com/distancecalculation.asp.
D.J. Dailey et al. Seattle smart traveler Jan. 12, 1997, 13 pages internet url: www.its.washington.edu/pubs/trb97sst.pdf.

Affiliated with

Also associated with

Rating

Matching stored routes to a required route does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Matching stored routes to a required route, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matching stored routes to a required route will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3330961