5th International/11th Construction Specialty Conference 5e International/11e Conférence spécialisée sur la construction Vancouver, British Columbia June 8 to June 10, 2015 / 8 juin au 10 juin 2015 OPTIMIZING EARTHWORK HAULING PLAN WITH MINIMUM COST FLOW NETWORK Duanshun Li1, Chang Liu1 and Ming Lu1, 2 1 Department of Civil & Environmental Engineering, University of Alberta, Canada 2 mlu6@ualberta.ca Abstract: Linear programming is commonly used in earthwork hauling plan. However special expertise in forming and solving linear equations, along with considerable efforts in interpreting results, is required to apply these methods in practice. Moreover, previous methods mainly focus on cost estimation and thus largely ignore the constructability issues; this makes earthwork hauling plan impractical for construction planning. We aim to address these problems by introducing an intuitive graph based approach which optimizes the earthwork hauling plan using the minimum cost flow network. We choose the total traveling time as the objective function to be minimized in order to separate the earthwork hauling plan from other factors such as fleet combination. Our method directly connects adjacent sections allowing accessibility between them, instead of connecting the centers of cut and fill cells as potential haul routes as in previous methods. As a result, the proposed method is capable to handle constructability issues caused by “soft blocks” -which cannot be eliminated in establishing the standard flow network as their existence impose constraints on the grading plan. The graphic earth flow network can be used to guide the execution of the earthwork project and generate multiple grading plans, providing more flexibility compared to traditional methods. We present an earthmoving example with a reserved soft area and show that the proposed method is graphically intuitive, easy to establish and able to handle soft blocks. 1 INTRODUCTION For large infrastructure construction projects such as road construction, it is common that earthwork accounts for about 25% of the total construction cost (Hare 2011). As a result, an optimized earthwork design is essential to enhance the performance of the project. Aiming to reduce the total quantity of earth to be moved, cut-fill balancing algorithms were proposed to equalize the quantity of earth for cut and minimize the quantity of earth handling from borrow pit and to landfill (Goktepe and Lav 2004). The technique has been well-studied and can be easily applied through commercial software such as Auto CAD Civil 3D which facilitates generation of the final topographic surface of the site. The quantity of materials in each cut and fill sections can then be derived from the elevation difference between the original and final as-designed surfaces. A well designed grading plan can reduce the total amount of earth excavated, however the most significant savings can be achieved by optimizing earthwork operations which involve large numbers of costly heavy equipment such as excavators, loaders, trucks and compactors. According to the research conducted by Hare et al (2011), an approximate optimal earthwork operation plan can result in as much as 48% to 74% cost improvements. The fleet composition and earthwork hauling plan are important factors in earthwork operations hence become the focus of productivity enhancement in earthmoving 175-1 projects. Though plenty of research has been done on fleet optimization (Moselhi and Alshibani 2009, Morley et al. 2014), it highly depends on the predefined earthwork hauling plan. Therefore an optimized earthwork hauling plan is critical to further reduce the amount of hauling efforts and facilitate the fleet optimization. Peurifoy and Schexnayder (2002) suggested three most significant factors of an earthwork hauling plan, i.e. the quantity of earth to be moved, the haul distances to move the material and the grade of the road that the material must be hauled over. This research addresses quantity of earth to be moved and hauling path explicitly; the grade of road is represented by travel speed implicitly. Mass-haul diagram is widely used for makring earthwork hauling plan in road construction, but it is limited to linear type of construction. Linear programming (LP) based earthwork hauling plan optimization was first introduced by Stark and Nicholls (1971) and then implemented by Mayer and Stark (1981) using haul distance as the unit cost. Easa (1988 a) proposed building a similar model aiming to optimize road way grades by minimizing the earthwork cost. Given that the unit cost of purchase and excavation of borrow pits is proportional to the quantity of materials required (Easa 1987), Easa (1988 b) modified the model by taking the variability of unit cost for purchase and excavation of borrow pits into consideration. However it is noteworthy that once the final grading design is defined, the purchase and excavation will be fixed and thus will not affect the total direct cost. The commonly applied shortest route cut and fill problem (SRCFP) model in road construction is intended to grade a project site with minimum total distance traveled by earthmoving vehicles (Hare et al. 2011). Because SRCFP considers the variation of return distance due to change in excavation sites, the model is much more realistic but also more complicated. To handle large earthwork projects in road construction, Ji et al. (2010) proposed a one dimensional earthwork section division LP model which minimized the earth handling between sections. Taking the duration into consideration, Jayawardane and Harris (1990) incorporated fleet selection into the linear model. Chu et al. (2012) proposed a time-space network which generated earthwork hauling plan and schedule simultaneously for projects with single type of trucks, the applicability to multiple trucks was undiscussed. More recently, Son (2005) introduced a minimal haul distance LP algorithm and proposed a graph based earthwork hauling plan visualization method. Building the models and solving the complicated equations in previous studies require a large amount of time and expertise, which in turn hampers wide utilization of those techniques in practice (Alshibani 2008). In real world construction projects, establishing these equations in a finite time frame in support of decision making creates additional challenges. Besides, executing a project based on interpretation of numerical results obtained from analytical or simulation algorithms with many “hidden” conditions, assumptions would be more difficult for coordinators on site. These conditions may include “hard blocks” which can be identified without the final hauling plan, and even more complicated “soft blocks” which depend on the final hauling plan. Previous methods like linear programming are able to handle “hard blocks” if well defined, however they usually generate hauling roads with ungraded “soft blocks” due to mutual reliance. To address these problems, this research applies the minimum cost flow network algorithm into earthwork volume balancing. Through a graphic way, the network provides users with an intuitive medium to build the underlying equations. Current linear programming models generally produce a unique grading plan, largely neglecting practical site conditions such as safety of particular haul roads. Such solutions can only serve the need of cost estimation and will likely result in unrealistic grading plans for implementation. Noting this critical issue, this research proposes a neighborhood method based on the classic minimum cost flow network with 4-connected neighborhood, aimed to make the solution ready for execution by integrating constructability issues. 2 PROBLEM DEFINITION AND TRADITIONAL MINIMUM FLOW NETWORK In graph theory, a flow network is a directed graph 𝐺𝐺(𝑁𝑁,𝐴𝐴) defined by a set N of n nodes and a set A of m directed arcs. Each arc (𝑖𝑖, 𝑗𝑗) ∈ 𝐴𝐴 is associated with three properties. The unit cost 𝑐𝑐𝑖𝑖𝑖𝑖 indicates the cost of unit of flow on the arc. Capacity limits 𝑢𝑢𝑖𝑖𝑖𝑖 and 𝑙𝑙𝑖𝑖𝑖𝑖 are used to constrain the maximum and minimum flow on arc (𝑖𝑖, 𝑗𝑗). For each node 𝑖𝑖 ∈ 𝑁𝑁, an integer number 𝑏𝑏(𝑖𝑖) denoting supply/demand is also defined. The nodes can be divided into three different categories based on 𝑏𝑏(𝑖𝑖). If 𝑏𝑏(𝑖𝑖) > 0, node 𝑖𝑖 is a supply node with a supply of 𝑏𝑏(𝑖𝑖); if 𝑏𝑏(𝑖𝑖) < 0, node 𝑖𝑖 is a demand node with a demand of −𝑏𝑏(𝑖𝑖); otherwise if 𝑏𝑏(𝑖𝑖) = 0, the node is a transshipment node. The minimum cost flow aims to find the flow 𝑥𝑥𝑖𝑖𝑖𝑖 on each arc (𝑖𝑖, 𝑗𝑗) that 175-2 The earthwork hauling plan problem can be depicted as the flow of earth on the construction site from one section to another; thus it can be modeled as a flow network. Each sub-divided section can be regarded as a node in the graph, and the supply/demand 𝑏𝑏(𝑖𝑖) will be the cut or fill quantity of earth. For extra materials, borrow and land fill sites can be added as either a node or a connected sub-network. In previous research, the equations usually assume that the supply and demand nodes are connected directly as illustrated in Figure 2. Each arc in the figure represents a hauling path which can be built in the field to haul earth. As the aim of earthwork hauling plan is to minimize the total cost of the project, the definition of unit cost is critical. Considering that various types of costs (such as time, capital, environment etc.) may apply, the unit cost is assigned accordingly. Current algorithms use either the hauling distance or the unit capital cost of material excavation & transportation as unit cost. For rough estimation or linear construction projects, the hauling distance between sections are usually determined as the direct distance between the centers of the two sections. For precise estimation, the hauling distance can be derived with shortest path algorithms (Liu and Lu 2014). The unit capital cost of traveling on the surface relies heavily on the fleet combination, which can be optimized based on the earthwork hauling plan. The proposed neighborhood method utilizes time as the final criterion based on the observation that no matter how the condition changes, both direct cost and indirect cost are proportional to time. As the amount of earthwork for excavation and dumping will be fixed as per the grading design, the only variable which can be optimized would be hauling. Therefore, only hauling time is considered when define the unit cost. Previous earthwork hauling plan methods mainly focused on cost estimation and thus barely catered to field construction needs. This often leads to oversimplification or neglecting constructability issues in connection with project execution. However, ignoring certain existing blocks in the field would result in inaccurate estimation of optimal earthwork costs and poor haul road design. These blocks can be divided into hard blocks and soft blocks according to the occurrence condition. The occurrence of hard blocks such as waterways, ponds and rock-bed is independent of the earthwork hauling plan. On the contrary, the existence of soft blocks can affect the final earthwork hauling plan. As hard blocks are known before the establishment of the earthwork hauling plan model, they can be embedded into the flow network with well-defined connections and unit costs. Take river as an example. An extremely high unit cost can be assigned to paths or sections crossing a creek on site. Through this approach the total cost to move the earth across the river will be extremely high and the paths crossing the creek will be automatically discarded through optimization if alternatives are available. On the contrary, the occurrence of soft blocks is unpredictable because they may rely on the earthwork hauling plan which is actually the final output of such optimization analysis. One typical constructability issue in earthwork hauling plan planning is that the sections along the path for particular earthmoving operation should have already been graded into temporary haul road while part of the path lies in soft blocks to be excavated or filled. Soft blocks may be produced due to mutual reliance when the earthwork plan is not generated properly. To illustrate the mutual reliance, assuming the volumes of C-1, C-2, F-1 and F-2 in the linear earthwork hauling plan (Figure 2) are all the same and regarded as 1 unit. In addition, the unit cost between the sections are defined as P1 = 2, P2 =3, P3 = 100, P4 = 1, P5 = 2, P6 = 100, P7 = P8 = P9 = 100. The optimal minimum total cost defined in Equation 1.1 for this problem will be 4 units. An earthwork hauling plan with two paths is given as: (A) moving earth from C-2 to F-2 passing F-1 (C-2, F-1, F-2); (B) Moving earth from C1 to F1 passing C2 (C-1, C-2, F-1). In this case, to move the earth excavated in C-2 (operation A), the intermediate sections along the path (C-2, F-1, F-2) will be regarded as soft blocks and should be removed first. Regarded as a soft block, F-1 has to be filled and graded beforehand. However to get F-1 filled, operation B must be completed which requires that C-2, as a soft block, to be excavated and graded first. For earthmoving projects with numerous sections in two dimensions, the mutual reliance will be even more complicated, which is commonplace in solving classic minimum cost flow network problems. Considering the random nature of traditional minimum cost flow algorithms, a conflict-free solution is not guaranteed. 175-4 be more practical and realistic because the proposed model not only optimizes the total cost but also provides an efficient way to handle both hard constraints and soft constraints such as reserved areas and mutual reliance of hauling roads which are not solved in previous methods. Moreover, the generated results can be translated into multiple grading plans which can provide alternative plans and support decision making in field execution. REFERENCES Alshibani, A. 2008. Optimizing and controlling earthmoving operations using spatial technologies (Doctoral dissertation, Concordia University). Alshibani, A., and Moselhi, O. 2012. “Fleet selection for earthmoving projects using optimization-based simulation.” Can. J. Civ. Eng., 39(6): 619–630. Christian, J., & Caldera, H. 1988. Earthmoving cost optimization by operational research. Canadian journal of civil engineering, 15(4): 679-684. Chu, J. C., Yan, S., & Chen, K. L. 2012. Optimization of earth recycling and dump truck dispatching. Computers & Industrial Engineering, 62(1), 108-118. Easa, S. M. 1987. Earthwork hauling plans with nonconstant unit costs. Journal of Construction Engineering and Management, 113(1), 34-50. Easa, S. M. 1988 a. Selection of roadway grades that minimize earthwork cost using linear programming. Transportation Research Part A: General, 22(2), 121-136. Easa, S. M. 1988 b. Earthwork hauling plans with linear unit costs. Journal of Construction Engineering and Management, 114(4), 641-655. Goktepe, A. B., & Lav, A. H. 2004. Method for optimizing earthwork considering soil properties in the geometric design of highways. Journal of surveying engineering, 130(4): 183-190. Hare, W. L., Koch, V. R., & Lucet, Y. 2011. Models and algorithms to improve earthwork operations in road design using mixed integer linear programming.European Journal of Operational Research, 215(2): 470-480. Jayawardane, A. K. W., & Harris, F. C. 1990. Further development of integer programming in earthwork optimization. Journal of Construction Engineering and Management, 116(1): 18-34. Mayer R., Stark R. 1981. Earthmoving logistics. Journal of the Construction Division, 107(2): 297–312 Morley, D., Lu, M., & AbouRizk, S. 2014. Identification of Invariant Average Weighted Haul Distance to Simplify Earthmoving Simulation Modeling in Planning Site Grading Operations. Journal of Construction Engineering and Management, 140(12): 1-11. Peurifoy, R. L., and Schexnayder, C. J. 2002. Construction planning, equipment, and methods, 6th Ed., McGraw-Hill, New York. Ravindra K. A., Thomas L.M., and James B.O. 1993. Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X. Son, J., Mattila, K. G., & Myers, D. S. 2005. Determination of haul distance and direction in mass excavation. Journal of Construction Engineering and Management, 131(3): 302-309. Stark, R. M., & Nicholls, R. L. 1971. Mathematical foundations for design: civil engineering systems. Technology and Engineering, McGraw-Hill. 175-9 5th International/11th Construction Specialty Conference 5e International/11e Conférence spécialisée sur la construction Vancouver, British Columbia June 8 to June 10, 2015 / 8 juin au 10 juin 2015 OPTIMIZING EARTHWORK HAULING PLAN WITH MINIMUM COST FLOW NETWORK Duanshun Li1, Chang Liu1 and Ming Lu1, 2 1 Department of Civil & Environmental Engineering, University of Alberta, Canada 2 mlu6@ualberta.ca Abstract: Linear programming is commonly used in earthwork hauling plan. However special expertise in forming and solving linear equations, along with considerable efforts in interpreting results, is required to apply these methods in practice. Moreover, previous methods mainly focus on cost estimation and thus largely ignore the constructability issues; this makes earthwork hauling plan impractical for construction planning. We aim to address these problems by introducing an intuitive graph based approach which optimizes the earthwork hauling plan using the minimum cost flow network. We choose the total traveling time as the objective function to be minimized in order to separate the earthwork hauling plan from other factors such as fleet combination. Our method directly connects adjacent sections allowing accessibility between them, instead of connecting the centers of cut and fill cells as potential haul routes as in previous methods. As a result, the proposed method is capable to handle constructability issues caused by “soft blocks” -which cannot be eliminated in establishing the standard flow network as their existence impose constraints on the grading plan. The graphic earth flow network can be used to guide the execution of the earthwork project and generate multiple grading plans, providing more flexibility compared to traditional methods. We present an earthmoving example with a reserved soft area and show that the proposed method is graphically intuitive, easy to establish and able to handle soft blocks. 1 INTRODUCTION For large infrastructure construction projects such as road construction, it is common that earthwork accounts for about 25% of the total construction cost (Hare 2011). As a result, an optimized earthwork design is essential to enhance the performance of the project. Aiming to reduce the total quantity of earth to be moved, cut-fill balancing algorithms were proposed to equalize the quantity of earth for cut and minimize the quantity of earth handling from borrow pit and to landfill (Goktepe and Lav 2004). The technique has been well-studied and can be easily applied through commercial software such as Auto CAD Civil 3D which facilitates generation of the final topographic surface of the site. The quantity of materials in each cut and fill sections can then be derived from the elevation difference between the original and final as-designed surfaces. A well designed grading plan can reduce the total amount of earth excavated, however the most significant savings can be achieved by optimizing earthwork operations which involve large numbers of costly heavy equipment such as excavators, loaders, trucks and compactors. According to the research conducted by Hare et al (2011), an approximate optimal earthwork operation plan can result in as much as 48% to 74% cost improvements. The fleet composition and earthwork hauling plan are important factors in earthwork operations hence become the focus of productivity enhancement in earthmoving 175-1 projects. Though plenty of research has been done on fleet optimization (Moselhi and Alshibani 2009, Morley et al. 2014), it highly depends on the predefined earthwork hauling plan. Therefore an optimized earthwork hauling plan is critical to further reduce the amount of hauling efforts and facilitate the fleet optimization. Peurifoy and Schexnayder (2002) suggested three most significant factors of an earthwork hauling plan, i.e. the quantity of earth to be moved, the haul distances to move the material and the grade of the road that the material must be hauled over. This research addresses quantity of earth to be moved and hauling path explicitly; the grade of road is represented by travel speed implicitly. Mass-haul diagram is widely used for makring earthwork hauling plan in road construction, but it is limited to linear type of construction. Linear programming (LP) based earthwork hauling plan optimization was first introduced by Stark and Nicholls (1971) and then implemented by Mayer and Stark (1981) using haul distance as the unit cost. Easa (1988 a) proposed building a similar model aiming to optimize road way grades by minimizing the earthwork cost. Given that the unit cost of purchase and excavation of borrow pits is proportional to the quantity of materials required (Easa 1987), Easa (1988 b) modified the model by taking the variability of unit cost for purchase and excavation of borrow pits into consideration. However it is noteworthy that once the final grading design is defined, the purchase and excavation will be fixed and thus will not affect the total direct cost. The commonly applied shortest route cut and fill problem (SRCFP) model in road construction is intended to grade a project site with minimum total distance traveled by earthmoving vehicles (Hare et al. 2011). Because SRCFP considers the variation of return distance due to change in excavation sites, the model is much more realistic but also more complicated. To handle large earthwork projects in road construction, Ji et al. (2010) proposed a one dimensional earthwork section division LP model which minimized the earth handling between sections. Taking the duration into consideration, Jayawardane and Harris (1990) incorporated fleet selection into the linear model. Chu et al. (2012) proposed a time-space network which generated earthwork hauling plan and schedule simultaneously for projects with single type of trucks, the applicability to multiple trucks was undiscussed. More recently, Son (2005) introduced a minimal haul distance LP algorithm and proposed a graph based earthwork hauling plan visualization method. Building the models and solving the complicated equations in previous studies require a large amount of time and expertise, which in turn hampers wide utilization of those techniques in practice (Alshibani 2008). In real world construction projects, establishing these equations in a finite time frame in support of decision making creates additional challenges. Besides, executing a project based on interpretation of numerical results obtained from analytical or simulation algorithms with many “hidden” conditions, assumptions would be more difficult for coordinators on site. These conditions may include “hard blocks” which can be identified without the final hauling plan, and even more complicated “soft blocks” which depend on the final hauling plan. Previous methods like linear programming are able to handle “hard blocks” if well defined, however they usually generate hauling roads with ungraded “soft blocks” due to mutual reliance. To address these problems, this research applies the minimum cost flow network algorithm into earthwork volume balancing. Through a graphic way, the network provides users with an intuitive medium to build the underlying equations. Current linear programming models generally produce a unique grading plan, largely neglecting practical site conditions such as safety of particular haul roads. Such solutions can only serve the need of cost estimation and will likely result in unrealistic grading plans for implementation. Noting this critical issue, this research proposes a neighborhood method based on the classic minimum cost flow network with 4-connected neighborhood, aimed to make the solution ready for execution by integrating constructability issues. 2 PROBLEM DEFINITION AND TRADITIONAL MINIMUM FLOW NETWORK In graph theory, a flow network is a directed graph 𝐺𝐺(𝑁𝑁,𝐴𝐴) defined by a set N of n nodes and a set A of m directed arcs. Each arc (𝑖𝑖, 𝑗𝑗) ∈ 𝐴𝐴 is associated with three properties. The unit cost 𝑐𝑐𝑖𝑖𝑖𝑖 indicates the cost of unit of flow on the arc. Capacity limits 𝑢𝑢𝑖𝑖𝑖𝑖 and 𝑙𝑙𝑖𝑖𝑖𝑖 are used to constrain the maximum and minimum flow on arc (𝑖𝑖, 𝑗𝑗). For each node 𝑖𝑖 ∈ 𝑁𝑁, an integer number 𝑏𝑏(𝑖𝑖) denoting supply/demand is also defined. The nodes can be divided into three different categories based on 𝑏𝑏(𝑖𝑖). If 𝑏𝑏(𝑖𝑖) > 0, node 𝑖𝑖 is a supply node with a supply of 𝑏𝑏(𝑖𝑖); if 𝑏𝑏(𝑖𝑖) < 0, node 𝑖𝑖 is a demand node with a demand of −𝑏𝑏(𝑖𝑖); otherwise if 𝑏𝑏(𝑖𝑖) = 0, the node is a transshipment node. The minimum cost flow aims to find the flow 𝑥𝑥𝑖𝑖𝑖𝑖 on each arc (𝑖𝑖, 𝑗𝑗) that 175-2 The earthwork hauling plan problem can be depicted as the flow of earth on the construction site from one section to another; thus it can be modeled as a flow network. Each sub-divided section can be regarded as a node in the graph, and the supply/demand 𝑏𝑏(𝑖𝑖) will be the cut or fill quantity of earth. For extra materials, borrow and land fill sites can be added as either a node or a connected sub-network. In previous research, the equations usually assume that the supply and demand nodes are connected directly as illustrated in Figure 2. Each arc in the figure represents a hauling path which can be built in the field to haul earth. As the aim of earthwork hauling plan is to minimize the total cost of the project, the definition of unit cost is critical. Considering that various types of costs (such as time, capital, environment etc.) may apply, the unit cost is assigned accordingly. Current algorithms use either the hauling distance or the unit capital cost of material excavation & transportation as unit cost. For rough estimation or linear construction projects, the hauling distance between sections are usually determined as the direct distance between the centers of the two sections. For precise estimation, the hauling distance can be derived with shortest path algorithms (Liu and Lu 2014). The unit capital cost of traveling on the surface relies heavily on the fleet combination, which can be optimized based on the earthwork hauling plan. The proposed neighborhood method utilizes time as the final criterion based on the observation that no matter how the condition changes, both direct cost and indirect cost are proportional to time. As the amount of earthwork for excavation and dumping will be fixed as per the grading design, the only variable which can be optimized would be hauling. Therefore, only hauling time is considered when define the unit cost. Previous earthwork hauling plan methods mainly focused on cost estimation and thus barely catered to field construction needs. This often leads to oversimplification or neglecting constructability issues in connection with project execution. However, ignoring certain existing blocks in the field would result in inaccurate estimation of optimal earthwork costs and poor haul road design. These blocks can be divided into hard blocks and soft blocks according to the occurrence condition. The occurrence of hard blocks such as waterways, ponds and rock-bed is independent of the earthwork hauling plan. On the contrary, the existence of soft blocks can affect the final earthwork hauling plan. As hard blocks are known before the establishment of the earthwork hauling plan model, they can be embedded into the flow network with well-defined connections and unit costs. Take river as an example. An extremely high unit cost can be assigned to paths or sections crossing a creek on site. Through this approach the total cost to move the earth across the river will be extremely high and the paths crossing the creek will be automatically discarded through optimization if alternatives are available. On the contrary, the occurrence of soft blocks is unpredictable because they may rely on the earthwork hauling plan which is actually the final output of such optimization analysis. One typical constructability issue in earthwork hauling plan planning is that the sections along the path for particular earthmoving operation should have already been graded into temporary haul road while part of the path lies in soft blocks to be excavated or filled. Soft blocks may be produced due to mutual reliance when the earthwork plan is not generated properly. To illustrate the mutual reliance, assuming the volumes of C-1, C-2, F-1 and F-2 in the linear earthwork hauling plan (Figure 2) are all the same and regarded as 1 unit. In addition, the unit cost between the sections are defined as P1 = 2, P2 =3, P3 = 100, P4 = 1, P5 = 2, P6 = 100, P7 = P8 = P9 = 100. The optimal minimum total cost defined in Equation 1.1 for this problem will be 4 units. An earthwork hauling plan with two paths is given as: (A) moving earth from C-2 to F-2 passing F-1 (C-2, F-1, F-2); (B) Moving earth from C1 to F1 passing C2 (C-1, C-2, F-1). In this case, to move the earth excavated in C-2 (operation A), the intermediate sections along the path (C-2, F-1, F-2) will be regarded as soft blocks and should be removed first. Regarded as a soft block, F-1 has to be filled and graded beforehand. However to get F-1 filled, operation B must be completed which requires that C-2, as a soft block, to be excavated and graded first. For earthmoving projects with numerous sections in two dimensions, the mutual reliance will be even more complicated, which is commonplace in solving classic minimum cost flow network problems. Considering the random nature of traditional minimum cost flow algorithms, a conflict-free solution is not guaranteed. 175-4 be more practical and realistic because the proposed model not only optimizes the total cost but also provides an efficient way to handle both hard constraints and soft constraints such as reserved areas and mutual reliance of hauling roads which are not solved in previous methods. Moreover, the generated results can be translated into multiple grading plans which can provide alternative plans and support decision making in field execution. REFERENCES Alshibani, A. 2008. Optimizing and controlling earthmoving operations using spatial technologies (Doctoral dissertation, Concordia University). Alshibani, A., and Moselhi, O. 2012. “Fleet selection for earthmoving projects using optimization-based simulation.” Can. J. Civ. Eng., 39(6): 619–630. Christian, J., & Caldera, H. 1988. Earthmoving cost optimization by operational research. Canadian journal of civil engineering, 15(4): 679-684. Chu, J. C., Yan, S., & Chen, K. L. 2012. Optimization of earth recycling and dump truck dispatching. Computers & Industrial Engineering, 62(1), 108-118. Easa, S. M. 1987. Earthwork hauling plans with nonconstant unit costs. Journal of Construction Engineering and Management, 113(1), 34-50. Easa, S. M. 1988 a. Selection of roadway grades that minimize earthwork cost using linear programming. Transportation Research Part A: General, 22(2), 121-136. Easa, S. M. 1988 b. Earthwork hauling plans with linear unit costs. Journal of Construction Engineering and Management, 114(4), 641-655. Goktepe, A. B., & Lav, A. H. 2004. Method for optimizing earthwork considering soil properties in the geometric design of highways. Journal of surveying engineering, 130(4): 183-190. Hare, W. L., Koch, V. R., & Lucet, Y. 2011. Models and algorithms to improve earthwork operations in road design using mixed integer linear programming.European Journal of Operational Research, 215(2): 470-480. Jayawardane, A. K. W., & Harris, F. C. 1990. Further development of integer programming in earthwork optimization. Journal of Construction Engineering and Management, 116(1): 18-34. Mayer R., Stark R. 1981. Earthmoving logistics. Journal of the Construction Division, 107(2): 297–312 Morley, D., Lu, M., & AbouRizk, S. 2014. Identification of Invariant Average Weighted Haul Distance to Simplify Earthmoving Simulation Modeling in Planning Site Grading Operations. Journal of Construction Engineering and Management, 140(12): 1-11. Peurifoy, R. L., and Schexnayder, C. J. 2002. Construction planning, equipment, and methods, 6th Ed., McGraw-Hill, New York. Ravindra K. A., Thomas L.M., and James B.O. 1993. Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X. Son, J., Mattila, K. G., & Myers, D. S. 2005. Determination of haul distance and direction in mass excavation. Journal of Construction Engineering and Management, 131(3): 302-309. Stark, R. M., & Nicholls, R. L. 1971. Mathematical foundations for design: civil engineering systems. Technology and Engineering, McGraw-Hill. 175-9 Optimize Earthwork Hauling Plan with Minimum Cost Flow NetworkDuanshun Li (duanshun@ualberta.ca)Ming Lu (mlu6@ualberta.ca) 1OutlineBackgroundMinimum Cost Flow Based MethodCase Study & ValidationConclusion2BackgroundCUTFillSite grading design completed Cut fill balance Quantity takeoffMajor tasks in earthwork planning: Material Earthwork Allocation Temporary haul road design Equipment Fleet optimization3BackgroundEarthwork allocation: Find the most economic combination of haul jobs to move the material from section to section Job Cut Fill Volume(bcm)RouteJob-A 20 19 8100 -Job-B 20 18 16700 [19]Job-C 21 18 5500 [20, 19,17]Job-D 21 17 4400 [20, 19, 18]Job-E 33 17 18600 [21, 20, 19, 18]Job-F 33 16 36000 [21, 20, 19, 18, 17]Job-G 33 15 8400 [21, 20, 19, 18, 17, 16]4ProblemLimitations of earthwork allocation optimization by linear programming1) Time consuming to establish and solve equations2) Generate Haul jobs with conflicts:Hard blocks: Can be identified before hand, but cannot be eliminated.Soft blocks: Embedded within haul jobs, can be eliminated.3) Cannot provide job sequence5Simulation MethodsConstruction Operations Simulation Limitations:Simulation is separated from earth work allocation1) User specify the route manually(Hajjar and AbouRizk 1997, Marzouk, and Moselhi 2004)2) Simulate with non-optimal heuristic approach(Morley, Lu, and AbouRizk 2014)Operation oriented: fleet selection6Minimum Cost Flow (MCF) Based MethodResearch objective1) Easy to use tool2) Accommodate “hard blocks”3) Avoid “soft blocks”4) Integrate time (job sequence) into earthwork planning7Minimum Cost Flow (MCF) Based MethodEarthwork Allocation with Flow Network OptimizationCut/Fill Volume and LayoutAccessibilityExisting RoadsReserved AreasBase Speed Between SectionsFlow Network ConstructionMinimum Cost Flow OptimizationEarthwork Plan GenerationOptimal Earth Flow netowrkHeuristic RulesLayout/Order constraintsEarthwork PlanFramework8Minimum Cost Flow(MCF) Based Methodb1b2b3b4b5b6c14c25c36𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 �𝑖𝑖,𝑗𝑗 ∈𝐴𝐴 𝑐𝑐𝑖𝑖𝑗𝑗𝑥𝑥𝑖𝑖𝑗𝑗�𝑗𝑗: 𝑖𝑖,𝑗𝑗 ∈𝐴𝐴 𝑥𝑥𝑖𝑖𝑗𝑗 − �𝑗𝑗: 𝑗𝑗,𝑖𝑖 ∈𝐴𝐴 𝑥𝑥𝑗𝑗𝑖𝑖 = 𝑏𝑏(𝑚𝑚)𝑙𝑙𝑖𝑖𝑗𝑗 ≤ 𝑥𝑥𝑖𝑖𝑗𝑗 ≤ 𝑢𝑢𝑖𝑖𝑗𝑗for all 𝑚𝑚 ∈ 𝑁𝑁for all (𝑚𝑚, 𝑗𝑗) ∈ 𝐴𝐴N is a set of n nodes A is a set of m directed arcsMinimum cost flow network9Minimum Cost Flow (MCF) Based MethodArea A is a negative net volume area (fill); Area B is a positive net volume area (cut).Area BArea A12345678910111213 16 19 2214 17 20 2315 18 21 24tr tr tr tr tr tr trFlow network constructionArcsDirectionsUnit costs10Minimum Cost Flow (MCF) Based MethodArea BArea A12345678910111213 16 19 2214 17 20 2315 18 21 241467430293039810655013148463713342578193526368938695670282578862113 53870 153494259 1342866537707160891115310732Earth Flow Network11Turning optimum material network flows into ready-to-execute haul jobs1) Maximum flow first2) Minimize mobilization of excavatorsArea BArea A12345678910111213 16 19 2214 17 20 2315 18 21 241467430293039810655013148463713342578193526368938695670282578862113 53870 153494259 1342866537707160891115310732Heuristic rules 12Haul jobs derived from optimum material flowsSub Flow Job Cut Fill Volume Route (𝑅𝑅) Predecessor1 1 10 11 1065 - -2 2 22 19 2661 - -3 22 16 9169 [19] 24 22 13 4259 [19,16] 33 5 23 20 4500 - -6 23 17 6653 [20] 54 7 5 8 4497 - -8 2 8 13423 [5] 79 2 11 5929 [5,8] 813Validation & EvaluationAverage weightedhaul distance (m)Haul effort(bm4)Morley, Lu, and AbouRizk (2014)Heuristic rules 411 165,805,946Morley, Lu, and AbouRizk (2014)Random rules 431 173,790,000Proposed Method 401 161,543,988Improvement compared to RandomRules 7% 8%Improvement compared to HeuristicRules 3% 3%Optimal validation & evaluation14Validation & EvaluationBlock removal validation & evaluationLayout 1Layout 315Validation & EvaluationLayout Percentage of Jobs with Mutual RelianceLiu and Lu (2014) (Original)with Floyd’s AlgorithmProposedMethodLayout1 34/57 = 60% 0%Layout3 30/56 = 54% 0%Mutual reliance of shortest path based method reaches up to 60%.Mutual reliance is eliminated in proposed research.Block removal validation & evaluation16ConclusionThe paper proposed an approach which:1) Provides an intuitive graph based interface.2) takes job sequence and constructability into consideration.3) Is able to generate multiple optimal solutions –practically feasible.4) Eliminates “soft blocks”17Questions ?18
Open Collections will be undergoing maintenance Monday June 8th, 2020 11:00 – 13:00 PT. No downtime is expected, but site performance may be temporarily impacted.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- International Construction Specialty Conference of the Canadian Society for Civil Engineering (ICSC) (5th : 2015) /
- Optimizing earthwork hauling plan with minimum cost...
Open Collections
International Construction Specialty Conference of the Canadian Society for Civil Engineering (ICSC) (5th : 2015)
Optimizing earthwork hauling plan with minimum cost flow network Li, Duanshun; Liu, Chang; Lu, Ming Jun 30, 2015
Page Metadata
Item Metadata
Title | Optimizing earthwork hauling plan with minimum cost flow network |
Alternate Title | Optimize earthwork hauling plan with minimum cost flow network |
Creator |
Li, Duanshun Liu, Chang Lu, Ming |
Contributor | International Construction Specialty Conference (5th : 2015 : Vancouver, B.C.) Canadian Society for Civil Engineering |
Date Issued | 2015-06 |
Description | Linear programming is commonly used in earthwork hauling plan. However special expertise in forming and solving linear equations, along with considerable efforts in interpreting results, is required to apply these methods in practice. Moreover, previous methods mainly focus on cost estimation and thus largely ignore the constructability issues; this makes earthwork hauling plan impractical for construction planning. We aim to address these problems by introducing an intuitive graph based approach which optimizes the earthwork hauling plan using the minimum cost flow network. We choose the total traveling time as the objective function to be minimized in order to separate the earthwork hauling plan from other factors such as fleet combination. Our method directly connects adjacent sections allowing accessibility between them, instead of connecting the centers of cut and fill cells as potential haul routes as in previous methods. As a result, the proposed method is capable to handle constructability issues caused by “soft blocks” -which cannot be eliminated in establishing the standard flow network as their existence impose constraints on the grading plan. The graphic earth flow network can be used to guide the execution of the earthwork project and generate multiple grading plans, providing more flexibility compared to traditional methods. We present an earthmoving example with a reserved soft area and show that the proposed method is graphically intuitive, easy to establish and able to handle soft blocks. |
Genre |
Conference Paper |
Type |
Text |
Language | eng |
Date Available | 2015-11-26 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0076334 |
URI | http://hdl.handle.net/2429/53721 |
Affiliation |
Non UBC |
Citation | Froese, T. M., Newton, L., Sadeghpour, F. & Vanier, D. J. (EDs.) (2015). Proceedings of ICSC15: The Canadian Society for Civil Engineering 5th International/11th Construction Specialty Conference, University of British Columbia, Vancouver, Canada. June 7-10. |
Peer Review Status | Unreviewed |
Scholarly Level | Faculty Other |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 52660-Li_D_et_al_ICSC15_175_Optimizing_Hauling.pdf [ 2.56MB ]
- 52660-Li_D_et_al_ICSC15_175_Optimizing_Hauling_slides.pdf [ 582.45kB ]
- Metadata
- JSON: 52660-1.0076334.json
- JSON-LD: 52660-1.0076334-ld.json
- RDF/XML (Pretty): 52660-1.0076334-rdf.xml
- RDF/JSON: 52660-1.0076334-rdf.json
- Turtle: 52660-1.0076334-turtle.txt
- N-Triples: 52660-1.0076334-rdf-ntriples.txt
- Original Record: 52660-1.0076334-source.json
- Full Text
- 52660-1.0076334-fulltext.txt
- Citation
- 52660-1.0076334.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.52660.1-0076334/manifest