Det finns många inverkande faktorer i samband med snöröjning som gör det till ett komplicerat optimeringsproblem som är svårt att formulera som en matematisk modell och lösa inom rimlig tid. 

Snöröjning och liknande aktiviteter, såsom sandning, saltning etcetera, är viktiga för att samhället ska fungera bra även vintertid, men utgör svåra optimeringsproblem. I vilken ordning ska gatorna tas?  Vilket fordon ska ta hand om vilken gata?  Hur ska fordonen köra? Vid vilken tidpunkt kan man räkna med att en viss gata är röjd?

Lösningar för snöröjningsproblem

Det finns många komplicerande detaljer. Exempelvis finns det olika typer av vägar som kan röjas av olika typer av fordon. Cykel- och gångvägar kan inte röjas av större fordon, speciellt om det finns tunnlar, utan kräver mindre, specialiserad fordon. Dessutom finns busshållplatser, korsningar, vändplatser med mera som kräver extra arbete.

Det är till och med svårt att formulera optimeringsproblemet som en matematisk modell. Det finns liknande modeller inom området ruttplanering, och de innehåller i vissa fall tid, men vanligtvis tillåts inte ett fordon att återvända till en plats flera gånger, något som måste ske vid snöröjning.

Gatunät i LinköpingGatunät i Linköping. Bild: Kaj Holmberg. Data från OpenStreetMap.

Det fullständiga problemet är mycket komplicerat och svårt att lösa optimalt inom rimlig tid. Ett möjligt angreppssätt är att dela upp optimeringen, så att man först bestämmer vilket område varje fordon ska röja, och därefter bestämmer hur fordonen ska köra.  Dessa beslut påverkar varandra, så när man vet rutterna för varje fordon kan man behöva göra om gatuallokeringen.

GPS-data kan hjälpa till

Möjligheten att inhämta indata till modellen har drastiskt förbättrats på senare tid. Digitala kartor (såsom OpenStreetMap) finns att tillgå på nätet. Fordon utrustas i allt högre grad med GPS-enheter, så att man i efterhand kan analysera turerna och få en bättre uppfattning om hur lång tid de olika uppgifterna tar. Tidigare har dessa uppgifter behövt matas in för hand, vilket har förhindrat användande av optimering i många fall.

Pågående forskning

Det som här beskrives, inklusive tillämpningar på andra serviceuppgifter i stadsnät, är pågående forskning vid avdelningen för Tillämpad matematik (TIMA).

Publikationer om snöröjning

In search of good relaxations for the urban snow removal problemLinköping University Electronic Press, 2023. , p. 46

Lagrangian relaxation for the urban snow removal problemLinköping University Electronic Press, 2023. , p. 37

Optimization of Snow Removal in Cities Linköping University Electronic Press, 2023. , p. 36

The Non Zealous Snow Remover ProblemLinköping University Electronic Press, 2022. , p. 7

Urban snow removal: Tree eliminationLinköping University Electronic Press, 2022. , p. 24

Coordination of vehicles in urban snow removal, Linköping University Electronic Press, 2021. , p. 64

A branch-and-dive heuristic for single vehicle snow removal, WILEY , 2020. Vol. 76, p. 509-521

Heuristics for the Rural Postman Problem, Computers & Operations Research 37, (2010) pp 981-990

The (Over)zealous Snow Remover Problem, Transportation Science 53:3 (2019) pp 867-881

Heuristics for the weighted k-rural postman problem with applications to urban snow removal, Journal on Vehicle Routing Algorithms,  (2018) 1:105–119

Prepared Test Instances Extracted from OpenStreetMapData Using Different Network Reductions

Urban Snow Removal:: Modeling and Relaxations

Map Matching by Optimization

On Using OpenStreetMap and GPS for Optimization

Kontakt

Forskningsområde