US 6,996,507 B1Grant
Computer-implemented method and system for designing transportation routes
Issue Date:2006-02-07
•27 Claims
•6 Drawing Sheets
Abstract
A computer-implemented method and system for designing transportation routes, wherein design criteria to be met in respect of at least one of said transportation routes are supplied and route profile data are obtained showing land heights at sampled points along each of said at least one transportation route. Per-unit cost estimates in respect of land-cut and land-fill operations are supplied, and a height profile is computed of the at least one transportation route which meets the design criteria and for which the land-cut and land-fill operations are adjusted to give a minimum cost.
Metadata
Assignee
- Makor Issues and Rights Ltd.
Inventor
- David Myr
Application Information
Application Number:US 09/831,093
Filing Date:1999-10-13
Priority Date:1998-11-09
Art Unit:2128
Classifications
IPC:
G06F17/10G06F17/60
Patent Drawings (6 sheets)
Description
Field of the Invention
[0001] This invention relates to techniques for designing transport routes.
Background of the Invention
[0002] Conventional approaches to the road design rely on separate design for each road system. Thus, the design of road systems usually begins with the planning stage where a civil engineer arranges the road to satisfy the standard specifications such as grade and meeting of centerlines at intersections. Then a draftsman produces an initial design using one of numerous software programs to draft profiles, vertical alignment, measure cross-sections and calculate the cut and fill quantities. In this connection, it will be appreciated that road surfaces are generally not level. Whenever a gradient is associated with the road surface, this requires that, during construction, earth be removed (“cut”) from those sections which are lower than the foundation level and that earth be added to those sections which are higher than the foundation level and must therefore be “filled”. Such earthworks require skilled operation of heavy and expensive machinery and is therefore highly costly. It is therefore desirable, as far as is possible, to equalize the cut and fill quantities so as to avoid unnecessary earthworks.
[0003] Such equalization is an iterative process requiring repeated fine-tuning by the engineer. The iteration may be repeated numerous times before the road system satisfies all of the physical constraints and the cut and fill quantities are properly balanced. Conventionally, the design has been a trial and error affair according to the experience of the civil engineer. The vertical alignment is determined for one road at a time and not for the entire road system. Earthworks of subdivision lots which border transportation routes have also not conventionally been taken into account, nor has the economical factor been properly considered.
[0004] A CAD approach to the design of rail tracks is presented by L. G. Allen et al. in “Cost Effective Design—The Use of Computer Aided Drafting In: Route Selection, Earthworks Optimisation and Rail Track Engineering” appearing in Conference on Railway Engineering, Perth/Australia, September 1987; XP-000917757. However, this article makes no reference to minimization of earthworks cost. Rather it attempts to achieve cost-effective design using an interactive CAD process. Thus, cost effectiveness is the result of user's interactive work (i.e. trial and error) and is not an automatic computerized process that uses pre-prepared data allowing the route to be optimized without any user interaction. In this respect, the CAD tools disclosed by this article are typical of prior art methods that relate on trial and error for optimizing transportation routes.
Summary of the Invention
[0005] A principal the object of the invention is thus to develop a method of road design that results in lower construction cost.
[0006] A further object of the invention is to facilitate comparison of different layouts and different unit prices so as to obtain better cost-effectiveness during the preliminary planning stage.
[0007] According to a broad aspect of the invention there is provided a computer-implemented method for designing transportation routes, the method comprising the steps of:
-
- [0008] (a) supplying linear constraints of allowable grades to be met in respect of at least one of said transportation routes,
- [0009] (b) obtaining route profile 3-D coordinates showing land heights at sampled points along each of said at least one transportation route prior to construction thereof,
- [0010] (c) supplying cost estimates per working unit in respect of land-cut and land-fill operations, and
- [0011] (d) computing a height profile of said at least one transportation route which meets said constraints and for which said land-cut and land-fill operations are adjusted to give a minimum cost by replacing all non-linear constraints by equivalent linear constraints so as to render the height profile solving using standard linear programming tools.
[0012] Such a method establishes a direct relationship between prevailing economic conditions and the status of the transportation system as a technical entity. The method according to the invention utilizes customized optimization which operate on raw data generated by a computer-aided design (CAD) program. Such raw data includes: topography, roads centerlines plan, road cross-sections and earthwork unit prices. It is to be noted that the invention is also applicable to railway transport systems, and within the context of the following description and claims, a “transport system” is any highway system comprising one or more roads, pedestrian routes or rail tracks or a combination thereof. The invention is of particular benefit for the optimization of complete transport systems having many intersecting roads or rail tracks, whilst nevertheless being applicable to the design of single transport routes only.
Brief Description of the Drawings
[0013] In order to understand the invention and to see how it may be carried out in practice, a preferred embodiment will now be described, by way of non-limiting example only, with reference to the accompanying drawings, in which:
[0014] FIG. 1 is a flow diagram showing the principal operating steps associated with a method of road design according to the invention;
[0015] FIG. 2 shows schematically a relation between grid and control points for grid optimization;
[0016] FIG. 3 shows pictorially a “Fill-Cut” geometrical presentation for a centerline linear model objective function;
[0017] FIG. 4 shows pictorially a relative proposed unsigned elevations for centerline nonlinear model objective function; and
[0018] FIG. 5 is a block diagram showing functionally a system for optimizing cut and fill costs for a transportation route in accordance with the invention.
Detailed Description of a Preferred Embodiment
[0019] FIG. 1 is a flow diagram showing the principal steps associated with an optimization process according to the invention using linear or nonlinear programming. Three approaches are described differing in the number of variables and the performance time.
[0020] 1. Grid Optimization Approach:
[0021] The optimization is reached through nonlinear programming when the objective is to minimize the total cost of the earthworks. The required variables are differences between proposed road elevations and existing topography elevations at all grid points on the right of way. The relevant constraints are prevailing roads standards.
[0022] FIG. 2 shows in plan view a road surface 10 having superimposed thereon an imaginary matrix of grid points designated GP each being a node point of a rectangular grid of definite size (e.g. 5 m×5 m) that are located on the right of way. Boundary grid points designated BGP are grid points located on edges of roads, i.e. points for which distance to the road centerline is equal to half of the road width (with some tolerance). Boundary grid points are used for cost estimation of retaining walls which support the earth under the road surface when the surface of the road is higher than that of the surrounding landscape, thus requiring earth to be filled to the level of the road surface. Likewise, retaining walls are built when the level of the surrounding landscape is higher than that of the road surface, thus requiring the earth to be cut down to the level of the road surface. In this case, the retaining walls serve the function of preventing rubble from falling on to the road surface. Both grid points and boundary grid points are quantified by coordinates in 3-dimensional space.
[0023] Also shown are control points designated CP being 3D points on the proposed centerlines of the road system (e.g. every 100 m). As shown in FIG. 2 , control points are not necessarily coincident with grid points. The gradient or “grade” of a road can be changed only at control points, such that each road section spanning a pair of control points is linear.
[0024] Referring back to FIG. 1 , respective X and Y coordinates of control points and grid points are entered as input data and coordinates Z are an output of the optimization procedure. Preferably, control points are located at points of centerlines where grades of the existing profile are changed, in order to improve the optimization process. Optimization of control points and grid points is formulated as a nonlinear programming task, as follows:
Let GP=Q(X′q,Y′q,Z′q)
Let GP=Q(X′q,Y′q,Z′q)
-
- [0025] where Q is some arbitrary point on the road surface.
[0026] Therefore Q lies on some specific road within the designated road system. There then exist A(Xa,Ya,Za) and B(Xb,Yb,Zb)—adjacent control points on the specific road centerline so that Q is located between A and B. This implies that if Q′ is the nearest point to point Q on the specific road's centerline including A and B, then Q′ is located between A and B. Since Q′ is the point nearest to Q, it follows that Q′ lies on a line perpendicular to the road centerline along which all points are horizontal. Thus, points Q and Q′ must have identical elevations. Therefore for any point Q there exists λ, με[0,1] so that:
Z′q=λ*Za+μ*Zb,
Z′q=λ*Za+μ*Zb,
-
- [0027] Where:
- [0028] Z′q, Za, Zb are proposed elevations of points Q, A, B respectively.
[0029] Seeing that by definition the interval AB is linear then it can be shown that:
λ=(AQ,AB)/(AB,AB)ε[0,1], and
μ=1−λ.
λ=(AQ,AB)/(AB,AB)ε[0,1], and
μ=1−λ.
-
- [0030] where AQ and AB are vectors and μ and λ are simply constants of proportionality each being equal to the respective fractional displacement of the point Q from the points A and B.
[0031] This implies that the proposed elevation of each grid point may be determined by linear interpolation from the proposed elevations of a corresponding pair of control points.
[0032] Let Zq=Z′q−Ze, where Z′q is the proposed elevation and Ze is the existing elevation at point Q.
[0033] The object is to minimize the total cost of the earthworks represented by the following objective function:
-
- [0034] where:
- [0035] G is grid size (e.g. 5 m);
- [0036] Fq(Zq) is cost of fill at point Q, where the proposed GP elevation is higher than the existing GP elevation (Zq>0);
- [0037] Wq(Zq) is cost of retaining wall for fill at point Q, where proposal GP is above existing GP (Zq>0);
- [0038] Cq(Zq) is cost of excavation at point Q, where the proposed GP is lower than the existing GP (Zq<0);
- [0039] Vq(Zq) is cost of retaining wall for excavation at point Q, where proposed GP is below existing GP (Zq<0);
- [0040] D is cost of total difference between fill and excavation volumes moving in or out of entire roads system area.
[0041] If Zq<0 then Wq(Zq)=Fq(Zq)=0; also if Q is not a boundary point then Wq(Zq)=0 since retaining walls are, by definition, built at the road boundary.
[0042] If Zq>0 then Cq(Zq)=Vq(Zq)=0. Here also, if Q is not a boundary point then Vq(Zq)=0.
[0043] Let price of fill=f0 (money unit/volume unit), then
Fq(Zq)=0.5*f0*(|Zq|−Zq),
Fq(Zq)=0.5*f0*(|Zq|−Zq),
[0044] Hence, if Zq<0 then Fq(Zq)=0.
[0045] If excavation price is constant=c0, then
Cq(Zq)=0.5*c0*(|Zq|−Zq).
Cq(Zq)=0.5*c0*(|Zq|−Zq).
[0046] Hence, if Zq>0 then Cq(Zq)=0.
[0047] If excavation price depends on Zq (e.g. due to different geology layers), prices may be entered as a table:
[0048] For 0>ajq>Zq>bjq the corresponding price is Pjq and then:
[0049] If Zq>0, then Cq(Zq)=0.
-
- [0050] Kq is number of different geological layers each having a specified excavation price at the point Q,
- [0051] ajq, bjq —upper and lower depths of jth layer at point Q,
- [0052] Pjq—excavation price of jth layer at point Q (order of layers may be dependent on Q).
- [0053] Pqmax is excavation price for Zq<bKq. (Here Zq, ajq, bjq, bKq<0).
[0054] If Q is BGP, then:
-
- [0055] where:
- [0056] for 0>ej>Zq>fj corresponding price of retaining wall for excavation is Fj denoting different unit costs of a retaining wall for different soil composition and (ej, fj) is an interval having a discrete price for excavating the retaining wall.
- [0057] M is number of levels of wall for excavation prices.
- [0058] Fmax is excavation wall price for Zq<fM<0.
[0059] If Zq>0, then Vq(Zq)=0.
-
- [0060] where:
- [0061] for 0<cj<Zq<dj corresponding price of retaining wall for fill is Wj:
- [0062] L is number of levels of fill wall prices.
- [0063] Wmax is wall price for Zq>dL.
- [0064] If Zq<0, then Wq(Zq)=0.
[0065] Finally:
-
- [0066] where:
- [0067] I is the price of conveying fill deficiency from another site to roads system area;
- [0068] O is the price of removing of redundant fill outside of the roads system area;
- [0069] N is total number of grid points on roads system.
[0070] Constraints include five sets:
-
- [0071] a) Constraints of road surface
Zq=λq*Z′q+μq*Z″q−Zqe+λq*Z′e+μq*Z″e, - [0072] Where:
- [0073] q=1, . . . ,N;
- [0074] Z′q, Z″q are the relative elevations of the adjacent control points A and B having point Q located between them;
- [0075] Zqe is existing elevation at point Q.
- [0076] Z′e, Z″e are existing elevations at adjacent control points.
- [0077] λq, μq are coefficients of linear interpolation of proposal elevation at point Q.
- [0071] a) Constraints of road surface
[0078] The above constraint expresses the requirement that the point Q is realized as the linear interpolation between the control points A and B, thus ensuring uniformity along the path described between points A and B.
[0079] Normally there are more than two grid points on each interval between control points. Therefore Z′q and Z″q can be linearly expressed via each pair Zq1 and Zq2 (except for the case where λq1=λq2 wherein the other pair must be used). This allows elimination of Z′q and Z″q from surface constraints, but imposes the following additional constraints:
-
- [0080] b) Control points relation constraints:
[0081] The above-mentioned linear expressions for Z′q and Z″q via pairs of Zq must be equal to such linear expressions for both adjacent intervals of control points respectively.
-
- [0082] c) Constraints of allowable grades (separately for control points near to intersection (e.g. 50 m) and for other control points).
|H′+Z′−(H+Z)|/D<S, - [0083] for all pairs of adjacent control points;
- [0084] where:
- [0085] H′, H are existing elevations of pair of adjacent control points,
- [0086] Z′, Z are relative elevations of these control points; instead Z′ and Z implicit their linear expressions via corresponding Zq of grid points;
- [0087] D is distance along the road between these control points;
- [0088] S is maximal allowable grade for road, or for intersection (e.g. S=10% or 6%).
- [0089] d) Constraints of intersections: (elevations of intersection points of different roads must be same).
H+Z−(H′+Z′)=0, for all control points at intersections, where H, H′ are the existing elevations at the intersection. That is, at the intersection of two roads, the elevation of each road surface must be identical. - [0090] e) Constraints for lack or excess total fill or excavation volumes:
- [0082] c) Constraints of allowable grades (separately for control points near to intersection (e.g. 50 m) and for other control points).
[0091] The expressions which appear in the objective function shown in Equation (1) include absolute values of the respective differences between variables and parameters, thus rendering the objective function non-linear. However, these absolute values can be transformed into linear form:
[0092] In case of:
-
- [0093] i.e. fill>cut, Equation (1) is reduced as follows:
- [0093] i.e. fill>cut, Equation (1) is reduced as follows:
[0094] It has been noted that the expressions appearing in the objective function contain absolute values, thus rendering the objective function non-linear. This is necessary in order to reflect the fact that regardless of whether material is cut or filled at a particular point, the cost is always positive. On the other hand, because taking absolute values introduces non-linearities, the expression is not amenable to solution using linear programming. In order to allow for the inclusion of absolute expressions whilst also allowing solution by means of linear programming, each of the expressions
-
- [0095] Zq−ai, Zq−bi, Zq−cj, Zq−dj, Zq−ej, Zq−fj is replaced by a pair of new variables, as follows:
(*)Zq−ai=Uqai1−Uqai2, i=1, . . . ,Kq,
(*)Zq−bi=Uqbi1−Uqbi2, i=1, . . . ,Kq,
(*)Zq−bKq=UqbK1−UqbK2;
(*)Zq−cj=Uqcj1−Uqcj2, j=1, . . . ,L,
(*)Zq−dj=Uqdj1−Uqdj2, j=1, . . . ,L,
(*)Zq−dL=UqdL1−UqdL2;
(*)Zq−ej=Uqej1−Uqej2, j=1, . . . ,M,
(*)Zq−fj=Uqfj1−Uqfj2, j=1, . . . ,M,
(*)Zq−fM=UqfM1−UqfM2.
- [0095] Zq−ai, Zq−bi, Zq−cj, Zq−dj, Zq−ej, Zq−fj is replaced by a pair of new variables, as follows:
[0096] In Equation (1) instead of |Zq−ai| substitute Uqai1+Uqai2 etc., so as to generate a Linear Programming task because all constraints are linear. The constraints no longer include Zq, but only their expressions via Uq . . . 1,Uq . . . 2.
[0097] For example, the nonlinear form of Cq(Zq) shown in Equation (2):
-
- [0098] and repeated above will be replaced by linear form:
- [0099] where:
- [0100] all aj, bj, Pj, bKq, Pqmax are constants and their sums and products have no influence on the optimization.
- [0098] and repeated above will be replaced by linear form:
[0101] It can be shown that, after optimization, one of the substituted pair of variables in the above set of linearized equations marked (*), will be equal to zero whilst the second substituted variable in the corresponding pair will be greater than or equal to zero, i.e. U . . . 1=0 and U . . . 0.2≧0, or U . . . 0.2=0 and U . . . 1≧0.
[0102] The cost can be further reduced by increasing the number of control points and/or by allowing the road surface to have a higher gradient.
[0103] The accuracy of the result can be improved by reducing the spacing between adjacent grid points and employing a finer resolution Digital Terrain Model, but this dramatically increases the number of variables.
[0104] 2. Centerline Optimization—Linear Programming Approach.
[0105] The method described above allows cost optimization of the complete surface of a transport route typically comprising many roads or railway track surfaces. There may, however, be times when optimization of the complete surface is impractical or undesirable, for example when time or memory considerations do not allow such optimization. In his case, a lower precision approximation may be achieved by optimizing only the routes' centerlines using linear programming when the objective is to minimize the cumulative difference between the proposed roads' elevations and the existing elevations dictated by the initial topography at the control points, i.e. the difference between cut and fill volumes for centerlines only at each control point.
[0106] This approach takes into account only the control points i.e. points on the centerlines of the road system.
[0107] The gradient of a road can be changed only at the control points which are defined by the end-user, either manually or automatically. Preferably, the control points are located at the points of centerlines where the gradient of the existing profile changes, thereby improving the optimization process. FIG. 3 shows existing and proposed vertical profiles of road centerline.
[0108] Suppose SABO is the area of ΔABO, and SODC is the area of ΔODC. Then it can be shown that:
SABO−SODC=AA′(BA+CD)/2;
SABO−SODC=AA′(BA+CD)/2;
-
- [0109] Where:
- [0110] AA′ is planar distance between A and D (later Dij);
- [0111] AB, DC are signed relative proposal elevations at control points A and D (later Zij);
- [0112] SABO is fill quantity;
- [0113] SODC is cut quantity;
[0114] Summing the cut and fill differences for all control points so as to give the cumulative difference for a single road and then summing again for all roads in the system, gives:
-
- [0115] where:
- [0116] K is number of roads in the road system;
- [0117] Nj is number of control points on the jth road of the system;
- [0118] Dij is the planar distance between adjacent control points with relative elevations Zij and Z(i+1)j on the jth road;
- [0119] D0j=DNjj=0 by definition;
- [0120] j=1, . . . ,K,
- [0121] i=1, . . . ,Nj,
- [0122] In the above Equation (8), Zij can be either positive or negative depending on whether the road surface must be cut or filled at the specific control point described by Zij. In order to construct a set of equations which can be solved using, linear programming techniques, Zij must be positive for all points. Values of Zij have units of meters and a value of 10,000 is added to each value of Zij so that, regardless of its value, there will thus emerge a positive value. To satisfy implicit constraints for all variables: ≧0 instead of relative elevations we used Zij+10,000. This has no effect on constraints based only on compensate for the hidden addition of 10,000. It should be noted that the value 10,000 is itself arbitrary and any other value, Δ, may be employed so long as it is sufficiently large that for all values of Zij, the sum of Zij+Δ is always ensured to be greater than zero.
[0123] In order to compensate for the addition of 10,000 to each value of Zij, there must now be subtracted 10,000 from the cumulative sum in respect of each Zij:
[0124] This gives:
[0125] Equation (10) is the objective function whose absolute value must be minimized in order to minimize the cumulative difference between cut and fill elevations. Two cases must be considered: (i) when the result of Equation (10) is positive and (ii) when the result of Equation (10) is negative. When the cumulative difference between cut and fill elevations given by Equation (10) is negative, the cumulative difference must be maximized, whilst when it is positive, it must be minimized, so that in either case the absolute cumulative difference is minimized. A further constraint is introduced in order to indicate which of the two cases is applicable. This gives:
[0126] Constraints:
- [0127] (a) Elevations of intersection points of different roads having respective indices j1 and j2 must be same, i.e.:
Z1j1+H1j1−Z1j2−H1j2=0,- [0128] Where:
- [0129] 1st point of j1th road coincides with 1st point of j2th road;
- [0130] Z1j1 and Z1j2 are relative elevations at these points;
- [0131] H1j1 and H1j2 are existing elevations at these points.
- [0132] (b) The absolute value of the gradient between adjacent control points (i, j) having respective elevations Hij and H(i+1),j cannot exceed a predetermined allowable maximum value, Gmax:
|Zi,j+Hi,j−Z(i+1),j−H(i+1),j|/Di,j<Gmax,- [0133] for j=1, . . . , K; i=1, . . . ,Nj.
- [0134] (c) Elevation at each CP should belong to maximal possible allowable interval:
- [0135] and
- [0136] for j0=1, . . . ,K; i0=1, . . . ,Nj
- [0137] Where:
- [0138] Zi0,j0−10,000 is the proposed relative elevation at the i0th point on j0th road;
- [0139] Di0,j0i,j is the shortest distance between i0th point on j0th road to ith point on jth road.
- [0135] and
[0140] This distance is the weighted graph shortest distance where weights of graph arcs are distances according to road paths, i.e. the shortest distance along the route rather than the shortest distance between two points. For this purpose the Shortest Paths Algorithm is used.
[0141] Centerline Optimization—Nonlinear Programming Approach.
[0142] FIG. 4 shows the proposed profile of a road to be constructed relative to an existing profile. The optimization is reached through nonlinear programming when objective is cumulative sum of unsigned differences between proposed and existing elevations; variables are differences between proposal road elevations and existing topography elevations at all control points; constraints are present roads standards.
[0143] This approach also takes into account only control points i.e. points on centerlines of all roads in the system. It is recommended to locate control points at points of centerlines where the existing profile changes grade, so as thereby to improve the optimization process.
[0144] The objective is to minimize the total sum of unsigned differences between proposed and existing elevations calculated for the centerlines only of each road, i.e. for vertical profiles as shown in FIG. 4 :
-
- [0145] A, B, C, D, E are control points;
- [0146] AA′ is the difference between the proposed elevation and the existing elevation at point A (later Zij).
- [0147] where:
- [0148] K is number of roads; Nj is number of control points on jth road of the system;
- [0149] Dij is distance between adjacent control points with relative elevations Zij and Z(i+j),j on jth road;
- [0150] D0j=DNjj=0 by definition;
[0151] Constraints:
- [0152] (a) Elevations of intersection points of different roads must be same:
Z1j1+H1j1−Z1j2−H1j2=0,- [0153] Where:
- [0154] 1st point of j1th road coincides with 1st point of j2th road;
- [0155] Z1j1 and Z1j2 are proposed elevations at these points;
- [0156] H1j1 and H1j2 are existing elevations at these points.
- [0157] (b) Maximal grades at all control points cannot exceed allowable values:
|Zij+Hij−Z(i+1),j−H(i+1),j|/Dij<Gmax,- [0158] for j=i, . . . ,K; i=1, . . . ,Nj.
[0159] To transform Equation (14) to linear form of variables substitute for each pair of variables as explained above.
Zij=Uij1−Uij2,
Uij1,Uij2>=0,
Zij=Uij1−Uij2,
Uij1,Uij2>=0,
-
- [0160] for j=1, . . . ,K; i=1, . . . ,Nj.
[0161] So in Equation (1) replace |Zij| by Uij1+Uij2.
[0162] Replace all constraints by Zij=Uij1−Uij2 for each corresponding index i, j.
[0163] Refinements:
[0164] If the control points are located close each to other (e.g. 10–50 m) it is recommended to add as a further constraint that the difference between adjacent road grades should not exceed predefined value per certain distance (e.g. 0.5% per 10 m). The received optimal centerlines may then be approximated by arcs of circles or parabolas or straight lines to satisfy roadway design rules.
[0165] If control points are located far each to other (e.g. 50–300 m) arcs of circles or parabolas may be inscribed between straight intervals according to roadway design rules.
[0166] After the solution has been obtained, there is started an iteration process of moving entire model along axis Z to minimize total cost whilst taking into account the roads' cross-sections. The result of the optimization is a set of control points elevations that define vertical alignment of the entire road system.
[0167] The result can be improved by adding control points and by allowing higher gradient.
[0168] Accuracy of the result can be improved by adding density of grid and DTM.
[0169] Fixed Points:
[0170] By “fixed points” are meant centerline points that must be at a definite height. For such points there are added fixed points constraints:
H+Z=E Equation (15)
H+Z=E Equation (15)
-
- [0171] where:
- [0172] Z is relative elevation of the fixed point;
- [0173] H is existing elevation at this point;
- [0174] E is required height at the fixed point.
[0175] Equation (15) is solved for each fixed point. This requires that each fixed point must be defined as a control point. If there are two or more fixed points, in each optimization method, it is necessary to ensure, before optimization, that grades between the fixed points do not exceed the maximal allowable value. This checking must be done for the shortest distance between fixed points. For that purpose the Shortest Paths Algorithm is used.
[0176] Subdivision:
[0177] If the optimization process takes into account earthworks required to conform the road elevation to the corresponding elevations of subdivision lots, such as private land adjoining the road boundary, then it is necessary add to the model the proposed sections and boundaries of lots.
[0178] Optimization Algorithm for Fill Transportation:
[0179] The invention allows determination of the optimal work program for transportation of excavation material at the preliminary planning stage. According to the invention, the suppliers are sites with excess of cut and the customers are sites with lack of fill. The objective is to minimize the sum of excavation volumes multiplied by distances, as given by:
-
- [0180] where:
[0181] Xij is fill quantity will be moved from ith supplier to jth customer; i=1, . . . ,N,j=1, . . . ,M;
-
- [0182] N is number of suppliers and M is number of customer;
- [0183] Dij is the shortest distance from ith supplier to jth customer;
[0184] Constraints are:
- [0185] (a) Move no more than each customer needs:
- [0186] Pj is volume of jth customer;
- [0187] (b) Move no more than each supplier has available:
- [0188] Qi is volume of ith supplier;
- [0189] (c) But move all that is possible:
[0190] The shortest distance between two points is calculated by the shortest path algorithm as applied to weighted graphs whose arcs are the road paths and for which the weights are lengths of these paths.
[0191] It will be appreciated that the method described above is particularly amenable to being implemented by a suitably programmed computer. FIG. 5 shows functionally a computer-implemented system depicted generally as 10 for designing transportation routes, comprising a computer 11 coupled to a memory 12 and a data output device 13 such as a display monitor, plotter, printer and the like.
[0192] Stored in the memory 12 are transportation route data including:
-
- [0193] design criteria to be met in respect of at least one of said transportation routes,
- [0194] route profile data showing land heights at sampled points along each of said at least one transportation route, and per-unit cost estimates in respect of land-cut and land-fill operations.
[0195] The computer 11 is so programmed as to be responsive to the design criteria, the route profile data and the per-unit cost estimates for computing a height profile of each transportation route which meets the design criteria and for which the land-cut and land-fill operations are adjusted to give a minimum cost in accordance with the method described in detail above with reference to FIGS. 1 to 4 of the drawings.
[0196] It will also be understood that the invention contemplates use of a programmable computer such as a PC wherein the method is carried out by means of a custom program stored on diskette, CD-ROM or other suitable data media.
[0197] In the method claims which follow, alphabetic and numeric characters used to designate claim steps are provided for convenience only and do not imply any particular order of performing the steps.
Claims
The invention claimed is:
1. A computer-implemented method for designing transportation routes, the method comprising the steps of:
(a) supplying linear constraints of allowable grades to be met in respect of at least one of said transportation routes,
(b) obtaining route profile 3-D coordinates showing land heights at sampled points along each of said at least one transportation route prior to construction thereof,
(c) supplying cost estimates per working unit in respect of land-cut and land-fill operations, and
(d) computing a height profile of said at least one transportation route which meets said constraints and for which said land-cut and land-fill operations are adjusted to give a minimum cost by replacing all non-linear constraints by equivalent linear constraints so as to render the height profile solving using standard linear programming tools.
2. The method according to claim 1, wherein step (d) includes:
i) representing a surface of the at least one transportation route as a 3-dimensional model having grid points and boundary grid points being grid points located on edges of roads for which distance to the road centerline is substantially equal to half of the road width,
ii) defining control points such that a gradient of the road surface is constant between adjacent control points by entering X and Y coordinates of said control points as input data, and
iii) calculating a respective elevation of each point on the road surface between adjacent control points as well as a respective elevation of each control point using linear or non-linear programming.
3. The method according to claim 1, wherein the route profile data includes soil composition and per unit excavation cost for each different level having a discrete soil composition.
4. The method according to claim 1, wherein: the height profile is computed to minimize a total cost of the earthworks represented by the following objective function:
where:
G is grid size;
Fq(Zq) is cost of fill at point Q, where the proposed GP elevation is higher than the existing GP elevation (Zq>0);
Wq(Zq) is cost of retaining wall for fill at point Q, where proposal GP is above existing GP (Zq>0);
Cq(Zq) is cost of excavation at point Q, where the proposed GP is lower than the existing GP (Zq<0);
Vq(Zq) is cost of retaining wall for excavation at point Q, where proposed GP is below existing GP (Zq<0);
D is cost of total difference between fill and excavation volumes moving in or out of entire roads system area;
Zq=Z′q−Ze, where Z′q is the proposed elevation and Ze is the elevation at point Q,
the cost Cq(Zq) is represented as the solution of a non-linear equation represented by:
and
each of the absolute expressions Zq−a1, Zq−b1, Zq−cj, Zq−dj, Zq−ej, Zq−fj is replaced by a pair of new variables, as follows:
(*)Zq−ai=Uqai1−Uqai2, i=1, . . . ,Kq,
(*)Zq−bi=Uqbi1−Uqbi2, i=1, . . . ,Kq,
(*)Zq−bKq=UqbK1−UqbK2;
(*)Zq−cj=Uqcj1−Uqcj2, j=1, . . . ,L,
(*)Zq−dj=Uqdj1−Uqdj2, j=1, . . . ,L,
(*)Zq−dL=UqdL1−UqdL2;
(*)Zq−ej=Uqej1−Uqej2, j=1, . . . ,M,
(*)Zq−fj=Uqfj1−Uqfj2, j=1, . . . ,M,
(*)Zq−fM=UqfM1−UqfM2,
(*)Zq−ai=Uqai1−Uqai2, i=1, . . . ,Kq,
(*)Zq−bi=Uqbi1−Uqbi2, i=1, . . . ,Kq,
(*)Zq−bKq=UqbK1−UqbK2;
(*)Zq−cj=Uqcj1−Uqcj2, j=1, . . . ,L,
(*)Zq−dj=Uqdj1−Uqdj2, j=1, . . . ,L,
(*)Zq−dL=UqdL1−UqdL2;
(*)Zq−ej=Uqej1−Uqej2, j=1, . . . ,M,
(*)Zq−fj=Uqfj1−Uqfj2, j=1, . . . ,M,
(*)Zq−fM=UqfM1−UqfM2,
so as to render all of the constraints linear and amenable to computation using Linear Programming techniques.
5. The method according to claim 2, further including:
(e) iteratively shifting said model vertically in order to minimize total cost whilst taking into account the cross-section of each transportation route, so as to derive a set of control points having elevations that define vertical alignment of the transportation routes.
6. The method according to claim 5, further including the step of adding control points and allowing a surface of the transportation route between adjacent control points to have a higher gradient.
7. The method according to claim 5, wherein accuracy is improved by reducing a mutual separation between adjacent grid points.
8. The method according to claim 5, wherein accuracy is improved by providing a higher resolution digital terrain model.
9. The method according to claim 2, wherein at least one of the transportation routes includes one or more subdivision lots adjoining a boundary of the transportation route and in step (d)(i) there are added to the model respective sections and boundaries of said subdivision lots so as to take into account earthworks required to conform an elevation of the transportation route to corresponding elevations of the subdivision lots.
10. The method according to claim 1, wherein the transportation routes include at least one road.
11. The method according to claim 1, wherein the transportation routes include at least one rail track.
12. The method according to claim 1, wherein the transportation routes include at least one pedestrian path.
13. The method according to claim 1 applied to a plurality of transportation routes comprising an integrated project so as optimize excavation costs for the project.
14. A computer-implemented system for designing transportation routes, said system comprising a computer coupled to a memory and a data output device,
(a) there being stored in the memory transportation route data including:
i) linear constraints of allowable grades to be met in respect of at least one of said transportation routes,
ii) route profile 3-D coordinates showing land heights at sampled points along each of said at least one transportation route prior to construction thereof, and
iii) cost estimates per working unit in respect of land-cut and land-fill operations; and
(b) the computer being responsive to the linear constraints, the route profile 3-D coordinates and the cost estimates per working unit for computing a height profile of said at least one transportation route which meets said design criteria and for which said land-cut and land-fill operations are adjusted to give a minimum cost by replacing all non-linear constraints by equivalent linear constraints so as to render the height profile solving using standard linear programming tools.
15. The system according to claim 14, wherein the computer is programmed to:
i) represent a surface of the at least one transportation route as a 3-dimensional model having grid points and boundary grid points being grid points located on edges of roads for which distance to the road centerline is substantially equal to half of the road width,
ii) define control points such that a gradient of the road surface is constant between adjacent control points by entering X and Y coordinates of said control points as input data, and
iii) calculate a respective elevation of each point on the road surface between adjacent control points as well as a respective elevation of each control point using linear or non-linear programming.
16. The system according to claim 15, wherein the route profile data includes soil composition and per unit excavation cost for each different level having a discrete soil composition.
17. The system according to claim 14, wherein the computer is programmed to compute the height profile by minimizing a total cost of the earthworks represented by the following objective function:
where:
G is grid size;
Fq(Zq) is cost of fill at point Q, where the proposed GP elevation is higher than the existing GP elevation (Zq>0);
Wq(Zq) is cost of retaining wall for fill at point Q, where proposal GP is above existing GP (Zq>0);
Cq(Zq) is cost of excavation at point Q, where the proposed GP is lower than the existing GP (Zq<0);
Vq(Zq) is cost of retaining wall for excavation at point Q, where proposed GP is below existing GP (Zq<0);
D is cost of total difference between fill and excavation volumes moving in or out of entire roads system area;
Zq=Z′q−Ze, where Z′q is the proposed elevation and Ze the elevation at point Q,
the cost Cq(Zq) is represented as the solution of a non-linear equation represented by:
each of the absolute expressions Zq−a1, Zq−b1, Zq−cj, Zq−dj, Zq−ej, Zq−fj is replaced by a pair of new variables) as follows:
(*)Zq−ai=Uqai1−Uqai2, i=1, . . . ,Kq,
(*)Zq−bi=Uqbi1−Uqbi2, i=1, . . . ,Kq,
(*)Zq−bKq=UqbK1−UqbK2;
(*)Zq−cj=Uqcj1−Uqcj2, j=1, . . . ,L,
(*)Zq−dj=Uqdj1−Uqdj2, j=1, . . . ,L,
(*)Zq−dL=UqdL1−UqdL2;
(*)Zq−ej=Uqej1−Uqej2, j=1, . . . ,M,
(*)Zq−fj=Uqfj1−Uqfj2, j=1, . . . ,M,
(*)Zq−fM=UqfM1−UqfM2,
(*)Zq−ai=Uqai1−Uqai2, i=1, . . . ,Kq,
(*)Zq−bi=Uqbi1−Uqbi2, i=1, . . . ,Kq,
(*)Zq−bKq=UqbK1−UqbK2;
(*)Zq−cj=Uqcj1−Uqcj2, j=1, . . . ,L,
(*)Zq−dj=Uqdj1−Uqdj2, j=1, . . . ,L,
(*)Zq−dL=UqdL1−UqdL2;
(*)Zq−ej=Uqej1−Uqej2, j=1, . . . ,M,
(*)Zq−fj=Uqfj1−Uqfj2, j=1, . . . ,M,
(*)Zq−fM=UqfM1−UqfM2,
so as to render all of the constraints linear and amenable to computation using Linear Programming techniques.
18. The system according to claim 15, further including:
(f) a vertical shifter for iteratively shifting said model vertically in order to minimize total cost whilst taking into account the cross-section of each transportation route, so as to derive a set of control points having elevations that define vertical alignment of the transportation routes.
19. The system according to claim 18, further including the step of adding control points and allowing a surface of the transportation route between adjacent control points to have a higher gradient.
20. The system according to claim 18, wherein accuracy is improved by reducing a mutual separation between adjacent grid points.
21. The system according to claim 18, wherein accuracy is improved by providing a higher resolution digital terrain model.
22. The system according to claim 15, wherein: at least one of the transportation routes includes one or more subdivision lots adjoining a boundary of the transportation route, there is further stored in the memory data relating to respective sections and boundaries of said subdivision lots, and the computer is responsive to the respective sections and boundaries of the subdivision lots so as to take into account earthworks required to conform an elevation of the transportation route to corresponding elevations of the subdivision lots.
23. The system according to claim 14, wherein the transportation route data includes data relating to at least one road.
24. The system according to claim 1, wherein the transportation route data includes data relating to at least one rail track.
25. The system according to claim 14, wherein the transportation route data includes data relating to at least one pedestrian path.
26. The system according to claim 14 for processing data relating a plurality of transportation routes comprising an integrated project so as optimize excavation costs for the project.
27. A storage medium storing therein a computer program for carrying out the method of claim 1.
Patent Citations (5)
Non-Patent Literature (8)
- Askew et al., Computer Aided Generation of Earthwork Activities in Project Planning, Developments in Computation Techniques for Civil Engineering, Aug. 1995, pp. 17-23.Examiner
- Minami et al., Earthwork Planning System by Microcomputer, Proceedings of the 1st Int. Conference on Engineering Software for Microcomputers, Apr. 1984, pp. 643-655.Examiner
- Roberts et al., Use of Computers for Road Design, Proceedings of the Institution of Civil Engineers, vol. 42, Jan. 1969, pp. 105-128.Examiner
- Bradley et al., Developing the Real-Time Autonomous Excavation—The LUCIE Story, Proceedings of the 34th IEEE Conference on Decision and Control, vol. 3, Dec. 1995, pp. 3028-3033.Examiner
- Allen, L.G., et al. Cost Effective Design-The Use of Computer Aided Drafting in: Selection, Earthworks Optimisation and Rial Track Engineering Peerth/Australia (1987) pp 114-118 XP00917757.Applicant
- Flood, I.,et al. Modeling Constructing Process Using Artificial Neural Networks Automation in Construction 4 (1996) pp 307-320.Applicant
- Papamichael, K, et al.,Building Design Advisor: Automated Integration of Multiple Automation in Construction 6 (1997) pp 341-352.Applicant
- Sacks, R.,et al., A Project Model for an Automated Building System: Design and Planning Phases Automation in Construction 7 (1997) pp 21-34.Applicant