Resource-Constrained Project Scheduling for the Mass Relocation Problem

Abstract

Anleggsmaskiner står for en femtedel av klimagassutslippene i bygg- og anleggsbransjen i Norge, og tilbringer opptil 40 % av arbeidsdagen på tomgang som følge av venting og dårlig planlegging. Bruk av prosjektplanlegging og ruteoptimering for å redusere tomgangskjøring er dermed et viktig steg mot å skape en mer effektiv og bærekraftig byggeprosess.

Denne masteroppgaven handler om transportering av masse på anleggsplasser. Vi tar sikte på å finne optimale tidsplaner for henting og levering av masse mellom lokasjoner med et begrenset antall tilgjengelige dumpere. Vi formulerer optimeringsproblemet som en utvidelse av Resource-Constrained Project Scheduling-problemet (RCPSP), med mål om å maksimere mengden masse transportert innen en gitt tidshorisont. På grunn av den kompliserte RCPSP-formuleringen er det beregningsmessig krevende å finne optimale tidsplaner for prosjekter over lange tidsrom. Vi utvikler derfor flere ikke-eksakte metoder for å planlegge hente- og leveringsaktivitetene mer effektivt. Vi introdusere en lokasjonsparing for å redusere løsningsrommet til probleminstansene, og utvikler en plansammenslåingsalgoritme for å raskt kunne finne lange tidsplaner ved å slå sammen kortere planer. Vi utvikler også en grådig planleggingsheuristikk for å finne tidsplaner iterativt ved å legge til nye aktiviteter en etter en. Vi løser optimeringsproblemene ved hjelp av optimeringsverktøyet Gurobi, og med en egen implementasjon av Benders dekomponeringsalgoritme. En simuleringsstudie og en casestudie med ekte data viser lovende resultater for de ikke-eksakte metodene.

Construction machinery is responsible for one fifth of the greenhouse gas emissions from the construction industry in Norway, and spends up to 40 % of the workday idle with the engine running due to conflicting schedules. Reducing idle time by project scheduling and route optimization is thus an important step towards creating a more efficient and sustainable construction process.

This thesis is concerned with the relocation of mass on a road construction site. We aim at finding optimal schedules for mass pickup and delivery activities, given a fleet of available dump trucks. We formulate the problem as an extension of the Resource-Constrained Project Scheduling Problem (RCPSP), with the objective of maximizing the number of pickups and deliveries completed within a fixed time horizon. Due to the intractability of the RCPSP formulation, finding optimal schedules for projects with many activities is computationally infeasible. Thus, we develop several inexact methods to schedule the pickup and delivery activities more efficiently. We introduce a location mapping to narrow the solution space of the RCPSP instances, and create a schedule concatenation algorithm to find feasible schedules with long time horizons by merging shorter plans. In addition, we develop a greedy scheduling heuristic to build schedules iteratively by adding new activities one by one until infeasibility is proven. We solve the RCPSP instances using the optimization tool Gurobi and with a custom implementation of Benders decomposition. A simulation study and a real-world case study show promising results for the inexact methods.