Roadway Profile Modeled by Polynomials to Minimize Earthwork Cost
M. S. ALJOHANI*, A. A. MOREB**
*Department of Nuclear Engineering
King Abdulaziz University
P.O. Box 80204, Jeddah, 21589
SAUDI ARABIA
**Industrial & Management Systems Engineering
Kuwait University,
P.O. Box 5969 Safat 13060
KUWAIT
Abstract: - The most recent development in roadway design was representing the road profile by piece-wise-linear grade lines, followed by representing the new road profile by a quadratic function. Quadratic representation had solved the problem of sharp connectivity points that existed in piece-wise-linear grade lines.
In this paper higher order polynomials are used to fit the road profile; it preserved the smoothness of the quadratic model while maintaining linearity. The model maintains the same efficiency as was obtained by both the piece-wise-linear model and the quadratic one. Moreover, the polynomial model gives a much lower cost than that obtained by all previous models.
Keywords: Linear programming; Transportation; Earthwork allocation; Roadway grades.
1
1 Introduction
Roadway design in the literature is usually handled in two stages. The first stage is to select roadway grades (profile); while the second stage is to minimize the earthwork cost involved after stage one is completed. There have been attempts to integrate the two stages into one problem. Easa’s [1] integration method was based on finding a complete enumeration of all technically feasible grades, calculating the cut and fill for each grade and then using linear programming to optimize the earthwork involved. This trial and error approach reaches optimality only through an exhaustive consideration of all possible feasible grades.
Moreb [2] was able to combine the roadway grade selection stage with the earthwork allocation stage in a single linear programming problem. This was later followed by another development by Moreb and Aljohani [3] that represented the new road profile by a quadratic function to resolve the sharp connectivity points associated with piece-wise-linear model. Both representations possess combining the earthwork involved and the associated transportation in one single model; and both representation result in a mathematical model that is purely linear. Linearity had facilitated the use of the linear simplex method that lead to global
optimality. The advancement that a piece-wise-linear model provided compared to previous work in this field was the efficiency in solving this type of problems. Quadratic model maintained the same efficiency as in the piece-wise-linear one, while resolving the sharp connectivity points.
2 The Model
The designer must divide the road into a number of small sections. A section is the portion of the road between two stations. In Fig. 1, the road under consideration is divided into 8 sections. To represent the problem as a linear programming model, each section i is considered as a point (xi,yi) in the x-y plane. The y-coordinate of this point is the average height of the ground at this section, and the x-coordinate is the center of this section.
3 Variable definitions
3.1 General parameters
= number of sections in the road.
= surface area of section i.
= the actual average height of section i (as if it is leveled with zero slope).
= the midpoint of section i.
= the order of the polynomial.
3.2 Decision variables
= the height of earth to be removed from section i.
= the height of earth to be added to section i.
= number of cubic yards of earth to be transported from section i to section j.
= the coefficient of in the polynomial.
What is commonly used as a coefficient of the polynomial () is now considered decision variables. Their values will be determined by the model that would result in the optimum road profile. Because they are unrestricted in sign they may be suited to linear programming with the following substitutions:
= - (1)
where , and are non-negative variables. This step may not be needed if software used to solve the linear program can handle these variables as free variables taking either sign.
3.3 Cost parameters
= cost of transporting one cubic unit of earth from section i to section j.
= cost of excavating one cubic unit of earth from section i.
= cost of embanking one cubic unit of earth to section i.
3.4 Grade line parameters
= the lower limit of the slope of the polynomial.
= the upper limit of the slope of the polynomial.
4 Problem description
The objective function that minimizes the total cost of embankment, excavation and haul is:
Minimize Z = (2)
Excavation cost and that of embankment can both be added to the transportation cost, in which case the first term of the objective function can be dropped out.
The following set of constraints guarantees that whatever is transported to or from a section is the result of excavation and embankment done to that section:
(3)
The next set of constraints says that the gap between the original height (elevation) of section i and its height after final leveling (levels according to the polynomial) is an exact result of the addition and removal that has been done to section i.
– ( ) = – , (4)
The height of the beginning and the end of the road are usually known since it is a continuation of parts of the road constructed in previous projects and it is a beginning of other parts to be constructed in the future. To comply with the road technical specification, the slope of the road may have some upper and lower limits, thus:
≤ ( ) ≤ , (5)
To adapt equation (5) for linear programming format it has to be deployed at each section (of the 8 sections of the road).
5 Example
An example is adopted from Easa [1] as shown in Fig. 1 and replicated by Moreb [2] and Moreb and Aljohani [3].
.
Excavation Costs:
common (between the sections) = $2.4/yd3
borrow (from borrow pit) = $2.7/yd3
Fig. 1 Ground profile and polynomial roadway profiles with land fill at 1000 ft on the LHS and a borrow pit at 1000 ft on the RHS.
Embankment Costs:
Common (between the sections)
= $5.4/yd3
borrow (from borrow pit) = $4.2/yd3
disposal (to landfill) = $0.6/yd3
Haul:
(across one section) = $1.05/yd3
The horizontal coordinates x, in feet (midpoints of the sections) are:
x1 = 250 x2 = 750 x3 = 1250
x4 = 1750 x5 = 2250
x6 = 2750 x7 = 3250 x8 = 3750
The average heights h (in ft) at the various sections are not reported in Easa (1988), and are calculated here from his outputs:
h1 = 243.8938 h2 = 244.2132
h3 = 163.1114 h4 = 136.5578
h5 = 181.7187 h6 = 264.4738
h7 = 257.9165 h8 = 192.1919
The capacity of each of the borrow pit and the landfill is 900,000 ft3.
Roadway Specifications:
Width of road: 24 ft.
Elevation of the beginning of the road = 210 ft.
Elevation of the end of the road = 205 ft.
Minimum height of at mid-road = 182 ft.
The problem can now be formulated as follows:
Objective Function:
Minimize Z = + +
Note that cij is the collective cost of excavation from section i, the cost of embankment in section j and the cost of transportation from section i to section j, for example c13 = 2.4 + 5.4 + 2.(1.05) = $9.9 / yd3.
Constraints:
– ((- ) = –
The elevations at the beginning and at the end of the road are 210 ft and 205 ft respectively, thus:
(- ) = 210 (at = 0)
or (- ) = 210
and (- ) (4000)k = 205 The capacities of the borrow pit and landfill (ft3):
Tbi 900,000
and Tid 900,000
The quantity of soil excavated and embanked at a section is equal to the quantity transported from this section minus that transported into it (note, i ¹ j); note that A = 24 ft x 500 ft = 12000 ft2,
Results
The problem was modeled using a 3rd order, 4th order and 5th order polynomials; the results were as follows:
3rd Order Polynomial:
The minimum value of the objective function is $695,111.11 & the parameters for a 3rd order polynomial are:
a0 = 210 a1 = - 0.031333 a2 = 0.021038e-3
a3 = - 0.003379e-6
The quantity of earth to be moved from one section to another:
T23 = 15,108 yd3 T24 = 5,915.9 yd3 T64 = 22,940 yd3 T65 = 90.5 yd3 T75 = 11,373 yd3 T78 = 7,977.9 yd3
T1d = 17,985 yd3
The thickness of cuts and fills (u and v):
u1 = 40.465 ft v4 = 64.927 ft
u7 = 43.540 ft u2 = 47.305 ft
v5 = 25.794 ft v8 = 17.950 ft.
v3 = 33.994 ft u6 = 51.820 ft
4th Order Polynomial:
The minimum value of the objective function is $672,554.44 & the parameters for a 4th order polynomial are:
a0 = 210 a1 = 0.031333 a2 = - 0.049349e-3
a3 = 0.020445e-6 a4 = - 0.002536 e-9
The quantity of earth to be moved from one section another:
T23 = 13,622 yd3 T63 = 5,350.4 yd3
T64 = 21,919 yd3 T74 = 6,050.4 yd3
T75 = 7,483.4 yd3 T78 = 7,990.6 yd3
T1d = 12,816 yd3
The thickness of cuts and fills (u and v):
u1 = 28.836 ft v4 = 62.931 ft u7 = 48.430 ft
u2 = 30.649 ft v5 = 16.838 ft v8 = 17.979 ft. v3 = 42.688 ft u6 = 61.356 ft
5th Order Polynomial:
The minimum value of the objective function is $595,884.82 & the parameters for a 5th order polynomial are:
a0 = 210 a1 = 0.031333 a2 = -0.109406e-3
a3 = 0.080164 e-6 a4 = - 0.021135 e-9
a5 = 0.001856 e-12
The quantity of earth to be moved from one section another:
T23 = 11,441 yd3 T24 = 8,417.6 yd3 T64 = 16,063 yd3 T65 = 4,119.5 yd3
T75 = 6,268.7 yd3 T78 = 9,242.6 yd3
T1d = 14,101 yd3
The thickness of cuts and fills (u and v):
u1 = 31.727 ft v4 = 55.082 ft u7 = 34.900 ft
u2 = 44.682 ft v5 = 23.373 ft v8 = 20.796 ft. v3 = 25.742 ft u6 = 45.412 ft
6 Discussion
The formulation presented in this paper took the advantage of integrating the roadway selection stage with the earthwork allocation stages. The optimal solution achieved is efficient, since only one linear program is considered, resulting in optimum roadway grade and optimum earth allocation (transportation). Moreover, the problem of sharp connectivity points is eliminated resulting in a smooth continuous road.
Similar to the remarks made by Moreb [2] that the biggest advantage of his method was that he avoided the nonlinearity that was encountered by Easa’s [1] approach. The same is true in this paper, nonlinearity is also avoided; for more discussion on this issue refer to Moreb [2].
References
[1] Easa, S.M., Selection of roadway grades that minimize earthwork cost using linear programming, Transportation Research A 23A/2, 1988, pp. 121-136.
[2] Moreb A.A., Linear Programming Model for Finding Roadway Grades That Minimize Earthwork Cost, European Journal of Operational Research 93, 1996, pp. 148-154.
[3] Moreb A. A. and Aljohani, M., A Second Order Polynomial Describing Roadway Grades That Minimizes Earthwork Cost Using Linear Programming, The Seventh SIAM Conference on Optimization, Toronto, Ontario. 20-22 May, 2002
1