The Mass Relocation Problem with Uncertainty: A Robust Approach to the Optimization of a Real-World Road Construction Site

Abstract

Ved å effektivisere driften kan et veibyggingsselskap potensielt spare mye tid og ressurser. Det er derfor interessant å undersøke alternativer for hvordan de burde rute kjøretøyene sine. Denne masteroppgaven tar sikte på å formulere og løse masseflyttingsaspektet til et veibyggingsanlegg ved å uttrykke det som et robust optimeringsproblem. Arbeidet ble utført i samarbeid med SINTEF Digital på oppdrag fra Skanska.

Denne oppgaven undersøker først kjente kjøreruteproblemer (VRPs) og ser på hvordan de kan brukes til å formulere dette problemet. Vi finner at kjøreruteproblemet med henting og levering og tidsvinduer (VRPPDTW) ligner på den gitte beskrivelsen av anleggsplassen så vi omformulerer dette problemet til det såkalte masseflyttingsproblemet (MRP). Ettersom vi også ønsker å inkludere usikkerhet i formuleringen undersøker vi deretter de to mye brukte robusthetsteknikkene: Soyster-tilnærmingen og Bertsimas-Sim-tilnærmingen. Vi utvikler også vår egen robusthetstilnærming som vi kaller metoden for ekstremverdifjerning (ROA). Ved hjelp av disse formulerer vi masseflyttingsproblemet med usikkerhet (MRPU). For å vurdere ytelsen til våre MRP- og MRPU-formuleringer implementerer vi dem i optimaliseringsprogramvaren Gurobi. Vi undersøker de tilhørende løsningene for et enkelt testforsøk og for ekte data fra ett av Skanskas veibyggingsanlegg. Resultatene våre viser at formuleringen gir gode løsninger, men at beregningstiden er for høy til at metoden kan brukes til å modellere en hel arbeidsdag. Til slutt, presenterer vi mulige forbedringer av problemformuleringen og implementasjonen.

By streamlining operations, a road construction company can potentially save substantial amounts of time and resources. It is therefore interesting to investigate alternative approaches to routing on-site vehicles. This master's thesis aims to formulate and solve the mass relocation aspect of a road construction site by expressing it as a robust optimization problem. The work was conducted in collaboration with SINTEF Digital on assignment from Skanska.

This thesis first explores the field of Vehicle Routing Problems (VRPs) and examines how known variations can be adapted to fit this problem. We find that the Vehicle Routing Problem with Pickup and Delivery (VRPPDTW) closely resembles the given description of our problem, and we modify it into what we call the Mass Relocation Problem (MRP). To include uncertainty into the formulation, we investigate the known robustness techniques commonly used for VRPs; the Soyster approach and the Bertsimas-Sim approach. We also develop a new robustness approach that we call the Removing Outliers Approach (ROA). Using these approaches, we formulate the Mass Relocation Problem with Uncertainty (MRPU). To assess the performance of our MRP and MRPU formulations, we implement them in the optimization software Gurobi. We consider both a simple test case and a real-world case with data provided by Skanska. Our results show that the formulation provides feasible solutions but is currently too computationally expensive for modeling a full work day. Lastly, we present possible improvements to the problem formulation and its implementation to remedy these issues.