Kæmpeprojekter

Baggrund

Transvision (www.transvision.dk) har specialiseret sig i at løse komplicerede distributions- og ruteplanlægningsopgaver, hvor restriktioner (kapacitet, tidsvinduer, kvalifikationer etc.), dynamik og strenge krav til svartider spiller en vigtig rolle. Transvisions kunder tæller blandt andre Kinnarps, Arla Foods, Statoil, Unicon og Aalborg Portland.

En  forudsætning for al distributions- og ruteplanlægning er at kunne beregne en korrekt afstand og køretid imellem to kunder. Til det formål haves fuldt digitaliserede vejkort, der i realiteten repræsenteres ved hjælp af en orienteret graf. Knuderne i grafen svarer til punkter hvor vejstykker mødes, f.eks. kryds eller tilkørselsramper til motorveje og kanterne i grafen svarer til vejstykker. På hver kant er der informationer som bruges ved beregning af korteste eller hurtigste vej mellem to punkter i netværket. Typiske informationer er: vejtype, tilladt hastighed, ensretninger, etc.

Når man skal finde hurtigste vej fra punkt A til punkt B sker det ved hjælp af en udbredelsesalgoritme, der begynder ved punkt A og derfra udbreder sig gennem netværket indtil det når punkt B. Det er klart at størrelsen af vejnetværket er altafgørende for, hvor hurtig udbredelsesalgoritmen er. I praktisk ruteplanlægning er der situationer, hvor man er villig til at accepterer en kendt unøjagtighed på den beregnede afstand og køretid mellem to punkter, hvis man til gengæld får en væsentlig hurtigere svartid. I sådanne tilfælde er det oplagt at arbejde på et reduceret vejnet, hvor ikke alle veje er repræsenteret, hvorfor udbredelsen vil ske langt hurtigere, da der er væsentlig færre links at undersøges.

Projektforslag E

Formålet med projektet er at udvikle algoritmer til udtynding af vejnetværk. Udtynding kan ske ved at fjerne links og knuder og ved at erstatte eksisterende links og knuder med nye links og nye knuder. Det er et krav, at netværket fremdeles er enkeltsammenhængende efter udtyndingen, således at det er muligt at komme fra alle knuder til alle knuder.

Udtyndingen skal foregå homogent således at den fejl, der gennem udtyndingen introduceres på afstanden og køretiden mellem punkt A og punkt B, principielt ikke afhænger af, hvor i netværket punkt A og punkt B befinder sig. Algoritmerne skal endvidere konstrueres på en måde, så det på et vilkårligt vejnetværk er muligt at give et estimat af, hvor stor en fejl der er introduceret gennem udtyndingen. Endelig skal algoritmerne være fleksible således at man ved hjælp af parametre kan angive hvor stor udtyndingen skal være – og dermed også hvor store fejl der må introduceres.

Til  understøttelse af projektet stiller Transvision vejdata til rådighed, således at det er muligt at afprøve algoritmerne på realistiske vejdata. Desuden stiller Transvision sin udbredelsesalgoritme til rådighed, så det er muligt at lave afstandsberegninger i de reducerede vejnetværk og sammenligne disse med tilsvarende beregninger i de oprindelige netværk.

Kontaktperson hos Transvision

Jakob Birkedal Nielsen

Email: jbk@transvision.dk

Tel: +45 28 88 87 80