Artikel aangeleverd door Ignacio “Nacho” Correas, Chief Technology Innovation Officer bij Skymantics –
Er zijn twee afwegingen die zorgvuldig in evenwicht moeten worden gebracht: nauwkeurigheid versus prestatie. Het is nutteloos voor een routing engine om snel suboptimale routes te genereren, maar het is net zo onpraktisch om optimale routes te genereren die veel tijd kosten om te berekenen. Het eerste kritieke punt om naar te kijken in de routing engine is het routingalgoritme.
Routeringsalgoritmen
Skymantics heeft geëxperimenteerd met algoritmen voor het kortste pad, met name Dijkstra en A* (A-ster), in drie modi: unidirectioneel, bidirectioneel en met Contraction Hierarchies Optimization (CH). Het implementeren van een unidirectionele, vanilla-versie van deze algoritmen is vrij eenvoudig en er zijn genoeg tutorials op internet om te helpen begrijpen hoe je dit moet doen. Als vuistregel geldt dat het bouwen van bidirectionele algoritmen (met andere woorden, het pad wordt gelijktijdig berekend vanaf zowel de oorsprong als de bestemming) de optimale route 5x tot 10x sneller zal opleveren dan unidirectioneel, ook al heeft het kiezen van het optimale gezamenlijke knooppunt (waar het pad van de oorsprong het pad van de bestemming ontmoet) zijn eigen problemen. Kiezen tussen Dijkstra en A* en tussen bidirectioneel of met CH is echter niet eenvoudig.
Wanneer A* gebruiken
In theorie zou A* een efficiënter algoritme moeten zijn, omdat het minder berekeningen vereist: het is in principe een gerichte Dijkstra die alleen rekening houdt met de graafknooppunten die helpen bij het bewegen in de richting van de bestemming. Hiervoor is echter het berekenen van richting en heuristische afstanden vereist, wat een kostbare rekenkundige bewerking is dan een Dikjstra-iteratie, en het kan contraproductief zijn. Over het algemeen is A* voor zeer dichte mazen van straten/wegen van dezelfde hiërarchie wellicht een betere keuze. Voor de rest zal Dijkstra waarschijnlijk voldoende zijn.
Wanneer CH gebruiken
Voor lange, cross-country routes heb je een soort optimalisatie nodig, zoals Contraction Hierarchies. Deze optimalisatie geeft prioriteit aan routes met een hogere hiërarchie en negeert alternatieven met een lagere hiërarchie, waardoor de berekeningen om de kortste route te vinden, aanzienlijk worden verminderd. Hier is een voorbeeld van een route van 265 km (165 mijl) door België: het duurt 35 seconden om te berekenen met het bidirectionele algoritme van Dijkstra, maar slechts 0.1 seconde met de Contraction Hierarchies-optimalisatie.
Wanneer Bi-direction Dijkstra gebruiken
Voor kortere, stedelijke routes kunnen Contraction Hierarchies resulteren in een suboptimale route, omdat het algoritme omwegen kan nemen als het een route met een hogere hiërarchie in de buurt vindt. Het is mogelijk om dit effect te verminderen of zelfs volledig te verwijderen door de weghiërarchieën zorgvuldig aan te passen en het algoritme een paar extra iteraties toe te staan. Maar als de routetoepassing alleen voor een specifiek stedelijk gebied is, kan het eenvoudiger zijn om gewoon een bidirectionele Dijkstra te gebruiken. Hier is een voorbeeld van een route in het centrum van Providence, Rhode Island, die gewoon een rechte lijn zou moeten zijn, maar die Contraction Hierarchies voor de gek houdt en een omweg neemt via de nabijgelegen hoofdstraat. De rekentijd voor CH is 1 milliseconde versus 1.5 milliseconde voor bidirectionele Dijkstra, wat aantoont dat er ruimte is voor extra iteraties om dit omleidingseffect te vermijden.
Routingalgoritmen kunnen nauwkeurigheid garanderen en de prestaties tot op zekere hoogte verbeteren. De waarheid is dat ze routeren via een netwerk van wegen die zijn gedefinieerd in een kaartdataset, en de resultaten zijn sterk afhankelijk van de nauwkeurigheid van deze datasets en de manier waarop ze zijn voorverwerkt.
Datasets voorverwerken
Datasets en preprocessing zijn de belangrijkste manier om de nauwkeurigheid en prestaties van een routingalgoritme te verbeteren. Het is moeilijk om dit punt genoeg te benadrukken. Ik zal proberen de belangrijkste aspecten samen te vatten om rekening mee te houden in de volgende punten:
- Niet alle datasets zijn even nauwkeurig. OpenStreetMap is een geweldig voorbeeld; het bestrijkt praktisch de hele wereld en is gratis te downloaden en te gebruiken, maar het mist belangrijke informatie zoals veel snelheidslimieten, lengte-/gewichtslimieten of verboden manoeuvres. In sommige gevallen kan het zelfs onjuiste informatie bevatten met betrekking tot eenrichtingsverkeer of verbindingen, om er een paar te noemen. Andere kaarten, zoals HIER, bieden een veel hoger nauwkeurigheidsniveau, maar hebben een prijs. Grappig genoeg komen straatcoördinaten niet 100% overeen tussen verschillende datasets en ontdekt u mogelijk dat dezelfde coördinaten worden beschouwd als onderdeel van verschillende straten, afhankelijk van de dataset die u gebruikt.
- Afhankelijk van de toepassing van uw routing engine kunnen veel straat- of wegsegmenten die in een dataset worden geleverd, worden samengevoegd tot één rand, waardoor de grootte van de grafiek soms met wel 90% wordt verkleind. Er kunnen bijvoorbeeld snelkoppelingen worden gemaakt om over kruispunten van lagere hiërarchie te springen, waardoor de routeberekening over lange afstanden wordt versneld.
- Een cruciaal onderdeel van de preprocessing is het bepalen hoe de hiërarchie van wegverbindingen moet worden geclassificeerd: verbinden ze wegen van lagere naar hogere hiërarchie? Verbinden ze wegen van dezelfde hiërarchie? Dit is een bijzonder belangrijk aspect voor snelwegknooppunten, aangezien wegen die snelwegen verbinden de hoogste hiërarchie moeten hebben (om Contraction Hierarchies te versnellen), maar het instellen van alle wegverbindingen van een snelweg op de hoogste hiërarchie zal de berekeningen vertragen vanwege te veel kruispunten.
Routingalgoritmen en datasets & preprocessing zijn de belangrijkste aspecten om te overwegen bij het bouwen van een nauwkeurig en performant routingalgoritme. Maar er zijn andere aspecten die het verschil kunnen maken tussen een nuttige en een nutteloze routingengine.
Beste praktijken voor programmeren
Ik ga ervan uit dat er goede programmeerpraktijken zijn en dat er een geschikte programmeertaal is gekozen voor de taak. Er zijn drie kritische punten om te overwegen bij het implementeren en bedienen van een routing engine:
- Grafiekgegevens moeten in het geheugen staan voor maximale prestaties. Er kunnen onderdelen in een database staan, bijvoorbeeld geografische gegevens om de dichtstbijzijnde knooppunten bij de oorsprong en bestemming te vinden, maar het routeringsalgoritme moet werken met in-memory gegevens, anders loopt het risico ondermaats te presteren voor kaarten die iets groter zijn dan een stadscentrum.
- De routing engine moet alle vereiste data vooraf laden en moet threading gebruiken voor secundaire, tijdrovende taken, zoals het opslaan van de gegenereerde route op de schijf. Anders zullen deze tijden oplopen, wat de algehele prestaties vermindert.
- Dit lijkt misschien voor de hand liggend, maar als de routing engine als een externe service moet worden aangeboden, is de verbindingssnelheid cruciaal. Het heeft geen zin om de routingberekening te versnellen als de bottleneck in het communicatiekanaal zit. Latency en throughput zijn essentieel voor een performante API-service.
En dat is het eigenlijk. Het bouwen van een routing engine kan een spannende taak zijn, vol uitdagingen en plezier. Zelfs als je doel niet is om er een te bouwen, maar je routing intensief moet gebruiken, is het goed om de belangrijkste aspecten ervan te begrijpen. Ik hoop dat je net zoveel plezier hebt gehad met het lezen van deze reeks artikelen als ik had met het schrijven ervan. Proost!
