A Hybrid Optimization Approach for the School Layout Problem

Abstract

Å designe planløsningen til en skole er en kompleks oppgave, og krever at arkitektfirmaer bruker hundrevis av timer på å utvikle et planløsningsforslag. Kompleksiteten kommer av antall rom, ulike romstørrelser, spesifikke krav til hvert enkelt rom, samt kvalitative og kvantitative mål. Dette motiverer bruken av optimeringsteknikker til å kartlegge løsningsområdet ved å foreslå ulike planløsninger med ønskede egenskaper. Denne masteroppgaven utforsker problemet med å generere planløsninger til skolebygg som medfører lave byggekostnader, referert til som Planløsningsproblem for Skoler (SLP). Målet er å utvikle en algoritme som er i stand til å generere en planløsning der byggekostnadene, med tanke på bygningsareal og utvendige hjørner, minimeres.

Et omfattende litteratursøk viser at det ikke eksisterer tidligere forskning på bruk av optimeringsteknikker for å utforme planløsninger i skolebygg. Dermed gjennomføres et studie på sammenlignbare problemer, hovedsakelig pakkeproblemer og andre plan-løsningsproblemer. Basert på funnene implementeres en trestegsalgoritme. Algoritmen tar for seg det multi-objektive optimeringsproblemet å fordele rom og ganger på en tomt, som dermed danner en planløsning for en etasje i to dimensjoner. Algoritmen består av en memetisk algoritme (MA), en matematisk modell og et lokalsøk (LS). MA består av en genetisk algoritme (GA) og et LS, som sammen genererer et første utkast til en planløsning. Steg to er en matematisk modell som er formulert som et singel-objektiv linært heltallsprogram. Modellen tar for seg delområder i planløsningen, og forsøker å minimere antall hjørner lokalt i disse områdene. Til slutt benyttes et lokalsøk i steg tre med sikte på å minimere antall utvendige hjørner og det totale bygningsarealet.

SLP tar et romprogram (RSD) som input - et dokument som lister alle rom og romkrav for en bestemt skole. Kravene omhandler størrelse, form, nærhet og naturlig belysning. Korridorer er ikke spesifisert i et RSD. I stedet implementeres en sofistikert algoritme for dynamisk generering av korridorer. Trestegsalgoritmen genererer planløsninger som tilfredsstiller kravene i et RSD, samt andre krav som korridorforbindelser mellom rom.

Omfattende tester av algoritmen er gjennomført for å vurdere ulike implementeringsalternativer, finne passende parameterinnstillinger og forbedre kompatibiliteten mellom de tre stegene. Ytelsen til algoritmen testes på seks RSDer av ulik kompleksitet og med forskjellige egenskaper. RSDene er delmengder av romprogrammet til Levanger ungdomsskole som ble bygget i $2015$. Resultatene er tilfredsstillende, da algoritmen er i stand til å generere planløsninger som medfører lave byggekostnader, samtidig som de oppfyller kravene i RSDene.

Denne masteroppgaven illustrerer hvordan optimeringsteknikker kan brukes i utviklingen av planløsninger for skoler. Resultatene viser at en flertrinns algoritme som utnytter styrkene til flere løsningsmetoder har et sterkt potensiale til å fungere som beslutningsstøtte for arkitekter når de utformer planløsningen til en skole. Algoritmen genererer et bredt spekter av forskjellige, ønskelige planløsninger. Disse kan brukes både som inspirasjon og utgangspunkt for arkitekter i planleggingsfasen, og effektivisere prosessen med å utvikle planløsninger. Denne studien beriker litteraturen ved å utforske planløsningsproblemer for skoler, som er en fraværende gren i studier av planløsningsproblemer. I tillegg utvider den implementerte algoritmen eksisterende forskning på planløsningsproblemer ved å vurdere kvalitative og kvantitative mål for SLP som skiller seg fra sammenlignbare studier.

The process of designing a school layout is complex, requiring architectural firms to spend hundreds of hours developing a layout suggestion. The complexity arises from the number of rooms, the diverse composition of rooms, the set of requirements, and both qualitative and quantitative objectives. This motivates the use of optimization techniques to map out the solution space by suggesting layouts with desirable properties. This thesis considers the problem of generating school layouts with low building costs, referred to as the School Layout Problem (SLP). The goal is to develop an algorithm that generates school layout designs where building cost, in terms of building area and exterior corners, is minimized.

A comprehensive literature search reveals that there exists no previous research works on using optimization techniques in school layout design. Thus, a review is conducted on comparable problems, mainly packing problems and other layout problems. Based on the findings, a three-stage algorithm is implemented. The algorithm considers the multi-objective optimization problem of allocating rooms and hallways to a building site, forming a single floor in two dimensions. The algorithm consists of a memetic algorithm (MA), a mathematical model, and a local search (LS). The MA consists of a genetic algorithm (GA) and an LS, which jointly generate a first draft of the school layout. Stage two is a mathematical model formulated as a single-objective integer linear program. The model is applied to subareas of the layout, seeking to minimize the number of corners locally. Finally, a local search is employed in stage three, aiming to minimize the number of exterior corners and the total building area.

The SLP takes a room specification document (RSD) as input - a document listing all rooms and room requirements for a particular school. These are size, shape, proximity, and natural lighting requirements. The RSD does not specify hallways. Instead, this thesis introduces a sophisticated algorithm for dynamically generating hallways. The three-stage algorithm generates school layouts that satisfy the requirements in the RSD, along with additional constraints such as hallway connections between rooms.

Extensive tests of the algorithm are conducted to assess various implementation alternatives, find suitable parameter settings, and improve the compatibility of the three stages. Six RSDs with different complexity and characteristics are used to test the performance of the algorithm. The RSDs are subsets of the RSD for Levanger Middle School, which was built in 2015. The results are satisfying, as the algorithm generates desirable layouts in terms of cost, while meeting the requirements in the RSD.

This thesis illustrates the suitability of applying optimization techniques in the development process of school layouts. The results show that a multi-stage algorithm which exploits the strengths of several solution methods, has strong potential to serve as decision support for architects when designing school layouts. The algorithm generates a wide range of different, desirable layouts. These can be used both as inspiration and starting points for architects in the planning phase, streamlining the process of developing school layout designs. This study adds to the literature by exploring the absent branch of layout problems that is school layout problems. Additionally, the implemented algorithm extends existing research on layout problems by having to consider qualitative and quantitative objectives of the SLP that differ from comparable research works.