J.S.V. Staneke
Modellering wegennet en routeplanner voor stadsdistributie
Computeropdracht,
Rapport 2004.TL.6865, Sectie Transporttechniek en Logistieke Techniek.
De opdracht wordt in het kader van het CiDiS project uitgevoerd. Dit
project verhaalt over de stedelijke distributie. Om verschillende
alternatieven voor de distributie na te gaan, is er een routeplanner
nodig, die met informatie van een Geografisch Informatie Systeem een goed
beeld geeft van de werkelijkheid.
De opdracht bestaat uit vier delen:
- het (kort) beschrijven van bestaande routeplanningsalgoritmes uit de
literatuur
- het ontwerpen en implementeren van een algoritme gebaseerd op de
toepassing van simulatie
- het met behulp van een gebruikersinterface en animatie inzichtelijk
maken van het algoritme
- het verifiëren en valideren van de routeplanning met behulp van
een proeflevering van het NWB; het vergelijken van de resultaten met een
algemeen toegankelijke routeplanner.
Om een route te plannen zijn er verschillende mogelijkheden. Voorbeelden
daarvan zijn de kortste route of de snelste route. Deze routes hoeven niet
altijd aan elkaar gelijk te zijn. Voordat er begonnen kan worden met het
werkelijke ontwerp is het belangrijk om de eisen aan het programma te
definiëren. Voor deze opdracht zal in eerste instantie een programma
worden opgezet voor het bepalen van de kortste route. In een later stadium
zal er gewerkt worden naar de opzet van een bepaling voor de snelste
route. Deze snelste route zal wegens de ontbrekende data in het
proefbestand van het NWB op een heel simpele manier geïmplementeerd
worden, maar wel zo dat de transitie naar het volledige NWB zonder al te
veel problemen zal kunnen verlopen.
Aangezien dit een vervolgopdracht is, is er al een gegevensbestand en een
begin van het algoritme. Dit gegevensbestand bestaat uit een proeflevering
van het Nederlands Wegenbestand (NWB-Wegen). Het volledige NWB-Wegen
voldoet wel aan het programma van eisen met betrekking tot het
gegevensbestand, maar de proeflevering voldoet niet op alle punten. Toch
is gekozen om met deze proeflevering te gaan werken, omdat de
implementatie van het volledige NWB-Wegen, als het algoritme eenmaal
werkt, geen grote problemen hoeft op te leveren. Het algoritme wat
geleverd is bij het begin van de opdracht voldoet wel aan de gestelde
eisen die op dit deel van het algoritme van toepassing zijn.
De kortste route kan op verschillende manieren worden bepaald. Gekozen is
er voor een bepaling om een wagen te laten rijden over de wegen en deze
wagen zich bij elke splitsing te laten klonen en dan weer verder te
rijden. De wagen die op deze manier als eerste bij het gewenste eindpunt
aankomt, heeft dan automatisch de kortste route afgelegd. Voor de bepaling
van de snelste route wordt hetzelfde systeem gehanteerd, maar hier worden
de lengtes van de wegen nog gedeeld door de maximale snelheid op deze
wegen gelden. Het algoritme geeft de kaart van Gorinchem in vergelijking
met de werkelijkheid en andere kaarten redelijk tot goed weer.
De prestatie-indicator die gebruikt wordt zal de rekentijd van het
algoritme zijn. Hiermee kan worden bepaald of deze bij de gegevens van
heel Nederland niet te lang zal worden, waardoor het programma niet meer
voldoet. De resultaten van het programma zullen natuurlijk de gegenereerde
route zijn (hetzij de kortste route, hetzij de snelste route), de afgelegde
afstand, de reistijd en de afgelegde weg.
De configuratie van de PDL beschrijving naar een werkend algoritme in
Delphi is goed verlopen. Het programma bepaalt inderdaad een route, maar
om te concluderen dat deze ook werkelijk de kortste of de snelste route
weergeeft is een verificatie en validatie van het programma uitgevoerd.
Hieruit blijkt dat het programma geen fouten bevat en bij dezelfde
simulaties ook dezelfde resultaten geeft. Ook geeft het algoritme in
vergelijking met routeplanners op internet dezelfde routes, tenzij de
route die het algoritme genereert fietspaden, autovrije zones of wegen met
eenrichtingsverkeer loop bevat. Dit komt omdat deze gegevens niet zijn
verwerkt in de proeflevering van het NWB-Wegen. Ook zijn er nog een aantal
andere oorzaken waardoor de route kan afwijken: straat onbekend, keuze
eindpunt en andere route door andere routeplanner. Duidelijk wordt ook dat
de rekentijd bij toename van het aantal tracks en afgelegde afstand flink
toeneemt en gevreesd moet worden dat bij de implementatie van de gegevens
voor Zuid-Holland en/of Nederland de rekentijd te lang wordt en het
algoritme niet meer voldoet.
Om te onderzoeken of het programma aan de vooraf gestelde eisen voldoet,
wordt er per eis gekeken of deze gehaald is of niet. Uit dit onderzoek
blijkt dat een aantal eisen niet gehaald is. De belangrijkste hebben
betrekking op het invoerbestand. Deze bevat niet alle benodigde gegevens
en bevat ook niet de gegevens van heel Nederland. Een andere belangrijke
eis was dat het programma snel genoeg zou zijn. Zoals hierboven als is
geconcludeerd voldoet dit wel voor de gemeente Gorinchem, maar bij de
implementatie van Zuid-Holland en/of Nederland niet
Rapporten studenten Transporttechniek en Logistieke Techniek
Gewijzigd: 2004.10.13;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.