Construction site utilization planning esp. laydown area has implications for project safety, con struction efficiency, scheduling, and budgetary performance of a project. An important aspect not identified in past research efforts are the current practices for laydown area plan development currently used by the construction industry. Therefore, the objectives of this research were to: 1) determine the best practices for laydown area planning; 2) develop a procedure that outlines the laydown area planning process; and 3) show how current Building Information Modeling (BIM) technology can be harnessed for site utilization plan development. The current research hypothesize s a system that can computationally generate vast numbers of design options, respect project constraints, and analyze for laydown area hygiene goals, can assist the project team and procurement coordinator make better decisions thus reducing overhead costs and time routinely associated with manually planning this process. It also discussed the design and development of a parametric tool built from insights into space plannin g from architects and computational design, coupled with algorithms for evolutionary systems and computational geometry, to develop an automated computational framework that enables rapid generation and analysis of space plan layouts. Page 2 of 39 The system as propos ed in the paper automatically generates hundreds of design options from inputs typically provided by a construction manager , including a site outline and program document with desired spaces, areas, quantities, and adjacencies to be satisfied. We envision that this novel approach combines analytical tools and heuristics to model the dynamic nature of material management, encompassing commonly -used optimization techniques which use weighted target functions based on rule of thumb. A case study demonstrates t he suitability and efficiency of the proposed optimization method in reactive laydown yard management. THE PROBLEM Failure to plan the site layout in advance is a prime cause of operational inefficiency and can increase the overall cost of a project subst antially. In the absence of a precise site layout plan, the following problems may occur: a. Material stacks wrongly located : Materials arriving on site are off -loaded into what someone guesses to be the correct location. This problem may involve multiple handling of materials to another location. For example: • They may be stocked over a drainage line or near the edge of excavation; • They are too far from the work area; • They are too remote from the hoist or not within the radius of the crane; • They impede t he smooth flow of work traffic across the site; • Their delivery was wrongly phased, and they are not needed until much later in the project; Page 3 of 39 • They are fragile and susceptible to damage . b. Plant and equipment wrongly located. For example: • The mixer is inacces sible for the delivery of materials; not enough room for the storage of aggregates; • Fixed cranes are unable to reach all parts of the works; • Hoists have insufficient capacity or height to handle the loads or badly located in relation to the floor layout; c. Inadequate space allowed. Where inadequate space is allowed for the stacking of materials or activities: • Materials may be stacked to high or stacked on roadways causing hazards ; • Working areas may become too cramped or additional areas may have t o be alloc ated with the consequent waste of time caused by having to travel between them. d. Office Trailers wrongly located in relation to their effective use , such as: • Site office located too near noisy activities such as mixer, or located too near to site roads in dusty conditions, or too remote with insufficient overview of the site ; • Warehouses having inadequate access for loading and unloading or located in insecure area. Therefore, before moving on to a site, it is necessary to prepare a detailed site plan, depicting the locations of every item of equipment, accommodation, ancillary work areas and materials storage areas. Page 4 of 39 CURRENT PRACTICE Currently , the construction manager or site superintendent manually mark s up a single site drawing to include major temp orary facilities needed on site throughout the duration of the project. They depend on knowledge of years of experience, common sense, and adoption of past layouts in determining positions of temporary facilities on site. But, they cannot keep track of all factors that could affect the selection, location, and interactions of all facilities to be positioned esp. for activities scheduled in the future . In fact, site layout planning is one of the preplanning tasks to be accomplished in a construction project. This task has an interactive relationship with the other planning tasks such as scheduling, selection of construction method, procurement and material planning, manpower and equipment planning, and financial planning. So, it becomes a task as important as other tasks that project managers have to accomplish. A well-planned site including all temporary facilities and utilities lead to: 1) increasing productivity and safety, 2) reducing area(s) needed for temporary construction, and 3) maximizing utilization . LITERATURE REVIEW The current research builds on the implicit and explicit domain knowledge and processes in space planning and leverage s computation for repetitive design generation and analysis tasks, liberating construction managers from invest ing time in problem formulation and decision making related to dynamic laydown area planning. We first briefly describe foundational work in data structures and space -planning methodologies, then explain the working methodology via an analogy to space planning employed in architecture design practice (refer Figure 1) by describing the Page 5 of 39 Hierarchical Space Assignment strategy, a top -down approach from whole to part, and the K -dimensional (K -d) Tree Data Structure, which showcases an efficient data storage, retrieval, and traversal technique. Next, we discuss the splitting strategy to assign departments and programs to the site, and the implementation of a cell grid that enables circulation computation with analysis and scoring of the generated space plans. We then describe the implementation of the methodology in Autodesk Dynamo, and the testing of its the validity and efficacy within a case study. Any space planning process necessitat es multiple iterations until design goals are achieved. Consequently, we have implemente d a data structure which can rapidly access identical data multiple times and store spatial data in a manner supporting nearest neighbor search, which is necessary to build department and program topology maps for design fitness appraisal. Owing to its spat ial partitioning structure, K -d tree Figure 1 Flow Chart depicting the interaction between architecture design and various sta keholders in a design process Page 6 of 39 serves our purposes by using nested elements to store data. Nested elements provide a means to retrieve data through bidirectional traversal, top down and bottom up. K-d trees store and organize data as a set of ‘n’ poi nts in a multi- dimensional space, in a structure of a binary search and partitioning trees. Due to their efficiency and speed, they are primarily applied to nearest -neighbor queries, search algorithms, database applications, and ray -trace methods. Originat ing in computational geometry, their efficiency arises from the space partitioning algorithm organizing objects in K -d space (Knecht and König 2010). Average running time of an ‘n’ data point database for: • Insertion – O(log n); • Deletion of root – O(n(k -1)/k) • Deletion of any random node – O (log n) (Bentley 1975). Eastman (1972) automated space generation in two dimensions by implementing decision rules to guide subsequent placement and arrangement of design units. These rules were driven by operators that transformed the state of the design units iteratively to satisfy a set of relationships between them. Jo and Gero (1998) highlighted an evolutionary -design model describing a schema to represent design knowledge capable of providing design solutions f or the given problem requirement. Their work highlighted topological and geometrical arrangements of spatial elements tested on a large office layout problem. Though not many variations of the spatial arrangement were highlighted, their work showed the robustness of coupling genetic algorithm - based searches with design workflows to produce good results in space planning. Michalek, Choudhury, and Papalambrosa (2002) presented an optimization model integrating optimization and subjective decision making durin g conceptual design. Page 7 of 39 Coupling gradient -based algorithms and evolutionary algorithms, they innovated to include human decision making in the workflow. They implemented topology optimization algorithms on top of geometry optimization algorithms. The results were automated space plans but limited in variation. Nassar (2010) presented new findings in graph theory with direct implications in space planning problems. He described architectural space plans as simple, connected, labeled planar graphs, and elaborated on the relevance of finding a rectangle dual for every planar graph to increase solution space. This work outlined a tool for architects to generate space plans. Realizing spatial relationships as planar graphs with nodes as rooms and edges as adjacencie s, it claimed that the proposed model could provide a truly exhaustive set of potential designs. However, this model was limited to two -dimensional space plans only. Boon et al. (2015) employed genetic algorithms to generate 3D space stacking, respecting i nput adjacency requirements by the user. Their algorithm evaluates space plans based on adjacency constraints to minimize the total distance of all interconnected programmatic elements. They prioritized the program spaces based on practice expertise and us er input, which helps discard unrealistic design solutions. The algorithm stacks spaces in three dimensions, distributing program elements over multiple floors and sometimes unnecessarily complicating architectural space layouts. Some relevant research in automated space plan generation comes from game design, which requires extensive 3D environments at architectural scale. Lopes et.al (2010) generate floor plans for different classes of buildings, many with connected floor levels, offering limited control to the designer for functional constraints. One of the salient features of this system is the grid - based strategy for placing and growing rooms, Page 8 of 39 which generates building zones, followed by room areas, constrained by adjacency and connectivity. Marson and Musse (2010) implement a squarified t reemap algorithm (previously used to represent hierarchical information graphically) to compartmentalize the input space into different zones or regions. These zones are organized into a hierarchy that satisfies design goals and site constraints and are visualized into a square tree map to generate various floor layouts. Their work excels at building sophisticated circulation networks. After the rooms are site located, a circulation network graph is built to understand w hich rooms are connected or disconnected from each other. They use an A* algorithm to traverse the connectivity graph and find shortest paths to access spaces from the lobby. METHODOLOGY ADOPTED The Laydown Area Configurator has distinct components orchestrated to generate and analyze space plans. It generates layouts as closed polylines representing each space type (either the department or the program element), with the circulation network represented as colored poly surfaces for any generic architectural design problem. Hierarchical Space Assignment Our approach is hierarchical ( refer Figure 2). Program elements are spaces to fit on the site. Certain types of program elements can be clustered to form departments. The recurs ive algorithm first places the department on site and then programs within departments, finally placing circulation within and between departments. Page 9 of 39 Figure 2 The Hierarchical Space Planning approach adopted K-d Tree Data Structure The proposed space- assignment algorithm uses a K -d data structure dividing the K -d space by partition planes perpendicular to one of the coordinate axes ( refer Figure 3). Figure 3 Space assignment algorithm adopted based on K -d data structure binary tree Conventionally, the median or average of the point coordinates in the database is calculated in the split dimension. Site space is the root and the first node after the spatial split, dividing the point set in two. All points whose coordinates are smaller than the split value reside in the tree’s left branch, while the other points are relegated to the right branch. This step is repeated until reaching a threshold depth of the K -d tree. Page 10 of 39 Similar to an approach to Bentley 1990, e ach generated node is assigned a space or region, each of which can contain child nodes. Bentley 1975 corroborates that K -d Trees efficiently search and traverse data sets to create spatial plan partitions. Space data trees implement a modified version of K -d data structures, where the point set is split by a line dividing a monolithic space into two, using an algorithm to allocate program elements at site locations. For example, a programmatic requirement to locate patient rooms on the site periphery or the need of an entry lobby on the site’s west side. Any region on the site unassigned to a department or program element is termed a ‘container,’ while any region allocated to a department or program is termed a ‘space.’ The root of the data tree is the container (the site), with its left child the region of the site to the left of the splitting line. The remaining region becomes the right child of the root and the current container. The algorithm recursively r epeats the operation for each node until all spaces are stored in the tree. After each split of the container, the left node becomes a space node, and the right node becomes a container node. The direction of the split can be flipped from horizontal to ver tical alignment at every iteration, similar to Shneiderman ’s 1992 slice and dice techniques, depending upon the aspect ratio of the container and the program elements awaiting allocation. Space and Container Node Data After the split to represent site loca tion, every space node contains data including: Space Node ID, Parent Node ID, Left Child Node ID, Right Child Node ID, Split Line, Department ID Assigned, Cells Allocated, and Polyline representation. Page 11 of 39 Every container node retains data above except for Department ID. As each node stores links to its parent and child nodes, the space data tree can be traversed upwards and downwards ( refer Figure 3). Benefits of using Space Data Tree are elucidated below : a. Provides fast and efficient data storage to represent spatial data. b. Supports nearest neighbor searches, which help build department topology maps and appraise the efficiency of a layout by representing department neighbors and adjacency. c. Finds neighbors for departments and program elements and shared edges b etween them, with each Space and Container Node storing the splitting line. Th is allows the computation of circulation networks between and within departments. d. Can randomly ascertain circulation paths between any two spatial locations in the space plan, ai ding in space plan appraisal through key metrics such as nurse travel routes and distances, patient flow paths, fire egress routes, etc., in a healthcare facility. Splitting Strategies The current research deployed several custom methods to split a polyline into two or more by a dividing line, including: • Split by Distance: Creates a splitting line from a given point on a polyline by a specified distance or by a specified line orientation. Returns two polyli nes on a successful split. Page 12 of 39 • Split by Ratio: Splits a polyline into two polylines by a supplied ratio and direction. • Split by Area: Ensures split polylines meet area requirements as specified by the user or the algorithm, employing a brute force splitting strategy by iteratively applying the split by distance method, altering the distance variable after each iteration. • Split by Line: Requires the user or the algorithm to provide a splitting line when there is an existing splitting line for further splits. • Split Recursively to meet Minimum Dimension: A recursive split strategy adapted to split a single polyline into multiple polylines until the minimum dimension of each polyline meets an acceptable width or length constraint specified by the user. Employing a s lice and dice technique, after each split the split direction is toggled between horizontal and vertical. This strategy arrives at interesting spatial patterns with an accept- able level of architectural rationality. The listed methods divide the input sit e polyline into individual departments containing program elements. Method outputs coupled with department and program information are assigned to the space data tree to organize them for further computation. • Split by Offsetting Polyline Points: A computationally faster strategy generates two polylines by shifting the points of the parent polyline, avoiding more expensive algorithms such as line -poly intersection or ordering points in a list to rebuild a polyline as used in other split strategies. Cell Grid Underneath the Spaces Assigned Page 13 of 39 From an input site outline, the system builds a bounding object containing the site polyline ( refer Figure 4). The algorithm supplies the bounding box with points on an orthogonal grid, with spacing specified by the user. A site outline test determines the contained points used to build each cell. A collection of cells is termed a grid object, employed to compute the shortest path results between program elements, placement of doors and windows, and similar problems. Grid objects are used to build the cell neighbor matrix, which tracks the neighbors of every cell in three dimensions. The benefit of such a matrix is in its capability to efficiently traverse the site. Figure 4 Cell storage and neighborhood bounding based on ID, Cell neighbor matrix, Cell weights etc. Cell Neighbor Matrix Each cell in the grid object possesses a location ID. The neighbor matrix of a cell is a list of lists, which stores identifiers of all neighboring cells. Neig hboring cells are traversed in a fixed order of right, up, left, and down. A cell identified as 0 might have cells 05, 08, 02, 15 stored in its neighbor matrix row, with 05 identifying the right -side cell, 08 denoting the upside cell, cell 02 on the left s ide, with 15 identifying the downside cell. - 1 indicates a cell lacking any neighbors. The matrix provides a means Page 14 of 39 to traverse the site from one corner to another to find specific locations, such as doors and exit routes ( refer Figure 4). Cell Weighting fo r Specific Metrics Each cell is given a custom weight to gauge different aspects of the project, such as acoustic performance, daylighting, and site constraints. Weighting influences the allocation of spatial locations for a certain program. For example, if the northwest side of the site is conducive for daylighting, then cell weights can be increased for that zone to arrive at an appropriate distribution bias. Shortest Path to Find Doors / Access Points The cell neighbor matrix also helps find the shortes t path between site regions by implementing Dijkstra’s Algorithm (Wang 2012). Specific cells are marked as doors or windows, with the objective of pathfinding to discover the shortest path to those cells from a given program element. Polyline Boundary This algorithm finds the maximum sized orthogonal polyline boundary of any input polyline having both orthogonal and non-orthogonal angles between its sides ( refer Figure 5). To locate the bounding polyline, the algorithm first identifies border cells by traversing the cell neighbor matrix. A cell is identified as a border cell if it’s either a corner cell with two neighbors or an edge cell with three neighbors. The algorithm rebuilds the cell neighbor matrix from the border cell, finds the lowest leftmost cell in the border cell list, and subsequently traverses the cells. Initially, traversal attempts a rightward search, proceeding on failure through successive tries up, left, and down. The centroid of each visited cell is stored in a point list, and the cell is marked as Page 15 of 39 unavailable for further visits, preventing infinite search loops. Upon traversing every cell, the complete centroid list will be used to build the polyline boundary. Analyzer In addition to the design Configurator , an analyzer component validates the efficacy of the generated space plan with respect to the original goals. Some analysis types implemented include gauging the percentage of program elements fitted to the site outline in comparison to specified requirements, determining the quantity of day -lit rooms with external views, and dete rmining circulation efficiency. Kindly refer Figure 6 and 7 to understand the working methodology of the Laydown Area Configurator further. IMPLEMENTATION The prototype employs an Autodesk Dynamo Package written in C# as a library of ‘zero touch’ custom nodes (Helsberg et al. 2010), which helps construct the space plan Configurator as explained below ( refer Figure 7). The Dynamo graph is composed of two components, a ‘ Configurator ’ and an ‘Analyzer.’ Figure 5 Polygon Boundary algorithm depicting the orthogonal boundary for any input arbitrary site outline Page 16 of 39 Figure 6 Flow diagram depicting the working methodology of the Laydown Area Configurator After every graph evaluation, the ‘ Configurator ’ yields distinct plan layouts rendered as a list of polyline geometries. The ‘Analyzer’ gauges the fitness of each design option to input goals and constraints. Figure 7 Computation and information flow diagram of the Autodesk Dynamo Graph The prototype proceeds as follows: Step 1: User Inputs Page 17 of 39 The graph has input requirements in the form of a site outline ‘.sat’ file and program document ‘.csv’ file ( refer Figure 8). The ‘.csv’ should contain information for each program element to be fit onto the site, with each element possessing the attributes, namely: ID, name, department or zone or material , quantity, area or dimensions (width x depth) , preference value, and adjacency list. Preference value for each program element specifies the order in which the material will be placed onto the site. The adjacency list is a comparison chart to which the material zone topology map will adhere while allocating space/area elements on the site. Other user inputs include corridor width, the aspect ratio for circulation and program elements, grid cell dimension, etc. Figure 8 .csv file input to the Dynamo Graph Page 18 of 39 Step 2: Cell Grid Information The graph builds the cell grid on the site and the initial cell neighbor matrix, which are used repeatedly in the workflow explained above. Step 3: Data Stack This step extracts input information from the program document and builds a Department Data and Program Data class object. The data stack node sorts and stores the department and program data object based on the preference values from the program document. Any computation or analy sis regarding the spatial assignment of program elements is done with the aid of the data stack of departments and programs. Step 4: Form Generation The form maker node constructs the orthogonal laydown area and zone outline for an arbitrary site outline ( see Figure 10 and 11) traversing the cell grid via the cell neighbor matrix, implementing two strategies to pack programs. Strategy 1: Function Follows Form Figure 9 Site Boundary as .sat file input to the Dynamo Graph Page 19 of 39 This strategy splits the orthogonal laydown area outline into sub-polylines until each polyline has exactly four sides, and subsequently merges a random number of such four -sided orthogonal polylines together to get the laydown area form. One advantage of this approach is that the user can set a percentage of total s ite area for the laydown area to occupy, resulting in building perimeters of specific site coverage. The merge operation employs the Polyline Boundary algorithm as explained above. Figure 10 Snippet depicting conversion of site boundary into cells for further processing Strategy 2: Form Follows Function Unlike Strategy 1, Strategy 2 develops the building outline while placing department and program elements. After each department /zone polyline placement, the algorithm evaluates adherence to site constraints and design requirements. The algorithm will only proceed to subsequent departments /zones after constraints and requirements are satisfied or until reaching an allowed quantity of tr ials. When area requirements are satisfied for Page 20 of 39 departments /zones , the algorithm discards any leftover waste space, merging the outer lines of the department polylines to arrive at the final building outline. For both of the strategies, custom functions rem ove single or multiple notches from the site outline using minimum edge distance, thus refining the laydown area form and increasing the number of design choices for the user. Figure 11 Snippet depicting simultaneous development of laydown area boundary and placement of departments/zones Step 5: Department Placement and K -d Space Data Tree for Department This step assigns departments to the site based on preference values from the user a nd simultaneously builds the space data tree. The iterative process is appropriately integrated with the form maker from the previous step, depending upon which form - making strategies are adopted and how well design goals and constraints are satisfied. Refer Fig 12 for understanding the visual interface incorporating these user assigned weights. Step 6: Program Placement Page 21 of 39 This step assigns program elements inside each department, as prioritized by user goals, and updates the grid object by assigning each ce ll a certain program type and updating each cell’s weight. Refer Fig 1 3 through Fig 18 for understanding the visual interface and some of the arrangements possible . Figure 12 Snippet depicting the slider arrangement developed to ensure control using user assigned weights and p