An Optimization-Based Approach to the School Prioritization Problem in Trondheim Municipality

Abstract

En av de viktigste oppgavene til norske kommuner er å tilby innbyggerne sine et godt organisert skolesystem. Raskt økende innbyggertall og kontinuerlig slitasje av skolebygninger gjør dette til en stor utfordring for flere kommuner. Kommunene må derfor vurdere flere skoleutviklingsprosjekter for å imøtekomme disse utfordringene. Denne masteroppgaven har som mål å tilby et objektivt beslutningsverktøy for kommuner ved å studere et område sør i Trondheim.

Gjennom en omfattende litteraturstudie avdekker denne masteroppgaven at de fleste anleggslokasjonsproblemer (Facility Location Problems) retter seg mot å minimere reisekostnader og kostnader ved å åpne eller stenge anlegg. Videre er det tydelig at det å integrere usikkerhet og realistisk data, øker beregningskompleksisteten til problemene. Litteraturstudien avdekker tre mangler: en presis matematisk beskrivelse som inkluderer alle aspekter ved Trondheims problem, en objektivfunksjon som tar hensyn til utnyttelse og kvalitet ved skolene og en løsningsmetode som kan løse problemet innen akseptabel tid.

Med den hensikt å adressere disse manglene, foreslår denne masteroppgaven Skoleprioriteringsproblemet med alternativer (School Prioritizing Problem with Alternatives SPPA). Dette problemet tar for seg et viktig spørsmål: Når det finnes et sett av distinkte mulige prosjekter, hva er de optimale prosjektene å gjennomføre, og til hvilken tid? SPPA minimerer tre uttrykk samtidig: lengden på, og mulige farer langs, elevenes skolevei, uønsket kapasitetsutnyttelse på skolene og ulempene fra dårlig tilstand på skolebyggene som påvirker læringsmiljøet. Siden befolkningsutviklingen er usikker må flere framtidsscenarioer bli vurdert. For å håndtere kompleksiteten i modellen når antall scenarioer øker, er en løsningsalgoritme, basert på branch and bound metoden, utviklet i to variasjoner, den Utførelsesrekkefølgespesifikke branch and bound (EOSBB) algoritmen og den Alternative utførelses rekkefølgespesifikke branch and bound (AEOSBB) algoritmen.

Innledende tester på en deterministisk variasjon av SPPA finner prestasjonsfremmende utvidelser. Implementeringen av en maksimal tillat forverring av skolene og lengde på elevenes skolevei forbedrer modellens kjøretid betraktelig, uten at det blir store endringer i løsningene. Effektiviteten av løsningsalgoritmene er testet i en 15 års perspektiv på data i virkelig størrelse, gitt av Trondheim kommune. Videre tester demonstrerer at AEOSBB algoritmen lykkes med å løse SPPA til optimalitet for instanser med 100 scenarioer innen akseptabel tid. Derfor er AEOSBB algoritmen foretrukket løsningsmetode for modellen.

Resultatene fra SPPA demonstrerer hvordan modellen kan brukes som et objektivt beslutningsverktøy for å hjelpe kommuner. Løsningen er en utvetydig skoleprioriteringsrekkefølge med tilhørende år for ferdigstillelse hvert prosjekt. I tillegg inkluderer løsningen et helt nytt kart over skoledistriktene.

Denne masteroppgaven lykkes med å introdusere en presis matematisk modell og demonstrerer hvordan den foreslåtte løsningsmetoden kan brukes for å løse problemer av virkelig størrelse i kommuner i Norge. Siden dagens beslutningsprosess er omfattende og subjektiv, tror vi at bidraget fra denne masteroppgaven kan være av stor verdi når fremtidens skolestrategi skal planlegges i kommunene.

One of most important responsibilities the Norwegian municipalities is to provide its inhabitants with a well-organized school system. Rapidly increasing populations and continuous deterioration of school buildings make this a substantial challenge for several municipalities. The municipalities must therefore consider several school development projects to meet these challenges. This thesis aims to provide an unbiased decision tool for municipalities by studying an area in southern Trondheim.

Through an extensive literature study on school location problems, this thesis reveals that most facility location problems aim to minimize the travel costs and the opening or closing costs of a facility. Moreover, it is clear that integrating uncertainty and real-size data significantly increases the computational complexity of the problems. The literature study exposes three gaps: a precise mathematical description including all the aspects of Trondheim’s problem, an objective function taking utilization and quality of the schools into account, and a solution method that can solve the problem within an acceptable time.

To close these gaps, this thesis proposes the School Prioritizing Problem with Alternatives (SPPA). This problem addresses an important question: Given a set of distinct possible projects what are the optimal projects to execute at what time? The SPPA aims to simultaneously minimize three terms: the length and hazard of the pupils’ road to school, unwanted school capacity utilization, and inconveniences from poor school conditions that affect the educational environment. As the population development is uncertain, multiple future scenarios are taken into account. To manage the complexity of the model as the number of considered scenarios increase, a solution algorithm based on the branch and bound scheme is developed in two variations, the Execution Order Specific Branch and Bound (EOSBB) algorithm and Alternative Execution Order Specific Branch and Bound (AEOSBB) algorithm.

Preliminary tests on a deterministic variation of the SPPA find performance-enhancing extensions. The implementation of a maximum allowed school deterioration and distance iii to school improves the computational effort without causing significant alterations to the solutions. The performance of the solution algorithms is tested on real-size data provided by Trondheim municipality, in a 15-year planning horizon. The tests demonstrate that the AEOSBB algorithm successfully solves the SPPA to optimality for instances of up to 100 scenarios within an acceptable time. Consequently, the AEOSBB algorithm is the preferred solution method for the model.

The outputs from the SPPA demonstrate how the model can aid the municipalities as an unbiased tool in decision-making. The solution is an unambiguous school prioritization order, with coherent years of execution for each project. The solution also includes a completely new school district map.

This thesis successfully introduces a precise, mathematical model and demonstrates how the proposed solution method can be used to solve real-world problems for a municipality in Norway. As today’s decision-making process is tedious and subjective, we believe that the contribution of this thesis can be of great value when planning a future school expansion strategy in the municipalities.