HORIZONTAL OPTIMIZATION OF TRANSPORT ALIGNMENTS

• US 20150154323A1
• Filed: 10/31/2014
• Published: 06/04/2015
• Est. Priority Date: 09/27/2011
• Status: Active Grant

• Current Assignee: Autodesk, Inc.
• Original Assignee: Autodesk, Inc.
• Inventors: Koch, Valentin R., Liu, Song
• Granted Patent: US 10,606,962 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 30/13 Architectural design, e.g. computer-aided architectural design [CAAD] related to design of buildings, bridges, landscapes, production plants or roads

Abstract

A method, apparatus, system, article of manufacture, and computer program product provide the ability to optimize a transport alignment. Terrain data, constraint data, and cost data are read. Terrain pixels having elevation values are organized and stored in a first grid structure with rows and columns that enable efficient access to each terrain pixel. One or more raster layers of a same dimension and orientation as the first grid structure are created. A starting alignment is obtained. The starting alignment is then optimized using the one or more raster layers.

Claims

1. A computer-implemented method for optimizing transport alignments, comprising:

reading terrain data, constraint data, and cost data;

organizing and storing one or more terrain pixels, comprising elevation values, in a first grid structure comprising rows and columns to enable efficient access to each terrain pixel;

creating one or more raster layers of a same dimension and orientation as the first grid structure;

obtaining a starting alignment; and

optimizing the starting alignment using the one or more raster layers.

2. The computer-implemented method of claim 1, wherein a first raster layer of the one or more raster layers comprises water data.

3. The computer-implemented method of claim 2, wherein a second raster layer of the one or more raster layers comprises an avoidance zone.

4. The computer-implemented method of claim 1, wherein a first layer of the one or more of the raster layers comprises hard costs that are quantifiable in monetary values.

5. The computer-implemented method of claim 1, wherein a first layer of the one or more of the raster layers comprises soft costs that are not quantifiable in monetary values.

6. The computer-implemented method of claim 1, wherein the obtaining a starting alignment comprises:

(a) obtaining a start point and an end point;

(b) producing a second grid structure wherein;

(1) the second grid structure is coarser than the first grid structure; and

(2) one or more edges, of the second grid structure, connect grid points horizontally, vertically, and diagonally;

(c) for each of the one or more edges;

(1) computing a cost corresponding to an alignment segment that connects the grid points of each edge;

(d) determining, based on the cost for each of the one or more edges, a first cheapest discrete path on the second grid structure;

(e) smoothing the first cheapest discrete path to create a smoothed cheapest discrete path; and

(f) selecting the smoothed cheapest discrete path as the starting alignment.

7. The computer-implemented method of claim 6, wherein the cost comprises earthwork and construction costs.

8. The computer-implemented method of claim 6, wherein the cost comprises a weighted and scaled combination of values from stored cost layers that lay under a portion of the alignment segment.

9. The computer-implemented method of claim 6, wherein the selecting the smoothed cheapest discrete path as the starting alignment comprises:

taking the smoothest cheapest discrete path and minimizing a distance between the smoothest cheapest discrete path and the first cheapest discrete path using an optimization method.

10. The computer-implemented method of claim 1, wherein the optimizing utilizes a covariance matrix adaptation evolution strategy (CMA-ES).

11. The computer-implemented method of claim 1, wherein the optimizing comprises:

(a) utilizing the starting alignment as an evaluating alignment;

(b) projecting the evaluating alignment along a centerline onto the first grid structure;

(c) reading one or more points where one or more tangents, of the evaluating alignment, intersect with the first grid structure;

(d) storing, based on the one or more points, one or more elevation values to produce a first profile;

(e) reading the one or more elevation values and a corresponding soft cost value;

(f) obtaining, using the first profile, hard costs that are quantifiable in monetary values;

(g) adding the soft cost value to the hard costs to determine an alignment cost;

(h) changing a point of intersection configuration to provide a different evaluating alignment and repeating steps (b)-(g) for the changed point of intersection configuration to determine an additional alignment cost;

(i) comparing the alignment cost and the additional alignment cost to determine the cheapest alignment cost;

(j) storing the alignment corresponding to the cheapest alignment cost; and

(k) returning the stored alignment to a user.

12. The computer-implemented method of claim 11, further comprising:

producing one or more offset second profiles, to a left and right of the centerline, to obtain additional elevation values.

13. The computer-implemented method of claim 11, wherein:

the optimizing is performed on multiple alignments in parallel utilizing different weights for soft costs.

14. The computer-implemented method of claim 11, wherein the adding the soft cost value to the hard costs comprises:

h(x)+λ

h(x)s(x)+p(x),

where h(x) is the hard costs, s(x) is the soft cost value, p(x) is a penalty cost for violating a constraint, and λ

is a weight factor that weights the soft cost value relative to the hard costs.

15. A non-transitory computer readable storage medium encoded with computer program instructions which when accessed by a computer cause the computer to load the program instructions to a memory therein creating a special purpose data structure causing the computer to operate as a specially programmed computer, executing a method of optimizing transport alignments, comprising:

reading, in the specially programmed computer, terrain data, constraint data, and cost data;

organizing and storing, in the specially programmed computer, one or more terrain pixels comprising elevation values in a first grid structure comprising rows and columns to enable efficient access to each terrain pixel;

creating, in the specially programmed computer, one or more raster layers of a same dimension and orientation as the first grid structure;

obtaining, in the specially programmed computer, a starting alignment; and

optimizing, in the specially programmed computer, the starting alignment using the one or more raster layers.

16. The non-transitory computer readable storage medium of claim 15, wherein a first raster layer of the one or more raster layers comprises water data.

17. The non-transitory computer readable storage medium of claim 16, wherein a second raster layer of the one or more raster layers comprises an avoidance zone.

18. The non-transitory computer readable storage medium of claim 15, wherein a first layer of the one or more of the raster layers comprises hard costs that are quantifiable in monetary values.

19. The non-transitory computer readable storage medium of claim 15, wherein a first layer of the one or more of the raster layers comprises soft costs that are not quantifiable in monetary values.

20. The non-transitory computer readable storage medium of claim 15, wherein the obtaining a starting alignment comprises:

(a) obtaining, in the specially programmed computer, a start point and an end point;

(b) producing, in the specially programmed computer, a second grid structure wherein;

(1) the second grid structure is coarser than the first grid structure; and

(2) one or more edges, of the second grid structure, connect grid points horizontally, vertically, and diagonally;

(c) for each of the one or more edges;

(1) computing, in the specially programmed computer, a cost corresponding to an alignment segment that connects the grid points of each edge;

(d) determining, in the specially programmed computer, based on the cost for each of the one or more edges, a cheapest path on the second grid structure;

(e) smoothing, in the specially programmed computer, the cheapest path; and

(f) selecting, in the specially programmed computer, the smoothed cheapest path as the starting alignment.

21. The non-transitory computer readable storage medium of claim 20, wherein the cost comprises earthwork and construction costs.

22. The non-transitory computer readable storage medium of claim 20, wherein the cost comprises a weighted and scaled combination of values from stored cost layers that lay under a portion of the alignment segment.

23. The non-transitory computer readable storage medium of claim 20, wherein the selecting the smoothed cheapest discrete path as the starting alignment comprises:

taking the smoothest cheapest discrete path and minimizing a distance between the smoothest cheapest discrete path and the first cheapest discrete path using an optimization method.

24. The non-transitory computer readable storage medium of claim 15, wherein the optimizing utilizes a covariance matrix adaptation evolution strategy (CMA-ES).

25. The non-transitory computer readable storage medium of claim 15, wherein the optimizing comprises:

(a) utilizing, in the specially programmed computer, the starting alignment as an evaluating alignment;

(b) projecting, in the specially programmed computer, the evaluating alignment along a centerline onto the first grid structure;

(c) reading, in the specially programmed computer, one or more points where one or more tangents, of the evaluating alignment, intersect with the first grid structure;

(d) storing, in the specially programmed computer, based on the one or more points, one or more elevation values to produce a first profile;

(e) reading, in the specially programmed computer, the one or more elevation values and a corresponding soft cost value;

(f) obtaining, in the specially programmed computer, using the first profile, hard costs that are quantifiable in monetary values;

(g) adding, in the specially programmed computer, the soft cost value to the hard costs to determine an alignment cost;

(h) changing, in the specially programmed computer, a point of intersection configuration to provide a different evaluating alignment and repeating steps (b)-(g) for the changed point of intersection configuration to determine an additional alignment cost;

(i) comparing, in the specially programmed computer, the alignment cost and the additional alignment cost to determine the cheapest alignment cost;

(j) storing, in the specially programmed computer, the alignment corresponding to the cheapest alignment cost; and

(k) returning, in the specially programmed computer, the stored alignment to a user.

26. The non-transitory computer readable storage medium of claim 25, further comprising:

producing one or more offset second profiles, to a left and right of the centerline, to obtain additional elevation values.

27. The non-transitory computer readable storage medium of claim 25, wherein:

the optimizing is performed on multiple alignments in parallel utilizing different weights for soft costs.

28. The non-transitory computer readable storage medium of claim 25, wherein the adding the soft cost value to the hard costs comprises:

h(x)+λ

h(x)s(x)+p(x),

where h(x) is the hard costs, s(x) is the soft cost value, p(x) is a penalty cost for violating a constraint, and λ

is a weight factor that weights the soft cost value relative to the hard costs.