Data formats and usage for massive point-to-point route calculation
a data format and point-to-point route technology, applied in the direction of traffic control systems, navigation instruments, instruments, etc., can solve the problems of large load time for these huge problems, difficult to determine the scheduling and mapping of the paths between the points, and difficult to map the travel times in large numbers
Inactive Publication Date: 2006-05-23
GEOTAB
View PDF16 Cites 10 Cited by
- Summary
- Abstract
- Description
- Claims
- Application Information
AI Technical Summary
Problems solved by technology
But when the number of nodes and edges is large, say as in a high density metropolitan area or in a large geographic area, the determination of scheduling and mapping the paths between the points may be an enormous task, due to the large number of possible node-edge computations.
This complexity makes the mapping of travel times in large numbers problematic.
Additionally, the load time for these huge problems is also quite large.
However, this approximation lends to inherent error in the travel times, since the edges are not completely modeled and since the node locations are only approximated.
This problem is also typical in systems utilizing scheduling or travel values based on zip code.
However, these coarse solutions do offer the ability to encompass solutions for large regions, at the expense of accuracy.
Additionally, these coarse solutions cannot employ explicit path determinations.
As such, many typical travel time solutions suffer from deficiencies in providing accurate solutions.
Others, using an opposite approach, suffer in computational size and speed for large detailed solutions.
Method used
the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View moreExamples
Experimental program
Comparison scheme
Effect test
Embodiment Construction
[0029]In the present invention, transit data is converted to weighted path information. The weighted path information is then optimized. This may be by, for example, a modified Dijkstra shortest path algorithm to determine optimal transit times given a specific road network. For purposes of the invention, the nodes translate to sources and destinations, and the weighted paths are associated with formatted data structures that indicate path information on the road network, as well as travel value weights.
[0030]In a geographic example, roadway information may be in a TIGER format and converted to a format easier to work with, such as that described later in this document. Or, other network information formats may be converted, such that the information may be represented in an edge-node fashion.
[0031]It should be noted that any delivery, transit, or network topology might be converted to such node and edge topology. In this manner, all number of transit systems may be included by refe...
the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more PUM
Login to view more Abstract
The invention is directed to a method by which optimal paths are found between one or more start destinations and one or more end destinations. First destination and travel data is converted into a node and edge data format, wherein the nodes represent start points and the the edges have a weight related to a travel weight. These nodes and edges are subdivided into subsets. The paths between the start nodes and each of the end nodes are determined using the node and edge representations stored in the subsets. A selected union of subsets is determined that contains the start end end destinations. The optimal paths are determined by using the travel values associated with the edges connecting the nodes. The union of subsets, which may comprise less than the full amount of subsets, is loaded for the path determination. Or, when the path determination perceives that a relevant boundary has been reached in a path determination, that next subset in the union of subsets is loaded. The newly loaded subset is “joined” to the already loaded subsets, thus allowing the completion of the path determination.
Description
[0001]This application claims priority of U.S. patent Application, Ser. No. 60 / 184,186, filed Feb. 22, 2000 entitled: “Data Formats and Usage for Massive Point to Point Route Calculation”, and is incorporated herein by reference in its entirety.BACKGROUND OF THE INVENTION[0002]1. Field of the Invention[0003]The present invention generally relates to a dynamic mapping and scheduling apparatus and method. In particular, the present invention relates to such a mapping and scheduling system that may be employed in a computerized and / or networked environment, and employs multiple subsets of weighted path data.[0004]2. Description of Prior Art[0005]Many typical mapping and scheduling systems determine a schedule or time of arrival based upon the lengths of arcs between several points. In this manner, these systems employ data representations of points and paths as nodes and edges. This scheduling is applicable to many different applications, including shipping, delivery routes, airline or...
Claims
the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more Application Information
Patent Timeline
Login to view more Patent Type & Authority Patents(United States)
IPC IPC(8): G06F17/00G01C21/34G06Q10/00
CPCG06Q10/047G01C21/3446
Inventor POWELL, G. EDWARDCHEN, SHENGINDSETH, RUNAR
Owner GEOTAB
Who we serve
- R&D Engineer
- R&D Manager
- IP Professional
Why Eureka
- Industry Leading Data Capabilities
- Powerful AI technology
- Patent DNA Extraction
Social media
Try Eureka
Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.
© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap