| dc.description.abstract | Det er mer enn 30 000 kilometer med langrennsløyper i Norge, og for å vedlikeholde og preppe disse løypene bruker kommuner og skiklubber med enn 250 millioner kroner i året. Den største kostnadsdriveren er den daglige preppingen, som er planlagt manuelt basert på erfaring hos maskinførerne. Store nettverk med flere preppemaskiner som starter i forskjellige depoter kompliserer problemet med å finne effektive ruter. Dette resulterer i en unødvendig høy kostnad på grunn av suboptimale rutevalg, og medfører at ruteplanleggingsproblemet med fordel kan løses med optimeringsteknikker.
I Trondheimsområdet er det Trondheim Bydrift som har ansvaret for løypenettverket og vedlikeholdelse av dette. Deres ansatte forteller dagens metode for valg av prepperuter er basert på erfaring og gammel vane. Siden området rundt Trondheim er kjent for ustabile værforhold, mangler langtidsplanleggingen robusthet. Daglige morgenmøter blir avholdt for å ta høyde for variasjoner i vær og andre forhold som spiller inn i planleggingen. Problemet med å preppe skiløyper blir kalt for SGP (the Snow Grooming Problem). Aspekter ved dette problemet som må tas høyde for er at det har flere depoter, at flåten av kjøretøy er heterogen og at løypesegmentene har forskjellige attributter. Løypene blir enten kategorisert som vanlige, prioriterte eller obligatoriske. De obligatoriske løypene er segmenter der prepping er bestilt av en brukergruppe, og har et tidsvindu der prepping må forekomme for gi riktig kvalitet og standard på skiløypene. De resterende løypene blir behandlet som valgfrie, mens populære løyper blir prioritert over perifere deler at løypenettet. Løypene er enten brede eller smale. Små preppemaskiner kan traversere alle løyper, mens store maskiner kun kan kjøre på brede løyper.
I denne oppgaven utvikler vi en matematisk modell for SGP, og sikter mot å finne effektive prepperuter for instanser basert på det lokale løypenettet rundt Trondheim. Målet er å finne gode ruter for den daglige preppingen som blir gjort i vinterhalvåret, der mest mulig av nettverket blir preppet med de tilgjengelige ressursene. Først introduserer vi en kantrutemodell (arc routing problem), som er en intuitiv måte å forstå problemet på. Å løse denne modellen til optimalitet ved eksakte løsningsmetoder har vist seg å ikke håndtere tilstrekkelige store instanser. Derfor blir en transformasjon til et noderutingsproblem (vehicle routing problem) presentert, og en implementering av dette problemet i en kommersiell heuristikkbasert solver.
Kanruteproblemet er formulert som et MILP (Mixed Integer Linear Program) og implementert i den kommersielle programvaren Xpress. Denne modellen er kapabel til å løse instanser på opptil 20 noder 32 kanter til optimalitet på under 3600 sekunder, mens større instanser krever ytterligere løsningstid. LocalSolver utkonkurrerer den eksakte modellen, og de samme løsningene som den eksakte modellen på 0.20\% av tiden for de små instansene. Den håndterer også de større instansene, men for de aller største er gapene relativt store etter 3600 sekunder.
Dette verket fremstår som det første kjente forsøk på å løse SGP. Både problemet og løsningsmetodene er nye med hensyn til litteraturen, så vårt fokus har vært på tekniske aspekter. Problemet er krevende med mange elementer, men ved initielle forsøk virker resultatene lovende. For videre forskning kan det være interessant å implementere VRP-formuleringen i Xpress, for å sammenligne ARP- og VRP-formuleringene videre. Å løse SGP som et set-partitioning problem før man finner optimale ruter kan også være en interessant angrepsvinkel for videre studier. | |
| dc.description.abstract | There are more than 30,000 kilometers of cross-country skiing tracks in Norway, and to maintain these track networks municipalities and local ski clubs spend more than 250 million NOK every year. The primary cost driver is the daily grooming operations which are manually planned based on the experience of the snowcat operators. Large networks with many vehicles starting at different depots complicate the problem of finding effective routes. The result is unnecessary high costs due to sub-optimal route choices, yielding a benefit of solving the route planning problem.
Employees of the municipal enterprise responsible for the cross country facilities in Trondheim, Trondheim Bydrift, explains that today's planning of grooming activities is based on experience and old habits. As Trondheim is an area known for unstable weather conditions, long-term planning lack robustness. Meetings are therefore conducted every morning to handle the variations. The multifaceted Snow Grooming Problem (SGP) involves multiple depots and a heterogeneous fleet of vehicles, where track segments have numerous attributes. First, they are ranked as requested, priority or regular. Requested segments are segments booked for grooming by stakeholders like ski clubs, ensuring top quality for their training sessions and competitions. The requested segments are handled as mandatory by the facilitators of the track network, and a specific time window is set for grooming operations to obtain a certain standard. The remaining segments are considered optional, where popular segments are prioritized over peripheral parts of the network. The track segments are either broad or narrow. Small vehicles can traverse all tracks, but large vehicles can only traverse broad track segments.
In this report, we further develop an intuitive mathematical model for the SGP faced by cross-country skiing facilitators, which was implemented and tested in the project report leading up to this thesis. The goal is finding optimal routes for the daily grooming operation conducted throughout the winter season, covering as much of the network as possible with the resources available. Solving the arc routing model to optimality by exact solution methods was not found to handle sufficiently large instances. To solve large, real instances the model is implemented in LocalSolver, a heuristic based commercial solver. A transformation of the arc routing model into a vehicle routing problem is necessary to enable implementation in LocalSolver and is therefore conducted.
The arc routing model is formulated as a Mixed Integer Linear Program (MILP) and implemented in the commercial software Xpress. The model is capable of solving instances up to 20 nodes and 32 edges to optimality within 3,600 seconds, while larger instances require additional runtime. LocalSolver outperforms the exact model, returning satisfactory solutions within seconds on instances successfully solved by Xpress. The heuristic is also able to return solutions on the larger instances, but with significant gaps within the runtime limit of 3,600 seconds.
To our knowledge, this report constitutes the first known attempt of solving the SGP. An interesting area for future research may be to implement the VRP formulation in Xpress for additional comparisons between the ARP and VRP formulations, as well as the heuristic approach. Solving the SGP as a set-partitioning problem before optimizing the routes is also an interesting approach currently not studied. | |
