Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In general, layout planning problems can be classified as in-house location problems where the aim is to minimize traveling or material handling costs based on distances by deciding on the relative positions of any kind of organizational units inside a building. This class of operations research problems originates from industrial applications, for example, planning the location of different machines of an assembly line needed to manufacture a product or the arrangement of racks and shelves within a warehouse.

The special case of layout planning problems in health care has been first introduced by Elshafei in 1977 (Elshafei 1977). He modeled a hospital layout problem as a quadratic assignment problem (QAP) and developed heuristics to solve it. In the framework for hospital planning and control the hospital layout planning problem is classified as a resource capacity planning problem on a strategic level (Hans et al. 2012). Although it is a long-term decision, the spatial organization within hospitals also directly influences the quality and efficiency of health care and secondary services of the daily routine (Choudhary et al. 2010; Hignett and Lu 2010) as well as patient satisfaction (Chaudhury et al. 2005). In practice, hospital buildings are commonly planned by architects based on experience, design aspects and legal regulations. Instead of that, it is important to develop and follow a holistic approach in order to combine the architectural and legal aspects with logistics, i.e., patient, personnel and material flows inside the future hospital building. In this context, the established operations research methodologies, especially optimization and simulation techniques, can be applied in order to support finding an optimal or robust hospital layout . On the one hand, optimal can mean to minimize traveling costs for personnel or traveling distances and/or times for patients and/or material. Although these objectives might be conflicting, they not only result in more efficient workflows and, thus, in patient and personnel satisfaction but also in economic efficiency. On the other hand, robustness implies that a layout plan has a good performance for different scenarios with uncertain input data, for example, uncertain clinical pathways depending on the patients’ recovery .

A hospital layout planning problem where all functional departments, wards, surgery rooms and other necessary and supporting areas have to be assigned to locations inside the hospital building is referred to as a layout planning problem on the macro level. In contrast, when only planning the layout of a single functional department, ward, etc. in the building it is called a hospital layout planning problem on the micro level. In the next section an overview of the literature on hospital layout planning problems on both levels is given. Nevertheless, the focus of the applications detailed in Sect. 5.3 as well as the framework presented in Sect. 5.4 lies on the macro level. In Sect. 5.5 a summary is given and some practical challenges are discussed.

2 Literature Review

A survey on layout planning problems was conducted by Drira et al. (2007). Furthermore, Tompkins et al. (2010), Heragu (2008), and Francis et al. (1992) published textbooks presenting different modeling and solution techniques for layout planning problems in general. In most applications the layout is considered as a long-term decision (Drira et al. 2007). In such static layout problems all relevant parameters are assumed to remain constant during the entire planning horizon . Nevertheless, there may also come up issues that make it necessary to rearrange a given layout, for example, the development of new products with different production processes or new treatment procedures that change the clinical pathways of patients with a specific disease. Thus, dynamic layout problems were developed in order to consider varying input data during the planning horizon. Two approaches exist to reflect this variability (Drira et al. 2007; Moslemipour et al. 2012): developing a robust layout that is best in sum over all periods during the planning horizon (see, for example, Kouvelis 1992; Benjaafar and Sheikhzadeh 2000; Azadivar and Wang 2000; Aiello 2001; Kulturel-Konak et al. 2004; Enea et al. 2005; Braglia et al. 2005; Norman and Smith 2006; Pillai et al. 2011; Arnolds and Nickel 2013b), or developing a layout plan for multiple periods where layout adaptations are allowed for while incurring rearrangement costs (see, for example, Lacksonen 1994; Urban 1998; Yang and Peters 1998; Kochhar and Heragu 1999; Balakrishnan and Cheng 2000; Chang et al. 2002; Krishnan et al. 2006, 2008; Kulturel-Konak 2007a; Ulutas and Islier 2009; Bashiri and Dehghan 2010). Reviews on dynamic layout problems and solution approaches are given in Balakrishnan and Cheng (1998), and Kulturel-Konak et al. (2007).

Regarding hospital layout planning problems, an exhaustive search for relevant literature follows. The objective of this literature review is threefold: First, it is designed to give an overview on recent advances in layout planning problems in health care with a focus on hospitals both on the macro and micro level. Second, a taxonomy , i.e., a structured way of classifying the reviewed papers, is developed to support discovering linkages between various publications as well as comparing them. Third, the extent to which diverse issues on layout planning in health care have already been covered in the literature is identified. Thus, existing research gaps can be revealed.

The following search string was used in the search engine Scopus:

TITLE-ABS-KEY ((“layout” OR “facility planning” OR “facilities planning” OR “facility design” OR “facilities design”) AND (“hospital” OR “clinic”) AND (“heuristic*” OR “optimization” OR “mixed integer program*” OR “mathematical program*” OR “integer program*” OR “linear program*” OR “binary program*” OR “quadratic program*” OR “dynamic program*” OR “goal program*” OR “discrete event simulation” OR “discrete-event simulation” OR “discrete-event-simulation”)).

The asterisk (*) may be replaced by different character combinations. For example, searching for “mathematical program*” can result in, for example, “mathematical program” or “mathematical programming”.

Using the presented search string, 59 papers were retrieved. The abstracts of these papers were screened in order to identify irrelevant articles and sort them out. After that, 22 relevant papers remained. Based on these, both a forward and a backward search were conducted. As an indicator for relevant papers the titles, abstracts and keywords of the forward and backward search results were scanned for layout and health care relevant applications. Furthermore, the papers cited by the literature reviews of Jun et al. (1999), Günal and Pidd (2010), Forsberg et al. (2011) were examined such that an additional 33 papers were retrieved.

In order to categorize the total of 55 papers, the following taxonomy was developed where most of the papers can be categorized into at least one topic of each category:

  • Scope: This category differentiates between hospital layout planning problems on the macro and micro level. The micro level is further broken down to different organizational units such as operating theater, ward, radiology, emergency department or other patient service centers.

  • Modeling technique: This category refers to the modeling approach such as quadratic assignment problems (QAP) , mixed integer programs (MIP) or discrete-event simulation models (DES).

  • Solution technique: In this category it is differentiated, for example, between optimal solution approaches, heuristics or process analysis.

  • Objectives: This category distinguishes between general facility design aspects, patient or resource centered objectives, amongst others.

For each of the categories of the developed taxonomy a table is built which gives an overview on the retrieved research papers (see Tables 5.1–5.4).

Table 5.1 Scope of the reviewed papers
Full size table
Table 5.2 Modeling techniques of the reviewed papers
Full size table
Table 5.3 Solution techniques of the reviewed papers
Full size table
Table 5.4 Objectives of the reviewed papers
Full size table

Figure 5.1 shows the statistics with respect to the number of published papers per 5-year interval from 1965 to 2013. Obviously, the topic gets more and more attention within the scientific community. This could particularly be observed during the last 5 years where the number of published papers more than doubled.

Fig. 5.1
figure 1

Number of published papers per 5-year interval

Full size image

3 A Graph-Theoretical Layout Planning Approach Applied to a Major German Hospital

As already mentioned, hospital buildings still are mainly planned by architects. They are experts in the field of design, usually have experience from other hospital planning projects and know the relevant legal regulations with respect to hospital buildings. Furthermore, there exist first example projects where architects take into account the processes, i.e., patient, personnel and material flows, when planning a hospital. But, lack of knowledge can still be detected in some cases and, consequently, no application of decision supporting operations research methodologies such as optimization or simulation techniques. Nevertheless, in the last years the authors have had the experience that responsible hospital planners are becoming more and more interested and open minded towards such kind of decision supporting operations research methodologies. Last but not least, this could be a result of the increasing financial pressure on hospitals.

In what follows, a project is detailed where the authors applied a graph-theoretical heuristic to support developing a layout plan for a new building of a major German hospital.

3.1 The Cooperating Hospital

The project was initiated by the Institute of Operations Research of the Karlsruhe Institute of Technology (http://dol.ior.kit.edu) and a major German community hospital with more than 1500 beds. Over the years, the hospital has grown on an area of 155,758  m2 and currently comprises 23 buildings. The historical development of the different buildings results in long travel distances and times for both patients and personnel. This impedes process efficiency and, thus, treatment quality as well as economic efficiency. At the same time, the technical infrastructure of the existing buildings is not expandable such that, for example, the requirements for the installation of medical technology cannot be covered anymore. Summarizing, there is a need for a new building which is also manifested in the target planning program of the hospital for the upcoming years. According to the hospital’s plan, the new building shall comprise the following organizational units:

  • Wards of different intensities of care.

  • Interdisciplinary inpatient and outpatient operating theaters.

  • Walk-in clinics for different disciplines.

3.2 Goal and Methodology

For the hospital, the objective of the layout planning project was to reduce the long travel distances and times for patients and personnel which can be observed in the current setting. This can be achieved by an efficient planning of the location of the organizational units inside the new building according to the patients’ clinical pathways and logistic processes that will take place during daily routine.

Three main characteristics of the given layout planning problem have to be considered when deciding for an appropriate modeling and solution technique: Firstly, the high number of wards and functional departments to be located; secondly, the different sizes of the organizational units, and, thirdly, the necessity to plan a multi-floor building. These characteristics make the problem too complex to find an optimal solution by formulating and solving a mathematical model, as, for example, a quadratic assignment or a mixed integer program. Moreover, these models are rather appropriate if organizational units have to be (re-)located within a given structure of an existing building with defined dimensions (length and width of each level of the building). Contrarily, in this project there still were some degrees of freedom with respect to the architectural dimensions since a completely new building had to be developed where only the dimensions of the ground level were fixed beforehand. To solve this kind of layout problems, a graph theoretical approach was developed (see, for example, Francis et al. 1992). Particularly, an advantage of this procedure is that it is illustrative and visually presentable which makes it easier to convince the responsible hospital managers to apply the approach.

3.3 A Graph-Theoretical Approach for Layout Planning

The graph-theoretical approach for layout planning and its theoretical background is thoroughly described by Francis et al. (1992). In this section a short overview of the procedure and the underlying theory is given. For more detailed information the interested reader is referred to Francis et al. (1992). As a basis for the application an interaction or flow matrix is needed, where each entry represents the number of interactions between two organizational units, for example, during 1 year. This number can also be interpreted as the importance of locating two organizational units close to each other. The higher the interaction between two organizational units, the higher is the importance of a direct adjacency of the corresponding units. Organizational units can be, for example, machines in a manufacturing environment, offices in any service setting or wards and functional departments in a hospital . The idea of the approach is to construct a graph in the first step and then to derive a block layout from its dual graph in the second step. The objective is to maximize the sum of the interactions of organizational units that are adjacent in the resulting layout plan.

In the graph to be constructed each node represents one organizational unit. An edge between two nodes means that the represented units are adjacent in the resulting block layout . In order to derive a layout from the graph the latter has to be planar. A graph is called planar if it can be drawn on a plane without any crossover of edges (see Fig. 5.2). Furthermore, a planar graph is called a maximally planar graph if and only if the characteristic of planarity gets lost when adding a further edge (see Fig. 5.3).

By depicting a graph, the plane is subdivided in facets γ, i.e., a set of one or more inner facets and one outer facet. An inner facet is an area in the plane bounded by nodes and edges where, first, the bounding nodes and edges form an elementary circle (consisting only of different nodes and edges), second, a pairwise intersection of two facets is empty, and, third, no subset of a facet features the former two characteristics. In Fig. 5.2 the following areas are inner facets: \({{\gamma }_{1,2,3,4}},\quad {{\gamma }_{1,4,6,7}},\quad {{\gamma }_{2,3,5,8}},\quad {{\gamma }_{3,4,5,6}}\) and \({{\gamma }_{5,6,7,8}}\). An outer facet is the area in the plane which is not covered by inner facets. In Fig. 5.2 the outer facet is \({{\gamma }_{1,2,7,8}}\).

Fig. 5.2
figure 2

Planar graph with five inner and one outer facet

Full size image

A facet which is bounded by the three nodes i, j and k and the three edges [i, j], [j, k], and [k, i] is called a triangle \({{\delta }_{i,j,k}}\) (see Fig. 5.3). If all facets of the graph are triangles it is called a deltahedron. A planar graph is maximal if and only if it is a deltahedron.

Fig. 5.3
figure 3

Maximally planar graph (deltahedron) consisting of eight triangles (seven inner and one outer facet)

Full size image

A graph is connected if there is a walk between every pair of vertices. A walk in a graph is an alternating sequence of vertices and edges \(W={{v}_{0}},{{e}_{1}},{{v}_{1}},...,{{e}_{n}},{{v}_{n}}\) such that for j = 1, …, n the vertices \({{v}_{j-1}}\) and \({{v}_{j}}\) are the endpoints of edge \({{e}_{j}}\). A simple graph is a graph that has no self-loops or multi-edges. A simple graph is a complete graph if every pair of vertices is joined by an edge.

If a planar graph representing the adjacency requirements of several organizational units can be constructed, then it is possible to derive a compatible block layout using its dual graph. Given a connected, undirected and planar graph, then the dual graph is built as follows:

  • The dual graph includes exactly one node for each facet of the primal graph.

  • The dual graph includes exactly one edge for each edge in the primal graph that separates two facets. In the dual graph, this edge connects the two nodes that represent these two facets in the primal graph.

To solve the layout problem by applying the graph-theoretical approach, first, a planar graph has to be determined in which the sum of the edge weights, which represent the corresponding entries of the interaction matrix, is maximized. Thus, the search for such a graph can be limited to maximally planar graphs and, consequently, to deltahedrons.

If a graph is a deltahedron with n nodes and m edges, then the following relation holds: \(m=3n-6\) (see Francis et al. 1992). Using this relation, an upper bound for the sum of the edge weights of a layout problem can be derived by simply summing up the \(3n-6\) highest values of the interaction matrix.

Given an interaction matrix \(\mathbf{U}=({{u}_{ij}})\) and a simple, complete and undirected graph \(G=[V,E,\mathbf{U}]\) with nodes \(v\in V\) and edges \(e\in E\) which are weighted with the values in U. The problem to identify a maximally planar subgraph \({G}'=\left[ V,{E}',U \right]\) of G with \({E}'\subset E\), which has the highest sum of edge weights, can be formulated as follows:

Decision variables:

$${{x}_{ij}}=\left\{ \begin{array}{*{35}{l}} 1 & \text{if edge }\left[ i,j \right]\in {E}' \\ 0 & \text{else} \\\end{array} \right.\forall i,j\text{ with }i<j$$

Model:

$$\begin{aligned} \text{Max } & \sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n}{{{u}_{ij}}{{x}_{ij}}}}& \\ \text{s}\text{.t}\text{.}\quad & {G}'=[V,{E}']\ \text{is}\ \text{a}\ \text{maximal}\ \text{planar}\ \text{graph} &\\ & {{x}_{ij}}\in \text{ }\{0,\text{ }1]\text{ }\forall i,j\,\text{with}\,i<j. &\\ \end{aligned}$$

Since the problem is NP-hard , large instances cannot be solved to optimality. Thus, the following heuristic procedure was developed to construct a maximally planar graph (see Leung 1992).

  • Prerequisite: Calculate the row sums of the interaction matrix and sort them according to monotonic decreasing values.

  • Initialization: Build an initial deltahedron using the four nodes with the highest row sums.

  • Iterations: Integrate the remaining nodes into the deltahedron in the order of decreasing row sums. Always include them into the triangle where the objective function value is increased the most. Here, including means connecting the new node with the three existing nodes of the triangle. Thus, the new node is connected with the nodes of that triangle with which it has the most interactions.

Regarding the quality of this heuristic, Leung (1992) showed that the sum of the edge weights of the obtained graphs using this heuristic lie between 92.4 and 99.8 % of the upper bound on the optimal value generated by summing up the weight of the (\(3n-6\)) edges of maximum weight.

Example 5.1

Given the following interaction matrix \(\mathbf{U}=({{u}_{ij}})\) of a complete graph with six nodes \(v\in V\) and row sums u i :

$$\mathbf{U}=\left( \begin{matrix} - & 4 & 7 & 1 & 7 & 10 \\ 4 & - & 2 & 5 & 2 & 4 \\ 7 & 2 & - & 8 & 8 & 1 \\ 1 & 5 & 8 & - & 1 & 3 \\ 7 & 2 & 8 & 1 & - & 5 \\ 10 & 4 & 1 & 3 & 5 & - \\\end{matrix} \right),\,\ {{u}_{i}}=\left( \begin{matrix} 29 \\ 17 \\ 26 \\ 18 \\ 23 \\ 23 \\\end{matrix} \right)$$

Initialization

  • Nodes with highest row sums: \(V'=\{1,3,5,6\}\)

  • Corresponding edges: \(E'=\{[1,3],[1,5],[1,6],[3,5],[3,6],[5,6]\}\)

  • Corresponding triangles: \(\Delta =\{{{\delta }_{135}},{{\delta }_{136}},{{\delta }_{156}},{{\delta }_{356}}\}\)

  • Objective function value: \(Z=7+7+10+8+1+5=38\)

  • Resulting graph (Note: In order to construct the initial deltahedron, one node has to be chosen to be put in the center, here node 3 is chosen.):

figure a

Iteration \(it=1\)

  • Choose \(v=4\), because \({{u}_{4}}=\max \{{{u}_{2}}=17,{{u}_{4}}=18\}\)

Table 5
Full size table

Note: The table shows the values representing the increase of the objective function value when integrating node 4 in the existing triangles. The highest increase is marked with an asterisk, ties are broken arbitrarily.

  • Resulting graph:

figure b

Iteration \(it=2\)

  • Choose the last remaining node \(v=2\)

Table 6
Full size table

  • Resulting graph:

figure c

If all nodes are inserted the objective function value can be calculated by summing up the edge weights (see Fig. 5.4): \(Z=63\)

Fig. 5.4
figure 4

Constructed graph with edge weights

Full size image

Before constructing the dual graph and deriving a block layout, an additional node has to be integrated into the maximally planar graph. This node represents the environment of the new building and, thus, the origin of all flows before entering the building. Constructing the block layout from the dual graph without this additional node would result in one organizational unit located outside the building. In Fig. 5.5, node (7) represents the environment. This new node has to be connected to all the nodes that formerly established the outer facet of the maximally planar graph.

Fig. 5.5
figure 5

Additional node (7) for the environment

Full size image

When constructing the dual graph it has to be ensured that the node representing the environment lies outside the dual graph (see Fig. 5.6).

Fig. 5.6
figure 6

Construction of the dual graph (red)

Full size image

One possible block layout to be derived from the dual graph is shown in Fig. 5.7. Note that no area restrictions are given for the organizational units.

Fig. 5.7
figure 7

Block layout derived from the dual graph

Full size image

3.4 Application of the Graph-Theoretical Heuristic to Construct a Hospital Layout

The hospital layout planning problem instance addressed in this chapter consists of 25 organizational units to be located (see Table 5.5). Each organizational unit comprises a set of rooms. In accordance with the hospital management, the rooms were grouped to organizational units since for the total of more than 700 rooms it would not have been possible to reliably derive an interaction matrix from the available data sources. By applying the graph-theoretical heuristic a two-dimensional block layout in the plane, i.e., representing one level, can be constructed. Thus, in the last step the organizational units have to be assigned manually to the different floors of the new building .

3.4.1 Data

In order to derive a layout by applying the graph-theoretical heuristic, the data described in the following sections has to be obtained.

3.4.1.1 Area of each Organizational Unit

For planning purposes the hospital developed a so-called space allocation plan for the new building. This plan details the kind and area of each organizational unit. Table 5.5 gives an overview of the space allocation plan.

Table 5.5 Space allocation plan
Full size table
3.4.1.2 Further Restrictions Regarding the Layout

Before applying the described approach, the hospital management already had defined the following basics for the new building: The building shall have six levels where with each level the floor area decreases. The ground level shall have a dimension of 214 m of length and 54 m of width, including aisles, waiting areas, technical equipment areas, elevators, stairs etc. For the remaining levels of the building the area had not been fixed yet.

3.4.1.3 Interaction Matrices

The data that was delivered from the hospital to infer the interaction matrix for the organizational units was the hospital’s specific case mix:

  • Number of cases per discipline, for example, eye clinic, dermatology or women’s clinic.

  • Number of surgery cases per discipline, for example, trauma surgery or children’s surgery.

The assumptions which had to be made in order to derive the quantitative interactions between all pairs of organizational units from the case mix data are specified in the following section. Since no detailed information on quantitative flows was available directly, it had to be derived by making these assumptions. Furthermore, patient, personnel and material flows were not weighted differently such that the entries in the interaction matrix equal the sums of the different kinds of flows.

3.4.2 Assumptions

As it is usual in practical applications, not all data which is needed to apply the approach was available directly. This section deals with the assumptions that had to be made in order to derive quantitative information regarding the general, surgical and emergency patient flows as well as the sterile goods and medical device supply and the flows to and from the standby rooms for physicians. Based on these assumptions and (derived) data the interaction matrix was then set up. Since this is sensitive data for the hospital management , the absolute values, i.e., the entries of the interactions matrix, cannot be shown here.

The section on general patient flow refers to assumptions relevant for all in- and outpatients. Also, the surgical and emergency patient flows are not necessarily excluding each other, that means, an emergency patient may, for example, have to undergo a surgery. In most of the cases only patient flows were considered as these could be derived more reliably from the available data than the usually highly variable personnel and material flows. Nevertheless, for some organizational units, where patients do not have access to, for example, the central sterilization unit or standby rooms for physicians, relevant personnel and material flows were inferred from expert interviews.

Furthermore, there is assumed a \(15\%\) increase on the number of patients per year based on the current numbers. This rise was stipulated by the hospital management.

3.4.2.1 General Patient Flow

Regarding the general patient flow, the first contact point inside the hospital for all outpatients is the organizational unit called “medical services”. In contrast, all inpatients are directly guided to their assigned ward. Outpatients leave the hospital from the corresponding outpatient clinics and inpatients from the discharging ward.

From the case mix data an average length of stay of 6 days from admission to discharge was calculated and taken as a basis for all patients and intensities of care. During their treatment process, patients recover and are transferred to less intense care units. It is assumed that due to reconvalescence \(50\%\) of the intensive care patients are directly transferred to a general care unit, whereas the remaining \(50\%\) have to be transferred to an intermediate care unit first before being moved to a general care unit later. The transfers take place in equal shares to each of the four general care and two intermediate care units, respectively. Furthermore, patients are only discharged from general care units.

3.4.2.2 Surgical Patient Flow

Regarding the surgical patient flow, it is divided between inpatient (59 %) and outpatient (41 %) surgeries, with a current total of about 21,600 surgeries per year. It is assumed that each outpatient is operated once. Contrarily, inpatients are at least operated once during their hospital stay, and 10 % have to undergo a second surgery. Patients may come from each of the care units or from the emergency department. After surgery, the patients are transferred back to the care unit where they came from or, in case of the emergency patients, are assigned to one of the different care units in equal shares.

Before surgery, each outpatient has to sign a consent form and is given a surgical clearance in the clinic for anesthesiology. Since the clearance has to be completed at least 1 day before surgery the patients leave the hospital afterwards and return on the day of their surgery.

3.4.2.3 Emergency Patient Flow

About 40 % of all arriving patients are emergency patients. Less than 1 % of those emergency patients have to be transferred to one of the intensive care units immediately. From the remaining emergency patients 20 % are assigned to one of the outpatient clinics and 80 % have to be operated immediately.

3.4.2.4 Sterile Goods Supply

A sterile good unit is a defined unit of volume used for sterilization of materials in an autoclave. Sterile good units are needed for each surgery. For the transportation of sterile goods between the operating theaters and the unit for sterile goods supply the personnel uses trolleys with a capacity of 12 sterile good units. From the case mix data it is known that 59 % of the trolleys have to be transported to/from the inpatient operating theater and 41 % to/from the outpatient operating theater.

3.4.2.5 Medical Device Supply

The unit for medical device supply prepares all devices which are needed in the operating theaters. These are, for example, respiration machines or medical appliances needed for treatment or examination during a surgery. Again, 59 % are transported to/from the inpatient operating theater and 41 % to/from the outpatient operating theater.

Furthermore, in the intensive care units artificial respiration devices are used that have to be cleaned and sterilized for new patients. These devices have also to be transported between the intensive care units and the unit for medical device supply. It is assumed, that each intensive care unit needs the same amount of respiration devices.

3.4.2.6 Standby Rooms for Physicians

According to the medical personnel’s information, it can be assumed that each night each of the 13 physicians on standby is called twice on average. The physician then either has to go to the emergency department or to one of the care units. After the patient’s treatment the physician usually returns to the standby room.

3.4.3 Results

The solution of the implemented graph-theoretical heuristic procedure shows how to construct the resulting maximally planar graph. This primal graph is shown in Fig. 5.8 with a color code that highlights the different groups of organizational units. It can be observed that the inpatient surgical unit (11) is connected to the other organizational units with the highest number of edges or, mathematically spoken, it is the node with the highest degree.

The environment of the building is represented by node (26). The heuristic has to be slightly adapted in order to guarantee that this node is part of the outer facet in the resulting graph. Since all patients enter the hospital building from the environment this node is one of those chosen in the initialization step of the heuristic. Regarding the further steps, it then has to be ensured that new nodes are only inserted into one of the existing inner facets.

Fig. 5.8
figure 8

Primal graph

Full size image

Figure 5.9 shows how to construct the dual graph that is needed to derive the single-floor block layout. Within each facet of the primal graph a new node is located which is colored red. The red nodes are connected such that each new (red) edge cuts one edge of the primal graph. Node (26) which represents the environment is not included in any of the inner facets because, obviously, it has to be outside the building.

Fig. 5.9
figure 9

Construction of the dual graph

Full size image

After removing the primal graph from Fig. 5.9 a cluster of outpatient clinics can be recognized as well as two care clusters, each consisting of one intensive care unit, two intermediate care units and two general care units (see Fig. 5.10). The inpatient surgical unit (11) has a quite central position and the medical service unit (02) which is the first contact point for all outpatients is adjacent to the environment where all the patients come from.

Fig. 5.10
figure 10

Dual graph

Full size image

In the next step, the edges of the dual graph are rectified. The result is a single-floor block layout as depicted in Fig. 5.11. Again, both the outpatient cluster as well as the two care clusters are clearly recognizable. Up to now, the real areas of the organizational units have not been taken into account yet. The sterile goods supply (24) and the medical device supply (25) units are close to the inpatient (11) and outpatient (12) surgical units. The emergency department (1) is located at a central position next to the medical service for admission (2), the cluster of outpatient clinics (3)-(10) and the outpatient surgery unit (12). The standby rooms for physicians (13) are placed between the outpatient clinics for anesthesiology (3) and general and abdominal surgery (5) as well as the medical service (2).

Fig. 5.11
figure 11

Single-floor block layout without area restrictions

Full size image

Considering the given areas for each organizational unit, the layout plan shown in Fig. 5.12 can be constructed. Still, this is a single-floor block layout , but now it considers the dimensions of each organizational unit. In the center , the inpatient surgical unit (11) is located. To its left and right the two care clusters are placed. The sterile goods (24) and medical device (25) supply units are adjacent to both the inpatient (11) and outpatient (12) surgical units. The emergency department (1) and the outpatient clinics (3)–(10) are located in the south-western part of the floor plan. The standby rooms are placed between the outpatient clinics for anesthesiology (3), abdominal surgery (5), vascular surgery (6), urology (9), the cancer center (10) and one of the intensive care units (14). As all outpatients first have to contact the medical service unit (2), from there they can easily reach the outpatient clinics via the aisle that has been incorporated additionally.

It can be observed that due to the given area restrictions of each organizational unit, some of the required adjacencies cannot be preserved anymore. But in accordance with the hospital management , the identified outpatient and care clusters are kept. Furthermore, the hospital management had already decided for a building with six levels such that the single-floor block layout had to be adapted accordingly. During this manual adaptation step, the desired width-length dimensions of the ground floor as well as the requirement that with an increasing level the floor areas shall decrease (see Sect. 5.3.4.1) have to be kept.

Fig. 5.12
figure 12

Single-floor block layout with area restrictions

Full size image

Figure 5.13 depicts the manually generated multi-floor layout plan where the outpatient and care clusters can still be identified. Level-01 contains the inpatient surgery unit (11), the sterile goods (24) and medical device (25) supply units as well as the emergency department (1).

All outpatient clinics (3)–(10) as well as the outpatient surgical unit (12), the doctor’s standby rooms (13) and the first contact point for all elective patients, i.e., the medical services unit (2) are located on level 00.

Through the assignment of the emergency department (1) and the medical services unit (2) to different levels, the emergency and elective patient arrivals can be separated from each other so that overcrowding is prevented. Although the two surgery units for inpatients (11) and outpatients (12) are located on different levels, they could easily be connected via “sterile stairs.” These are connecting stairs which only the personnel may use in order to move from one unit to the other without the necessity to, for example, change clothes due to hygienic requirements. Nevertheless, the assignment of personnel to either the inpatient or outpatient surgery unit during one shift is usually fixed. Consequently, the usage of the “sterile stairs” would in most cases only be necessary at the beginning or end of a shift, during the rest period or due to personnel shortage.

Levels 01 and 02 each contain one care cluster consisting of one general, one intermediate, and one intensive care unit. Also, levels 03 and 04 each comprise one general and one intensive care unit. The arrangement in care clusters is advantageous regarding, on the one hand, the possibility of a transfer from one care level to another within the same specialty located on the same floor due to an improvement or deterioration of the patient’s medical condition. On the other hand, transfers between the same care levels of different specialties which are located on different floors are very unusual such that vertical transports can be avoided. But, by locating the intensive care units on levels 03 and 04 directly above the intermediate care units on levels 01 and 02, the transfer of patients via an elevator between the intensive and the intermediate care unit is as easy and convenient as possible since it includes as less as possible horizontal movements. Furthermore, each care group can be directly connected to the inpatient surgical unit via elevators what makes the transport to and from the operating theater very comfortable.

Fig. 5.13
figure 13

Multi-floor layout plan

Full size image

3.4.4 Discussion

In this section the results of applying the graph-theoretical heuristic to the real-world hospital layout problem will be discussed thoroughly with respect to the assumptions, the multi-floor aspect, possible layout distortions, and the development of the layout plan. Although all the potential drawbacks of the presented approach have been addressed during the application process with common sense solutions there is still some potential for future research on a more methodological level.

3.4.4.1 Assumptions

As already detailed in Sect. 5.3.4.2, some assumptions had to be made to derive the necessary data for the graph-theoretical heuristic. As far as possible, the available data was used to set up assumptions, especially regarding realistic patient, personnel and material flows through the hospital. Here, the focus was laid on the patient flow because the available target planning program of the hospital, which served as data basis to plan the layout , contained no information on the personnel and material flows but only on the patients’ case mix related data such as the number of cases or surgery numbers per discipline. Furthermore, on the one hand, the personnel usually belongs to and, consequently, moves within an organizational unit and, on the other hand, the material flow is highly variable and, therefore, hardly predictable. Obviously, this assumption regarding the input data influences the result of the graph-theoretical heuristic. Nevertheless, according to the hospital management the constructed layout shows a reasonable arrangement of organizational units which justifies the data-based assumptions. The results have not been compared to another hospital due to the difficulty of finding a similar hospital with respect to patient flows which are the essential and critical input data for the proposed approach.

Furthermore, only data relevant for interactions between organizational units within the new building but not to and from other buildings on the hospital’s campus were taken into account. Nevertheless, some organizational units which will not be moved into the new building as, for example, the radiology or endoscopy departments will have interactions with organizational units which will be located in the new building. These interactions are not taken into account since the patient and personnel flows within the building are assumed to be more important than the flows between buildings. The only effect which the flows between buildings could have on the solution would be a shift of organizational units inside the new building nearer to the entrance if they have high interaction rates with organizational units in the other buildings. But the distance within the new building has a much smaller share on the total distance than the distance to the corresponding organizational unit in another building anywhere on the campus. Obviously, the latter part of the distance cannot be influenced by solving the layout problem because the locations of all organizational units in any of the other buildings are fixed. This means that the total distances between organizational units in the existing and new buildings would only be influenced marginally by different layouts. Furthermore, the hospital management’s focus was laid on the operational processes inside the new building and not between buildings.

3.4.4.2 Multi-Floor Layout

The layout generated by the graph-theoretical heuristic only comprises one level but due to the limited space available, the new building has to be a multi-floor building. Consequently, a manual adaptation is necessary which was justified by identifying different clusters in the single-floor layout . Nevertheless, some of the adjacencies had to be neglected when deriving the multi-floor layout plan from the single-floor layout plan. Obviously, in this step, other layout plans could also be identified but since expert opinions were included when deriving the clusters and the final layout the solution could be proven to be adequate. Nevertheless, future research aims at measuring the potential error of the graph-theoretical approach and developing a procedure to avoid high errors.

3.4.4.3 Layout Distortion

The graph-theoretical heuristic does not consider any area restrictions of the organizational units. In the presented application the areas of the organizational units differ with a factor of up to 1:10. Consequently, it has to be ensured manually that small organizational units are not stretched too much in order to be adjacent to other organizational units. This problem can be solved quite easily by fixing the shape of small departments and then adjusting the shape and position of the larger departments accordingly. For example, neighboring organizational units do not have to be adjacent along the whole width or length but only along a part of it.

3.4.4.4 Development of the Layout Plan

When developing the layout plan using the graph-theoretical heuristic, each organizational unit is regarded as a whole. In our application this means, for example, that all standby rooms for medical doctors are handled as a group. The possibility to include single standby rooms in other organizational units is not considered by the approach. On the one hand, this shortcoming can be overcome by an appropriate grouping of rooms to organizational units. On the other hand, care needs to be taken to ensure that for each organizational unit the entries in the interaction matrix are needed and that the problem becomes more complex with more organizational units to be located.

4 An Iterative Simulation-Optimization Approach for Hospital Layout Planning

The presented graph-theoretical method is only one of many possible approaches for layout planning . As most of the procedures that can be found in the literature, it assumes deterministic data regarding patient, personnel and material flows. In this section an innovative framework for hospital layout planning is presented that takes into account the impact of strategic layout decisions on the operational performance with uncertain process flows (Arnolds and Nickel 2013b). Taking into account this stochastic influence distinguishes the simulation-optimization approach from the formerly presented graph-theoretical approach for layout planning where the data is assumed to be deterministic.

In a preparatory step, the term operational performance has to be defined depending on the application. For example, if the aim is to improve patient and personnel flows through the hospital building, the total travel times for patients and personnel as well as the patients’ waiting times for elevators or personnel can be evaluated.

In order to incorporate process uncertainties in the layout planning phase, optimization is combined with discrete event simulation (DES). While solving a mathematical model results in an optimal layout under deterministic data, simulation scenarios help to find a robust layout which will show a good performance even when patient, personnel and material flows are uncertain. At a later point in time, the DES model can further be used to test, for example, new schedules for working hours or the influence of building modifications on workflows.

The idea of an iterative simulation-optimization approach for hospital layout planning is adapted from Acar et al. (2009) who presented a generic approach to combine mixed integer programming and simulation in order to solve combinatorial problems under uncertainty. Regarding the application of this approach for a hospital layout planning problem, an optimization model for layout planning has to be set up in a first step. In general, any kind of problem formulation can be used. For example, for small instances one can apply the well-known quadratic assignment problem (QAP) which has been introduced by Koopmans and Beckmann (1957). By solving the QAP, each organizational unit is assigned to a predefined location inside the building. That means, the layout is not constructed from scratch but the structure of the building with defined dimensions (length and width of each level of the building) and locations is given. The following flow chart depicts the iterative simulation-optimization approach adapted to the interaction of a QAP and a DES model.

Fig. 5.14
figure 14

Iterative simulation-optimization approach

Full size image

As Fig. 5.14 shows, the models interact multiple times, i.e., iteratively until the stopping criterion is met. The first iteration consists of four basic steps: First, the QAP is solved assuming deterministic flow data (i.e., generation of a candidate layout n). Second, the DES model is applied to test the generated QAP layout with stochastic flow data. In this step, it is important to ensure that the simulated objective value is worse than the optimal objective value. For example, this can be guaranteed by assuming an increasing amount of arriving patients. Third, the difference between the QAP and DES objective values (i.e., impact of uncertainty N n of candidate layout n) is calculated. Fourth, the relevant parameters of the QAP model are updated:

  • N n : The impact of uncertainty of candidate layout \(n\) as calculated in step three.

  • Q min : Minimum simulation result obtained so far from any simulation run.

  • T njr : Indicator that shows if the binary variable y jr in candidate layout n is 1, i.e., if organizational unit j is assigned to location r in candidate layout n of the QAP result.

  • i: Current iteration − 1.

In the next iteration, solving the updated QAP either results in a new candidate layout and the described steps are repeated or it results in a solution that has already been found in an earlier iteration such that the procedure stops. In the latter case, the last found QAP solution is saved as the best robust layout. In order to realize the feedback between the optimization and the simulation models, a generic DES model was developed, which can be easily adapted to different hospital layout plans according to the QAP solution.

The QAP model formulation according to Koopmans and Beckmann (1957) is as follows:

Parameters:

f jk ::

Flow between organizational units j and k

d rℓ::

Distance between locations r and ℓ·

m::

Number of organization units and locations.

The decision variables are:

$${{y}_{jr}}=\left\{ \begin{array}{*{35}{l}} 1 & \text{if organizational unit }j\text{ is assigned to location }r \\ 0 & \text{else} \\\end{array} \right.$$

The model can then be written as:

$$\begin{aligned} \text{Min} & \sum\limits_{j=1}^{m}{\sum\limits_{k=1}^{m}{\sum\limits_{l=1}^{m}{\sum\limits_{r=1}^{m}{{{f}_{jk}}{{d}_{rl}}{{y}_{jr}}}}}} \\\end{aligned}{{y}_{kl}}$$
(5.1)
$$\text{s}\text{.t}\text{.}\ \ \sum\limits_{r=1}^{m}{{{y}_{jr}}=1\ \forall \ j\in \{1,...,m\}}$$
(5.2)
$$\sum\limits_{j=1}^{m}{{{y}_{jr}}=1\ \forall \ r\in \{1,\ldots ,m\}}$$
(5.3)
$${{y}_{jr}}\in \left\{ 0,1 \right\}\ \forall \ j,\ r\in \left\{ 1,\ldots ,m \right\}$$
(5.4)

The objective function (1) minimizes the total travel distance between the organizational units. Constraints (2) ensure that each organizational unit is assigned to exactly one room whereas constraints (3) guarantee that each room is only occupied by one organizational unit. Constraints (4) define the domain of the decision variables.

In order to facilitate a feedback loop between the optimization and DES solutions according to Acar et al. (2009), additional parameters, decision variables and constraints have to be introduced in the QAP. Furthermore, the objective function has to be adapted.

The additional parameters are:

i::

Current iteration − 1

M::

large number

N n ::

Impact of uncertainty of candidate solution n

Q min ::

Minimum simulation result obtained so far from any simulation run

$${{T}_{njr}}=\left\{ \begin{array}{*{35}{l}} 1 & \text{if binary variable }{{y}_{jr}}\; \text{ in candidate solution }n\text{ is 1} \\ 0 & \text{else} \\\end{array} \right.$$

Additional decision variables are:

$$\begin{matrix} {{Z}_{n}}= & \left\{ \begin{array}{*{35}{l}} 1 & \text{if candidate layout }n\text{ has already been suggested in a previous iteration} \\ 0 & \text{else} \\\end{array} \right. \\\end{matrix}$$

The resulting model (a modified QAP) is then:

$$\text{Min}\ \,Z=\sum\limits_{j=1}^{m}{\sum\limits_{k=1}^{m}{\sum\limits_{l=1}^{m}{\sum\limits_{r=1}^{m}{{{f}_{jk}}{{d}_{rl}}{{y}_{jr}}{{y}_{kl}}}}}}+\sum\limits_{n=1}^{i}{{{N}_{n}}{{Z}_{n}}}$$
(5.5)
$$\text{s}\text{.t}\text{.}\ \ \sum\limits_{r=1}^{m}{{{y}_{jr}}=1\ \forall \ j\in \{1,\ldots ,\ m\}}$$
(5.6)
$$\sum\limits_{j=1}^{m}{{{y}_{jr}}=1\ \forall \ r\ \in \{1,\ldots ,\ m\}}$$
(5.7)
$${{y}_{jr}}\in \{0,1\}\ \forall \ j,\ r\in \{1,\ldots ,\ m\}$$
(5.8)
$$\sum\limits_{j=1}^{m}{\sum\limits_{r=1}^{m}{(2{{T}_{njr}}\ {{y}_{jr}}-{{y}_{jr}}-{{T}_{njr}})\le {{Z}_{n}}-1\ }}\forall \ n\in \{1,\ldots ,\ i\}$$
(5.9)
$$\sum\limits_{j=1}^{m}{\sum\limits_{r=1}^{m}{(2{{T}_{njr}}\ {{y}_{jr}}-{{y}_{jr}}-{{T}_{njr}})\ge M\ ({{Z}_{n}}-1)\ \forall \ n\in \{1,\ldots ,\ i\}}}$$
(5.10)
$$Z\le {{Q}_{\min }}$$
(5.11)

A penalty factor is added in the objective function (5) which reflects the impact of uncertainty N n of a candidate layout n that has already been found and simulated in an earlier iteration (see Fig. 5.14). Constraints (6)–(8) are the same as constraints (2)–(4) in the original QAP. Constraints (9) and (10) ensure that the impact of uncertainty of a previously simulated solution is only incorporated if this solution is currently considered. Constraints (11) define an upper bound for the objective function value equal to the smallest found objective value of any previously simulated solution.

The advantages of the presented simulation-optimization approach are manifold. Firstly, the impact of the strategic layout decision on the operational performance with uncertain process flows and increasing demand in the future is considered. Secondly, the performance and robustness of hospital layouts can be compared and improved for various scenarios. Scenarios can be defined by changing both input data (extrinsic configuration) and factors, which are revealed during the simulation run (stochastic influences). The former comprises items like the control, capacity and number of elevators, the existence of dedicated personnel elevators or personnel shifts and schedules for breaks. The latter incorporates issues like the uncertainty of clinical pathways depending on the state of health of patients, the used means and speed of transportation, patient arrival rates or service durations. Thirdly, by applying a DES model factors like the aforementioned which are hard to integrate in mathematical models or heuristics for hospital layout planning can be studied. Fourthly, the performance of the hospital layout can be evaluated separately for different patient types. Thus, a fairness factor can be established. Patient types can be defined, for example, by severity of illness or level of mobility.

5 Conclusion

Regarding the application of operations research methodologies to health care problems in general and to hospital layout problems in particular, it still remains a challenge to convince the people in charge as, for example, hospital managers, medical doctors or nurses of the positive and supporting effects of these methods. Until recently, hospitals were built the way they had been built through the centuries, i.e., hospital designers and planners used to rely mostly on experience and existing campus outlays for inspiration (Arnolds and Nickel 2013a). Today, hospital design is shifting towards patient logistics, opening up totally new perspectives. Hospital budgets, quality of care and patient satisfaction will profit from this transformation.

Mostly, long-term perspectives regarding resource and capacity planning are in the focus of hospital design. However, the emerging building will also significantly influence short-term aspects, i.e., operational workflows. Furthermore, most architectural designers assume that the information they take into account is fixed and deterministic. However, uncertainty can impact data, for example, on future patient figures for certain diseases, as can processes, i.e., the flow of patients, personnel and materials, depending on outcomes and reconvalescence. This uncertainty should be reflected during the design process. Processes should determine how buildings are designed, and not vice versa. Consequently, planning should integrate methods for logistical analysis. Prior to entering the design phase for a new construction project, an analysis of processes needs to be carried out. In particular, clinical pathways for the patients to be cared for in the building should be investigated, providing information on the paths of movement of patients, personnel and material.

The distances travelled can be reduced by an efficient location of organizational units according to the processes which take place in the building, including the flows of patients, personnel and material. Reducing distances means savings in time and, consequently, in resources. Increased efficiency leaves more time to spend on care, which in turn leads to improved patient and personnel satisfaction. To support these improvements in efficiency it is planned to build a layout planning data base for benchmarking.

The challenge for researchers is now to work together with architects and hospital managers and to convince them that operations research methodologies can be used as additional decision support tools besides expert domain knowledge for hospital layout planning problems. Here, particularly discrete event simulation models can act as a door opener for the practitioners’ acceptance of operations research methodologies not only in hospital layout planning but also in other health care topics.