Multimodaal routeren van vracht met OpenStreetMap data

Efficiënt vracht routeren over weg en water

Er bestaan verschillende systemen voor het vinden van de beste route over water en de weg. Google Maps is bijvoorbeeld goed in het vinden van de beste route voor auto, fiets en voetgangers. Ook voor vrachtwagens zijn er meerdere opties, bijvoorbeeld de Geodan Maps API en de TomTom API. Voor vrachtverkeer over water is er de Euris API voor het vinden van de beste route over het binnenvaartnetwerk van Europa.
Voor een project waarbij zo efficient en milieuvriendelijk mogelijk zand moest worden vervoerd zijn we aanvankelijk met deze APIs aan de slag gegaan. Bij dit soort multimodaal vervoer wordt gewerkt met 'overslagpunten'. Dit zijn plaatsen waar het zand tussen vrachtwagens en vrachtschepen wordt overgezet. Als je de standaard route-APIs probeert te gebruiken voor het vinden van het beste overslagpunt, wordt duidelijk dat het lastig is om hiermee een optimale multimodale (= weg + water) route te berekenen. Je zou bijvoorbeeld vanaf het startpunt de kortste route kunnen berekenen naar een haven of ander overslagpunt voor zand en daarvandaan via het water zo dicht mogelijk bij de eindbestemming proberen te komen. Met een standaard route API kun je niet de lijst van dichtstbijgelegen overslagpunten vinden. Ook is er kans dat de verbinding tussen de gevonden overslagpunten niet optimaal is. Soms kan het veel beter zijn om een verderop gelegen overslagpunt te kiezen omdat de route over het water dan veel korter kan zijn. Het verhaal wordt nog complexer als je kunt kiezen uit verschillende typen vrachtschepen: grotere schepen kunnen meestal efficiënter vervoeren, maar kunnen op minder plaatsen komen.

Afbeelding 1. Blauw is water, groen is beginpunt, rood is eindpunt, zwart is vervoer over de weg. Overslagpunt a en b zijn dichterbij begin- en eindpunt dan overslagpunten c, d en e maar de waterroute tussen c en d is korter dan de waterroute tussen a en b en de waterroute tussen c en e is breder dan tussen a en b. Soms zijn de overslagkosten zo hoog dat het voordeliger is om helemaal af te zien van vervoer over het water. Wat is wanneer de meest efficiente route?
Voor de berekening van de efficientste route is de totale hoeveelheid lading ook van belang. Een vrachtwagen kan ongeveer 30 ton aan zand vervoeren. Als de totale hoeveelheid lading bijvoorbeeld 90 ton is, dan volstaan 3 vrachtwagens (3 x 30 ton = 90 ton). 3 vrachtwagens zijn lang niet genoeg om een klein vrachtschip te vullen (CEMT klasse 1, 250 tot 400 ton) en varen met lege schepen is relatief duur. Het is dus alleen efficient om vervoer over water te kiezen als er ook voldoende lading is.
Door bovenstaande uitgaanspunten wordt het aantal mogelijkheden van routeren zo groot, dat het rekenkundig sneller is om de verschillende netwerken met elkaar te intergreren tot 1 "supernetwerk".

Samenstellen geintegreerde netwerken weg en water

Voor zover bekend zijn er geen kant-en-klare geintegreerde algemeen beschikbare netwerken voor weg- en watervervoer. Het lag daarom voor de hand om zo'n netwerk samen te stellen. Met het Nationaal Wegenbestand (NWB) en NWB Vaarwegen kan weliswaar worden gerouteerd, maar de voor vrachtvervoer noodzakelijke informatie is niet direct in deze bestanden beschikbaar. Rijkswaterstaat heeft ook wegvakken en maximum snelheden. Vaarweginformatie wordt ook gepubliceerd. Zulke bestanden hebben elk hun eigen specificatie en verschillen per land. Een andere voor de hand ligggende bron is Open Streetmap (OSM). Deze dataset wordt wereldwijd dagelijks onderhouden en bevat o.a. informatie voor routeren over de weg (weg soort, maximum snelheid, maximum gewicht etc.) en over het water (CEMT klasse van schepen). Vaak is de in OSM aanwezige informatie gebaseerd op de verschillende nationale bestanden, hier en daar aangevuld en verbeterd door lokele vrijwilligers of bedrijven die belang hebben bij zo nauwkeurig mogelijke en meest up-to-date gehouden data.
OSM data kan o.a. worden gedownload van geofabrik. Data is er o.a. per land beschikbaar. Zo is er een dataset voor Nederland in (gecomprimeerd) protobuf bestandsformaat (pbf, augustus 2025: 1.3 GByte). Elk OSM bestand bevat punten ('node'), lijnen ('way', verwijst o.a. naar een set van nodes) en vlakken ('relations' een set van ways, nodes of relations). Voor routeren zijn alleen de nodes en ways van wegen nodig. Een weg is in OSM te herkennen aan bepaalde "tags". De tag voor een standaard weg is "highway" (wordt ook gebruik voor bijvoorbeeld voet- en fietspaden). Voor multimodaal routeren hebben we ook waterwegen en punten nodig, tags "waterway" en "route"="ferry". Er is een javascript library waarmee OSM pbf bestanden kunnen worden gelezen. Bij het lezen roept deze library een callbackfunctie aan voor elke node, way of relation die wordt aangetroffen. Voor het routeren beginnen we met het filteren van ways met OSM tags "highway" of "route"="ferry" of "waterway". De eigenschappen van deze gefilterde ways worden opgeslagen. Elke way heeft o.a. een eigenschap "nodes", de lijst van punten die samen de way vormen. Daarna wordt het bestand nog een keer gelezen op zoek naar de nodes die horen bij de gefilterde ways uit de eerste leesstap.

Het resultaat is een lijst van alle wegen, waterwegen en ponten in Nederland.

Data geschikt maken voor routeren

Voor routeren wordt een weg gerepresenteerd door een lijn. Een lijn bestaat uit verschillende punten die de lijn een vorm geven: de vormpunten. Sommige punten hebben nog een extra functie, namelijk waar er een verbinding met een andere lijn wordt gelegd: verbindingspunten.  

Afbeelding 2. In deze afbeelding zie je 5 verschillende wegen (kleuren). De genummerde cirkels zijn de vormpunten. Punten 3, 4 en 5 zijn ook verbindingspunten. Op punt 3 wordt het uiteinde van de zwarte weg verbonden met één van vormpunten van de blauwe weg. Op punt 4 worden twee kruisende rechte wegen met elkaar verbonden. Punt 5 verbindt twee verschillende wegen met elkaar. Merk op dat de rode en groene weg niet met elkaar verbonden zijn. Dat gebeurt bijvoorbeeld als de groene weg via een brug over de rode weg heen gaat. Van elk wegvak tussen twee punten kan ook de richting worden aangegeven. In OSM gebeurt dat met tag "oneway"="yes", waarbij de volgorde van de bij de way opgeslagen nodes de richting bepaalt.

Om te kunnen routeren, zijn alleen de eindpunten en verbindingspunten van belang. De vormpunten kunnen buiten beschouwing worden gelaten.  Vormpunten 2 en 10 worden daarom verwijderd. De blauwe en gele lijnen worden in meerdere stukken gesplitst, zodat elk lijnstuk tussen precies 2 tussen verbindingspunten of eindpunt zit.

Afbeelding 3. Netwerk geschikt gemaakt voor routeren. Vormpunten (2 en 10) zijn vervallen, wegen zijn opgesplitst (verschillende kleuren blauw en geel) zodat elk wegstuk precies 2 verbindingspunten verbindt.

Vervoerskosten toekennen

Een routeeralgoritme zoekt in principe naar de kortste weg. In de praktijk willen we vaak niet de kortste, maar de snelste of de goedkoopste weg. Je kunt dit bereiken door de data daarvoor aan te passen. In plaats van de afstand tussen twee verbindingspunten te gebruiken, kun je bijvoorbeeld ook de reistijd of de reiskosten tussen die twee verbindingspunten nemen. Het routeeralgoritme vindt daarmee dan automatisch de snelste of goedkoopste weg. Voor de meeste toepassingen van routeren werken reiskosten beter dan alleen de afstand of de snelheid. Een route via een ringweg kan bijvoorbeeld 2 minuten sneller zijn dan de directe route, maar de directe route kan bijvoorbeeld wel 4 kilometer korter zijn. Als je rekent met kosten, dan kun je dus de kosten van 4 kilometer omrijden besparen door 2 minuten extra reistijd te besteden. In het beroepsvervoer zijn zulke kosten voor tijd en kilometers vaak goed gedefinieerd.

Andere vervoeroptimalisaties

Bij veel projecten bestaan er ook extra wensen voor het optimaliseren van het vervoer. Er kan bijvoorbeeld worden gestreefd naar een zo laag mogelijke fossiele CO2 uitstoot, zo min mogelijk stikstof en zo min mogelijk geluidsoverlast. Een routeeralgoritme zoekt de route tussen A en B met de laagste totale som. Als je bijvoorbeeld hoge prioriteit geeft aan een lage CO2 uitstoot, dan kan die uitstoot als kostenpost worden toegevoegd aan elk wegvak. Hoe hoger de prioriteit, hoe hoger de kostenpost. Bij extreme instellingen zal dan bijvoorbeeld blijken dat het vervoeren van zand met paard en wagen en roei- of zeilboot de beste routes oplevert. Electrisch vervoer zal dan nameiljk 'duurder' blijken te zijn omdat elektriciteit vaak nog deels met fossiele energie wordt opgewekt.

De netwerkgraaf (network graph)

In routeeralgoritmes wordt het netwerk verder gereduceerd tot een graaf. Een netwerkgraaf is een lijst van verbindingspunten (nodes) en directe verbindingen (edges) tussen die nodes. Van elke edge worden de kosten van transport vastgelegd.Voor het netwerk in de afbeelding wordt de graaf bijvoorbeeld:

Hierboven is de netwerkgraaf voor het netwerk in de vorige afbeelding. De meeste edges in het netwerk kunnen in 2 richtingen gebruikt worden. Je kunt bijvoorbeeld reizen van punt 1 naar 3 met een kostenpost van 10.6, maar ook van 3 naar 1, eveneens met een kostenpost van 10.6. Eénrichtingwegen kunnen maar in één richting worden bereisd. Edge 9 - 4 staat wel in de graaf, maar 4 - 9 niet, omdat edge 9 - 4 een éénrichtingweg is.

Routeeralgoritme

Het Dijkstra algoritme wordt vaak als basis gebruikt voor het vinden van de beste route tussen A en B. Er bestaan allerlei variaties zoals "bi-directioneel Dijkstra", "A*", "Landmark routing" en "contraction hierarchies". Dit zijn optimalisaties op het Dijkstra algoritme waarbij mogelijk onnodige berekeningen worden overgeslagen. Deze snellere algoritmen kosten minder rekenkracht en geven meestal een (bijna) perfect berekende beste route. Het dijkstra algoritme heeft een rekentijd van O(N log N) waarbij N staat voor het aantal nodes in het netwerk. Als N groot wordt (bijvoorbeeld 1 miljoen nodes), dan begint de rekentijd in de praktijk merkbaar op te lopen. De bi-directionele Dijkstra is een relatief eenvoudige optimalisatie. In plaats van het netwerk to doorzoeken van A naar B, wordt gelijktijdig in A en B begonnen met zoeken en wordt de kortste route gevonden als beide zoekacties elkaar ongeveer halverwege ontmoeten. Met contraction hierarchies kan verbluffend snel worden gezocht in zeer grote netwerken, maar dit vereist uitgebreide voorbewerking van de netwerkgraaf. Er moet nog worden onderzocht of contraction hierarchies wel in aanmerking komen voor multimodaal routeren over weg- en water, omdat de netwerkgraaf voorbewerking meestal uitgaat van 1 uniform netwerk. Voor het rekenen op het Nederlandse weg-waternetwerk blijkt het bi-directioneel Dijkstra algoritme, geimplementeerd in Web Assembly (WASM), voorlopig voldoende snel te zijn.

Multimodaal routeren

Bij het vervoeren van zand over weg en water speelt dat de maximale hoeveelheid vracht afhangt van het vervoermiddel. Een vrachtwagen kan meestal zo'n 30 ton zand vervoeren, terwijl vrachtschepen 300 ton tot 3000 ton per schip kunnen vervoeren. Ook moet rekening worden gehouden dat er extra kosten zijn verbonden aan het overslaan van zand tussen vrachtwagen en schip. Voor het berekenen van routes wordt daarom uitgegaan van de totale hoeveelheid te vervoeren zand. Daaruit kan worden afgeleid hoeveel vrachtwagens en schepen van verschillende types (CEMT1 t/m CEMT5) nodig zijn voor het vervoer. Voor wegen worden de kosten vermenigvuldigd met het aantal vrachtwagens, voor overslag en vervoer over water worden de kosten vermenigvuldigd met het aantal benodigde schepen.

30 ton	300 ton	3000 ton

In bovenstaand overzicht worden verschillende hoeveelheden zand vervoerd tussen omgeving Enkhuizen en Leeuwarden. De lichtblauwe lijn is de gevonden route. Voor 30 ton (1 vrachtwagen) is volledig vervoer over de weg via de afsluitdijk de beste oplossing. Bij 300 ton (10 vrachtwagens, 1 klein schip) loopt het vervoer o.a. via het IJsselmeer en het van Harinxmakanaal in Friesland. Voor 3000 ton (100 vrachtwagens) loopt de route via het IJsselmeer en het ruimere Prinses Margrietkanaal.
Welke vorm van vervoer het beste is hangt sterk af van de beschikbare waterwegen. Soms kan een dichtbij gelegen, maar kleine waterweg de goedkoopste oplossing leveren terwijl in andere gevallen beter iets verder kan worden gereden naar een grotere waterweg voor grotere schepen. In dit project wordt het vervoer over alle 5 netwerktypen (CEMT1 t/m CEMT5) parallel berekend en het beste resultaat als oplossing opgeleverd.

Implementatie in JavaScript

JavaScript is een multiplatform programmeertaal die goed werkt in browsers, maar ook direct onder Linux en Windows (Node.js). JavaScript heeft speciale functionaliteit voor het afhandelen van asynchrone processen. Het is daarom zeer geschikt voor webbrowsers waar gebruikers een interactieve ervaring verwachten, ook tijdens het wachten op antwoorden van internet services. De asynchrone afhandeling van taken maakt het ook extra geschikt voor de afhandeling van API requests zoals bij het berekenen van routes. Een JavaScript server handelt met gemak nieuwe opdrachten af terwijl ondertussen bijvoorbeeld nieuwe routes berekend worden. Dit werkt nog beter door zogenaamde webworkers in te zetten. Dit zijn aparte processen die helemaal los van de server of browser taken kunnen uitvoeren. Hiermee wordt het ook mogelijk om meerdere CPU-cores (server rekenkracht) parallel in gebruik te nemen om zo de rekenkracht van de computer beter te benutten. JavaScript zorgt daarbij min of meer automatisch voor isolatie en synchronisatie van de verschillende processen. Om deze redenen lag het voor de hand om Javascript te kiezen als implementatietaal voor de routing software.
In de praktijk bleken er echter ook nadelen aan JavaScript te kleven. Deze nadelen bleken vooral bij het gebruik van grote hoeveelheden geheugen. De routeersoftware werkt het best als de netwerken in hun geheel in het geheugen worden geladen. Boven bepaalde limieten wordt JavaScript plotseling erg langzaam. Dit heeft te maken met hoe JavaScript het geheugenbeheer intern organiseert. Dit gebeurt automatisch met een zogenaamde 'garbage collector', die binnen bepaalde geheugen limieten zeer snel en efficient werkt. Maar als de ontworpen geheugenlimieten worden overschreden, wordt JavaScript haast onwerkbaar traag.
Als workaround voor dit probleem is de routering uitgevoerd in Web Assemby (WASM), een speciale vorm van JavaScript waarbij het geheugenbeheer niet door de garbage collector maar door de programmeur moet worden beheerd. De software wordt dan vaak geschreven in een andere programmeertaal zoals C, C++ of Rust. In deze programmeertalen ligt het geheugenbeheer bij de programmeur. Voor dit project is de routeermodule in C++ geimplementeerd en met een zogenoemde WASM compiler naar WASM JavaScript omgezet. Hoewel de broncode in C++ is geschreven, kan de resulterende WASM code in alle JavaScript omgevingen (Browsers, Linux, Windows, Mac) draaien. Een bijkomend voordeel is dat veel rekenstappen nog veel sneller gaan omdat de WASM code efficienter is om te zetten naar machinecode, de interne taal waarmee computers rekenen. In de C++ code wordt bijvoorbeeld expliciet gebruik gemaakt van integer berekeningen, terwijl in standaard JavaScript de meeste berekeningen met de minder efficiente maar breder toepasbare floating point getallen worden uitgevoerd.

Demo: Live routeringsysteem (PoC)

Een praktijkvoorbeeld van de ontwikkelde routering is hier te vinden. Het bijbehorende Open API endpoint wordt hier beschreven.
Let op: om demo-capaciteit te besparen, kunnen de eerste berekeningen 1 tot 2 minuten duren.
Deze interactieve demo toont het multimodale routeringsysteem in actie, waarbij gebruikers interactief start- en eindpunten kunnen selecteren, verschillende transportmodi kunnen kiezen (vrachtwagen, schepen van type CEMT1-CEMT5) en optimale routes kunnen vergelijken tussen verschillende modaliteiten. Het systeem berekent automatisch de meest kosteneffectieve route, rekening houdend met transportkosten per kilometer, arbeidskosten per uur, laad- en loskosten, en overslagkosten tussen verschillende modi.

In de demo kunnen de verschillende beschikbare netwerken worden geprobeerd. Je kunt bijvoorbeeld kiezen voor 'boatCEMT1-truck', waarmee het multimodale netwerk voor vrachtvervoer en kleine vrachtschepen (300 ton) wordt geselecteerd. Daarna kun je instellen hoeveel vracht je wilt vervoeren. Bij dit netwerk is de keuze 30 ton (1 vrachtwagen) of 300 ton (1 schip). Nadat begin- en eindpunt op de kaart zijn ingesteld, wordt de route voor de ingestelde vracht berekend en op de kaart getoond. Als een route eenmaal is berekend, verschijnt in deze demo ook de mogelijkheid om de beste route te laten berekenen met alle beschikbare netwerken tegelijk met een instelbare hoeveelheid vracht met knop 'calculate'.

Voor deze demo worden de Open API functies gebruikt die hier zijn beschreven.

Status: Proof of Concept

Het is belangrijk te benadrukken dat dit systeem een Proof of Concept betreft. De huidige implementatie toont aan dat multimodaal routeren met OSM data technisch haalbaar is en goede resultaten oplevert voor demonstratie- en onderzoeksdoeleinden. De versie zoals gedemonstreerd is echter nog niet geschikt voor productieomgevingen.
De belangrijkste beperkingen van de huidige implementatie zijn geheugenlimieten bij grote netwerken. JavaScript heeft inherente beperkingen wat betreft geheugengebruik waarbij het inlezen van uitgebreide wegennetwerken zoals die van Duitsland op praktische grenzen stuit. Voor kleinere gebieden zoals Nederland functioneert het systeem uitstekend, maar bij uitbreiding naar grotere Europese netwerken worden de huidige technische grenzen duidelijk.

Verbeteringen

In de huidige opzet wordt nog geen rekening gehouden met de mogelijkheid om onderweg vracht te verladen tussen scheepstypen of schepen aan te passen aan de doorvaartcapaciteit (variabele hoeveelheid duwbakken). Er moet worden onderzocht of de kosten van opnieuw verladen tussen schepen kunnen worden terugverdiend met een efficienter transport over groter water.

Conclusie

Het beschreven multimodale routeringsysteem laat als Proof of Concept zien hoe moderne webtechnologieën en open data kunnen worden gecombineerd om bepaalde complexe logistieke uitdagingen aan te pakken. Door de combinatie van flexibele netwerkgeneratie uit OSM data, flexibele kostenmodellering en JavaScript implementatie ontstaat een basis voor multimodale vrachtoptimalisatie.