Arrangement of material depots for line segment–modeled structures using continuous conditions

One of the preliminary processes in construction management is the planning of the construction process. Part of the construction planning process is construction site layout planning (CSLP), in which space, time, material, labor, money and equipment are recognized as resources (Tommelein et al. 1992; Winch and North 2006). The target of CSLP is to minimize construction time, cost or required resources. Because CSLP has significant impact on productivity, cost, time, safety and security, several site layout planning models have been developed in the past decades. These have been collected and presented in an overview (Sadeghpour and Andayesh 2015). These models use the space in three different ways: predetermined location, grid system and continuous site space. The space types were clustered into the following five groups: total space, product space, installation space, available space and required space (Winch and North 2006). A partial task of CSLP is the allocation of construction objects on site. In practice, the allocation of construction objects is carried out routinely (Sanad et al. 2008) based on human judgment using the first-come-first-served method (Zouein and Tommelein 1999) or using the construction manager's experience (Cheng and O’Connor 1996). Due to the large number of factors that are involved in CSLP, computers have been identified as efficient tools for solving the problem, using resources such as computer-aided systems that are based on computer-aided drawing (CAD) (Sadeghpour et al. 2004), artificial intelligence (AI) techniques (Tommelein et al. 1992) or genetic algorithms (Hesham et al. 2003; Li and Love 1998; Hegazy and Elbeltagi 1999; Mawdesley et al. 2002; Tam and Tong 2003). The objects, the structure and the spaces are continuously adjusted during different phases of the construction project. Therefore, researchers have developed dynamic site planning methods as well, such as the max–min ant system (Ning et al. 2010) or building information modeling (BIM) (Kumar and Cheng 2015). Most of the developed models identify the number and the size of the temporary facilities that serve the construction site and then search for the optimal arrangement by minimizing the total transportation costs between the facilities or from the facility to the structure to be built: (1)min∑i=1n∑j=1mdijRij\min \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {{d_{ij}}{R_{ij}}}} where n is the total number of construction objects; m is the total number of constraining objects; d_ij is the traveling distance from the location of the construction object i to its ideal location concerning the constraining object j and R_ij (R_ij∈Q) is the parameter that represents the transportation cost or the weight of constraint between construction objects i and constraining object j (Sadeghpour et al. 2004). The traveling distances can be calculated by using either Euclidean distance or rectilinear distance.

The root of the CSLP problem is known as the k-median problem in the operation research literature as a part of the location allocation problem (LAP), where the demand is understood as the structure that needs to be built, the density is readable as the volume of the structure and the facility is readable as the material depot. If the number of facilities (k) is one, the problem is known as the classic Fermat–Weber problem (Friedrich 1929). In the CSLP models, if the number k≥1, the facilities’ locations can be calculated in discrete form by dividing the site into a given grid-based set of feasible location points and dividing the structures into unit areas or even in a continuous manner using genetic algorithms or other AI techniques because of the infinite number of possibilities. Most of the LAP literature is based on discrete demand (Drezner 1995), such as the known models of the CSLP where the target is to define the site objects’ space and shape by using a collection of unit areas. In this article, for the k-median problem, a model is presented that uses the structures as continuous demand as line segments or areas (as these were provided by the architect and engineers in their CAD drawings) and searches for the optimal arrangement on the entire XY plane.

Architects and engineers define most structures with 3D CAD elements. The structures are represented by 2D markings, with the Z directional information included on the drawings. Some structures are marked by symbols (e.g. pillars or windows), some are marked by line segments or curves (e.g. wall tiling) and some are marked by areas (e.g. floor tiling, concrete slabs or the boarding of the slab formwork). The material, size, volume and exact location of the structure are given in the architectural documentation in advance. The problem presented in this study is very similar to the problem studied in an earlier publication of the authors (Pém and Mályusz 2015), but here we deal with the structures that are marked as line segments instead of areas. The structure is modeled as a 2D figure denoted by the end points (A_i) of the line segments.

2.1

Assumption 1

The structures are marked by a group of line segments. The line segments that belong to a depot must look like a line segment chain. The group of line segments consists of K pieces of line segment chains. The line segment chains are connected to each other by their end points. A line segment chain consists of L pieces of line segments where the end point of each line segment is the beginning point of the next one that has a volume W>0 if it is possible (as shown in Fig. 1). Each line segment is defined in advance by its end points A_i(x,y), where (i=1 . . . m, m∈N), and a W_i,i+1 figure that represents the Z directional size of the structure V_s. At each point of a line segment, the Z directional size is constant.

Fig. 1

2.4

Assumption 4

The handling paths from a final material depot to each point of the served structure (line segment) can be calculated by two ways: using either the Euclidean distance or the shortest path inside the feasible handling area. In this study, for the calculations, we use the Euclidean distance in an unusual way. The length of the total delivery path from a certain point to the structure is counted by the measure of the areas or volumes that are defined by the modeled structure's 2D marking [Fig. 2(a)] and the vertical projection of the marking onto the envelope of the Euclidean cone, which is set into that certain point. In this case, where the structure is marked by line segment [A_iA_(i+1)] or curve and defined by its end points A_i(x,y), the total delivery path from a point S(a,b) to the structure is counted as areas (line integrals), as shown in Fig. 2(b). (2)Ti,i+1=∫titi+1(|a−x|2+|b−y|2)1/2dϕ{T_{i,i + 1}} = \int\limits_{{t_i}}^{{t_{i + 1}}} {{{\left({{{\left| {a - x} \right|}^2} + {{\left| {b - y} \right|}^2}} \right)}^{1/2}}d\phi} where T represents the size of the area bounded by the 2D marking, the vertical projection of it onto the Euclidean cone; dΦ is an extremely small change in arc length of the curve and A′_i is the distance between the points A_i and S; (3)x=g(t),y=h(t):dφ=(dx2+dy2)1/2Ai'((a−xi)2+(b−yi)2)1/2\matrix{{x = g(t),y = h(t):} \cr {d\varphi = {{\left( {d{x^2} + d{y^2}} \right)}^{1/2}}} \cr {A_i^{'}{{\left( {{{\left( {a - {x_i}} \right)}^2} + {{\left( {b - {y_i}} \right)}^2}} \right)}^{1/2}}} \cr}

Fig. 2

2.5

Objective function

The objective is to find the allocation of the final material depots, from where the material can be handled in pieces to their built-in locations in the structure along the minimal length of paths. This model leaves out of consideration the delivery cost because it assumes that all of the delivery paths are horizontal and that the delivery cost is directly proportional to the length of the delivery path. The target is to minimize the length of the total delivery path.

2.5.1

In the case of k=1

The line segment chain is given and the minimization form can be solved by any kind of two-parameter minimization: (4)min(a,b)∑i=1l[W(Ai,Ai+1)∫AiAi+1(|ak−x|2+|bk−y|2)1/2dφ]\mathop {\min}\limits_{(a,b)} \sum\limits_{i = 1}^l {\left[ {{W_{\left( {{A_i},{A_{i + 1}}} \right)}}\int\limits_{{A_i}}^{{A_{i + 1}}} {{{\left( {{{\left| {{a_k} - x} \right|}^2} + {{\left| {{b_k} - y} \right|}^2}} \right)}^{1/2}}d\varphi}} \right]} where l (l∈N) is the number of line segments; W_{(i, i+1)} (W∈Q) is the Z directional volume of the line segment between A_i and A_i+1 (defined by the volume of the structure); and a_k and b_k are the x and y coordinates of the searched (S_k) final material depot on the entire XY plane.

2.5.2

In the case of k>1

There are an infinite number of solutions because the start points and the end points of each line segment chains are unknown. If any point of the line segment group is renamed as cut point (C) for dividing the structure into K pieces with equal volume, then each of the line segment chains is defined and the minimum of the sum of the delivery paths (areas) for that certain cut point can be calculated as follows: (5)∑k=1kmin(a,b){W(C,Ai)∫CAi(|ak−x|2+|bk−y|2)1/2dφ+∑i=1Lk[W(Ai,Ai+1)∫AiAi+1(|ak−x|2+|bk−y|2)1/2dφ]W(Ai+1,Ek)∫Ai+1AE(|ak−x|2+|bk−y|2)1/2dφ+}\sum\limits_{k = 1}^k {\mathop {\min}\limits_{(a,b)}} \left\{{\matrix{{{W_{(C,{A_i})}}\int\limits_C^{{A_i}} {{{\left( {{{\left| {{a_k} - x} \right|}^2} + {{\left| {{b_k} - y} \right|}^2}} \right)}^{1/2}}d\varphi +}} \hfill \cr {\sum\limits_{i = 1}^{{L_k}} {\left[ {{W_{\left( {{A_i},{A_{i + 1}}} \right)}}\int\limits_{{A_i}}^{{A_{i + 1}}} {{{\left( {{{\left| {{a_k} - x} \right|}^2} + {{\left| {{b_k} - y} \right|}^2}} \right)}^{1/2}}d\varphi}} \right]}} \hfill \cr {{W_{\left( {{A_{i + 1}},{E_k}} \right)}}\int\limits_{{A_{i + 1}}}^{{A_E}} {{{\left( {{{\left| {{a_k} - x} \right|}^2} + {{\left| {{b_k} - y} \right|}^2}} \right)}^{1/2}}d\varphi}} \hfill \cr} +} \right\} where C is the cut point for dividing the group of line segments into line segment chains, C is any point of any line segment and E_k∈(A_i, A_i+1) is the end point of each line segment chain. The end point of a line segment chain is the start point of the next line segment chain; K (k=1 . . . K, k∈N) is the number of needed depots and L_k is the number of line segments that belong to the certain depot.

If all A_i and E_k are identified and renamed as relevant points R_j (j=1 . . . n, n∈N and n≤k·m), where R_(j+1) is the closest A_i or E_k point counterclockwise to R_j, then the form can be simplified as follows: (6)∑k=1Kmin(a,b)∑j=1Lk[W(Rj,Rj+1)∫RjRj+1(|ak−x|2+|bk−y|2)1/2dφ]\sum\limits_{k = 1}^K {\mathop {\min}\limits_{(a,b)} \sum\limits_{j = 1}^{{L_k}} {\left[ {{W_{\left( {Rj,{R_{j + 1}}} \right)}}\int\limits_{{R_j}}^{{R_{j + 1}}} {{{\left( {{{\left| {{a_k} - x} \right|}^2} + {{\left| {{b_k} - y} \right|}^2}} \right)}^{1/2}}d\varphi}} \right]}}

So, the minimization form for the case of k>1 is as follows: (7)minC∑k=1Kmin(a,b)∑j=1Lk[W(Rj,Rj+1)∫RjRj+1(|ak−x|2+|bk−y|2)1/2dφ]\mathop {\min}\limits_C \sum\limits_{k = 1}^K {\mathop {\min}\limits_{(a,b)} \sum\limits_{j = 1}^{{L_k}} {\left[ {{W_{\left( {{R_j},{R_{j + 1}}} \right)}}\int\limits_{{R_j}}^{{R_{j + 1}}} {{{\left( {{{\left| {{a_k} - x} \right|}^2} + {{\left| {{b_k} - y} \right|}^2}} \right)}^{1/2}}d\varphi}} \right]}}

The objective is to find C for the global optimal arrangement. If we place C onto each A_i and solve the equation m times, each counting will give a minimum of the total delivery paths that belongs to the certain C_i (where C_i is the cut point set in A_i). If we relocate the cut point to any of the E_K points that are produced by a certain C_i, the equation will give the same result as with the original C_i. If we place the cut point anywhere on the line segment between R_j and R_j+1, the solution will be a member of a curve (f_R) that has one minimum or one maximum point. If the curve is concave, then R_j or R_j+1 will be the location of the cut point for the local minimum solution between R_j and R_j+1. If the curve is convex, the minimization of the curve between R_j and R_j+1 will give the location of the best cut point and will result in the minimum of the total delivery distance, as shown in Fig. 3.

Fig. 3

The global minimum of the model is the lowest result of all the counted local minimums. This means the minimization has to be solved 2m times (m times for all A_j and m times for all the curves between R_j and R_j+1) to find the global minimum of the model (Fig. 6.).

In this example, the target is to find the optimal allocation of the final material depots [S_i(a,b)] for the wall tiling work of a rectangular room (Fig. 4), from where the material units can be delivered to the structure along the minimal path.

Fig. 4

The volume of a material depot, as well as the volume and the geometry of the tiling work, with Z directional information is provided in advance [V_d, V_s, A_i(x,y), Fig. 4]. The number of needed depots is calculated using the expression k=V_s/V_d. Vs=3×(10+5+10+5)−(3×1.5)−(1×1.5)−(2.5×1.5)−(1×3)=77.25 m2;Vd=25.75 m2;k=Vs/Vd=3 pieces\matrix{{{V_s} = 3 \times (10 + 5 + 10 + 5) - (3 \times 1.5) - (1 \times 1.5) - (2.5 \times 1.5) -} \hfill \cr {(1 \times 3) = 77.25\,{{\rm{m}}^2};{V_d} = 25.75\,{{\rm{m}}^2};k = {V_s}/{V_d} = 3\,{\rm{pieces}}} \hfill \cr}

At first, all R_j points have to be found by measuring counterclockwise k pieces’ V_d, the volume of line segment chains from all A_i (Fig. 5), and their coordinates have to be marked (Tab. 1). We have m=12 pieces for A_i and we have (k−1)m=24 pieces for E_ik.

Fig. 5

After all of the relevant points are found, the local minimums of the total delivery paths are counted by a program called Mathematica 7 for each A_i as cut point. The minimization form ran 12 times and gave the minimums of the sums of the total delivery path for all Rj (Tab. 2). (8)∑k=1Kmin(a,b)∑i=1Lk[W(Ai,Ai+1)∫AiAi+1|ak−x|2+|bk−y|2dφ]\sum\limits_{k = 1}^K {\mathop {\min}\limits_{(a,b)}} \sum\limits_{i = 1}^{{L_k}} {\left[ {{W_{\left( {{A_i},{A_{i + 1}}} \right)}}\int\limits_{{A_i}}^{{A_{i + 1}}} {\sqrt {{{\left| {{a_k} - x} \right|}^2} + {{\left| {{b_k} - y} \right|}^2}} d\varphi}} \right]}

The calculated lengths of the sums of the total delivery path (Tab. 2) are marked in each R_j point by a perpendicular line to the line segment chain, where the length of each marked line corresponds to the length of the sum of the total delivery path (Fig. 6). In Fig. 6, the line segment chains are rotated into one straight line so that the calculated lengths are more readable. If we move the cut point counterclockwise from R_j, the minimal of the total delivery distance will move on a curve (Fig. 6) until the cut point reaches R_j+1.

Fig. 6

The equation of the curve is known between all R_j. It means that we know k·m=36 pieces of curves, but there are only m=12 pieces of different essential curves because it gives the same result between A₁ and E₁, E₂ and E₃, E₃ and A₁, as shown in Fig. 6. It is easier to decide whether the curve should be minimized if the cut point and the end point of the line segment chain are moved from R_j counterclockwise with a short volume distance (Δ), and the lengths are compared with each other as follows: (9)IF{∑1k(CK'+EK')−(CK+Δ'+EK+Δ')<0⇒min≥0⇒end}{\rm IF}\left\{{\sum\limits_1^k {\left( {C_K^{'} + E_K^{'}} \right) - \left( {C_{K + \Delta}^{'} + E_{K + \Delta}^{'}} \right)\matrix{{< 0 \Rightarrow \min} \cr {\ge 0 \Rightarrow {\rm{end}}} \cr}}} \right\}

Only just those curves where the movement causes shorter length are significant. In this example, these curves are between (R₁ and R₂), (R₂ and R₃) and (R₉ and R₁₀). Each of these curves should be minimized but memorized only if the evaluated cut point is located between R_j and R_j+1 (Fig. 3).

In this example, there were none like this, so the lowest solution of all counted equations for all relevant points is the global minimum of the total delivery distance. In this case, the optimal allocation of the depots belongs to the cut point of R₁₀=R₁₁=A₁₀=A₁₁, as presented in Tab. 2 and shown in Fig. 7.

Fig. 7

The architect drawing of this example was given to professional bricklayer experts. The experts were asked to mark the best arrangement of the three depots and the parts of the structure that they would serve from each depot for minimizing the total delivery path. The solution provided by one of the experts is shown in Fig. 8, which is the closest solution to the optimal arrangement. This expert's layout is shown in Fig. 8(a), where the surfaces of the walls are tilted onto the XY plane. Each color represents the surface of the structure part that the expert would serve from a certain depot. It is seen in Fig. 8(b) that from the first depot (S₁), the expert would serve a bigger-volume structure part than the depot volume and from the other two depots (S₂, S₃), the expert would serve smaller-volume structure parts. Based on the technology itself, the first depot will run out of the material before the tiling work is done, so the top part of the structure should be served from the other two depots that are located farther [shown in Fig. 8(b)].

Fig. 8

In this case, according to the expert's solution, the workers would deliver the materials by a >38% longer path compared to the optimal arrangement shown in Tab. 2. This 38% increment of the total delivery path is significant if we consider that an increase in the total delivery path by 7% causes a measureable rise in the total delivery time (Pém 2009). There were experts whose results were >69.91% worse than the optimal solution. Based on these experiments, the search for C to find the optimal arrangement is worth the time because the worst minimal solution for different cut points (row R₆ in Tab. 2) is 12.12% worse than the optimal arrangement (row R₁₀ on Tab. 2).

It is a well-known fact that everybody wants to use the least amount of energy to do a job. It means that the laborer for each delivery will choose that particular final material depot to carry a piece of material that is the closest to the destination of that certain piece of material. This way of behavior is described in mathematics and called Voronoi regions (Voronoi 1908). It is a method of dividing an area into a number of regions, where all points of the region are closer to the corresponding seed (also called host, or here, as location of the final material depot) than to any other seed. The model gives the optimal arrangement of the final material depots [shown in Fig. 9(a)] so that the Voronoi regions can be drawn [Fig. 9(b)]. These regions give the boundary of the structure parts that will be served by the corresponding final material depots in terms of laborers’ mentality. It can be observed from Fig. 9(c) that two of the final material depots will run out of the material before their structure part is complete. When the first final material depot (S₁) runs out of the material, the worker will choose a new host out of the remaining ones based on which is closer to the destination (a new set of Voronoi region should be drawn). After the second final material depot runs out of the material, only the third one can host the entire structure that is left. In this case, the workers would deliver the materials by a 45% longer path than was found as the optimal arrangement, shown in Tab. 2.

Fig. 9

This example was given to other experts and one of the experts proposed a solution that resulted in a 69.91% longer path. It is very obvious that the arrangement of the final material depots is not adequate for minimizing the sum of total delivery paths, and the served structure parts need to be identified and unequivocally marked on the site for each depot. The next step is to convince the laborer that it is the best practice.

In this example, the location of each depot was searched on the entire XY plane, but it could be localized into a certain place as available space (Winch and North 2006). This example was solved for a convex-shaped structure, and the model counted the lengths of the delivery paths by Euclidean distances, but it can deal with obstacles and concave structures in exactly the same way as the discrete model does by dividing the area up into areas named “visible from”, “partly visible from” and “not visible from” (Sadeghpour et al. 2006). In this example, the delivery cost was left out of consideration because the allocation of only one kind of material depots was searched for and the delivery paths were horizontal in every direction, but this model can be integrated into the model that minimizes the total delivery cost as well. It needs less input data than the discrete model does because it does not need the number and the exact places of the units that build up the structure. This model can be an alternative model to the discrete model even if the number of units that make up the structure is large or unknown because in this case, the required time for the calculation can be significantly less, and the difference between the solution of these two models is negligible.