Eerder lieten we zien hoe we de wegennetdata en -kaart kunnen gebruiken en tonen. Een andere uitdaging in het project is om een lusroute te genereren. Veel routeplanners berekenen (kortste of snelste) routes van A naar B. Als een lusroute al mogelijk is, maken ze gebruik van bestaande (bewaarde) routes. Die routes wijken meestal af van de behoeften van de fietser of (hard)loper.
De oplossing hiervoor is gebaseerd op het kortstepad-algoritme tussen twee punten. Je voert het startpunt en de gewenste afstand in meters in. Op basis daarvan wordt in een willekeurige richting (aanpasbaar tussen 1 en 360 richtingen) een middelpunt van een cirkel voor de route bepaald. Vervolgens worden voor het startpunt en een aantal andere, gelijkmatig verdeelde punten op de cirkel (bijv. 10) de dichtstbijzijnde nodes (lengte- en breedtegraadcoördinaten) bepaald. Zie figuur 1 ter verduidelijking.
Vervolgens wordt tussen die nodes opeenvolgend de kortste route bepaald. Dit resulteert uiteindelijk in een lusroute van de gewenste afstand. Zie voorbeeld in figuur 2.
Evaluatie algoritme
Een eerste evaluatie van het algoritme leverde de volgende resultaten op. Bij een gelijkblijvende lengte van de route is de tijdsduur van het genereren van een route evenredig en lineair afhankelijk van het aantal punten (‘nodes’) op de cirkel dat gebruikt wordt om de route te bepalen. Zie grafiek 1.
Als het aantal punten op de cirkel gelijk blijft is de tijdsduur voor het generen van een route nagenoeg gelijk bij verschillende lengtes van de cirkel (van 5 tot 45 km).
Hoe nu verder?
Met behulp van het algoritme is het op dit moment mogelijk om op een gebruiksvriendelijke manier routes te genereren. Nu de eerste versie van het prototype er ligt zijn er nog een aantal uitdagingen om aan te werken:
- Bij fietsen en (hard)lopen zijn de hoogtemeters, maximale stijgingspercentage, en type wegen vaak belangrijk. Deze worden nu nog niet meegenomen bij de routegeneratie.
- We onderzoeken hoe bestaande, geavanceerdere algoritmes wellicht ook een oplossing kunnen bieden voor dit project.