Algoritme for effektiv snørydding

Av: Ole Peter Galaasen | Publisert: 14. Jan 2016 | Kategori: Vei

Algoritme for effektiv snørydding

Snørydding / Foto: iStock

Forskere fra Canada har utviklet en algoritme for å beregne den mest effektive ruten for snørydding og salting av veier.

Olivier Quirion-Blais, Martin Trépanier og André Langevin har sett på hvordan man kan dirigere en flåte av brøytebiler slik at ingen veier blir brøytet mer enn én gang. GPS er lenge blitt brukt til å holde oversikt over brøytebilene. Nå tar forskerne ved CIRRELT (Centre for Inter-university Research and Transport Logistics) og Polytechnique Montréal GPS-dataene videre for å beregne optimale veivalg.

Fakta

 

På 1700-tallet var byen Königsberg (nåværende Kaliningrad) oppdelt i fire deler: den nordlige og sørlige siden av elven Pregel, som fløt gjennom byen, samt to øyer midt i elven. Det ble sagt at byens innbyggere på sine søndagsturer forsøkte å finne en måte å gå gjennom byen på en slik måte at man passerte hver bro bare en gang, og når turen var over var man tilbake til utgangspunktet. Ingen hadde dog lyktes med dette. Enkelte hevdet at det var umulig, men ingen visste dette sikkert.

 

Den sveitsiske matematikeren Leonhard Euler fikk høre om problemet med Königsbergs sju broer og besluttet å løse det. Problemet var å finne en vei som passerer alle bruene eksakt en gang. I 1736 viste han at hvis det finnes flere enn to noder som har et odde antall forbindelser så finnes det ingen løsning.

GPS-data er et effektivt verktøy for å beregne den korteste veien fra et sted til et annet. Til sammenligning er beregning av den korteste ruten for brøytebiler mye mer komplisert. I stedet for å beregne den raskeste veien for et kjøretøy fra et sted til et annet må man ta hensyn til mange kjøretøy og et nettverk av veier som skal ryddes for snø.

For å løse problemet måtte forskerne samle kjørerutene til alle brøytebilene. Dataene blir så analysert for å definere korteste rute samtidig som man forsikrer seg om at alle veiene blir ryddet for snø. Problemet viste seg å være så tungt at snøen ville ha smeltet innen problemet var løst.

For å gjøre beregningene raskere måtte man i stedet for å finne den optimale ruten, ta til takke med gode nok rutevalg. For å komme frem til en raskere beregning, benyttet forskerne en metaheuristisk metode som grunnlag for algoritmen.

Forskerne valgte å basere seg på 260 kilometer med vei i en by i nordlige Quebec for å utvikle en god nok algoritme. Veinettet ble kategorisert i fire klasser avhengig av mengden trafikk på veistrekningene. I tillegg ble veier i forbindelse med sykehus eller politistasjoner gitt ekstra prioritet. Brøytebilene ble også definert på bakgrunn av rekkevidde og andre egenskaper som bredde på plogen.

Med dette som utgangspunkt definerte forskerne ulike mål. Et av målene var å rydde mest mulig vei på kortest mulig tid. Andre mål som ble definert var trafikksikkerhet, kostnader, og kvalitet. Det viktigste var å kunne vurdere effekten av endringer på rutevalgene.

For å kunne utviklet en velfungerende løsning valgte forskerne å tilnærme seg problemet over to faser. I første fase ble det utviklet en kjørerute som ryddet snøen på alle veiene, men som ikke alltid var gjennomførbar. Resultatet ble så tatt videre til andre fase hvor man gjorde endringer på den opprinnelige kjøreruten for å finne realistiske og gode løsninger.

En av de største utfordringene var å utvikle en løsning som lot forskerne søke i et bredt utvalg av kjøreruter. De ulike foreslåtte kjørerutene ble så brukt som beslutningsgrunnlag for valg av kjøreruter. En annen fordel ved løsningen er at man kan eksperimentere med ulike scenarier for kjøreruter.

Forskerne har også sett på hvordan systemet kan brukes til sanntidsanalyser av brøytebilene. Gjennom å koble bilene til ITS-systemer, GPS og værdata vil algoritmen kunne beregne de beste kjørerutene direkte til sjåføren. Erfaringene med løsningen til nå, viser at det er et stort potensiale for tidsbesparelser ved analyser av kjøreruter.