Methods and systems for optimizing network travel costs

• US 8,332,247 B1
• Filed: 02/06/2007
• Issued: 12/11/2012
• Est. Priority Date: 06/12/1997
• Status: Expired due to Fees

• Current Assignee: Bailey G. William
• Original Assignee: Bailey G. William
• Inventors: Bailey, G. William, Huber, William A.
• Primary Examiner(s): Sterrett, Jonathan G
• Assistant Examiner(s): Lan, Tzu-Hsiang
• Application Number:
  US11/702,627
• Time in Patent Office: 2,135 Days
• Field of Search: None
• US Class Current: 705/7.11
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: G06Q 30/0206 Price or cost determination based on market factors
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

Methods and systems optimize travel costs both on and off a sequence of one or more networks used to represent travel, communication, or transport of anything within a spatial medium. Such systems and methods can develop a data structure for optimizing travel costs for a region having an embedded network. The data structure includes a grid representation of the region having an array of cells covering the region, an optimal-cost grid dataset containing optimal costs for travel between an initial location in the region and cells in the grid, a hybrid grid-network dataset representing travel costs within the network, within the grid, and between the network and the grid, and back-links among elements of the hybrid grid-network dataset, reflecting optimal travel routes originating at the initial location. Methods and systems also include querying the datasets of the data structure to generate a route with an optimal travel cost from the initial location to a query point.

Claims

1. A computer-implemented method for computing travel costs across a region having an embedded network, the method comprising steps, performed by a computer, of:

obtaining data associated with the network, the network comprising nodes and edges connecting the nodes, wherein the data associated with the edges indicates (i) allowed directions of travel along the edges, (ii) total travel costs to traverse the edges, and (iii) whether the edges are accessible;

obtaining a grid representing the region, the grid comprising a plurality of cells covering the region and representing unit costs of travel across the cells;

preparing a cost-grid dataset comprising costs for off-network travel between an initial location in the region and the plurality of cells in the grid;

preparing, using the computer, a hybrid grid-network dataset comprising network travel costs between nodes of the network, the off-network travel costs between cells of the grid, and travel costs between the network and the grid, wherein the preparing step comprises;

rasterizing accessible edges of the network to locate grid cells connecting the network with the grid;

identifying, based on the rasterized edges, one or more of the plurality of cells of the grid that are accessible to the network; and

computing the network travel costs associated with travel between the nodes of the network, and the travel costs between the nodes of the network and connected grid cells;

calculating back-links between elements of the hybrid grid-network dataset, the back-links reflecting travel routes originating at the initial location;

storing, using a storage device, the prepared hybrid grid-network dataset and the calculated back-links; and

querying the hybrid grid-network dataset and the calculated back-links to identify a route with a minimum travel cost from the initial location to a query point within the region.

2. The method of claim 1, wherein the cost-grid dataset further comprises costs for off-network travel from a group of initial locations in the region.

3. The method of claim 1, wherein the initial location in the region includes points off the network.

4. The method of claim 1, wherein the elements of the hybrid grid-network include centers of cells in the grid and nodes of the network.

5. The method of claim 1, further comprising reporting the minimum travel cost.

6. The method of claim 1, further comprising:

providing a set of initial locations within the region; and

initializing one or more of the hybrid grid-network and cost-grid datasets.

7. The method of claim 6, wherein the step of initializing the datasets includes:

labeling each initial location in the set with a zero cost;

initializing the costs in the cost-grid dataset to infinity; and

nullifying the back-links between elements of the hybrid grid-network dataset.

8. The method of claim 1, wherein the step of obtaining the grid includes:

computing unit costs of travel as a function of location or other attributes of points in the region.

9. The method of claim 6, wherein the step of preparing the cost-grid dataset includes:

computing costs and back-links to travel along the grid to a nearest accessible node of the network from each of the set of initial locations.

10. The method of claim 1, wherein:

the step of calculating the back links comprises;

computing minimum costs and back-links for traveling from cell to cell in the grid of the region beginning at the accessible network nodes in the network; and

the method further comprises;

updating the cost-grid dataset using the back-links in the network; and

updating the hybrid grid-network dataset with the back-links corresponding to the minimum costs.

11. The method of claim 1, further comprising:

obtaining data associated with one or more additional networks; and

repeating, for the one or more networks, the steps of preparing the hybrid grid-network dataset, calculating the back-links, storing the hybrid grid-network dataset and the calculated back-links, and querying the hybrid grid-network dataset and the calculated back-links.

12. The method of claim 1, wherein the step of rasterizing the accessible edges includes:

creating a raster representation of the accessible edges;

interpolating costs along the accessible edges based on costs at endpoint nodes; and

copying the interpolated costs to corresponding cells.

13. The method of claim 10 further including:

halting the computation of minimum costs and back-links upon reaching a predetermined cost limit.

14. The method of claim 10, further including:

halting the computation of minimum costs and back-links upon reaching a predetermined distance limit.

15. A system for computing travel costs across a region having an embedded network, comprising:

means for obtaining a data associated with the network, the network comprising nodes and edges connecting the nodes, wherein the data associated with the edges indicates (i) allowed directions of travel along the edges, (ii) total travel costs to traverse the edges, and (iii) whether the edges are accessible;

means for obtaining a grid representing the region, the grid comprising a plurality of cells covering the region unit costs of travel across the cells;

means for preparing a cost-grid dataset comprising costs for off-network travel between an initial location in the region and the plurality of cells in the grid;

means for preparing a hybrid grid-network dataset representing network travel costs between the nodes of the network, the off-network travel costs between cells of the grid, and travel costs between the network and the grid, wherein the means for preparing comprises;

means for rasterizing accessible edges of the network to locate grid cells connecting the network with the grid;

means for identifying, based on the rasterized edges, one or more of the plurality of cells of the grid that are accessible to the network; and

means for computing the network travel costs associated with travel between the nodes of the network, and the travel costs between the nodes of the network and connected grid cells;

means for calculating back-links between elements of the hybrid grid-network dataset, the back-links reflecting travel routes originating at the initial location;

means for storing, using a storage device, the prepared hybrid grid-network dataset and the calculated back-links; and

means for querying the hybrid grid-network dataset and the calculated back-links to identify a route with a minimum travel cost from the initial location to a query point within the region.

16. The system of claim 15, wherein the cost-grid dataset further comprises costs for off-network travel from a group of initial locations in the region.

17. The system of claim 15, wherein the initial location in the region includes points off the network.

18. The system of claim 15, wherein the elements of the hybrid grid-network comprise centers of cells in the grid and nodes of the network.

19. The system of claim 15, further comprising means for reporting the minimum travel cost.

20. The system of claim 15, further comprising:

means for providing a set of initial locations within the region; and

means for initializing one or more of the cost-grid and hybrid grid-network datasets.

21. The system of claim 20, wherein the means for initializing the datasets includes:

means for labeling each initial location in the set with a zero cost;

means for initializing the costs in the cost-grid dataset to infinity; and

means for nullifying the back-links in the hybrid grid-network dataset.

22. The system of claim 20, wherein the means for obtaining the grid includes:

computing the unit costs of travel as a function of location or other attributes of points in the region.

23. The system of claim 20, wherein the means for the cost-grid dataset includes:

means for computing costs and back-links to travel along the cost grid to a nearest accessible node of the network from each of the set of initial locations.

24. The system of claim 15, wherein

the means for calculating the back-links comprises:

means for computing minimum costs for traveling from cell to cell in the region beginning at the accessible network nodes in the network; and

the system further comprises;

means for updating the cost-grid dataset using the back-links of the network; and

means for updating the hybrid grid-network dataset with back-links corresponding to the minimum costs.

25. The system of claim 15, further comprising:

means for obtaining data associated with one or more additional networks; and

means for repeating, for the one or more additional networks, the steps of preparing the hybrid grid-network dataset, calculating the back-links, storing the hybrid grid-network dataset and the calculated back-links, and querying the hybrid grid-network dataset and the calculated back-links.

26. The system of claim 15, wherein the means for rasterizing the accessible edges includes:

means for creating a raster representation of the accessible edges;

means for interpolating costs along the accessible edges based on costs at endpoint nodes; and

means for copying the interpolated costs to corresponding cells.

27. The system of claim 24, further including:

means for halting the computation of minimum costs and back-links upon reaching a predetermined cost limit.

28. The system of claim 24, further including:

means for halting the computation of minimum costs and back-links upon reaching a predetermined distance limit.

29. A computer-readable medium containing instructions, when executed by a computer, for performing a method for computing travel costs across a region having an embedded network, the method comprising:

obtaining data associated with the network, the network comprising nodes and edges connecting the nodes, wherein the data associated with the edges indicates (i) allowed directions of travel along the edges, (ii) total travel costs to traverse the edges, and (iii) whether the edges are accessible;

obtaining a grid representing the region, the grid comprising a plurality of cells covering the region and representing unit costs of travel across the cells;

preparing a cost-grid dataset comprising costs for off-network travel between an initial location in the region and the plurality of cells in the grid;

preparing, using the computer, a hybrid grid-network dataset representing network travel costs between nodes of the network, the off-network travel costs between cells of the grid, and travel costs between the network and the grid, wherein the preparing step comprises;

rasterizing accessible edges of the network to locate grid cells connecting the network with the grid;

identifying, based on the rasterized edges, one or more of the plurality of cells of the grid that are accessible to the network; and

computing the network travel costs associated with travel between the nodes of the network, and the travel costs between the nodes of the network and connected grid cells;

calculating back-links between elements of the hybrid grid-network dataset, the back-links reflecting travel routes originating at the initial location;

storing, using a storage device, the prepared hybrid grid-network dataset and the calculated back-links; and

querying the hybrid grid-network dataset and the calculated back-links to identify a route with a minimum travel cost from the initial location to a query point within the region.

30. A computer-implemented method for determining a market area, the method comprising steps, performed by a computer, of:

receiving a potential market location and a maximum travel time;

defining a preliminary market area around the potential market location using the maximum travel time from that potential market location;

defining, within the preliminary market area, bands reflecting increasing travel time from the potential market location;

weighting the bands according to a market-related factor; and

determining a final market area based on the weighted bands,

wherein defining bands includes;

obtaining data associated with the network, the network comprising nodes and edges connecting the nodes, wherein the data associated with the edges indicates (i) allowed directions of travel along the edges, (ii) total travel costs to traverse the edges, and (iii) whether the edges are accessible;

obtaining a grid representing the region associated with the market area, the grid comprising a plurality of cells covering the region and representing unit costs of travel across each cell;

preparing a cost-grid dataset comprising costs for off-network travel between an initial location in the region and the plurality of cells in the grid;

preparing, using the computer, a hybrid grid-network dataset representing network travel costs between the nodes of the network, the off-network travel costs between cells of the grid, and travel costs between the network and the grid, wherein the preparing step comprises;

rasterizing accessible edges of the network to locate grid cells connecting the network with the grid;

identifying, based on the rasterized edges, one or more of the plurality of cells of the grid that are accessible to the network; and

computing the network travel costs associated with travel between the nodes of the network, and the travel costs between the nodes of the network and connected grid cells;

calculating back-links between elements of the hybrid grid-network dataset, the back-links reflecting travel routes originating at the initial location;

storing, using a storage device, the prepared hybrid grid-network dataset and the calculated back-links; and

querying the hybrid grid-network dataset and the calculated back-links to identify a route with a minimum travel cost from the initial location to a query point within the region.

31. A system for determining a market area, the system comprising:

means for receiving a potential market location and a maximum travel time;

means for defining a preliminary market area around the potential market location using the maximum travel time from that potential market location;

means for defining, within the preliminary market area, bands reflecting increasing travel time from the potential market location;

means for weighting the bands according to a market-related factor; and

means for determining a final market area based on the weighted bands,

wherein means for defining bands includes;

means for obtaining a data associated with the network, the network comprising nodes and edges connecting the nodes, wherein the data associated with the edges indicates (i) allowed directions of travel along the edges, (ii) total travel costs to traverse the edges, and (iii) whether the edges are accessible;

means for obtaining a grid representing the region associated with the market area, the grid comprising a plurality of cells covering the region and representing unit costs of travel across each cell;

means for preparing a cost-grid dataset-comprising costs for off-network travel between an initial location in the region and the plurality of cells in the grid;

means for preparing a hybrid grid-network dataset representing the network travel costs between nodes of the network, the off-network travel costs between cells of the grid, and travel costs between the network and the grid, wherein the means for preparing comprises;

means for rasterizing accessible edges of the network to locate grid cells connecting the network with the grid;

means for identifying, based on the rasterized edges, one or more of the plurality of cells of the grid that are accessible to the network; and

computing the network travel costs associated with travel between the nodes of the network, and the travel costs between the nodes of the network and connected grid cells;

means for calculating back-links between elements of the hybrid grid-network dataset, the back-links reflecting travel routes originating at the initial location;

means for storing, using a storage device, the prepared hybrid grid-network dataset and the calculated back-links; and

means for querying the hybrid grid-network dataset and the calculated back-links to identify a route with a minimum travel cost from the initial location to a query point within the region.