Afstudeerverslag: Voorkeursroutes in Routenavigatie

Afstudeerverslag: Voorkeursroutes in Routenavigatie Een requirements analyse ten behoeve van een beoogd beslissingsondersteunend informatiesysteem voor routekeuze bij bestuurders van motorvoertuigen

Hafida Boutahar 16 augustus 2012

Voorkeursroutes in Routenavigatie

Pagina 2 van 79

-2-



-3-

Afstudeercommissie: Dr. K. van der Meer Prof. Dr. Drs. L.J.M. Rothkrantz Prof. Dr. Ir. J.L.G. Dietz

Boutahar, Hafida ([email protected]) Afstudeerverslag, augustus 2012 Voorkeursroutes in Routenavigatie Technische Universiteit Delft, Nederland Faculteit Elektrotechniek, Wiskunde & Informatica Vakgroep Informatiesystemen

Pagina 3 van 79



Pagina 4 van 79

-4-



-5-

Aan mijn moeder, Fatima Ziani, voor haar liefde, steun en oneindige offers Aan mijn vader, El Khadir Boutahar, voor zijn liefde, steun en aanmoedigen Aan mijn kinderen Amin en Aya voor hun begrip ondanks hun jonge leeftijd

Pagina 5 van 79



Pagina 6 van 79

-6-



-7-

Dankwoord Ik wil beginnen met het bedanken van mijn begeleider aan de TU Delft, Dr. Kees van der Meer voor de begeleiding, het aanmoedigen, de inspirerende gesprekken, de discussies, voor het zorgvuldig lezen van mijn verslag en alle tussenstukken en het geven van opbouwende commentaar. Ik wil Prof. Jan Dietz en Prof. Leon Rothkrantz bedanken voor hun flexibiliteit bij het snel faciliteren van mijn afstuderen ondanks hun vele verplichtingen buiten de TU Delft. Tevens wil ik de heren Ir. Eddy de Ridder en Ing. Marco Pas, inmiddels allebei nieuwe uitdagingen aangegaan buiten Logica, bedanken voor hun begeleiding vanuit Logica. Ik wil Drs. Eric van der Laan, voormalig project manager Working Tomorrow, bedanken voor het in mij gestelde vertrouwen, het gunnen van deze interessante en uitdagende afstudeeropdracht en het faciliteren van een goede start van het afstudeerwerk. Woorden schieten tekort om mijn moeder te bedanken voor haar continue steun en voor het overnemen van een groot deel van de zorgtaken voor mijn kinderen. Woorden schieten tekort om mijn vader te bedanken die mij van jongs af aan liefde voor de wetenschap heeft bijgebracht en mij continu aanmoedigde om te studeren. Speciale dank aan mijn broer Driss voor het feit dat ik zo vaak op hem terug kon vallen, voor zijn bereidwilligheid om te helpen. Dankzij hem heeft mijn zoon weinig last gehad van het feit dat ik vaak er niet voor hem kon zijn. Veel dank voor alle tijd en moeite die hij hierin heeft gestoken. Verder wil ik de volgende mensen uit mijn familie en vriendenkring hartelijk bedanken voor hun steun en begrip: Fatiha, Naima, Salama, Said, Yassin, Abdeslam, Fatima, Sanae, Inge, Soaad en Sandra. Zij hebben ervoor gezorgd dat mijn sociale leven overeind bleef ondanks de hectische combinatie met werk en studie en dat er voor mijn kinderen goed werd gezorgd tijdens de vakanties van mijn moeder. En last but not least speciale dank aan mijn echtgenoot Miloed en mijn kinderen Amin en Aya voor hun liefde, begrip en geduld.

Pagina 7 van 79



Pagina 8 van 79

-8-



-9-

Voorwoord Omrijden om die ene drukke straat met voetgangersoversteekplaatsen, stoplichten en openbaar vervoer te omzeilen. Rijden door deze straat kan misschien wel de meest voor de hand liggende optie zijn omdat deze korter is dan de alternatieven maar toch neemt men vaak niet deze straat! Automobilisten staan voortdurend voor zulke keuzes. Welke keuze zal er gemaakt worden op het volgende beslissingspunt/kruispunt en waarom? Feit is dat mensen significant van elkaar verschillen in hun routekeuze–gedrag. Uit studies is gebleken dat dit gedrag onder meer samenhangt met karakteristieken van de automobilist zelf, van zijn rit en van de routes waaruit gekozen kan worden. Alhoewel moderne routenavigatiesystemen/routeplanners steeds meer betrouwbaar worden en steeds meer informatie bevatten over allerlei details zoals eenrichtingswegen en dergelijke; ze blijven achter in de overal waarneembare trend naar personalisatie. Het uitgangspunt bij zulke systemen is nog altijd dat een optimale route onafhankelijk is van de voorkeuren van de weggebruikers. De gebruikte routeselectie–functies maken gebruik van data over afstanden (statisch) en informatie over gemiddelde snelheid (dynamisch). De focus voor selectie van een optimale route ligt op het reduceren van reisafstand en reistijd. Deze zijn echter niet de enige factoren van belang voor routeselectie. Het onderwerp van onderzoek hier is om te achterhalen hoe automobilisten/bestuurders van motorvoertuigen/weggebruikers effectief ondersteund kunnen worden in het routekeuzeproces naar eigen voorkeur.

Pagina 9 van 79



1

- 10 -

Introductie

Dit rapport is het verslag van het afstudeerwerk verricht in het kader van het afstuderen voor de opleiding Technische Informatica bij de Vakgroep Informatie Systemen aan de Technische Universiteit Delft en in opdracht van het bedrijf Logica 1. Er ligt een tijdsbestek van enkele jaren tussen het uitvoeren van het afstudeerwerk en het uiteindelijke afronden ervan door middel van het vervaardigen van dit eindrapport. De oorzaak hiervan ligt in de persoonlijke sfeer. Het afstudeerwerk is (in deeltijd) verricht in de periode tussen september 2006 en september 2007. Enige nieuwe ontwikkelingen die enigszins gerelateerd zijn aan het onderwerp van dit afstudeerwerk hebben in de tussentijd plaatsgevonden. In dit verslag is waar nodig rekening gehouden met deze nieuwe ontwikkelingen. Dit afstudeerwerk past momenteel binnen verdere activiteiten van Logica op het gebied van onder andere het innovatieve Strategic Platform for Intelligent Traffic Systems (SPITS) project en overige projecten die hierop naar verwachting zullen volgen en die nog in een bid–fase verkeren en waarvoor Logica inmiddels een aparte zogenaamde Delivery Center voor heeft opgericht namelijk de Delivery Center “Smart Technologies”. In paragraaf 1.1 wordt een introductie gegeven van het probleemgebied van het afstudeeronderwerp. Vervolgens worden de doelstellingen neergezet in paragraaf 1.2. Daarna wordt in paragraaf 1.3 beschreven in welke context het afstudeerwerk is verricht en wie de opdrachtgever is. Het hoofdstuk wordt afgesloten met een leeswijzer voor dit verslag. 1.1

Inleiding tot het project

Informatietechnologie is tegenwoordig zodanig geavanceerd dat systemen voor het genereren van routeplanning breed beschikbaar zijn. Verscheidene websites bieden routeplanningsfunctionaliteit, verscheidene inbouwnavigatiesystemen zijn verkrijgbaar zoals ook diverse draagbare navigatiesystemen. De beschikbaarheid van digitale kaarten en krachtige snelle processoren maken deze technologie (van routeplanning en routebegeleiding) mogelijk. Het aanbieden van verkeersinformatie en het betrekken hiervan in routeadvies/routeplanning wordt steeds meer gemeengoed tussen commercieel verkrijgbare systemen. Huidige systemen bepalen hun routeplanningen gebruikmakend van kortste pad algoritmen die de route met minimale kosten berekenen. Voor de kosten van een route nemen sommige systemen enkel de verwachte reistijd in beschouwing terwijl andere de keuze bieden tussen de kortste route en de snelste route. Deze systemen beschrijven en presenteren de route aan de gebruiker maar helpen de gebruiker niet of nauwelijks in geval hij aanvullende wensen heeft. Deze systemen negeren het feit dat (auto)rijden in een rijke omgeving plaatsvindt waar verscheidene factoren de wenselijkheid van een bepaalde route beïnvloeden. Een voorbeeld staat 1

Ten tijde van het verrichten van het afstudeerwerk heette het bedrijf nog LogicaCMG

Pagina 10 van 79



- 11 -

getoond in figuur 1.1 . Hierin staat de route afgebeeld welke daadwerkelijk elke ochtend wordt gereden door een pendelende automobilist. Deze route wijkt af van drie verschillende routes geproduceerd door drie routeplanners die elk een andere maar redelijke kostenfunctie gebruiken. Dit voorbeeld toont aan dat deze automobilist voorkeuren, aannames en/of kennis heeft die verschillen van de kennis en de aannames ingesloten in de drie routeplanners. In [1] heeft men data verzameld waaruit blijkt dat automobilisten maar in 35% van hun ritten kiezen voor de snelste route. De conclusie die hieruit getrokken kan worden is dat een scala aan factoren de routekeuzes beïnvloeden van bestuurders.

Figuur 1.1 Vier verschillende routes: A is de gebruikelijke route van een automobilist, B is de kortste route, C is de snelste route op basis van historische data en D is een route geadviseerd door een routeplanner [1] Er is dus nog weinig aandacht besteed aan het bieden van routeplanningen naar tevredenheid van de gebruikers met aanvullende wensen. Het probleem met huidige systemen is het gebrek aan personalisatie en selectie. Commerciële dienstenaanbieders zullen in toenemende mate nieuwe functionaliteiten willen aanbieden aan autobestuurders (of weggebruikers in het algemeen). De beoogde nieuwe functionaliteit “voorkeursroutes in routenavigatie” vormt één van deze nieuwe diensten die in de toekomst aangeboden worden. 1.2

Eerste analyse

Een eerste analyse van wensen en eisen aan een gepersonaliseerd selectief routeinformatiesysteem voor de nabije toekomst omvat de volgende factoren: Efficiëntie gerelateerd: 1. Tijdbesparen t.o.v. alternatieve methoden; nauwkeurige reistijdberekening en daarmee ook nauwkeurige aankomsttijd berekening. Pagina 11 van 79



- 12 -

2. Reisafstand reduceren; tijdelijke restricties zoals wegwerkzaamheden identificeren. 3. Geld besparen; naast aantal kilometers ook rekening houden met tolwegen en (congestie)zones waar rekening rijden geldt. Veiligheid gerelateerd : 1. Een gepersonaliseerd selectief route-informatiesysteem doet de bestuurder gevaarlijke trajecten vermijden. 2. Een gepersonaliseerd selectief route-informatiesysteem voorkomt dat de bestuurder onverwacht op een file stuit en leidt hem via een alternatieve route langs een stremming. Plezier gerelateerd: 1. Een gepersonaliseerd selectief route-informatiesysteem kan de subjectieve kwaliteit van een reis verbeteren en een rijkere reiservaring creëren. Voor een vakantiereis bijvoorbeeld kan dit het leveren van route-alternatieven betekenen zoals routes met uitzichtpunten. 2. Een gepersonaliseerd selectief route-informatiesysteem kan relevante nuttige plaatsen identificeren zoals restauranten, winkelcentra, toeristische attracties en dergelijke. 3. Een gepersonaliseerd selectief route-informatiesysteem is voor veel gebruikers op zich vermakelijk door het inherente spelelement.

1.3

Doelstelling

Het afstudeerwerk behelst een requirements analyse die als basis dient voor het realiseren van een gepersonaliseerd selectief route-informatiesysteem; het opstellen van een globaal ontwerp ervan; en het onderzoeken van de consequenties voor de kaartdatabase die de grondslag is van routeplanning. De focus ligt met name op de functionele aspecten. 1.4

De afstudeercontext

In deze paragraaf wordt beschreven wie de opdrachtgever is en hoe de opdracht zich verhoudt tot de werkzaamheden binnen de organisatie. 1.4.1

Working Tomorrow

Het afstudeerwerk is verricht binnen het Working Tomorrow programma van Logica. Working Tomorrow is een programma van Logica waarbinnen afstudeerders, afkomstig van HBO of Universiteit, zich bezighouden met het toetsen van nieuwe technologische ontwikkelingen op haalbaarheid en mogelijkheden. Binnen Working Tomorrow ontwikkelt men prototypes en demo’s ter verkenning van de technologie en geeft men een indicatie van de factoren die bij een

Pagina 12 van 79



- 13 -

daadwerkelijke implementatie een rol kunnen gaan spelen. Deze afstudeeropdracht past, gezien het karakter en het niveau ervan, uitstekend binnen het Working Tomorrow programma. 1.4.2

Context opdracht binnen de organisatie

Logica is een actieve speler op het gebied van mobiele telematica [29]. Met overheden en partners heeft Logica een jarenlange ervaring met het aanpakken van mobiliteitsvraagstukken. IToplossingen worden steeds belangrijker om de verkeersstromen in goede banen te leiden. Als systeem integrator speelt Logica een centrale rol bij de implementatie van dergelijke oplossingen. Hier volgen een paar voorbeelden van projecten waar Logica bij betrokken is geweest:

1.5

•

Inrichting van tolsystemen of andere vormen van rekening rijden in Nederland, Engeland, Ierland, Oostenrijk en Zweden.

•

Bedenken, bouwen en onderhouden van IT-systemen in verkeerscentrales.

•

Autofabrikanten, transportbedrijven en overheden adviseren over de implementatie van intelligente routeplanners in voertuigen.

•

Inrichten van een systeem voor het betalen met de mobiele telefoon in treinen.

•

Ontwikkelen van systemen voor het alarmeren en informeren van burgers en weggebruikers met behulp van Cell Broadcast (bijvoorbeeld bij calamiteiten). Opbouw van het verslag

Hoofdstuk 2 bevat een nadere probleemspecificatie. Hoofdstuk 3 beschrijft kenmerken van routenavigatiesystemen. Hoofdstuk 4 beschrijft personalisatie en selectie bij enkele reeds bestaande commerciële systemen, en hoofdstuk 5 bij enkele niet-commerciële systemen. Daarop gebaseerd is hoofdstuk 6, dat bevat een analyse van de functionele requirements. Hoofdstuk 7 beschrijft het globale ontwerp van het een gepersonaliseerd selectief route-informatiesysteem. In Hoofdstuk 8 wordt een indicatie gegeven van de toepasbaarheid van kritieke technische hulpmiddelen die bij een daadwerkelijke implementatie een rol kunnen gaan spelen. Hoofdstuk 9 bevat de conclusie en geeft aanbevelingen. De bijlagen bevatten de geraadpleegde deskundigen, voorbeelden van algoritmen, een beschouwing over reinforcement learning, enkele screendumps van het beoogde systeem en literatuurverwijzingen.

Pagina 13 van 79



2

- 14 -

Probleem Analyse

Dit hoofdstuk bevat een nadere specificatie en analyse van het beoogde gepersonaliseerd selectief route-informatiesysteem. Het hoofdstuk wordt afgesloten met een definitieve probleemstelling en het formuleren van de doelstellingen. 2.1

Aanleiding

Het idee van deze opdracht is ontstaan bij de competence GeoICT van Logica. Een consultant kwam met het idee van een zelflerend routenavigatiesysteem. Men formuleerde vervolgens een korte beschrijving van het idee en die luidt als volgt: “Zelflerende routenavigatie: Een navigatiesysteem dat op basis van ‘oude route’ informatie nieuwe routes beter kan bepalen en/of een betere tijdsindicatie (dus op tijd aankomen!) kan geven voor te rijden routes. Op deze manier kan rekening gehouden worden met files a.g.v. wegwerkzaamheden, rijgedrag c.q. - stijl, wegvoorkeur, regelmatige tank- en/of koffiestops, etc.” Met deze beschrijving als uitgangspunt heeft een aantal gesprekken plaatsgevonden om een duidelijker beeld te krijgen van de ideeën van de opdrachtgever over de invulling van de opdracht. De gesprekken waren oriënterend en verkennend van aard en zijn gehouden met een aantal personen binnen Logica zelf en een aantal personen van het bedrijf Almende. De namen en functies van deze personen staan vermeld in bijlage 1. Men had al vanaf het begin een mogelijke oplossingsrichting in gedachten. De tijdsduur van een rit kan mogelijk beter worden bepaald aan de hand van informatie verkregen uit MTS (Mobile Traffic Services), een dienst die LogicaCMG aanbood voor het leveren van actuele informatie over doorstroming en reistijd in het verkeer. Daarnaast zou een agent aan boord van een navigatiesysteem kunnen communiceren met andere agents aan boord van navigatiesystemen in de auto’s van het tegemoetkomende verkeer om informatie te krijgen over de verkeerssituatie op wegen waar het tegemoetkomende verkeer langs is geweest en waar de auto in kwestie naartoe moet. De tevredenheid van de automobilist over de route bepaald aan de hand van deze criteria zou dan aan het einde van de rit door de automobilist aangegeven moeten worden door één enkel antwoord/terugkoppeling, door het bijvoorbeeld geven van een soort rapportcijfer. Dit oordeel moet dan als feedback fungeren voor het bepalen van betere routes naar tevredenheid van de automobilist. Als eerste stap moest duidelijk worden van welke probleemsituatie(s) er sprake is. Tijdens de gesprekken met bovengenoemde personen is dan ook geprobeerd om een aantal probleemsituaties boven tafel te krijgen. Eén daarvan luidt als volgt: “ Altijd als ik op een bepaald kruispunt kom, zegt het navigatiesysteem dat ik rechtsaf moet slaan terwijl ik altijd op dat punt liever rechtdoor rij. Het is irritant dat het systeem hier maar blijft Pagina 14 van 79



- 15 -

herhalen dat ik rechtsaf moet slaan. Kunnen we het systeem niet zo maken dat het “leert” dat ik hier liever rechtdoor rij?” Een andere situatie die tijdens de gesprekken werd beschreven is de situatie waarin een automobilist liever een route neemt wat langer duurt dan dat hij het risico loopt dat hij in de file komt te staan. De automobilist ervaart het door-blijven-rijden, al zou er geen sprake zijn van tijdwinst, als prettiger dan het risico van een langdurige file. Weer andere situaties die naar boven kwamen tijdens het gesprek bij Almende zijn: Een automobilist die door het navigatiesysteem de verkeerde kant op wordt gestuurd van een éénrichtingsweg omdat het systeem “niet weet” dat het een éénrichtingsweg is. Een vrachtwagenchauffeur die voor een tunnel of viaduct komt te staan waarvan de doorrijhoogte kleiner is dan de hoogte van zijn eigen voertuig. Het feit dat automobilisten, bij gebrek aan nauwkeurige reistijdbepaling in huidige systemen, altijd een tijdbuffer moeten inplannen voor een te maken rit en dat deze in de praktijk te groot of te klein blijkt te zijn met het resultaat dat men te vroeg of te laat aankomt op de plaats van bestemming. Samenvattend kunnen de bovengenoemde probleemsituaties samengevoegd worden tot de stelling dat huidige routenavigatiesystemen falen in het berekenen van een betrouwbare indicatie van de achteraf werkelijk persoonlijk ervaren reistijd en dat huidige systemen daarnaast ook geen rekening houden met persoonlijke voorkeuren. Het probleem met huidige systemen lijkt dus een personalisatieprobleem. Het achterhalen om welke personalisatie aspecten het überhaupt gaat en het verifiëren of de hiervoor geformuleerde stelling onderbouwd kan worden, vormde de volgende stap. Voor dit doel zijn diverse wetenschappelijke onderzoeken geraadpleegd. De genoemde onderzoeken zijn verricht onder zowel weggebruikers in het algemeen als gebruikers van routenavigatiesystemen in het bijzonder. 2.2

Achtergrond en motivatie

Uit onderzoek blijkt dat de automobilist voor de dagelijkse routine reizen niet bereid is om herhaald invoer te verrichten in het navigatiesysteem. Dat wil zeggen dat de automobilist niet bereid is tot het continu aansturen van zijn navigatiesysteem terwijl hij wel bij voorkeur ziet dat routeselectie in een hem bekend gebied gedaan wordt op basis van zijn eigen lokale kennis en persoonlijke ervaring. Soortgelijke resultaten zijn verkregen uit onderzoek onder honderd automobilisten, woonachtig binnen de driehonderd vierkante mijl van het testgebied - een deel van Chicago in de VS - , die twee weken lang hebben gereden met auto’s voorzien van routenavigatie [4]. De deelnemers aan Pagina 15 van 79



- 16 -

het genoemde onderzoek oordeelden dat de kwaliteit van de routeplanning gegenereerd door een routenavigatiesysteem niet goed genoeg is. Sommige routes waren langer (soms veel langer) dan de routes die gebruikers zelf zouden kiezen. Reden hiervoor is de structuur van de routeplanner en zijn routeselectiecriteria. Deze zijn zo ontworpen dat de voorkeur wordt gegeven aan grotere wegen om de locale straten (die door woonwijken gaan) zoveel mogelijk te ontlasten. De voorgestelde routes waren niet altijd de meest directe en logische routes vonden de gebruikers. Automobilisten die welbekend zijn met de omgeving herkenden dit snel en weken af naar hun eigen voorkeursroutes. Deze automobilisten kennen gemakkelijkere, kortere en snellere routes die gebaseerd zijn op straten die functioneel lager geclassificeerd worden in het routeplanningsproces van een routenavigatiesysteem. Bovendien kennen deze automobilisten sluiproutes die een rit sneller kunnen maken maar die mogelijk niet gecodeerd zijn in de netwerkdatabases gebruikt door routenavigatie. Uit weer andere onafhankelijke studies blijkt dat een sleutelprobleem met huidige routeplanningssystemen schuilt in het gebrek aan aandacht voor voorkeuren van individuele gebruikers [18], wederom het personalisatieprobleem. Deze studies hebben laten zien dat zulke “one-size-fits-all” strategieën niet geschikt zijn voor alle gevallen omdat gebruikers verschillende voorkeuren kunnen hebben. Sommige studies wijzen erop dat gebruikers vaak niet eens bewust zijn van hun eigen impliciete voorkeuren [2]. De conclusie die getrokken kan worden op basis van al deze studies is dat er behoefte bestaat aan systemen die in staat zijn routes te genereren die in overeenstemming zijn met de voorkeursmodellen van individuele gebruikers [5]. 2.3

Probleemstelling & Doelstellingen

Het routekeuze gedrag van bestuurders wordt bepaald door verschillende factoren [18]. Deze zijn onder te verdelen in factoren die samenhangen met de persoonlijkheid van de bestuurder zelf, factoren die samenhangen met de aard en het doel van de reis en tot slot omgevingsfactoren zoals weersomstandigheden. Het vinden van een optimale route is het gemeenschappelijke doel voor weggebruikers (in dit rapport wordt met name de bestuurder van een motorvoertuig bedoeld) wanneer zij hun reis plannen. Wat een route optimaal maakt hangt echter af van de voorkeuren van de weggebruiker. Ongetwijfeld is het kiezen van de kortste route en/of de snelste route het intuïtieve doel waar men in eerste instantie aan zou denken. Een groot aantal autonavigatiesystemen is ook ontworpen om te voorzien in kortste afstand/reistijd oplossingen. In de gebruikte algoritmen voor het kortste pad probleem (zie bijlage 2) is de aanname altijd geweest dat er alleen één enkelvoudig doel (dat is kortste afstand of minimale reistijd) is dat bereikt moet worden. Toch zijn er zoals gezegd naast reisafstand en reistijd ook andere factoren waarin bestuurders geïnteresseerd zijn tijdens het plannen van hun reis.

Pagina 16 van 79



- 17 -

Wij menen dat de weggebruiker gediend is van een gepersonaliseerd selectief routeinformatiesysteem dat hem helpt een weloverwogen keuze te maken voor een route. Op basis hiervan en na overleg met de begeleiders van Logica en de TU Delft is besloten dat het onderzoek een requirements analyse zal behelzen die als basis kan dienen voor een globaal ontwerp en de realisatie van een dergelijk routenavigatiesysteem. Gelet op de gewenste diepgang van het onderzoek is de doelstelling uit hoofdstuk 1 introductie nader afgebakend en gespecificeerd als volgt: 1. Het analyseren van eisen en wensen ten aanzien van voorkeuren in routenavigatie leidende tot de beschrijving ervan. 2. Het analyseren van de onderscheidende kenmerken en functionaliteiten van wensen en eisen ten aanzien van voorkeuren in routenavigatie in bestaande systemen, zowel commercieel verkrijgbare routenavigatiesystemen als state of the art systemen die nog in een onderzoeksstadium verkeren. 3. Het opstellen van een requirements analyse en globaal ontwerp die als basis kunnen dienen voor het realiseren van een een gepersonaliseerd selectief route-informatiesysteem. 4. Het geven van een indicatie van de toepasbaarheid van kritieke technische hulmiddelen die bij een daadwerkelijke implementatie een rol kunnen gaan spelen.

Pagina 17 van 79



3

- 18 -

Routenavigatiesysteem

Dit hoofdstuk bevat een korte beschrijving van kenmerken van een routenavigatiesysteem en de hoofdfunctionaliteit ervan. 3.1

Plaatsbepaling

De plaatsbepaling [21] wordt gedaan door toepassing van het GPS systeem (Global Positioning System) in combinatie met de zogenaamde “map-matching” technieken, waarbij de locatie op de kaart teruggevonden wordt. Inbouwnavigatiesystemen gebruiken eveneens een gyroscoop en “speed pulse” (een rechtstreekse verbinding tussen de snelheidsmeter van het voertuig en het navigatiesysteem) waardoor het systeem goed blijft werken ook wanneer er tijdelijk geen GPS ontvangst is, zoals in tunnels en tussen hoge gebouwen. 3.2

Routeplanning

Een routeplanner [20]bestaat uit een database en een routeplanner applicatie. In de database zijn alle locatiegegevens en routegegevens waar de routeplanner over beschikt opgeslagen. De routeplanner applicatie bevat alle routines die nodig zijn om de door de gebruiker ingevoerde gegevens te koppelen aan de database, de route te berekenen en de routebeschrijving en het routekaartje te genereren. Om een route uit te kunnen stippelen moet een routeplanner beschikken over locatiegegevens en routegegevens. Een locatie invoervenster biedt de gebruikers de mogelijkheid om de gegevens van de beginlocatie en de eindlocatie en eventueel van een tussenlocatie in te voeren. De beginlocatie kan ook automatisch bepaald worden door het plaatsbepalingsysteem. Via de invoervensters kunnen bij de meeste routeplanners ook configureerbare optimalisatie parameters aangepast worden. De gebruiker kan bijvoorbeeld een route aanvragen op voorkeur van rijafstand of reistijd, een route selecteren en route instellingen zoals wegtype voorkeuren aanpassen. Kortom, het hele routeplanning proces vindt plaats via de invoervensters. De ingevoerde/bepaalde locatiegegevens worden na het drukken op een startknop gekoppeld aan de database van de routeplanner. Als de routeplanner de ingevoerde locatiegegevens met succes in overeenstemming heeft gebracht met de locatiegegevens in de database, wordt de route tussen de locaties berekend aan de hand van de instellingen die de gebruiker heeft geselecteerd. Ten slotte wordt de route in de vorm van een route overzicht, een routebeschrijving en een routekaartje gepresenteerd. In het route overzicht wordt de lengte van de route vermeld en een schatting gegeven van de reistijd. 3.3

Routebegeleiding

Bij routebegeleiding gaat het erom de automobilist de richting te wijzen langs een geplande route. Instructies door middel van spraakberichten en door middel van scherm aanwijzingen, worden om de beurt gepresenteerd om iedere noodzakelijke actie te ondersteunen. Zowel actuele informatie over de afstand tot een actie als de relevante straatnamen bij een kruising worden Pagina 18 van 79



- 19 -

gepresenteerd. Verder wordt een gedetailleerde kruisingskaart getoond om een overzicht van het kruisingsgebied te geven. 3.4

Een commerciële routeplanningsalgoritme

De routeplanningsalgoritme die geïmplementeerd is in de (meeste) bestaande autonavigatiesystemen [11] is een benaderingsalgoritme gebaseerd op de A* algoritme (zie bijlage 2 voor een beschrijving). Het is dus niet gegarandeerd dat een optimale route vanuit een startknoop s, in de graafpresentatie van het wegennetwerk, naar een bestemmingsknoop d wordt gepland. Deze algoritme wordt voor het gemak in het vervolg de CA-algoritme (Commerciële Algoritme) genoemd. De CA algoritme is gebaseerd op een onderverdeling van het wegennetwerk in belangrijke en minder belangrijke wegen. Elk wegsegment van het wegennetwerk of, equivalent hieraan, elke kant in de wegengraaf heeft een zekere wegklasse toegewezen gekregen. Deze wegklasse kan gebruikt worden om het belang van een weg aan te geven: hoe hoger de wegklasse nummer des te minder belangrijk de weg is. Kanten met een wegklasse nummer 0 zijn hoofdzakelijk snelwegen. De CA-algoritme evalueert kanten van alle wegklassen in de nabijheid van de auto en de bestemming. Hoe groter de afstand van een kant ten opzichte van de auto of de bestemming des te groter het belang van een kant moet zijn om in aanmerking te komen voor evaluatie door de algoritme. Meer specifiek, de wegengraaf wordt onderverdeeld in een aantal niveaus. De wegklasse van een kant kan dienen als basis voor de onderverdeling van het wegennetwerk in niveaus. Het meest gedetailleerde niveau wordt het detail netwerk (DT) genoemd en bevat alle kanten van alle wegklassen. Daarnaast worden een aantal hogere niveaus gecreëerd, de zogenaamde hoog–niveau netwerken (HL). Deze hoog–niveau netwerken bevatten alle kanten met minstens een zekere wegklasse. Zo kan bijvoorbeeld een HL netwerk worden gecreëerd dat bestaat uit alle kanten met wegklasse 3, 2, 1 en 0 die dan vervolgens de naam HL3 krijgt. Evenzo krijgt een HL netwerk bestaande uit alle kanten met wegklasse 0 de naam HL0. Zodoende kunnen er voor een wegennetwerk met zeven mogelijke wegklassen nul tot en met zes mogelijk zes hoog-niveau netwerken gemaakt worden (HL0 tot en met HL5) en een gedetailleerde netwerk DT. Het netwerk HL6 komt in dit geval overeen met het gedetailleerd netwerk DT. Het aanmaken van het DT netwerk en een aantal HL netwerken gebeurt vooraf, vervolgens worden de netwerken opgeslagen op een opslagmedium dat ook de digitale kaart bevat. Gewoonlijk worden hooguit drie HL netwerken daadwerkelijk aangemaakt. Wanneer een route gepland moet worden, begint de CA-algoritme met het bepalen van gebieden rondom de auto en de bestemmingspositie. Deze gebieden geven aan welk soort netwerk de algoritme zal moeten gebruiken binnen welk gebied. Als de auto en de bestemming dicht bij elkaar liggen, gebruikt de algoritme over het algemeen alleen het DT netwerk. Echter, wanneer de auto en de bestemmingspositie ver van elkaar liggen, wordt het DT netwerk over het algemeen Pagina 19 van 79



- 20 -

alleen in de buurt van de auto en de bestemmingspositie gebruikt. Er worden gebieden aangemaakt voor elk netwerk behalve het minst gedetailleerde netwerk. Voor het geval één DT netwerk en drie HL netwerken beschikbaar zijn op het opslagmedium dan worden bijvoorbeeld twee gebieden (één rondom de bestemming en één rondom de positie van de auto) aangemaakt voor drie van deze netwerken in dit geval dus zes gebieden, zie ook figuur 3.1. De zoekgraaf van de CA-algoritme bestaat uit alle kanten van een netwerk die deel uitmaken van de gebieden gevormd uit dat netwerk. Een voorbeeld: als we de beschikking hebben over alleen een DT, een HL2 en een HL0 netwerk dan omvat de zoekgraaf alle kanten die deel uitmaken van de gebieden gevormd uit het DT netwerk, alle kanten binnen het HL2 netwerk die deel uitmaken van de gebieden gevormd uit het HL2 netwerk en alle kanten binnen het HL0 netwerk die buiten de gebieden gevormd uit het HL2 netwerk liggen. De CA-algoritme gebruikt dan een aangepaste A*-algoritme om een route te plannen op deze zoekgraaf. De kosten voor het te volgen pad vanuit een vertreklocatie tot aan een bestemming worden vaak overschat om sneller te kunnen plannen. Nadat een initiële route gevonden is, krijgt de automobilist routegeleiding. Hierna maakt de CA-algoritme de berekening van de huidige route af door het te proberen te verbeteren. De resulterende route wordt de definitieve route.

Figuur 3.1. Een voorbeeld van gebieden gebruikt door de CA-algoritme

Pagina 20 van 79



4

- 21 -

Personalisatie: functionaliteit in commerciële systemen

In het kader en het tijdsbestek van het afstuderen is gezocht naar functionaliteit voor personalisatie in operationele commerciële informatiesystemen. In dit hoofdstuk wordt de gevonden informatie over wat huidige 2 systemen te bieden hebben met betrekking tot een zelflerende functionaliteit weergegeven. Bij het kijken naar huidige systemen konden er geen systemen, althans geen informatie daarover, gevonden worden met functionaliteit lijkend op de beoogde functionaliteit. Zeker in Europa niet. In Europa was geen enkel routenavigatiesysteem te vinden met zelflerende functionaliteit. Er is gekeken naar (informatie over) systemen van de volgende producenten: Garmin [36], Mio [37], ViaMichelin [38], Vdo Dayton [39], Pioneer [24] [40], Alturion [41], Navigon [42], MapSonic [38], Blaupunkt Travelpilot [32], Becker [32], Navman [32], THB [32], ROUTE66 [32], JVC [32], LG Electronics [32], Nissan [28], Honda [33], Denso [34], Aisin AW [35], Fujitsu Ten [43], Panasonic [44], Kenwood, Clarion, Alpine, Sony, TOYOTA en TomTom [22]. Onder alle systemen waarover informatie opgezocht is, kon van de volgende systemen informatie teruggevonden worden met betrekking tot personalisatie. Het eerste routenavigatiesysteem dat een (zelf)lerend functionaliteit/een personalisatie functionaliteit, lijkend op wat gezocht wordt, claimt is van de hand van Pioneer. Dat systeem is verkrijgbaar in Japan. Japan [27] blijkt voor te lopen op de rest van de wereld op het gebied van ontwikkeling, productie en verkoop van routenavigatiesystemen. Een tweede systeem heeft Pioneer daarna in de Verenigde Staten uitgebracht. 4.1

Pioneer’s Cyber Navi

Volgens de bronnen [24] [25] van de weergegeven informatie over Cyber Navi, heeft Pioneer voor het eerst in 2003 een “Agent functie” geïntroduceerd in haar harddiskgebaseerde Cyber Navi autonavigatiesystemen bedoeld voor de Japanse markt. Een nieuw concept in autonavigatie dat automatisch “de voorkeuren” en “de rijpatronen” van de automobilist traceert en vervolgens opslaat. In 2004 werden nieuwe functies toegevoegd zoals het voorspellen van verkeerscongesties. In 2005 is aan de Cyber Navi nog eens nieuwe functionaliteit toegevoegd waaronder de VICS (Vehicle Information and Communication Systems) die op aanvraag door het navigatiesysteem ontvangen kan worden. VICS is een geavanceerd systeem in Japan voor het verzorgen van actuele verkeersinformatie (files, ongelukken en andere verkeersrestricties) vanuit de VICS centrale naar de navigatie systemen. 4.2 2

Toyota’s Information Service Function

Wederom wordt hier de situatie tot aan september 2007 bedoeld; wanneer dit niet het geval is, wordt dit expliciet gemeld.

Pagina 21 van 79



- 22 -

Ook Toyota [26] produceerde auto’s voorzien van ingebouwde navigatie die de eerder genoemde VICS dienst ondersteunt. Vervolgens heeft het bedrijf in 2005 een functionaliteit, Information Service Function, toegevoegd dat gebruik maakt van historische statistische data om toekomstige wegcondities te voorspellen. Het systeem geeft routekeuzes aan om congestie te vermijden en geeft informatie over verwachte congesties op het scherm weer. 4.3

Nissan’s Carwings navigatiesysteem

Dit systeem [28] biedt de gebruiker door een druk op de knop contact met een menselijke operator voor het vragen naar de snelste route naar een bepaalde bestemming. Het zoeken naar de snelste route naar een bepaalde bestemming gebeurt op basis van historische verkeersdata met betrekking tot de route en de huidige verkeerssituatie zoals bekend van de actuele verkeersinformatie verzorgd door (de hierboven genoemde) VICS. Communicatie met de operator gaat via een spraakinterface. 4.4

Mobile Traffic Services

LogicaCMG heeft Mobile Traffic Services (MTS) [29] ontwikkeld3, een systeem waarmee verkeersinformatie wordt verkregen. MTS maakt gebruik van het gsm–netwerk, waardoor ingrijpende investeringen, zoals het aanbrengen en beheren van detectielussen in het wegdek, niet nodig zijn. Bijkomend voordeel is dat met MTS gegevens over het hele wegennetwerk verkregen kunnen worden. Met de traditionele detectielussen en camerasystemen is dat alleen op snelwegen mogelijk. MTS wordt aangeboden op abonnementsbasis, zodat wegbeheerders, informatieleveranciers of transportbedrijven over actuele gegevens kunnen beschikken. Het bijzondere van MTS is de manier waarop de data worden ingewonnen. In de meeste auto’s op de weg zijn mobiele telefoons aanwezig. Het is mogelijk om, weliswaar met een kleine afwijking, de locatie te bepalen van mobiele telefoons waarmee gebeld wordt. De verplaatsingen van bellend verkeer kunnen getraceerd worden. Auto’s die een congestie zone naderen, verminderen hun snelheid en hieruit kan bepaald worden dat de mobiele telefoons in de auto’s langzamer voortbewegen op de weg. Door veel mobiele telefoons te ‘volgen’ ontstaat een beeld van de doorstroomsnelheden op het gehele wegennetwerk. Het inwinnen van deze gegevens gebeurt volledig anoniem, zonder inbreuk te maken op de privacy. De voordelen: • De verkeersinformatie is te verkrijgen over alle wegen tegen veel lagere kosten dan met huidige systemen waarbij detectielussen en camerasystemen gebruikt worden. 3 Het bedrijf dat de software–bouwwerkzaamheden heeft verricht voor MTS, Applied Generics, is later opgekocht door TomTom. MTS heeft een andere naam gekregen namelijk TomTom HD Traffic.

Pagina 22 van 79



- 23 -

• Wegbeheerders krijgen met MTS een volledig overzicht van de verkeerssituatie in de regio, zowel historisch als actueel. Met historische gegevens kunnen knelpunten worden geanalyseerd. Het afstemmen van samenhangende maatregelen wordt efficiënter en effectiever. Ook bij tactisch beleid (draaiboeken voor gebiedsinrichting, inrichting verkeerscentrale) kan MTS een rol spelen. De actuele gegevens kunnen direct worden ingezet in operationele situaties, zoals bij het weergeven van reistijden op elektronische panelen langs de weg. • Met een relatief eenvoudige ingreep kan MTS worden aangepast aan het gebied en de wegen waarover informatie wordt ingewonnen. Bij Werk In Uitvoering, waarbij vaak een gewijzigde informatiebehoefte ontstaat, komt dat goed van pas. • De informatie wordt kant-en-klaar aangeleverd en kan direct in de bedrijfsprocessen van transportbedrijven of wegbeheerders worden opgenomen. Content providers kunnen de gegevens verwerken tot aantrekkelijke diensten voor automobilisten (bijvoorbeeld actuele deurtot-deur reistijden en voorkeursroutes). 4.5

(Het ontstaan van) de Nationale Databank Wegverkeergegevens (NDW)

NDW is een databank van wegverkeersgegevens. Maar NDW is ook een samenwerkingsverband van overheden. Overheden die de krachten hebben gebundeld om verkeersgegevens te verzamelen en te benutten. Door deze samenwerking wordt het mogelijk om de filedruk op korte termijn landelijk aan te pakken. De uitvoeringsorganisatie is de spil in het netwerk van betrokken overheids- en marktpartijen. In Nederland wordt hard gewerkt aan het verbeteren van de mobiliteit. Het beter benutten van het bestaande wegennet is een maatregel die op korte termijn effect heeft. Door de inzet van verkeersmanagement en verkeersinformatie. NDW is in 2007 opgericht om voor dit doel landelijke verkeersgegevens in te winnen, te verwerken, op te slaan en te publiceren. De wijze waarop dit gebeurt staat schematisch weergegeven in figuur 4.1.

Figuur 4.1 Het verzamelen en distribueren van Verkeersinformatie in Nederland anno 2012 [45]

Pagina 23 van 79



5

- 24 -

Personalisatie: functionaliteit in niet–commerciële systemen

In het kader en het tijdsbestek van het afstuderen zijn niet alleen commerciële systemen bekeken maar ook is een inventarisatie gemaakt van wetenschappelijk onderzoek dat zich ten doel stelde te experimenteren met het uitwerken van (delen van) de beoogde personalisatiefunctionaliteit in prototype informatiesystemen. Het doel van deze inventarisatie is om een helder beeld te krijgen van de mogelijkheden. Per onderzoek wordt beschreven met welke functionaliteiten men heeft geëxperimenteerd en hoe men deze functionaliteiten in grote lijnen heeft geprobeerd te implementeren. Bij wijze van voorbeeld staan de relevante detailbeschrijvingen van de experimenten uitgevoerd en/of de algoritmes gebruikt binnen genoemde onderzoeken. De volgende onderzoeken worden in dit hoofdstuk besproken: [6], [2], [1], [7], [8] en [9]. Verder worden ook enige relevante aspecten en functionaliteiten van de zogenaamde Intelligent Transportation Systems/Services (ITS) besproken. 5.1

Intelligent Transportation Systems/Services

Intelligent Transportation Systems of Services (ITS) is het internationale verzamelbegrip voor de toepassing van diverse technologieën in relatie tot verkeer en vervoer om systemen veiliger, efficiënter, betrouwbaarder en milieuvriendelijker te maken zonder noodzakelijkerwijs de fysieke infrastructuur te veranderen [46] [47]. ITS maakt het mogelijk om het verkeer centraal te beheren. Nauwkeurige voorspellingen kunnen gemaakt worden, actuele verkeersinformatie kan snel en nauwkeurig gegenereerd worden waardoor incidenten snel opgespoord kunnen worden, en vervolgens geïdentificeerd worden naar aard en gevolg. De informatie kan dan gebruikt worden om het verkeer, dat mogelijk last kan krijgen van het incident, om te leiden. Een goed voorbeeld hiervan is het INVENT onderzoeksproject [23]. Een component project hiervan is het “Traffic Network Equalization” project waarin samenwerking wordt nagestreefd tussen enerzijds persoonlijke (navigatie) systemen in een auto, systemen gelokaliseerd bij verkeerscentra en anderzijds systemen die in het bezit zijn van dienstverleners. 5.1.1

De rol van persoonlijke (navigatie) systemen in de auto

Auto’s worden, in plaats van alleen ontvangers van, ook bron van data. Deze data wordt eXtended Floating Car Data (XFCD) genoemd. De auto’s fungeren als mobiele sensoren. Ze verzamelen, gebruikmakend van data over snelheid en positie en dergelijke, gedurende hun reis belangrijke informatie over de locale verkeerssituatie, de verkeerscontext en de omgeving. Als er relevante informatie is, wordt het anoniem verzonden naar een centrale instantie en wordt het daar gecombineerd met andere data bronnen. Het voordeel van deze gedistribueerde databronnen is dat metingen aan het verkeer mogelijk worden over het gehele wegennetwerk Pagina 24 van 79



- 25 -

zonder de noodzaak van dure vaste infrastructuur zoals sensoren op bruggen of inductielussen in het wegdek die op het moment worden gebruikt. 5.1.2

De rol van centrale verkeerscentra en dienstverleners

De hierboven genoemde gedistribueerde data uit XFCD- auto’s komt binnen bij een verkeerscentrale. Daar wordt het vervolgens verwerkt en geïntegreerd. Ook wordt hier een zogenaamde uitgebreide Knowledge Base met dynamische elementen geconstrueerd en bijgehouden. De Knowledge Base omvat verkeers- en omgevings- data/informatie verkregen uit vaste en mobiele sensoren. De dienstverleners kunnen op hun beurt routeplanningen verzorgen, voor hun klanten, rekening houdend met de informatie afkomstig uit de verkeerscentra en andere bronnen van informatie. De verkeerscentrales en dienstverleners kunnen samen ook zorgen voor een optimale samenwerking waarbij de belangen van alle partijen nagestreefd worden. Zo, kan bijvoorbeeld voorkomen worden dat de dienstverleners het algemene belang ondermijnen door de adviezen van verkeerscentra te misbruiken en bijvoorbeeld sluiproutes aan te raden aan hun klanten. 5.1.3

Routenavigatie in ITS

In de benadering van het hierboven genoemde INVENT onderzoeksproject is een routenavigatiesysteem een onderdeel van een Intelligent Transport Systeem. Routenavigatie wordt hierbij ondersteund door samenvoeging van individuele locale verkeersstrategieën en publieke centrale verkeersstrategieën. Twee aspecten van belang in dit verband om hieruit uit te lichten zijn dynamische routeplanning en personalisatie. Routeplanning gaat uit van een wegennetwerk met dynamische attributen. Dit netwerk combineert criteria afkomstig van een statische digitale kaart met attributen verkregen vanuit een reconstructie van de huidige verkeerssituatie, een voorspelling van de toekomstige verkeerssituatie en ten slotte de kennis van verkeersmanagement en verkeersregeling strategieën. Hoewel deze vorm van routeplanning centraal plaatsvindt, kan er in de (uiteindelijke) routeplanning rekening worden gehouden met persoonlijke voorkeuren van de gebruiker door de routeplanning een personalisatieslag te laten doormaken. Dat laatste kan plaatsvinden in het routenavigatiesysteem dat zich in de auto bevindt. Waar de dienstverlener, op grond van locatie en bestemming van de gebruiker, een route-aanbeveling bestaande uit een lijst van waypoints tot beschikking van (het systeem van) de gebruiker kan stellen, kan het systeem in de auto zelf de uiteindelijke route berekenen rekening houdend met de persoonlijke voorkeuren van de gebruiker. Een andere aanpak is wanneer de dienstverlener informatie over een heel subnetwerk dat tussen locatie en bestemming ligt tot beschikking stelt. Deze informatie wordt vervolgens gecodeerd in de auto ontvangen en op basis daarvan berekent het systeem (in de auto) de gehele route afgestemd op de wensen van de gebruiker. Pagina 25 van 79



5.2

- 26 -

RouteCompiler

In [6] heeft men onderzoek gedaan aan een persoonlijke route-advies systeem. Het uiteindelijke doel van dit onderzoek is een systeem te realiseren dat op dynamische wijze de voor een bestuurder bekende routes, de routekennis van een bestuurder, leert/achterhaalt om deze vervolgens te gebruiken bij diverse toepassingen als routeplanning, routebeschrijving/begeleiding en bestemmingsvoorspelling. Het systeem in onderzoek, RouteCompiler genaamd, probeert de routekennis van bestuurders te achterhalen. Het systeem probeert dit in twee stappen te realiseren: 1) het genereren van de gereden wegen uit GPS lezingen en 2) het achterhalen/leren van welke routes (wegsegment-opeenvolgingen) een bestuurder gebruikt tussen afzonderlijke vertrekpunten en bestemmingen. 5.2.1

Het genereren van gereden wegen

Men is begonnen met het verzamelen van data over het routegebruik van de automobilisten. Dit is gedaan door de GPS sporen van de ritten gemaakt door de automobilisten te loggen. In [6] staat niet duidelijk beschreven hoe men te werk is gegaan. Echter, in [1] heeft men ook een dergelijke experiment uitgevoerd. De werkwijze die men daar heeft gehanteerd staat beschreven in paragraaf 5.2.1. Aan het einde van deze stap beschikt men over een verzameling GPS sporen voorzien van positie- en tijdstipaanduidingen. De volgende stap bestaat uit het bewerken van de data teneinde het betreffende wegennetwerk te representeren. De meest voor de hand liggende representatievorm voor het wegennetwerk is een graaf. In de regel wordt data die overeenkomt met een kruising gerepresenteerd door een knoop in de graaf. Data afkomstig uit stukken weg tussen twee kruisingen in maakt in de representatie deel uit van een kant tussen twee knopen. Representatie van een enkele weg geschiedt met behulp van meerdere kanten omdat elk wegsegment (de kleinste onafgebroken deel van een weg tussen twee kruisingen) een aparte kant is in de graaf. De verzameling GPS punten voorzien van positie- en tijdstipaanduidingen worden in volgorde verwerkt. De volgorde van de metingen wordt bepaald aan de hand van de tijdstipaanduidingen in de data. In grote lijnen komt de verwerking van de GPS data er op neer dat er voor elk nieuw punt nagegaan wordt of deze past in de gedeeltelijke graafstructuur dat tot op dat moment geconstrueerd is. Wanneer dit niet het geval is, moet er dus een nieuwe knoop of kant aan de graaf toegevoegd worden. Dit proces omvat drie algemene stappen die voor elk punt doorlopen worden in de volgorde zoals beschreven in de volgende paragraaf. 5.2.2

Graafconstruerende algoritme

Pagina 26 van 79



- 27 -

Eerst wordt er nagegaan of de positie en tijd gegevens van het nieuwe punt verschillen ten opzichte van het vorige punt. Zijn de gegevens van het vorige en het huidige punt identiek dan wordt het huidige punt genegeerd. Het bevat immers geen nieuwe informatie. Als de twee punten wel van elkaar verschillen dan controleert het algoritme ze op discontinuïteit in de tijd en de geografie. Als die er is dan vormt het nieuwe punt ofwel deel uit van de bestaande structuur van de graaf ofwel een nieuwe knoop. Als het nieuwe punt én niet identiek is aan de vorige én geen discontinuïteit weergeeft ten opzichte van het vorige punt dan wordt er bekeken of het past binnen een bekende knoop dan wel kant in de bestaande graafstructuur. Wanneer dit het geval blijkt te zijn en wanneer ook het vorige punt onderdeel was van de bekende graaf dan hoeft er niets gedaan te worden. Alleen wanneer het vorige punt onderdeel was van een nieuwe kant dan voegt het algoritme de nieuw bijgewerkte kant aan de graaf toe. Als het nieuwe punt geen deel uitmaakt van de bekende structuur dan moet er kennelijk een kant doorgetrokken worden of een geheel nieuwe kant aangemaakt worden. De afstand tussen een nieuw punt en de lijn door de punten die tot dusver een kant vormen, wordt vergeleken met een bepaalde drempelwaarde. Als deze wordt overschreden dan wordt er een nieuwe knoop en een nieuwe kant aangemaakt anders wordt de bestaande kant gewoon uitgebreid. Deze graafconstructie stap resulteert in (a) een representatie van de wegen in de vorm van een graaf bestaande uit een verzameling knopen welke punten representeren waar de GPS data start, stopt, keert of discontinu is en (b) een verzameling kanten die de GPS punten tussen twee knopen representeren. 5.2.3

Het achterhalen van routekennis

De uit de vorige stap resulterende graaf dient op zijn beurt als input voor een algoritme voor het afleiden van welke routes (wegsegmentopeenvolgingen) de bestuurder gebruikt tussen afzonderlijke vertrekpunten en bestemmingen. Uitgaande van de graaf genereert het systeem een grammatica van mogelijke routes tussen twee punten. Een voorbeeld graaf met de bijbehorende grammatica staat afgebeeld in figuur 5.1 .

Pagina 27 van 79



- 28 -

Figuur 5.1 Een voorbeeld graaf met bijbehorende grammatica uit [6] Ter verificatie van de geëxtraheerde routekennis heeft men een experiment opgezet waarbij de gebruikte algoritmes zowel op reële data als op synthetische data zijn getraind. Een gesimuleerde generator van GPS locaties genereerde synthetische data door het doorlopen/doorkruisen van random kaarten. De werkelijke GPS databron was een auto in het oosten van de staat van Washington. De data reikte over enkele uren van autorijden en bestond uit honderden punten. Door het vergelijken van de (op de hierboven beschreven wijze verkregen) graafpresentatie met een digitale-kaart van het gebied wilde men verifiëren of de knopen corresponderen met de kruisingen en de kanten met de wegen. Het RouteCompiler systeem blijkt gevoelig te zijn voor de ruis in de data. Men verwacht dat het gebruik van een digitale kaart om de fouten in de GPS data te corrigeren, zal leiden tot een verbetering van de nauwkeurigheid van de resulterende graaf. 5.3

TRIP

In [1] heeft men met behulp van de GPS data over de routes gereden door gebruikers schattingen gemaakt van tijdsafhankelijke snelheden op de weg en een modellering opgesteld van de impliciete individuele voorkeuren. Men heeft deze twee dimensies vervolgens gebruikt voor het aanpassen van de kostenfunctie gebruikt voor routeplanning. Vervolgens demonstreerde men middels een experiment dat de op deze wijze verkregen routes significant meer lijken op de routes gekozen door bestuurders met lokale routekennis dan de routes berekend met behulp van traditionele statische routeplanners. De voor TRIP (een afkorting voor een prototype routeplanner genaamd “Trip Router with Individualized Preferences”) gebruikte benadering valt onder wat in dit verslag de impliciete benadering wordt genoemd. Cruciaal voor deze benadering is de data over daadwerkelijk gereden routes door gebruikers. Voor deze doeleinde worden GPS sporen van gereden routes vastgelegd en verwerkt. De wijze waarop men dit heeft gedaan voor TRIP wordt in de volgende paragraaf beschreven. 5.3.1

Het verzamelen van een GPS dataset (MSMLS)

Pagina 28 van 79



- 29 -

Men gebruikte in [1] een dataset die eerder was verzameld en de naam had gekregen van “The Microsoft Multi-Person Location Survey” (MSMLS) data. In het experiment, van Microsoft Research, is men op de volgende wijze te werk gegaan. Er werden veertig GPS apparaten gebruikt om geografische (lengte, breedte) coördinaten voorzien van tijdstipindicatie te verzamelen. Elk apparaat werd voor een periode van twee weken geplaatst op het dashboard van een voertuig van telkens weer een ander inwoner van Seattle in de Verenigde Staten. Dit proces werd herhaald voor steeds weer nieuwe personen over een aantal perioden. Hiermee werd data verzameld van de gereden sporen van honderdentwee verschillende individuen in een twee weken durende periode. Aan de personen in kwestie werd geen wijziging van het rijgedrag gevraagd. De GPS apparaten werden zodanig geconfigureerd dat ze alleen data opnamen wanneer de voertuigen in beweging waren. De automobilisten zelf hadden daar geen omkijken naar en zij hoefden de apparaten dan ook niet aan of uit te zetten. Hierdoor zou de data verzameld voor elke automobilist een momentopname moeten weergeven van zijn of haar natuurlijke rijgewoontes.

Figuur 5.2 De MSMLS dataset van het centrum van Seattle verzameld in dit experiment Gedurende het verzamelen van de data stopten de GPS apparaten met het opnemen na enkele minuten van stilstand (wanneer het voertuig geparkeerd stond) of na enkele minuten van verlies van het satellietsignaal (wanneer het voertuig zich bevond in een garage). Het opnemen werd hervat wanneer de normale reiscondities zich weer voordeden. De tijdgaten in de GPS logs bij elk eindpunt van een rit zijn gebruikt voor het identificeren van individuele ritten. Een klein aantal gevallen bleek complexer te zijn en daarvoor is een aparte segmentatie gebruikt. De verzamelde dataset bestond uit 288021 individuele GPS metingen en resulteerde uiteindelijk in 2517 afzonderlijke ritten met een totale lengte van 18853 mijl oftewel ongeveer 30341 kilometer. Een voorbeeld van hoe deze data gebruikt kan worden voor het representeren van een wegennetwerk

Pagina 29 van 79



- 30 -

staat beschreven in paragraaf 5.1.1. In het geval van TRIP heeft men een alfa versie van de MapPoint software, van Microsoft, gebruikt voor referentie naar een digitale-kaart database. 5.3.2

Het opnemen van bestuurdersvoorkeuren in routeplanning

TRIP probeert voorkeur impliciet vast te leggen en te verwerken. TRIP modelleert niet de factoren die van invloed zijn op routevoorkeur. In plaats daarvan, beschouwt TRIP (de aanwezigheid van) elke reis in de GPS sporen van een bestuurder als een verklaring van voorkeur. Hierbij wordt de aanname gedaan dat de door de bestuurder genomen route zijn voorkeur heeft boven alle andere mogelijke routes tussen dezelfde eindpunten. De onderzoekers in [1] steunen voor deze aanname op het gegeven dat de bestuurders waarvan de data is verzameld lokale bewoners zijn die steeds binnen een voor hen bekend gebied hebben gereden. Voor elk automobilist werd de verzameling GPS sporen één voor één doorlopen. Per spoor werd een zogenaamde inefficiency ratio r berekend. Deze is gelijk aan de ratio van de duur van de werkelijke reis gemaakt door de automobilist en van de duur van de snelste route (naar verwachting) tussen de eindpunten van het spoor. Deze laatste (snelste) route werd berekend aan de hand van een A* routeplanner (zie paragraaf 3.4) die gebruikmaakt van variërende snelheden in de tijd berekend aan de hand van daadwerkelijk ervaren reistijden gewonnen uit GPS data. De waarde van r lag in de meeste gevallen tussen nul en één. In gevallen waar de werkelijke reisduur van de automobilist korter was dan de verwachte snelste reistijd werd de waarde van r op één gezet. Voor elke automobilist werd vervolgens zijn persoonlijke inefficiëntie parameter r berekend als het gemiddelde van de afzonderlijke r waarden, berekend uit de GPS sporen van de automobilist. Net als de r waarden, liggen de r waarden ook tussen nul en één. Een r waarde gelijk aan één geeft aan dat de automobilist over het algemeen de meest efficiënte route (lees de snelste route) kiest, terwijl lagere waarden een hogere bereidheid impliceren tot het opofferen van efficiëntie voor andere voorkeuren. De r waarden werden als volgt gebruikt om een voor de automobilist specifieke kostenfunctie/utiliteitsfunctie te definiëren voor het rijden op een bepaald wegsegment i :

ci =

{

r ti als i eerder gereden is

ti als i niet eerder gereden is Waarbij ti de verwachte reistijd (afhankelijk van de tijdstip van de reis) is die nodig is om segment i af te reizen. Hieruit volgt dat een pad (in de graaf representatie) dat alleen maar niet eerder gereden (geen voorkeur hebbende) kanten gebruikt en x seconden reistijd vereist, equivalent is qua kosten aan een pad dat alleen gebruik maakt van voorkeurkanten (eerder gereden) en (1 r ) x seconden reistijd vereist om te berijden (zoals hierboven vermeld is r < 1). Immers, de reductie door de Pagina 30 van 79



- 31 -

factor r zorgt ervoor dat dit laatste voorkeurspad ook r (1 r ) x = x kost. Deze equivalentie komt overeen met het uitgangspunt dat de automobilist bereid is de duur van zijn reis te verlengen met een factor maximaal gelijk aan 1/ r om tegemoet te komen aan zijn voorkeuren die niet gerelateerd zijn aan efficiëntie (lees reistijd). Bovenstaande kostenfunctie reduceert de kosten van eerder gereden (voorkeur)kanten en weerspiegelt daarmee ook de interpretatie dat de eerder door de automobilist gereden routes voorkeursuitingen zijn van hem. Twee hoofdaannames zijn inherent aan deze benadering. De eerste is dat automobilisten hun keuzes maken op basis van voldoende kennis. Met andere woorden ze verlengen de duur van hun reis niet uit onwetendheid. De tweede aanname is dat automobilisten de voorkeur geven aan wegen die ze eerder hebben genomen. De onderzoekers constateren dat deze aannames niet waar hoeven te zijn voor alle reizen. In de MSMLS data gebruikt voor het TRIP systeem is geen onderscheid gemaakt tussen de routes genomen uit voorkeur en de routes genomen uit onwetendheid. Desondanks werd met resultaten uit een experiment aannemelijk gemaakt dat het genereren van routes op basis van deze aannames gerechtvaardigd is. 5.3.3. Een experiment In dit experiment werden routes gegenereerd door het TRIP systeem vergeleken met de routes die daadwerkelijk door de automobilisten zijn genomen. Per keer werd telkens weer één verschillende reis weggelaten uit de verzamelde GPS data. Door gebruik te maken van de overblijvende GPS sporen berekende het TRIP systeem de bij een automobilist behorende inefficiëntie ratio op dezelfde wijze als hierboven wordt beschreven. Het TRIP systeem werd dan bevraagd voor een route waarvan de eindpunten overeenkomen met de eindpunten van de reis die op dat moment uit de data is weggelaten. Een dergelijke poging werd als succes beschouwd als de voorgestelde route overeenkomt met de route die daadwerkelijk door de automobilist is genomen. Een goede overeenkomst werd gedefinieerd als een overlap van meer dan vijfennegentig procent in afstand tussen beide routes. Na elke poging werd de weggelaten route weer toegevoegd aan de data alvorens door te gaan met de volgende poging. Het TRIP systeem stelde in bijna de helft (46.6%) van de gevallen een route voor die goed overeenkomt met de route daadwerkelijk gereden door de automobilist. Ter vergelijking stellen de onderzoekers dat slechts dertig procent van de routes daadwerkelijk gereden door de automobilisten (in de GPS sporen data) overeenkomen met routes voorgesteld, als de snelst zijnde routes, door een traditionele (statische) routeplanner 4. Men concludeerde hieruit dat het opnemen van dynamische snelheden en voorkeursroutes in routeplanning de performance verbetert. De gegeneerde route sluit beter aan bij de persoonlijke voorkeur van de automobilist.

4

In de gebruikte bron [1] is niet duidelijk om welke traditionele routeplanner(s) het gaat. Men heeft alleen MapPoint expliciet genoemd.

Pagina 31 van 79



- 32 -

Daarnaast heeft men ook het volgende bevonden. Slechts 10.8% van de routes in de verzamelde GPS sporen data waren duplicaten. Hierbij wordt een duplicaat gedefinieerd als een spoor dat dezelfde automobilist, startpunt en eindpunt heeft als een ander spoor ongeacht of de route genomen tussen de eindpunten hetzelfde is. Dit betekent dat in 35.8% (46.6% - 10.8%) van de testgevallen het TRIP systeem nieuwe optimale routes, routes die niet gezien zijn in de trainingsdata, aan het construeren was door het samenvoegen van voorkeuren uit een verzameling onafhankelijke trainingsritten. Men concludeerde dat het TRIP systeem in staat blijkt te zijn routes te berekenen die de voorkeur van de automobilist genieten zonder ooit een trainingsexemplaar te hebben gehad van de gevraagde route. 5.4

Adaptive Route Advisor

In een reeks onderzoeken [10], [2] en [12] heeft men geëxperimenteerd met een prototype systeem genaamd “The Adaptive Route Advisor”. Deze serie onderzoeken hebben als uiteindelijke doel een systeem dat de functies van een menselijke reisagent overneemt. Het systeem zou moeten voorspellen welke route de voorkeur van een automobilist zou hebben op basis van een model van de bestuurdersvoorkeuren. Als de voorspelde route niet naar tevredenheid is, zou het systeem meer routes moeten genereren op basis van interactie met de bestuurder. De route welke de gebruiker uiteindelijk kiest, dient als feedback om diens voorkeursmodel te verbeteren. De relevante functionaliteiten/ideeën behandeld in deze reeks onderzoeken waren het construeren van een gebruikersmodel op basis van (beperkte) interactie met gebruiker en met behulp van een adaptatie algoritme. Men gebruikte hier wat in dit verslag de expliciete benadering wordt genoemd. Het uitgangspunt hierbij is dat de criteria voor het maken van beslissingen bij routekeuze samenhangen met de attributen van wegsegmenten. Het relatieve belang van deze attributen voor een gebruiker, uitgedrukt in numerieke waarden zou het gebruikersvoorkeurmodel en equivalent hieraan de persoonlijke kostenfunctie van deze gebruiker moeten representeren. Door het gebruiken van de zo verkregen persoonlijke kostenfunctie (in plaats van een traditionele kostenfunctie) in de routeringalgoritme zou een route kunnen worden berekend dat optimaal is op basis van de persoonlijke kostenfunctie van de gebruiker en daarmee conform de persoonlijke voorkeuren van de gebruiker is. Het construeren van een gebruikersmodel/persoonlijke kostenfunctie vindt hierbij plaats aan de hand van een adaptatie algoritme. Het model, in de vorm van een vector numerieke waarden, wordt afgeleid uit de rankings gegeven door een gebruiker aan een verzameling routes. 5.4.1

Het testen van een adaptatie algoritme

Pagina 32 van 79



- 33 -

Voor het testen van de adaptatie algoritme gebruikt voor The Adaptive Route Advisor simuleerde men een serie interacties op papier met testpersonen die de output van de routeplanner evalueerden.  Hierbij werden routes gepresenteerd door middel van een vector x die vier attributen bevat: de geschatte totale reistijd, de totale afstand, het aantal bochten en het aantal kruisingen. Een initiële  gewichtenvector w wordt gebruikt om de kosten van een route te schatten met het lineaire   product: c= w ⋅ x.

   Als route x1 door de testpersoon verkozen wordt boven route x2 én de kosten van route x1 zijn  lager dan de kosten van route x2 , dan zijn de gewichten (in de gewichtenvector) overeenkomstig de voorkeur van de automobilist en hoeven ze niet aangepast te worden.   Als de kosten van route x1 hoger zijn dan die van route x2 dan zijn de gewichten niet overeenkomstig de voorkeur van de testpersoon en moeten ze aangepast worden. Om de kosten    van x1 te verlagen en die van x2 te verhogen wordt de gewichtenvector w volgens de volgende formule aangepast, een zogenaamde perceptron update regel, dat de basis vormt voor de hier gebruikte adaptatie algoritme:      ∆w= η x2 − η x1= η ( x2 − x1 ).

η is de leergraad (eng. the learning rate), η = 0.0001 komt overeen met 100.000 trainingsrondes.   De waarde ∆w wordt bij w opgeteld totdat deze laatste niet meer wijzigt óf totdat een vastgelegd aantal iteraties overschreden is. De test bestond uit twintig taken betreffende ritten tussen kruisingen in het Palo Alto gebied (in de Verenigde Staten). Voor elke taak werden vier routes geproduceerd gebruikmakende van dummy gebruikersmodellen met een eenheidsgewicht voor één attribuut en een nul gewicht voor de rest. Zodoende werden routes gecreëerd welke geoptimaliseerd zijn voor reistijd, afstand, aantal kruisingen en aantal afslagen. De routes gelabeld met A tot en met D werden in willekeurige volgorde weergegeven op een kaart van Palo Alto. De (test)taken werden in steeds verschillende willekeurige volgorde voorgelegd aan elk testpersoon. Figuur 5.3 laat een voorbeeld zien van één van de taken en de bijbehorende vier routekeuzes.

Pagina 33 van 79



- 34 -

Figuur 5.3 : Vier verschillende routes tussen twee eindpunten [2] Route A is de route met het minste aantal bochten/afslagen. Route B is de snelste route. Route C is de route met het minste aantal kruisingen. Route D is de kortste route. De testpersonen werd gevraagd om de routes te evalueren voor elke taak en te waarderen/ranken in volgorde van voorkeur waarbij de waarde 1 gebruikt kon worden voor het aangeven van de meest voorkeur hebbende route en 4 voor de minst voorkeur hebbende route, hetgeen werd herhaald voor elke taak opnieuw. Het ranken van de vier routes heeft de (120) trainingsinstanties opgeleverd. Men trainde de perceptron 100.000 trainingsrondes ( η = 0.0001) voor elke testpersoon. Vervolgens zocht men naar een manier om de resulterende gebruikersmodellen te vergelijken. Men heeft hiervoor de relatieve waarden van de gewichten in de kostenfunctie vergeleken. Een zogenaamde wisselgraad (Eng. exchange ratio) werd gedefinieerd als de ratio van twee gewichten behorende bij twee verschillende attributen omdat deze aangeven hoeveel een gebruiker bereid is op te geven ten aanzien van de ene attribuut om de andere attribuut te verbeteren. Als bijvoorbeeld de wisselgraad tussen de gewichten voor reistijd en aantal afslagen gelijk is aan 30, dan is de persoon in kwestie bereid om 30 seconden langer te rijden om één Pagina 34 van 79



- 35 -

afstand wisselwaarde in meters

afslag te omzeilen maar niet langer. Figuur 5.4 laat de bevonden wisselgraden zien tussen reisafstand en drie andere attributen.

testpersoonnummer Figuur 5.4 uit [2]. Wisselgraden van drie attributen ten opzichte van afstand, berekend op basis van alle data van elk testpersoon. Hoge positieve waarden voor een attribuut geven weer dat een kortere afstand minder belangrijk is dan het verminderen van de betreffende attribuut, waarden in de buurt van nul geven weer dat een kortere afstand belangrijker is en hoge negatieve waarden geven weer dat langere afstand de voorkeur heeft. De resultaten geven aan dat er grote verschillen zijn in routevoorkeuren tussen mensen. Echter, in sommige gevallen is er sprake van een negatieve wisselgraad. Bijvoorbeeld, bij testpersoon 10 is de wisselgraad van afstand en aantal afslagen gelijk aan – 1027. Dit betekent dat gegeven twee routes A en B, als route A een afslag meer heeft dan route B het lagere kosten heeft indien het ook nog 1027 meters langer is dan route B. Dergelijke resultaten zijn intuïtief tegenstrijdig, bovendien kunnen er geen negatieve kosten worden gebruikt binnen de routeringalgoritmiek (in het geval van [2] de algoritme van Dijkstra). Men denkt dat de tegenstrijdige resultaten in de vorm van negatieve gewichten van kanten mogelijk veroorzaakt zijn doordat de routes gegenereerd als trainingsdata optimaal zijn gemaakt voor één enkele attribuut. Het feit dat bestuurders voorkeur kunnen hebben voor bijvoorbeeld kortere routes en andere factoren even (on)belangrijk vinden, wordt niet expliciet gepresenteerd in de trainingsdata. Wanneer dit als achtergrondinformatie zou worden meegenomen, zou dit de negatieve waarden elimineren. 5.5

Een case-gebaseerd routeplanningssysteem

Pagina 35 van 79



- 36 -

In [13]en [14] stelt men dat voor het bepalen van optimale/goede routes informatie nodig is welke ontbreekt in traditionele digitale kaarten. Men beschrijft hier ideeën over een eigen methode van routeplanning en dynamische update van informatie beschikbaar in een digitalekaart. Men laat zien hoe routeplanning gedaan kan worden door hergebruik van eerdere routeplanningsgevallen die samen een goede basis zouden vormen voor het genereren van een nieuwe routeplanning. Het idee/de gedachtengang is dat aangezien de taak van het vinden van een pad dynamisch en complex is, leren noodzakelijk is. Men gaat er hier vanuit dat dit het beste gedaan kan worden door voordeel te halen uit eerdere routeplanning en uitvoeringservaring. Men heeft gekozen voor het toepassen van case-based reasoning (CBR) methoden voor padplanning omdat ze het de planner mogelijk maken cases, dat zijn oplossingen voor eerdere vergelijkbare/gelijkende problemen, te hergebruiken om nieuwe problemen op te lossen. Aangezien het niet haalbaar is een statische evaluatiefunctie te ontwikkelen welke gebruikersvoorkeuren vangt/omvat, is een systeem dat in staat is automatisch te leren en zijn evaluatiefunctie aan te passen krachtiger. Men gelooft dat het bewaren van routes gereden en geëvalueerd door een bestuurder een goede manier is om het systeem aan te sturen richting voorkeursroutes. De basis voor de benadering in [14] is het gebruik van analogisch redeneren, als zijnde een instantie van case gebaseerd redeneren. 5.5.1

Een case library

Van een geplande route wordt allerlei relevante informatie vastgelegd waaronder een beschrijving van het planningsproces en de foutafhandelingen. Het geheel wordt opgeslagen als een zogenaamde case in een zogenaamde case library. Van een geplande route wordt een abstractie gemaakt in de vorm van een grafische representatie met rechte lijnstukken, case-segmenten genaamd. Deze abstractie wordt gebruikt voor het indexeren van de werkelijke case om deze laatste makkelijk en efficiënt te kunnen terugvinden. 5.5.2

Experiment met similarity metriek en replay mechanisme

Met dit experiment wil men/probeerde men te demonstreren dat hun methode van ophalen en hergebruik van meerdere cases, geschikte oplossingen produceert op een effectieve manier. De geproduceerde routes zouden beter overeenkomen met vertrouwde routes en niet overdreven bochtig of lang zijn. De twee andere algoritmen waarmee vergeleken is: A* en een ‘best-first’ heuristiek zijn niet in staat onderscheid te maken tussen verschillende situaties. Het gebruik van analogie met kwalitatief goede routes zou een systeem kunnen creëren dat zichzelf zal aanpassen aan veranderingen in zijn omgeving, aan bepaalde situaties en aan bepaalde gebruikers. 5.6

TURAS

Pagina 36 van 79



- 37 -

Het uitgangspunt in [15] is dat routeplanners routes moeten genereren die gepersonaliseerd zijn met betrekking tot individuen maar zonder sterke aannames te maken over het type voorkeursmodel dat een bepaald individu heeft. Individuele voorkeur zou moeilijk expliciet te modelleren zijn. Men heeft hier geëxperimenteerd met een webapplicatie (gemaakt in Java) met een onderliggende digitale kaart van Dublin. Het idee is dat een gebruikersprofiel/gebruikersvoorkeursmodel gemaakt kan worden bestaande uit routes die door de gebruikers zijn beoordeeld op kwaliteit. Een profiel zou dan bestaan uit routebeschrijvingen in de vorm van een lijst van opeenvolgende wegsegmenten vanuit een startlocatie tot aan een bestemming en een toegekende beoordeling. Het profiel zou de functie hebben van een lokale case-base van routeplanningservaringen van een bepaalde gebruiker en gebruikt worden door een case-based routeplanningsalgoritme om gepersonaliseerde routes te plannen. De constructie van profielen is hier wederom gedaan aan de hand van een simulatie in plaats van echte gebruikers. De nadruk van de reeks onderzoeken lag meer op het demonstreren van de efficiëntieverbetering die gehaald zou kunnen worden ten aanzien van de routeplanningsalgoritmiek bij toepassing van een case gebaseerde benadering als alternatief voor traditionele benaderingen gebaseerd op grafentheorie en kortste pad algoritmen zoals de algoritme van Dijkstra of A*. In [15] vindt men dat deze algoritmen (qua tijdscomplexiteit) duur zijn en verspillend zijn in hun zoekstrategieën. Vaak zouden deze algoritmen routesecties/wegsegmenten in beschouwing nemen die niet redelijkerwijs een onderdeel kunnen vormen van een realistische oplossing. Een theoretisch punt uit deze reeks onderzoeken dat wel interessant lijkt ten aanzien van personalisatie is de opstelling van de gebruikersspecifieke kostenfunctie voor routeplanning. De kosten voor een individueel wegsegment worden aan de hand van de volgende formule berekend: Kosten(segment) = lengte (segment) * gewicht (segment) Waarbij het gewicht van een segment omgekeerd evenredig wordt geacht te zijn aan de ‘wenselijkheid’ van het wegsegment. Wenselijkheid is daarbij gebaseerd op een complex en verborgen gebruikersvoorkeurmodel. Wegsegmenten met een groot gewicht hebben een lage wenselijkheid en daarmee hogere kosten dan wegsegmenten met een zelfde lengte maar een klein gewicht en dus hogere wenselijkheid. In [5] behandelt men ook het probleem van routeplanningsverzoeken die niet vallen binnen het routekennisdomein van de gebruiker in kwestie. Voor een dergelijke routeverzoek biedt een (eigen individuele) case gebaseerde routeplanningsalgoritme geen oplossing. Men heeft in [5] daarom het idee uitgewerkt van een zogenaamde samenwerkingsgebaseerde case-based routeplanningstechniek (eng. collaborative case-based reasoning) afgekort met C-CBR. Door het associëren van elk gebruiker met een individuele routeplanning-agent kan de ervaring van andere agents met relevante planningsexpertise gebruikt worden voor het plannen van een route binnen onbekend gebied voor de gebruiker waar het routeverzoek vandaan komt. Daarbij is het van Pagina 37 van 79



- 38 -

belang dat een agent Aj wiens ervaring wordt gebruikt vergelijkbare routeplanningsvoorkeuren heeft als de doelgebruiker/doelagent Ai . De kwaliteit van een agent Aj hangt af van de dekkingsgraad dat Aj heeft voor een routeplanningsprobleem p en de mate van gelijkenis tussen Ai en Aj. Om deze kwaliteit te meten, wordt een metriek gebruikt waarbij het relatieve gewicht van de gebruikersgelijkenis en de mate van dekking van het probleem aangepast kan worden. Men heeft in [5] op basis van experimenten bevonden dat een gewicht w = 0.75 de beste resultaten oplevert. De formule voor de metriek is als volgt gedefinieerd: Kwaliteit(Aj, Ai, p) = (1-w) * ProbDekking(Aj, p) + w * AgentGelijkenis(Aj, Ai) De mate van dekking van het probleem wordt bepaald door het meten van de overlap tussen de verzameling kruisingen in de case-base van Aj en die in het gebied van het doelprobleem p. Hoe groter de overlap des te groter de kans dat agent Aj cases bevat die het probleem p dekken. Het meten van gelijkenis tussen agents gebeurt door het meten van de gelijkenis tussen de onderliggende voorkeursmodellen. Dat laatste gebeurt door het zoeken naar overeenkomsten in hun case-bases. De oplossingen die deze agents hebben voor problemen die zij gemeenschappelijk hebben, worden vergeleken. De aanname hierbij is dat als deze agents dezelfde gedeelde/ gemeenschappelijke problemen op dezelfde wijze oplossen dan doen ze dat vanwege gelijkenissen in hun onderliggende voorkeursmodellen. 5.7

Een mobiel voorkeurgebaseerde systeem voor routeplanning

Men beschouwde in [7] en in de daaropvolgende onderzoek in [9] de karakteristieken gerelateerd aan verkeersinformatie als zijnde bijna allemaal van een kwantitatieve aard. Een gebruiker zou een kortere route bijvoorbeeld voorkeur geven boven een langere route en hoe korter de route hoe meer de gebruiker bereid is om ongunstige factoren te accepteren. Dit zou ook gelden voor files en wegwerkzaamheden. Men onderbouwt hiermee de keuze voor gebruik van gerangschikte voorkeuren met adequate score-functies f en een ranking functie F dat aangepast kan worden aan de eisen en wensen van de gebruiker. Hoe de score-functies f voor de afzonderlijke route-eigenschappen zijn gedefinieerd in [7] is beschreven in de volgende paragraaf (5.7.1). Voor het integreren van alle factoren (tot een ranking functie F) heeft men in [7] en [9] gebruikgemaakt van door gebruikers gedefinieerde gewichten die toegekend kunnen worden aan elke eigenschap. Echter, omdat het hier om individuele menselijke beoordelingen gaat, koos men in [9] in plaats van numerieke gewichten voor meer intuïtieve linguïstische variabelen om de combinerende ranking functie te specificeren. De gebruiker kreeg de mogelijkheid onderscheid te maken tussen vijf maten van belang (niet belangrijk, normaal, gemiddeld, belangrijk, zeer belangrijk) die vervolgens automatisch werden

Pagina 38 van 79



- 39 -

vertaald naar numerieke gewichten wi voor gebruik in de ranking functie F. In [7] en [9] wordt deze functie ongeveer als volgt gedefinieerd voor een gegeven route x. F(x) = ((w1 + 1) flengte(x) + w2.ffile (x) + w3.fwerkzaamheden (x) + w4.fweer(x))/(∑wi + 1) Omdat de lengte van een route van groot belang is, heeft men ervoor gekozen om het bijbehorende gewicht met een factor 1 te verhogen. Zodoende wordt een route a geprefereerd boven een route b indien F(a) > F(b). 5.7.1

Route eigenschappen vertalen naar numerieke scores

Een voorbeeldaanpak van hoe routes geclassificeerd kunnen worden en hoe elk route van een score kan worden voorzien staat beschreven in [7]. Hier volgt de aanpak in [7] ten aanzien van een aantal route-eigenschappen. De lengte van een route: alternatieve routes worden gerangschikt naar hun lengte, vervolgens worden genormaliseerde score waarden toegekend aan elke route. De kortste route krijgt de score 1.0 . De langste (alleen routes die maximaal anderhalf keer zo lang zijn als de kortste route worden in beschouwing genomen) route krijgt een score 0. Gebruikmakend van het verschil tussen de langste en de kortste route worden de score waarden genormaliseerd. Routes met dezelfde lengte krijgen op deze wijze dezelfde score. De volgende formule geeft weer hoe de score van een route x wordt berekend ten aanzien van de eigenschap/attribuut lengte. flengte(x) = (lengte(langste_route) – lengte(x))/(lengte(langste_route) – lengte(kortste_route)) Echter, ten aanzien van de eigenschappen files en wegwerkzaamheden komt er meer bij kijken. Men heeft gebruikgemaakt van informatie over het aantal files en wegwerkzaamheden en hun totale lengte aan de ene kant. Aan de andere kant maakte men onderscheid tussen twee typen files en wegwerkzaamheden. Te weten files met stilstaand verkeer en files met langzaam bewegend verkeer. Wegwerkzaamheden met gesloten rijbanen en wegwerkzaamheden zonder gesloten rijbanen. Files met stilstaand verkeer en wegwerkzaamheden met gesloten rijbanen zijn zware hindernissen, hun lengte wordt voor de berekening van de score daarom dubbel geteld. Deze waarden worden op hun beurt genormaliseerd naar scores tussen 0 en 1.0. In het geval van een complete wegblokkade wordt de score automatisch op 0 gezet. De formule voor scoreberekening ten aanzien van de eigenschap files heeft men als volgt gedefinieerd. Voor de eigenschap wegwerkzaamheden geldt een soortgelijke berekening. ffile(x) = q * (1 – (∑ (p * file_lengte(x)) – file_lengte(route_met_kortste_file))/ (file_lengte(route_met_langste_file) – file_lengte(route_met_kortste_file))) Met q = 0 als het gaat om een complete blokkade, anders is q = 1. En p = 2 voor het geval van stilstaand verkeer, anders is p = 1.

Pagina 39 van 79



- 40 -

Voor informatie over weersomstandigheden heeft men een samengestelde score gebruikt waarin informatie is verwerkt over gemiddelde temperaturen, regenval, wind en vochtigheid. De temperatuur in beschouwing nemend, is zowel een te lage als een te hoge temperatuur minder gewenst. Men heeft er daarom voor gekozen om een score van 1.0 toe te kennen aan alle temperaturen tussen 10 en 20°C en de score lineair omlaag te interpoleren naar een score van 0 bij een temperatuurdaling tot -5°C en bij temperatuurstijging to 40°C. Ten aanzien van regenval koos men voor een lineaire interpolatie vanaf een score 1.0 voor droog weer naar een score 0 voor regenval tot 1 l/m2. Voor wind interpoleerde men vanaf een windsnelheid van 0 km/uur met een bijbehorende score van 1.0 tot aan een windsnelheid van 75 km/uur (storm) met een score 0. Voor wat betreft de vochtigheidsgraad interpoleerde men vanaf een score 1.0 bij 0 % vochtigheid naar een score 0 bij een vochtigheidsgraad boven de 100 %. Alle data over de weersomstandigheden heeft men vervolgens proberen numeriek te integreren op een wijze dat veiligheidseisen voor verkeer in acht neemt. Men heeft vooral rekening gehouden met het gevaar van ijzel, hierbij spelen de temperatuur en de regenval een belangrijkere rol dan de wind en de vochtigheid. Voor de berekening van de totale score voor weersomstandigheden heeft men de volgende formule gebruikt (de afkorting gem. staat voor gemiddelde). fweer(x) = 1/6 (2 fgem_temperatuur(x) + 2 fgem_regenval(x) + fgem_wind(x) + fgem_vochtigheid(x)) Men heeft ook een aantal specifieke regels geïmplementeerd door de score op 0 te zetten voor het geval van ijzel, complete storm en mist met een zicht onder de vijftien meter. 5.8

Een dynamisch routebegeleidingssysteem

In [8] heeft men geëxperimenteerd met een benadering voor het modelleren van het routekeuzeproces van een bestuurder/gebruiker d.w.z. het modelleren van het gedrag van de bestuurder op het gebied van routeselectie. Het onderzoek had als focus een optimale routeselectie functie voor gebruik in een routenavigatiesysteem/dynamische routebegeleidingssysteem in de auto. Daarbij heeft men als uitgangspunt genomen dat elke haalbare route geassocieerd kan worden met een verzameling attributen die de eigenschappen van de route beschrijven. De benadering tracht de correlatie te vinden/achterhalen tussen de eigenschappen van een route en de keuze van de bestuurder. (De aanname die hierbij is gedaan is dat deze correlatie een niet-lineaire functie is van (de waarden) van de attributen.) De routeselectie methode tracht zich te richten op de voorkeur van de bestuurder en op basis daarvan een rangschikking te maken van de beschikbare haalbare route-alternatieven. Een routeselectie algoritme is ontwikkeld. De uiteindelijke beoogde functionaliteit van het algoritme is dat routekeuzes van de bestuurder de trainingsdata voor de algoritme gaan vormen en dat de algoritme daarmee adaptief wordt gemaakt aan het routeselectie gedrag van de bestuurder. Deze Pagina 40 van 79



- 41 -

functionaliteit heeft men geprobeerd te implementeren als een fuzzy expert systeem. De reactie van de bestuurder op informatie geleverd door het systeem wordt opgeslagen. Eerdere keuzes van de bestuurder, met name afwijkingen van de adviezen van het systeem, worden gebruikt voor training zodat de routeselectiefunctie adaptief wordt gemaakt aan de voorkeuren van de bestuurder.

Pagina 41 van 79



6

- 42 -

Functionele Requirements Analyse & Engineering

Dit hoofdstuk bevat de functionaliteit van een gepersonaliseerd selectief route-informatiesysteem dat houdt in dat we nu aandacht schenken aan personalisatie en aan selectie. Tevens streven we naar een robuust (tamelijk beperkt en tamelijk overzichtelijk) systeem dat gemakkelijk te hanteren is. De gevonden bijdragen van personalisatie en selectie worden dus ingeperkt tot een minimale set van requirements. In het slot van dit hoofdstuk worden de consequenties voor kaartdatabasemanagement gepresenteerd. De volgende termen worden gebruikt. 6.1

Definities

Term wegsegment attribuut Score

definitie De kleinste onafgebroken deel van een weg tussen twee kruisingen oftewel een stuk weg begrensd door twee kruisingen. Een eigenschap van een wegsegment of een gehele route. De lengte en de maximale toegestane snelheid zijn bekende voorbeelden hiervan.

Statische routering

Veelal een numerieke waarde die aangeeft hoe een route beoordeeld kan worden op basis van een attribuut. De rangschikking van de route-alternatieven op basis van hun scores en de voorkeuren van de gebruiker. Een functie die de reisweerstand berekent. De reisweerstand is een maat die de hoeveelheid weerstand aangeeft om van herkomst- naar bestemmingslocatie te reizen. De parameters zijn in de regel de attributen van een wegsegment. Traditioneel worden de attributen lengte en reistijd (statisch) gebruikt. Een modellering van de voorkeuren van de gebruiker,in dit geval, ten aanzien van routeselectie. Routering aan de hand van een kostenfunctie die gebruikmaakt van attributen die niet of nauwelijks van waarde veranderen bijvoorbeeld de lengte/afstand.

Dynamische routering Digitale kaart

Routering aan de hand van een kostenfunctie die gebruikmaakt van attributen die wel van waarde veranderen bijvoorbeeld de werkelijke reistijd. Een database waarin gegevens over het wegennetwerk zijn gecodeerd.

Ranking kostenfunctie

voorkeursmodel

6.1.1

Afkortingen

GPS

Global Positioning

Pagina 42 van 79

Het global positioning system is de commerciële naam voor een wereldwijd satellietplaatsbepalingssysteem dat vanaf 1967 werd Voorkeursroutes in Routenavigatie


- 43 -

System

ontwikkeld voor gebruik door de strijdkrachten van de Verenigde Staten. Met gps werd het voor het eerst mogelijk om vrijwel overal continu te kunnen navigeren. DRIP Dynamic Route Een dynamisch route-informatiepaneel is een electronisch paneel Information naast of boven de weg waarop informatie wordt gepresenteerd aan de Panel weggebruiker.

Over het algemeen geldt voor een traditioneel routenavigatiesysteem een functionele decompositie zoals afgebeeld in figuur 6.1. Deze functionele componenten zijn reeds besproken in hoofdstuk 3 ‘Routenavigatiesysteem’. Gebruikersinterface Plaatsbepaling & RouteRoute(Verkeers) informatieNavigatie Planning Begeleiding diensten Database Management Figuur 6.1 : De functionele componenten van een routenavigatiesysteem Voor het realiseren van het beoogde systeem zijn minimaal aanpassingen nodig aan de bestaande componenten: Gebruikersinterface, Routeplanning ,(Verkeers) informatiediensten en Database Management. Daarnaast bestaat de behoefte aan een nieuw toe te voegen component ‘Voorkeursmodellering’. De benodigde aanpassingen en toevoegingen worden in dit hoofdstuk per functionele component besproken.

6.2

De Interactie Functionaliteit, als gevolg van de eis tot personalisatie en selectie

Aangezien het beoogde systeem rekening moet gaan houden met de voorkeuren en de wensen van de individuele gebruiker lijkt het voor de hand liggend de interactie functionaliteit uit te breiden met mogelijkheden voor het opgeven van deze voorkeuren. Een aantal van de onderzoeken ([8],[9],[7]) bestudeerd tijdens deze requirements analyse gaan uit van deze uitbreiding. Het systeem dient de gebruiker in staat te stellen zijn algemene voorkeuren in te voeren.

1

[8],[9], [7]

Weer andere onderzoeken gaan ervan uit dat het systeem de voorkeuren van de gebruiker zelf dient af te leiden. Een afweging tussen de verschillende benaderingen en ideeën volgt aan het begin van hoofdstuk 7.

Pagina 43 van 79



- 44 -

De gebruiker kan specifieke tijdelijke wensen hebben die alleen van belang zijn voor de thans te maken rit. Het systeem dient de gebruiker in staat te stellen specifieke en/of tijdelijke voorkeuren geldend voor de op handen zijnde reis in te voeren.

2

[8], [7], [14]

Een auto of voertuig in het algemeen kan door meerdere gebruikers worden gebruikt. Zo, ook het beoogde systeem. Door de gebruiker de mogelijkheid te bieden aan te loggen op het systeem, kan het zijn profiel ophalen en zich configureren aan de gebruiker. Deze functionaliteit is overbodig in het geval de identiteit van de gebruiker bekend is of eenduidig af te leiden is. Het systeem dient de gebruiker in staat te stellen zichzelf te identificeren binnen het systeem.

3

[2],[8]

Na de berekening van een route, wordt de presentatie ervan door huidige systemen weergegeven op een afbeelding van de kaart. Als de gebruiker de route accepteert krijgt hij routebegeleiding middels (elektronische) spraak(synthese). Het beoogde systeem zal waar mogelijk meerdere routealternatieven (zie verderop bij routeplanning) berekenen en presenteren. Het systeem dient de gebruiker in staat te stellen om een getoonde route te selecteren, om de presentatie ervan op een kaartje te zien en (op een eventueel andere (sub)scherm) de beschrijving te lezen van de routebegeleiding in hoofdstappen.

4

[2]

Opdat de gebruiker het overzicht kan houden en een relatief snelle keuze kan maken is het wenselijk dat de gebruiker de keuze krijgt om het maximaal aantal getoonde route-alternatieven te beperken. Voor elk van de alternatieven zal naast de gebruikelijke kaartafbeelding, meer informatie getoond moeten worden om de gebruiker te ondersteunen in zijn keuze. Een minimale set aan informatie lijkt te zijn een opsomming van de eigenschappen van de routealternatieven. Het systeem dient de gebruiker in staat te stellen om het maximaal aantal getoonde alternatieven aan te geven.

5

[7]

Het systeem dient per route-alternatief kenmerkende eigenschappen te tonen.

6

[2]

Als de gebruiker een geadviseerde route heeft gekozen, kan hij op een gegeven moment besluiten om toch van de gekozen route af te wijken. Huidige systemen gaan er in een dergelijke situatie vanuit dat de gebruiker niet opzettelijk van de route afwijkt. Ze blijven dan ook proberen de gebruiker terug te krijgen op de oorspronkelijke route. In het geval het afwijken van de Pagina 44 van 79



- 45 -

geadviseerde route niet opzettelijk is, is dit gewenste functionaliteit. In het geval de gebruiker daadwerkelijk wil afwijken van de route zou dit aan het systeem gecommuniceerd moeten worden. Het vrijwillig afwijken van een geadviseerde route vooral wanneer geen sprake is van een hindernis (file, wegwerkzaamheden, open brug … etc.) is een signaal aan het systeem dat de geadviseerde route toch niet helemaal aansluit bij de voorkeuren van de gebruiker. De nieuwe route is meteen een goede voorbeeldroute dat het systeem kan gebruiken om zich aan te passen aan de gebruiker. Indien de gebruiker afwijkt van een geselecteerde route, dient het systeem de gebruiker in staat te stellen om zijn eventuele wens van de route af te wijken, te bevestigen.

7

[eigen analyse]

Ook bij het daadwerkelijk volgen van de geadviseerde route is expliciete feedback van de gebruiker ter evaluatie gewenst. Het systeem kan de feedback gebruiken om zijn personalisatie functionaliteit te verbeteren. Het systeem dient de gebruiker in staat te stellen feedback te geven ter beoordeling van een geadviseerde en daadwerkelijk gereden route. 6.3

8

[opdrachtgever]

Personalisatie: Voorkeursmodellering

Voorkeursmodellering speelt een cruciale rol in elk personalisatie taak. De functionele component “voorkeursmodellering” ontbreekt in huidige commerciële oplossingen voor routeplanning en routenavigatie. Voor het realiseren van personalisatiefunctionaliteit dient deze nieuwe functionele component toegevoegd te worden, goede voorkeursmodellering vormt immers een van de kritische succesfactoren. Het berekenen van een optimale route in de optiek van een bepaalde gebruiker komt overeen met het berekenen van een route waarbij getracht wordt de werkelijke persoonlijke interne kostenfunctie te minimaliseren. Voor het bepalen van een persoonlijke interne kostenfunctie is een voorkeursmodel nodig. Het systeem dient voor elke gebruiker een voorkeursmodel aan te maken en te onderhouden.

9

[2],[1],[5], [14]

Naast algemene lange termijn voorkeuren, een motorfietsbestuurder zal naar verwachting (altijd) meer last hebben van regenval dan een automobilist, zijn ook specifieke voorkeuren te onderscheiden die vaak te maken hebben met het type reis, een vakantiereis kan andere wensen met zich meebrengen dan een zakelijke reis naar de klant voor een belangrijke afspraak. Voor Pagina 45 van 79



- 46 -

een reis kunnen echter ook tijdelijke voorkeuren gelden, een automobilist kan altijd voorkeur hebben voor de snelste route naar werk en een wat ontspannen route prefereren naar huis. Het systeem dient, naast de algemene voorkeuren van een gebruiker, ook diens specifieke en tijdelijke voorkeuren te kunnen verwerken in route adviezen.

10

[2],[8],[7],[13]

Uit de analyse is naar voren gekomen dat er grofweg twee benaderingen bestaan voor het modelleren van gebruikersvoorkeur voor de voorliggende personalisatie taak. In dit verslag wordt hiernaar gerefereerd met de termen impliciete benadering en expliciete benadering. Bij de expliciete benadering probeert men te achterhalen welke factoren een rol spelen bij de routekeuze om ze vervolgens te gebruiken als dimensies voor het op te stellen voorkeursmodel. Aanhangers van de impliciete benadering daartegenover stellen dat de impliciete voorkeuren van een gebruiker niet herleid kunnen worden tot een verzameling kenmerken en proberen deze voorkeuren te modelleren als een ‘black box’ functie aan de hand van eerdere routeplanningservaringen van de gebruiker. Hiervoor is het nodig dat het systeem bekend is met de routes die de gebruiker eerder heeft gereden, dat is de routekennis van de gebruiker. De aanname hierbij is dat de routes gereden door de automobilist gewenst zijn volgens diens werkelijke interne kostenfunctie/impliciete nutsfunctie. En dat het daarom nuttig is om gebruik te maken van informatie over bekende routes bij het plannen van nieuwe routes. Het systeem dient in staat te zijn de routekennis van de gebruiker te achterhalen en vast te leggen.

11

[6],[1]

Zolang een routeplanningsverzoek van de gebruiker routes betreft binnen een voor hem vertrouwde gebied kan het systeem gebruikmaken van eerdere routeplanningservaringen van de gebruiker. De situatie is anders wanneer een routeplanningsverzoek betrekking heeft op een voor de gebruiker onbekend gebied. Binnen de expliciete benadering is dit geen issue omdat daar niet uitgegaan wordt van bekendheid met het gebied. Om dit probleem op te lossen is het idee om gebruikers met elkaar te associëren op basis van hun voorkeursmodel. Wanneer de voorkeursmodellen van twee gebruikers onderling voldoende overeenkomsten hebben, zou het systeem de ervaringen van de ene gebruiker kunnen gebruiken voor het adviseren van een route voor de andere gebruiker. Het systeem dient in staat te zijn overeenkomsten te vinden tussen de voorkeursmodellen van verschillende gebruikers. Het systeem dient in staat te zijn de routeplanningservaringen uit te wisselen van gebruikers met een vergelijkbaar voorkeursmodel.

Pagina 46 van 79

12

[5]

13

[5]



- 47 -

De verschillende aanpakken die onder de noemer van de expliciete benadering geschoven kunnen worden vereisen in meerdere of mindere mate enige vorm van interactie met de gebruiker voor het aanmaken van een initieel gebruikersprofiel. Bij de ene type aanpak wordt aan de gebruiker gevraagd om aan te geven hoe belangrijk hij bepaalde aspecten van een route vindt en hoe de mate van belang van de afzonderlijke aspecten in verhouding staan tot elkaar. De aanname hierbij is dat deze informatie verwerkt kan worden tot een gebruikersmodel dat de werkelijke interne kostenfunctie van een gebruiker weerspiegelt. En dat vervolgens door gebruik te maken van de op deze wijze verkregen persoonlijke kostenfunctie in de routeberekening routes kunnen worden berekend die voldoen aan de persoonlijke voorkeuren van de gebruiker. Het systeem dient de mate van belang van verschillende aspecten van een route voor een specifieke gebruiker te kunnen vastleggen en te kunnen gebruiken voor het afleiden van diens voorkeursmodel.

14

[8],[7]

Bij een andere type aanpak binnen de expliciete benadering is het idee dat de gebruiker als antwoord op zijn routeringverzoek een aantal route-alternatieven gepresenteerd krijgt en uit deze alternatieven een keuze maakt. Deze keuze van de gebruiker wordt geïnterpreteerd als een voorkeursuiting. De representatie van de gekozen route en die van de overige overgebleven route-alternatieven dienen als invoer voor een adaptatie algoritme dat vervolgens een voorkeursmodel produceert dat aansluit bij de voorkeuren van de gebruiker. Het systeem dient het voorkeursmodel van de gebruiker af te leiden uit zijn voorkeursuitingen ten aanzien van route-alternatieven.

15

[2]

Het kiezen van een route uit een aantal gepresenteerde route-alternatieven wordt beschouwd als een vorm van impliciete feedback. Ook wanneer het systeem al een initieel voorkeursmodel van de gebruiker heeft kunnen opstellen, wordt deze vorm van feedback gebruikt binnen de expliciete benadering om het model verder te verfijnen. Het systeem dient de routekeuze van de gebruiker te vergelijken met de aanbevolen route-alternatieven en op basis daarvan eventueel het voorkeursmodel aan te passen.

16

[2],[8]

Naast deze impliciete feedback is ook een vorm van expliciete feedback gewenst. Na het berijden van een bepaalde route moet de gebruiker een eindoordeel kunnen uitspreken over de gekozen route. Dit eindoordeel zou dan verwerkt moeten kunnen worden ten einde het voorkeursmodel indien nodig te verbeteren en te verfijnen. Het systeem dient de verkregen feedback (zie requirement nr. 8) te gebruiken ter Pagina 47 van 79

17

[opdrachtgever]



- 48 -

verbetering van het voorkeursmodel van de gebruiker. 6.4

Routeplanning

Huidige systemen zijn in staat een route te berekenen met de kortste afstand of met de kortste reistijd berekend aan de hand van de statisch (vermeld op vaste borden in tegenstelling to dynamisch vermeld op zogenaamde DRIPs of werkelijk ervaren door bestuurder) maximaal toegestane snelheid op een weg. Reistijd is echter slechts één van de factoren, weliswaar over het algemeen één van de belangrijkste naast reisafstand, van belang voor de routekeuze van een gebruiker. Er is behoefte aan routeplanningsalgoritmiek die routes produceert die meer overeenkomsten hebben met de persoonlijke routekeuze van een individuele gebruiker. De functionele component “Routeplanning” dient zodanig aangepast te worden dat de berekende routes conform de voorkeuren van de gebruiker zijn. Het systeem dient routeplanningsalgoritmiek te omvatten die in staat is gepersonaliseerde routes te berekenen.

18

[divers]

Zowel de impliciete als de expliciete benadering proberen op eigen wijze de werkelijke interne kostenfunctie van een gebruiker voor routeplanning en routekeuze te achterhalen. Het systeem dient de werkelijke interne kostenfunctie van een gebruiker voor routeplanning en routekeuze te achterhalen.

19

[6],[2],[1],[5],[14]

Het domein van routeplanning in het bijzonder en routeringalgoritmiek in het algemeen is een gebied waarover veel onderzoek is verricht en nog steeds veel onderzoek gaande is. Het resultaat is een diversiteit aan algoritmen die samenvattend gecategoriseerd kunnen worden naar statische routering en dynamische routering. Naar verhouding is veel minder onderzoek gedaan naar routeplanningalgoritmiek geschikt voor personalisatiedoeleinden. Veelal gaat het bij deze onderzoeken om het aanpassen van traditionele routeplanningsalgoritmiek. De focus hierbij ligt op het personaliseren van de kostenfunctie gebruikt door de algoritmiek. Dit geldt voor zowel de impliciete als de expliciete benadering. Hoewel de aanpak bij deze benaderingen verschillend is, is het idee hetzelfde. Traditionele routeplanningsalgoritmiek wordt gebruikt waarbij de traditionele kostenfunctie, voor het minimaliseren van reistijd of reisafstand, wordt vervangen door een gepersonaliseerde kostenfunctie die opgesteld wordt aan de hand van het voorkeursmodel van de individuele gebruiker. Binnen de expliciete benadering doet men dit door eigenschappen van routes/route-onderdelen te beschouwen als criteria voor het maken van keuzes door de gebruiker en de kostenfunctie als zijnde het relatieve belang dat de gebruiker toekent aan de afzonderlijke eigenschappen. Binnen de impliciete benadering zijn de criteria voor het maken van keuzes niet Pagina 48 van 79



- 49 -

bekend. Een impliciete kostenfunctie wordt afgeleid uit de routekeuzes die door de gebruiker eerder gemaakt zijn. Het systeem dient een gepersonaliseerde kostenfunctie te gebruiken voor de routeplanningsfunctionaliteit. De gepersonaliseerde kostenfunctie dient te worden bepaald aan de hand van het voorkeursmodel van de gebruiker. Het systeem kan traditionele routeringsalgoritmiek gebruiken in combinatie met een gepersonaliseerde kostenfunctie om routes te genereren die voldoen aan de voorkeuren van de gebruiker.

20

[divers]

21

[divers]

22

[divers]

Binnen de expliciete benadering kunnen twee aanpakken onderscheiden worden die significant van elkaar verschillen in de wijze waarop de routeberekening plaatsvindt. Bij de ene aanpak wordt de persoonlijke afweging van de verschillende attributen al op wegsegmentniveau gemaakt en de route waarvan de wegsegmenten cumulatief goed scoren, krijgt de hoogste ranking en wordt als de beste keuze aan de gebruiker geadviseerd. Terwijl bij de andere aanpak het uitgangspunt een vooraf berekende set haalbare routes is, welke onderling afgewogen worden op elk van de afzonderlijke eigenschappen. Het rangschikken van de alternatieven wordt vervolgens aan de hand van het voorkeursmodel van de gebruiker gedaan. Het systeem dient een aantal (initiële) route-alternatieven te bepalen/berekenen. Het systeem dient elk route-alternatief te voorzien van een score op basis van de eigenschappen; aan de hand van deze score en het voorkeursmodel van de gebruiker dient het systeem de verschillende route-alternatieven te rangschikken.

23

[8],[7],[9]

24

[8],[7],[9]

Het systeem dient in staat te zijn om een nauwkeurige schatting te geven voor de reistijd onafhankelijk van de starttijd van de reis. Dat wil o.a. zeggen dat ook zeer geavanceerde realtime/intelligente routeplanners (die alle real-time reisinformatie tot hun beschikking zouden hebben) in staat moeten zijn om een route te plannen met een acceptabele reistijd voor een reis waarvan de starttijd later ingaat dan het moment van het routeverzoek en waarvan de exacte verkeerscondities nog niet bekend zijn. Het systeem dient in staat te zijn om een schatting te geven voor de reistijd onafhankelijk van de starttijd van de reis en ook wanneer de exacte verkeerscondities nog niet bekend zijn. 6.6

25

Kaart Database Management

In dit paragraaf worden de consequenties van het toevoegen van de hierboven beschreven functionaliteiten voor de kaartdatabase besproken.

Pagina 49 van 79


[1]


- 50 -

Huidige systemen beschikken over een representatie van het wegennetwerk in de vorm van een digitale kaartdatabase. Eén grote tekortkoming van deze standaardrepresentaties is het ontbreken van informatie die relevant kan zijn voor het genereren van goede/optimale realistische routes. Voor het vaststellen van de optimale route zijn twee soorten gegevens nodig: statische en dynamische informatie. Statische informatie bestaat uit gegevens die niet, of slechts op lange termijn, veranderen zoals gegevens over het wegennetwerk. Dynamische informatie bestaat uit gegevens die snel veranderen en die binnen het tijdsbestek van de (geplande) verplaatsing invloed kunnen uitoefenen op het gegeven advies, zoals bijvoorbeeld filevormingen en wegafsluitingen. Met het introduceren van personalisatiefunctionaliteit en het definiëren van het begrip optimaal als optimaal voor een specifieke gebruiker zullen ook andere soorten attributen dan de bovengenoemde een rol spelen. Het systeem dient te beschikken over een representatie van het wegennetwerk die verrijkt is met de relevante informatie voor personalisatiedoeleinden.

26

[2],[14],[16]

Een van deze attributen, in dit verslag personalisatieattributen genoemd, is de bekendheid van de gebruiker met een weg(segment). Dit attribuut kan afgeleid worden uit de routekennis van een gebruiker wanneer deze routekennis vastgelegd wordt zoals besproken onder voorkeursmodellering. Het systeem dient in staat te zijn om informatie over bekendheid van de gebruiker met een weg(segment) te verwerken in zijn interne representatie van het wegennetwerk.

27

[6],[5],[14]

Op bepaalde terugkerende situaties die van invloed kunnen zijn op de routekeuze kan geanticipeerd worden mits de benodigde informatie hiervoor beschikbaar is. Het gaat hier om attributen die een rol spelen bij het voorspellen van een toekomstige verkeerssituatie. Tijdafhankelijke gemiddelde snelheden c.q. reistijden zijn hier een goed voorbeeld van. Zie ook requirement 25. Historische data over doorstroomsnelheden kan gebruikt worden om de verwachte reistijd uit te rekenen voor elk tijdstip van een dag en elke dag van de week. Het systeem dient de representatie van het wegennetwerk uit te breiden met tijdsafhankelijke gemiddelde snelheden/reistijden.

28

Ongeacht de gekozen representatie om het wegennetwerk te beschrijven, kan deze niet statisch zijn. Er zullen steeds weer wijzigingen zijn die gemaakt moeten worden. De wijzigingen zullen feiten in de beschrijving van het wegennetwerk corrigeren, toevoegen of verwijderen. Ook veranderingen als gevolg van het openstellen van nieuwe wegen en het vervallen van bestaande mogelijkheden moeten bijgehouden worden. Pagina 50 van 79


[1]


- 51 -

De representatie en/of beschrijving van de kaart dient gewijzigd te kunnen worden om feiten hierin te kunnen corrigeren, toevoegen of verwijderen. 6.7

29

[13]

(Verkeers) informatiediensten & Mobiele communicatie

Nadat vastgelegd is welke attributen bijgehouden gaan worden voor het bijhouden van een correcte en actuele interne representatie van het wegennetwerk, dienen de waarden voor deze attributen met passende regelmaat te worden geactualiseerd. De waarden van de dynamische attributen dienen buiten het voertuig te worden bepaald en dienen dus naar het voertuig te worden gecommuniceerd. Eenmaal onderweg kan als gevolg van een incident de situatie zodanig veranderen dat de gekozen/geadviseerde route niet meer de optimale is. De actuele verkeersgegevens die een omleiding wenselijk maken dienen zo snel mogelijk vastgelegd te worden en direct verwerkt te worden in de route-aanwijzingen.

Pagina 51 van 79

30


[7],[17]


7

- 52 -

Globaal Ontwerp

De lijst van eisen in het vorige hoofdstuk genoemd is uitputtend maar overladen. Een eerste versie van het gepersonaliseerd selectief route-informatiesysteem mag niet overladen zijn. Het gepersonaliseerd selectief route-informatiesysteem moet naar verhouding goedkoop te bouwen zijn, goedkoop te onderhouden zijn en gemakkelijk te gebruiken zijn. Bij gebleken succes kan later wel overwogen worden functionaliteit toe te voegen, bijvoorbeeld bij een tweede versie. Eerst gaan we de eisen uit het vorige hoofdstuk bezien op de volgende randvoorwaarden: niet complex te bouwen, niet duur in onderhoud, niet strijdig met privacy. De prioriteiten duiden we aan gebruikmakend van de MoSCoW techniek. De acroniem MoSCoW [48] staat voor het volgende: M – Must Have; S – Should Have; C – Could Have; W – Won’t Have (soms ook Would Have). Uitgaande hiervan stellen we vervolgens een globaal ontwerp op van een haalbare kosteneffectieve oplossing. Het doel van het beoogde systeem is het ondersteunen van de gebruiker in het maken van een weloverwogen keuze/selectie daar waar er sprake is van een overvloed aan informatie aangaande meerdere factoren die de wenselijkheid van een route–alternatief bepalen; naast de traditioneel in acht genomen factoren reisafstand en/of reistijd zullen ook andere factoren meespelen zoals dynamische (maximum)snelheid, (dynamisch) beprijzen, doorstroming, kans op filevorming, weersomstandigheden, groene golven, gemak van berijden, (bijdrage aan) milieu belasting … enzovoort. Deze overvloed aan informatie kan onmogelijk binnen de gewenste tijdmarges door een mens verwerkt worden ten einde een weloverwogen routekeuze te maken. De ondersteuning van het beoogde systeem is dan ook van cruciaal belang voor de individuele bestuurder om een goede selectie te maken op basis van de te gelegener tijd enorme hoeveelheid beschikbare informatie. 7.1

Reductie van de functionele eisen

Omdat een exemplaar van het beoogde systeem door meerdere bestuurders gebruikt kan worden en omdat het systeem min of meer persoonlijke informatie over de gebruiker vastlegt en verwerkt, moet de eis van identificatie gehandhaafd blijven. Het systeem dient de gebruiker in staat te stellen zichzelf te identificeren binnen het systeem.

3

M

De gebruiker zijn voorkeuren laten communiceren aan het systeem is uit het oogpunt van de ontwerper/ontwikkelaar van het systeem een snelle en makkelijke manier om deze voorkeuren te kunnen vastleggen en te kunnen verwerken tot een voorkeursmodel. Voor de meeste gebruikers is het echter lastig en onpraktisch om eerst door een uitgebreide invoerritueel heen te moeten voordat zij een gepersonaliseerde route-advies kunnen krijgen. Er zijn gebruikers die het invoeren Pagina 52 van 79



- 53 -

van hun voorkeuren op zich als vermakelijk ervaren. Dit is echter niet het geval voor alle gebruikers. Het voorstel is dan ook om de hoeveelheid benodigde handmatige invoer te beperken tot een minimum. Dus, het systeem dient in staat te zijn de gebruikersvoorkeuren af te leiden uit beperkte interactie met de bestuurder. Het systeem dient de uitgebreide invoermogelijkheden voor voorkeursuitingen wel te ondersteunen om daarmee tegemoet te komen aan gebruikers die deze extra functionaliteiten waarderen. Een eerste versie van het systeem mag echter niet afhankelijk zijn van deze uitgebreide invoer. Dat wil zeggen, het systeem maakt gebruik van de extra interactie met de gebruiker indien deze door de gebruiker zelf geïnitieerd wordt omdat dit het opstellen van het voorkeursmodel versnelt. Maar, ook indien de gebruiker de uitgebreide invoeropties niet wenst te gebruiken, dient het systeem in staat te zijn een voorkeursmodel van de gebruiker op te stellen. Echter, wanneer het systeem beschikt over de extra invoer, dient het in staat te zijn om meteen bij de eerste routeplanningsverzoeken de gebruiker van gepersonaliseerde route-adviezen te voorzien en de route-alternatieven overeenkomstig het voorkeursmodel van de gebruiker te rangschikken en te presenteren. Een soortgelijke redenering geldt ten aanzien van de feedback functionaliteit, het systeem biedt het aan. De gebruiker is vrij om er wel of niet gebruik van te maken. Doet de gebruiker dat wel dan dient het systeem de verkregen feedback ook te verwerken ten einde het voorkeursmodel te verfijnen. De prioriteiten met betrekking tot de eisen voor het invoeren van voorkeuren, het modelleren ervan, het geven van feedback en het verwerken ervan, zijn als volgt: Het systeem dient de gebruiker in staat te stellen zijn algemene voorkeuren in te voeren.

1

M

Het systeem dient de gebruiker in staat te stellen specifieke en/of tijdelijke voorkeuren geldend voor de op handen zijnde reis in te voeren. Het systeem dient voor elke gebruiker een voorkeursmodel aan te maken en te onderhouden.

2

M

9

M

Het systeem dient, naast de algemene voorkeuren van een gebruiker, ook diens specifieke en tijdelijke voorkeuren te kunnen verwerken in route-adviezen. Het systeem dient de mate van belang van verschillende aspecten van een route voor een specifieke gebruiker te kunnen vastleggen en te kunnen gebruiken voor het afleiden van diens voorkeursmodel. Het systeem dient het voorkeursmodel van de gebruiker af te leiden uit zijn voorkeursuitingen ten aanzien van route-alternatieven.

10

M

14

M

15

M

Het systeem dient de routekeuze van de gebruiker te vergelijken met de aanbevolen route-alternatieven en op basis daarvan eventueel het voorkeursmodel aan te passen. Het systeem dient de gebruiker in staat te stellen feedback te geven ter beoordeling van een geadviseerde en daadwerkelijk gereden route. Het systeem dient de verkregen feedback (zie requirement nr. 8) te gebruiken ter

16

M

8

M

17

M

Pagina 53 van 79



- 54 -

verbetering van het voorkeursmodel van de gebruiker.

Voor een eerste versie van het beoogde systeem zijn de requirements aangaande routeplanning verreweg de meest ingrijpende. Het risico op een achterblijvende acceptatie door de gebruikers hangt nauw samen met het succes van de gekozen routeplanningsalgoritmiek. Eerst dient dan ook nagegaan te worden hoe de gebruiker überhaupt reageert op het ontvangen van alternatieven en een lichte vorm van personalisatie. De ervaringen hiermee kunnen dan meegenomen worden in de ontwikkeling van een tweede versie en eventuele vervolg versies. Dus, het advies is: kies voor opbouwende stapsgewijze invoer van steeds meer functionaliteit. De prioriteiten ten aanzien van routeplanningseisen is als volgt: Het systeem dient routeplanningsalgoritmiek te omvatten die in staat is gepersonaliseerde routes te berekenen. Het systeem dient de werkelijke interne kostenfunctie van een gebruiker voor routeplanning en routekeuze te achterhalen. Het systeem dient een gepersonaliseerde kostenfunctie te gebruiken voor de routeplanningsfunctionaliteit. De gepersonaliseerde kostenfunctie dient te worden bepaald aan de hand van het voorkeursmodel van de gebruiker. Het systeem kan traditionele routeringsalgoritmiek gebruiken in combinatie met een gepersonaliseerde kostenfunctie om routes te genereren die voldoen aan de voorkeuren van de gebruiker.

18

W

19

W

20

W

21

W

22

W

Dus voor een eerste versie wordt volstaan met het presenteren van de haalbare routealternatieven en het rangschikken hiervan op basis van de voorkeuren van de gebruiker. De snelste route op basis van realtime informatie en historische informatie dient ten allen tijden één van de gepresenteerde alternatieven te zijn. De snelste route, vergezeld met een opsomming van de overige eigenschappen, kan gezien worden als een redelijke referentie om de kwaliteit (voor efficiëntie doeleinden) van de overige route-alternatieven te beoordelen. Het systeem dient de gebruiker in staat te stellen om het maximaal aantal gewenste alternatieven aan te geven. Het systeem dient een aantal (initiële) route-alternatieven te bepalen/berekenen. Het systeem dient per route-alternatief kenmerkende eigenschappen te tonen. Het systeem dient in staat te zijn om een schatting te geven voor de reistijd onafhankelijk van de starttijd van de reis en ook wanneer de exacte verkeerscondities nog niet bekend zijn. Het systeem dient de gebruiker in staat te stellen om een getoonde route te selecteren, om de presentatie ervan op een kaartje te zien en (op een eventueel ander (sub)scherm) de beschrijving te lezen van de routebegeleiding in hoofdstappen.

Pagina 54 van 79

5

S

23

M

6

M

25

M

4

M



- 55 -

Ingrijpende wijzigingen op de routeplanningsalgoritmiek vergeleken met bestaande vertrouwde algoritmiek kunnen het best eerst op een gratis bèta versie uitgeprobeerd worden. In een gratis bèta versie accepteert de gebruiker eventuele fouten en onvolkomenheden makkelijker. Hierin kunnen de eisen aangemerkt met W’s veilig worden geïmplementeerd. Een gratis bèta versie kan naast de eerste officiële versie van het systeem meegeleverd worden als supplement voor gebruik op een systeem thuis bijvoorbeeld of op een website toegankelijk na registratie als gebruiker van de eerste versie van het beoogde systeem. Routes kunnen dan, in ieder geval door gebruikers met een early adopters mentaliteit, naar hartenlust interactief samengesteld worden waarna ze naar het systeem voor in de auto gedownload kunnen worden.

Een moment waarop expliciete invoer van de gebruiker noodzakelijk is, is wanneer de bestuurder opzettelijk wenst af te wijken van een in eerste instantie geselecteerde route. Het kunnen afgeven van een dergelijk signaal is dusdanig belangrijk voor de tevredenheid van de gebruiker met het systeem en de gebruiksvriendelijkheid ervan dat besloten is om de betreffende eis mee te nemen. Indien de gebruiker afwijkt van een geselecteerde route, dient het systeem de gebruiker in staat te stellen om zijn eventuele wens van de route af te wijken, te bevestigen.

7

M

Het vastleggen van de routes die de bestuurder rijdt is een mogelijkheid om data te verzamelen voor voorkeursmodellering zonder tussenkomst van de gebruiker. De data is goed te gebruiken en tevens makkelijk, goedkoop en op een gebruikersvriendelijke manier te verkrijgen. Deze functionaliteit kan dan ook zonder meer geïmplementeerd worden in een eerste versie van het beoogde systeem. Het systeem dient in staat te zijn de routekennis van de gebruiker te achterhalen en vast te leggen.

11

M

Het delen van informatie over voorkeursmodellen van verschillende gebruikers en het uitwisselen van routeplanningservaringen door het systeem kan worden gezien als inbreuk op de privacy van de gebruikers. Tevens is de implementatie van het idee tamelijk complex om al in een eerste versie gerealiseerd te krijgen. De requirements 12 en 13 zullen dan ook pas in aanmerking komen in vervolgversies van het systeem nadat gebruikers voldoende acceptatie en vertrouwen hebben gekregen in de eerste versies. Tevens moet duidelijk zijn geworden of gebruikers zullen kiezen voor meer efficiëntie ten koste van privacy. Het systeem dient in staat te zijn overeenkomsten te vinden tussen de voorkeursmodellen van verschillende gebruikers. Het systeem dient in staat te zijn de routeplanningservaringen uit te wisselen van Pagina 55 van 79

12

W

13

W



- 56 -

gebruikers met een vergelijkbaar voorkeursmodel. 7.2

De Gebruikersinterface

Bij het opstarten van het systeem dient de gebruiker in staat te worden gesteld zichzelf te identificeren binnen het systeem. Voor het gemak toont het systeem de gebruikersnaam van de laatste en of meest frequente gebruiker zodat alleen het wachtwoord ingevoerd hoeft te worden door de frequente gebruiker. Nadat de gebruiker zijn routeplanningsverzoek heeft ingevoerd, dient het systeem een lijst met de berekende route-alternatieven te tonen. Tevens dient een opsomming van de attributen van de route-alternatieven te worden getoond. Het systeem dient de gebruiker in staat te stellen om de getoonde presentatie van een route-alternatief te selecteren en om de weergave ervan op een kaartje te kunnen zien. Het systeem dient de gebruiker in staat te stellen om interactief een gepresenteerde routealternatief, indien gewenst, te wijzigen door de presentatie ervan op het kaartje op gewenste punten te verslepen. De op deze wijze nieuw gecreëerde route dient aan de lijst te worden toegevoegd. Ook een opsomming van de eigenschappen voor de nieuw gecreëerde route dient te worden getoond. De gebruiker dient vervolgens in staat te worden gesteld om de route van zijn voorkeur te selecteren om daarover begeleiding te ontvangen. Indien de gebruiker gedurende zijn rit afwijkt van de geselecteerde route, dient de gebruikersinterface de gebruiker in staat te stellen om zijn eventuele wens van de route af te wijken, te bevestigen. Het systeem dient de daadwerkelijk gereden route (in elk geval) vast te leggen voor eventuele actualisering van het voorkeursmodel (zie paragraaf 7.3). Aan het einde van de rit dient de gebruikersinterface de gebruiker in staat te stellen feedback te geven ter beoordeling van een geadviseerde en daadwerkelijk gereden route. Wederom ten einde het voorkeursmodel te kunnen onderhouden. Voor het gemak van de gebruiker dient de feedback op een simpele en snelle manier gegeven te kunnen worden. Een mogelijkheid is om de gebruiker een keuze te laten maken uit een beperkt aantal numerieke scores. De gebruiker dient in staat te worden gesteld het geven van feedback over te slaan, indien gewenst. Als de gebruiker wel feedback geeft en de feedback is positief, dan dient hij de keuze te krijgen om de zojuist beoordeelde route te categoriseren. Deze categorisatie gebruikt het systeem voor het aanmaken van profielen. Voor het eerste gebruik dient de gebruiker, indien gewenst, de mogelijkheid te krijgen om zijn algemene voorkeuren ten aanzien van routeselectie aan te geven. Daarnaast dient de gebruiker de mogelijkheid te krijgen één of meerdere profielen aan te maken welke het systeem kan gebruiken om gepersonaliseerde rankings te maken van de haalbare route-alternatieven. Voorbeelden van Pagina 56 van 79



- 57 -

mogelijke profielen zijn: een profiel voor het genereren van routes binnen de context van woonwerk verkeer, een profiel voor het genereren van routes voor recreatiedoeleinden en een profiel voor het genereren van routes voor ritten met een of meer speciale doelen zoals bijvoorbeeld winkelen of boodschappen doen, enzovoort. Tevens dient de gebruiker, indien gewenst, de mogelijkheid te krijgen eventuele tijdelijke wijzigingen, op de vastgelegde voorkeuren in een profiel, aan te geven voor een te plannen rit. Deze wijzigingen gelden dan alleen voor die ene rit. 7.3

Het voorkeursmodel & Routeselectie

Om de gebruiker te kunnen helpen in het routeselectieproces op basis van eigen voorkeuren dient het systeem een voorkeursmodel van de gebruiker te kunnen aanmaken en onderhouden. Het systeem dient het voorkeursmodel aan te maken en te onderhouden op basis van de informatie die het systeem afleidt uit de interactie met de gebruiker. Het systeem dient in staat te zijn om alleen al op basis van de routeselecties gemaakt door de gebruiker zijn voorkeursmodel af te leiden. Immers, het systeem biedt standaard meerdere opties aan, de gebruiker moet derhalve een keuze maken. De gemaakte keuze is voor het systeem een uiting van voorkeur. Deze uiting van voorkeur gebruikt het systeem voor het onderhouden van het voorkeursmodel. Elke keer dat de gebruiker een selectie maakt uit de geboden alternatieven, controleert het systeem of de keuze overeenkomt met de verwachting van het systeem. Het systeem verwacht dat de gebruiker de route met de hoogste ranking kiest. De ranking is immers gemaakt op basis van het voorkeursmodel van de gebruiker. Kiest de gebruiker een route die lager staat in de ranking, dan weerspiegelt het vastgelegde voorkeursmodel niet correct de voorkeuren van de gebruiker. In dit laatste geval past het systeem het voorkeursmodel aan en slaat het vervolgens op in het profiel van de gebruiker. Het bijstellen van het voorkeursmodel blijft doorgaan de volgende keren van gebruik totdat het systeem erin slaagt om de juiste ranking te maken, dat is een ranking die overeenkomt met de wensen van de gebruiker. Als de gebruiker bereid is tot meer invoer en de mogelijkheden die het systeem daartoe biedt ook daadwerkelijk benut, dan zal het systeem mogelijkheden hebben om het voorkeursmodel verder te verfijnen. Alle eventuele handmatige invoer van de gebruiker met betrekking tot zijn voorkeuren, te weten: algemene initiële voorkeuren; profielen; specifieke korte termijn voorkeuren; enzovoort, dient het systeem vast te leggen en te gebruiken voor het aanmaken en het onderhouden van het voorkeursmodel. Informatie over het voorkeursmodel dient alleen toegankelijk te zijn voor de betreffende gebruiker na identificatie. Zoals reeds vermeld, zijn deze uitgebreide interactiemogelijkheden bij de eerste versie van het systeem niet vereist. De gebruiker zal de kans moeten krijgen om in fases aan steeds meer personalisatiefunctionaliteit te wennen en met steeds meer mogelijkheden van het systeem te leren omgaan.

Pagina 57 van 79



- 58 -

Daarnaast dient er functionaliteit toegevoegd te worden voor het verwerken van de feedback van de gebruiker. Zowel zijn impliciete feedback: het negeren van de adviezen, als zijn expliciete feedback: het selecteren van een route die lager staat in de rangorde van de geadviseerde routes alsook de andere vorm van expliciete feedback welke achteraf na het berijden van een route kan worden gegeven maar in de eerste versie van het systeem niet vereist wordt. Het negeren van de adviezen heeft geen directe gevolgen voor het voorkeursmodel. Het systeem gebruikt in dit laatste geval de daadwerkelijk gereden route als trainingsdata. Immers, de routekennis van de gebruiker is van groot belang voor voorkeursmodellering. Door het vastleggen en bijhouden van deze routekennis is het systeem in staat de voorkeursmodellering te verfijnen. Over het algemeen kan gesteld worden dat een bij de gebruiker bekende route voorkeur geniet boven een onbekende route. In ieder geval dient bekendheid met de route als één van de eigenschappen van route-alternatieven meegenomen te worden ter beoordeling. 7.4

De Routeplanner

De routeplanner dient per gegeven vertrek- en bestemmingslocatie meerdere route-alternatieven te genereren. Immers, om zijn voorkeur te kunnen uiten dient de gebruiker te kunnen kiezen. Omdat bestuurders korte routes prefereren ongeacht de overige eigenschappen van een route, dienen de route-alternatieven te voldoen aan de randvoorwaarde van een acceptabele maximale lengte relatief aan de kortste route. Het berekenen van meerdere route-alternatieven kan, afhankelijk van de gebruikte algoritmiek, een tijdscomplexiteit-issue met zich meebrengen. Een oplossing voor dit probleem is het voorberekenen van routes/route-onderdelen voor de hoogniveau netwerken (zie paragraaf 3.4) en het efficiënt opslaan van de resultaten. Een keuze hierin kan zijn om alleen routes/routeonderdelen tussen steden op te slaan. Het routeplanningsproces, kan aanzienlijk versneld worden door gebruik te maken van zulke voorberekende route-onderdelen. Reden hiervoor is dat het aantal knopen en takken (in de graafpresentatie van het wegennetwerk) die voor de berekening geëvalueerd moeten worden sterk afneemt. Op het moment dat de uiteindelijke (complete) routealternatieven berekend worden, valideert de routeplanner de bruikbaarheid van de routeonderdelen. De routeplanner doet dit op basis van verkeersinformatie (zie paragraaf 7.5). Redenen waarom een route-onderdeel tijdelijk onbruikbaar kan zijn, zijn: afsluiting wegens werkzaamheden of een evenement, ernstige verkeershinder door files als gevolg van een ongeluk of (extreme) weersomstandigheden, enzovoort. De routeplanner berekent in dergelijke gevallen een alternatief onderdeel gebruikmakend van de (binnen commerciële systemen) gebruikelijke A* algoritme (zie paragraaf 3.4). Een beschrijving/opsomming van de eigenschappen van de afzonderlijke route-alternatieven dient gegeven te worden (zie voor een voorbeeld figuur B5.2 in bijlage 5). Informatie over de te beschrijven criteria dient echter wel beschikbaar te komen voor de routeplanner. De Pagina 58 van 79



- 59 -

databasemanagementlaag/digitale kaart (zie paragraaf 7.6) dient deze informatie beschikbaar te stellen voor de routeplanner. Vervolgens dient het systeem een rangschikking van de route-alternatieven op basis van de voorkeuren van de gebruiker te gegeven. Indien de gebruiker het route-alternatief met de hoogste ranking kiest, dan is het systeem er in geslaagd om de ranking te maken op basis van een correct gebruikersvoorkeursmodel. Kiest de gebruiker een route met een lagere ranking dan dient het voorkeursmodel aangepast te worden. 7.5

Verkeersinformatiediensten en Mobiele Communicatie

Het beoogde systeem dient in staat te zijn tot draadloze communicatie. Communicatie stelt het systeem in staat om optimaal gebruik te maken van de verkeersinformatiediensten die tegenwoordig beschikbaar zijn. Op het moment zijn de prijzen van realtime verkeersinformatie in Nederland nog relatief hoog. Een belangrijke reden hiervoor is de monopolie positie van menig dienstenaanbieder die tevens fabrikant en leverancier is van routenavigatiesystemen inclusief digitale kaarten. In een vrije markt is deze positie niet lang houdbaar te meer omdat de Nederlandse overheid nu geavanceerde verkeersinformatie aanbiedt door het oprichten van de Nationale Databank Wegverkeergegevens (NDW) zie tabel 7.1 voor een opsomming van de geboden informatie, de NDW levert echter niet direct aan eindgebruikers maar doet dit via dienstenaanbieders. Concurrentie tussen meerdere dienstenaanbieders zal de prijzen doen dalen. Verder zullen afspraken gemaakt moeten worden om de ontvangende routenavigatie-apparaten compatibel te maken voor verkeersinformatie van verschillend dienstenaanbieders. Type Actuele verkeersgegevens

Attribuut/eigenschap verkeersintensiteit

gerealiseerde reistijd

geschatte reistijd puntsnelheden Statusgegevens

Pagina 59 van 79

voertuigcategorieën wegwerkzaamheden filemeldingen en meldingen van ongevallen en incidenten status (open of dicht) van

Beschrijving/Opmerkingen Het aantal voertuigen dat gedurende een bepaalde periode een bepaald punt passeert, gerekend in één rijrichting. Het rekenkundig gemiddelde van de tijd die alle voertuigen, die gedurende één minuut gearriveerd zijn op het eindpunt van een reistijdvak, nodig hebben gehad om vanaf het beginpunt van dat reistijdvak het eindpunt van dat reistijdvak te bereiken, gerekend in één rijrichting. Benadering van de reistijd die alle voertuigen , die gedurende 1 minuut het beginpunt van een reistijdvak passeren, nodig gaan hebben om vanaf het beginpunt van dat reistijdvak het eindpunt van dat reistijdvak te bereiken, gerekend in één rijrichting. De benadering van de reistijd wordt bepaald met een schattingsmethode. De gemiddelde snelheid van voertuigen die in een tijdseenheid een punt passeren, gerekend in één rijrichting. Dat is de classificatie van voertuigen op basis van voertuiglengte. _ _

_



- 60 -

bruggen status (open of dicht) van spitsstroken, plusstroken en rijstroken Historische gegevens

regelscenario’s

_

oftewel van tevoren vastgestelde maatregelen voor het regelen van het verkeer bij te verwachten drukte _

informatie over reistijden _ informatie over puntsnelheden _ informatie over intensiteiten Tabel 7.1 Een opsomming van de gegevens bijgehouden door de NDW 7.6

Kaart Database Management/ De digitale kaart

Als logisch gevolg van de in dit rapport beschreven ontwikkelingen dient de digitale kaart, de basis van de routeplanner, van tijd tot tijd te worden geactualiseerd. Deze paragraaf beschrijft het ontwerp op dit aspect De meest kritische succesfactor voor het realiseren van de beoogde functionaliteit is de beschikking van het systeem over een representatie van het wegennetwerk dat verrijkt is met de relevante informatie benodigd voor personalisatiedoeleinden. De nodige informatie die relevant is voor selectieve en gepersonaliseerde routekeuze moet verzameld en beheerd worden. Een opsomming van voorbeeldattributen genoemd of gebruikt in experimenten in de geraadpleegde onderzoeken staat in Tabel 7.2 en een opsomming van de gegevens die worden verzameld door de Nationale Databank Wegverkeergegevens staat in Tabel 7.1 in de vorige paragraaf. Attribuut/ Kenmerk Lengte

Type

Beschrijving/ Opmerkingen

statisch

Klassiek/standaard opgenomen in een digitale kaart

Reistijd

In de eerste systemen werd de reistijd uitgerekend op basis van de maximaal toegestane snelheid op een wegsegment, werd dus als statisch beschouwd. In werkelijkheid is reistijd uiteraard een dynamisch gegeven.

Draaihoek

eigenlijk dynamisch statisch

Mate van congestie Weg-rijstrookafsluitingen

dynamisch semidynamisch

[2] en anderen (e.a.)

Kwaliteit van de weg

(semi) statisch statisch

[1] e.a. Semi-statisch omdat de kwaliteit van de weg kan verbeteren na wegwerkzaamheden bijvoorbeeld.

Landschapswaarde Pagina 60 van 79

[2] de draaihoek (die gemaakt moet worden om) naar aangrenzende kanten (te bereiken); voor de berekening van soort en aantal bochten. [2] e.a. Een wegafsluiting kan van lange duur zijn, in die periode is het min of meer een statisch gegeven.

[1] e.a. ; bedoeld wordt routes met uitzichtpunten.



- 61 -

[6] bekendheid met een wegsegment of een reeks wegsegmenten. Bekendheid specifiek Tabel 7.2 Voorbeeld attributen van wegsegmenten en/of routes.

Huidige representaties van het wegennetwerk bevatten informatie over standaard statische attributen zoals afstandsinformatie. Voor personalisatiedoeleinden moet ook informatie worden toegevoegd over niet-traditionele statische attributen zoals bijvoorbeeld de kwaliteit van het wegdek, de aanwezigheid van verkeerslichten en specifieke attributen zoals de bekendheid van de gebruiker met de weg. Daarnaast is het belangrijk informatie toe te voegen over dynamische attributen. Hieronder vallen aspecten zoals weersomstandigheden en verkeersomstandigheden. De achterliggende data komt uit diverse bronnen. Tabel 7.3 bevat een opsomming van voorbeeldbronnen van dynamische data in Nederland. Databron

Beschrijving/Opmerkingen

fileradar.nl Voor file informatie buienradar.nl Voor informatie over (te verwachten) neerslag weeronline.nl Voor informatie over het weer www.vid.nl ndw

Voor verkeersinformatie ndw levert niet direct (op de website) aan eindgebruikers informatie maar levert aan dienstverleners, verkeerscentra en wegbeheerders Tabel 7.3 Een opsomming van voorbeeldbronnen van data Vervolgens dient de data verwerkt te worden tot een bruikbare vorm, het uiteindelijke resultaat dient een representatie van het wegennetwerk te zijn die verrijkt is met de benodigde informatie ten behoeve van personalisatiedoeleinden. Deze representatie dient regelmatig geactualiseerd te worden. De frequentie waarmee de informatie geactualiseerd moet worden is in dit werk niet onderzocht. Met de actualiteit van de benodigde realtime gegevens voorzien wij geen probleem. Bij de nationale databank wegverkeergegevens (NDW) bijvoorbeeld worden de verkeergegevens iedere minuut gemeten en duurt het vijfenzeventig seconden om de meetgegevens te verwerken en ter beschikking te stellen aan de afnemers.

Pagina 61 van 79



8

- 62 -

Algoritmen & Technieken

In dit hoofdstuk wordt een indicatie gegeven van de toepasbaarheid van kritieke technische hulpmiddelen die bij een daadwerkelijke implementatie een rol kunnen gaan spelen. Een zoveel mogelijk onderbouwde keuze voor algoritmen en technieken wordt gegeven voor het realiseren van delen van de beoogde functionaliteiten besproken in het Globale Ontwerp. 8.1

Routeplanningsalgortimiek

We hebben gezocht naar een bekende algoritme voor het berekenen van alle of meerdere paden tussen twee eindpunten. Bij ons weten bestaan hier nauwelijks praktisch toepasbare algoritmen voor. We hebben geprobeerd te achterhalen welke routeplanningsalgoritme schuilt achter de routeplanner van Google Maps. Deze routeplanner biedt sinds enige tijd als antwoord op een routeplanningsverzoek vaak een tweetal of drietal route-alternatieven. Het gebruikte algoritme blijkt echter een goed bewaard geheim te zijn. Ons vermoeden is dat de alternatieve routes verkregen worden door route-onderdelen, vanaf een bepaalde wegklasse, uit eerder berekende routes buiten beschouwing te laten en dan opnieuw de A* (of Dijkstra) algoritme te draaien op de overgebleven graaf. De nieuwsgierigheid naar een algoritme met bovengenoemde eigenschappen heeft ons echter in de tussentijd niet losgelaten. Recent wetenschappelijke onderzoek heeft zich met dit onderwerp bezig gehouden. De meest belovende ontwikkeling hierin naar ons taxatie lijkt wel die op het gebied van genetische algoritmen met meervoudige doelen (Eng. Multi-objective Genetic Algorithms) [3],[19]. Deze algoritmen combineren personalisatie en efficiëntie doeleinden zoals beschreven in dit verslag. Het gebruikte testgebied staat afgebeeld in figuur 8.1.

Figuur 8.1 De gebruikte test-wegenkaart van Fukuoka in Japan in [19]

De verkregen route-alternatieven staan afgebeeld in figuur 8.2.

Pagina 62 van 79



- 63 -

Figuur 8.2 De berekende route-alternatieven in [19]

8.2

Adaptatie algoritme

Eén van de beoogde functionaliteiten is dat er op basis van de routeselecties van de gebruiker diens voorkeursmodel wordt afgeleid. Een onderdeel van het voorkeursmodel wordt gevormd door een vector gewichten die aangeven wat het relatieve belang is van een set attributen voor een gebruiker. De vector, indien bekend, kan gebruikt worden om route-alternatieven waarvan de eigenschappen bekend zijn te ranken. Maar zou ook gebruikt kunnen worden om routes te berekenen indien een adequate vertaling voor handen zou zijn van eigenschappen van wegsegmenten naar numerieke waarden. Dit laatste punt vormt een uitdaging. In [8] heeft men geëxperimenteerd met het implementeren van een adaptatie algoritme door een combinate van een fuzzy expert systeem en een neurale netwerk (zie paragraaf 5.8). De onderzoekers hebben een aantal theoretische argumenten aangedragen om het succes van deze Pagina 63 van 79



- 64 -

aanpak, die zij de hybride fuzzy-neurale benadering hebben genoemd aannemelijk te maken. Experimentele resultaten ontbreken in het artikel. In de reeks onderzoeken rondom “The Adaptive Route Advisor” (zie paragraaf 5.4) heeft men met diverse algoritmen/leertechnieken (Large Margin algorithm, perceptron training, SANE, search over lexicographic orderings) geëxperimenteerd om de adaptatie algoritme te implementeren. Men komt hier echter ook tot de conclusie dat een natuurlijkere trainingsignaal voor de adaptatie algoritme van een reinforcement leerstijl moet zijn, waarbij positieve feedback overeenkomt met een correcte ranking van de route-alternatieven en negatieve feedback met een incorrecte. Dit is een conclusie die overeenkomt met onze analyse in een vroeg stadium van dit afstudeerwerk. Een korte beschrijving van het idee van reinforcement learning staat in bijlage 4. Ons idee voor het toepassen hiervan is in hoofdlijnen als volgt: een mapping van de strategiefunctie naar de interne persoonlijke kostenfunctie van de gebruiker; van de cumulatieve beloning naar de feedback van de gebruiker achteraf na de reis. Zodoende leert de reinforcement leeragent, die een soort vertegenwoordiger van de gebruiker is, de juiste keuzes te maken uit de haalbare routealternatieven.

Pagina 64 van 79



9

- 65 -

Conclusie & Aanbevelingen

Het afstudeerwerk behelst een requirements analyse die als basis dient voor het realiseren van een gepersonaliseerd selectief route-informatiesysteem; het opstellen van een globaal ontwerp ervan; en het onderzoeken van de consequenties voor de kaartdatabase die de grondslag is van routeplanning. De focus ligt met name op de functionele aspecten. Huidige routenavigatiesystemen ondersteunen de gebruiker niet of nauwelijks in het selecteren van een route naar eigen voorkeur. De geboden keuzemogelijkheden zijn beperkt tot enkele opties zoals het vermijden van tolwegen en langdurig afgesloten wegen. Huidige systemen voorzien niet in de behoefte van een gebruiker met aanvullende wensen. Eén enkele route wordt berekend aan de hand van een kostenfunctie met een enkelvoudig doel. Dat is het vinden van een route met de minimale reistijd of de minimale reisafstand. De gebruikte routeplanner is niet in staat om andere of meervoudige doelen na te streven. De reistijd wordt geschat aan de hand van de maximaal toegestane snelheid op een weg. Deze geschatte reistijd komt normaliter niet overeen met de daadwerkelijk ervaren reistijd. Immers, de gemiddelde doorstroomsnelheid op een weg is niet statisch en kan sterk fluctueren afhankelijk van de verkeersintensiteit en andere factoren die de verkeersconditie beïnvloeden. De berekende route wordt aan de gebruiker gepresenteerd ter acceptatie. De gebruiker heeft daarbij twee keuzemogelijkheden: de route accepteren en de bijbehorende routebegeleiding ontvangen of de route weigeren en geen begeleiding ontvangen. Huidige systemen bieden de gebruiker geen hulp indien hij niet tevreden is met de geboden oplossing. Huidige systemen hanteren een “one-size-fits-all” uitgangspunt. Het (impliciet) gebruikte voorkeursmodel staat vast en kan niet aangepast worden om tegemoet te komen aan de persoonlijke wensen van een individuele gebruiker. Als volgende generatie route-informatiesysteem voorzien wij een gepersonaliseerd selectief routeinformatiesysteem dat de weggebruiker helpt een weloverwogen keuze te maken voor een route. Het doel van dit onderzoek is het achterhalen hoe een dergelijk gepersonaliseerd selectief routeinformatiesysteem gerealiseerd kan worden. De kenmerken en functionaliteiten van een routenavigatiesysteem zijn vastgelegd en geanalyseerd. Een inventarisatie is gemaakt van huidige commerciële systemen. Tevens is een inventarisatie gemaakt van wetenschappelijk onderzoek dat zich ten doel stelde te experimenteren met het uitwerken van (delen van) de beoogde personalisatiefunctionaliteit in prototype informatiesystemen. Het doel van deze inventarisatie is om een helder beeld te krijgen van de mogelijkheden. Per onderzoek is beschreven met welke functionaliteiten men heeft

Pagina 65 van 79



- 66 -

geëxperimenteerd, hoe men deze functionaliteiten in grote lijnen heeft geprobeerd te implementeren en eventueel hoe de ervaringen waren. Een requirements analyse is uitgevoerd om te komen tot een set van eisen en wensen ten aanzien van de beoogde functionaliteiten personalisatie en selectie. Ook is een ontwerp gerealiseerd. Ten slotte zijn consequenties voor de kaartdatabase geschetst. De conclusie is dat de bestaande functionele componenten gebruikersinterface/interactie, routeplanning en verkeersinformatiediensten & Mobiele communicatie aangepast dienen te worden. De mogelijkheid tot voorkeursmodellering dient toegevoegd te worden. En dat deze aanpassingen consequenties hebben voor de bestaande functionele component kaart database management die op zijn beurt de nodige aanpassingen dient te ondergaan. Voor een op korte termijn haalbare oplossing met minder functionaliteiten biedt het uitbreiden van bestaande commerciële systemen uitkomst. De kenmerken van deze oplossing zijn beschreven in een globaal ontwerp. Tot slot is een indicatie gegeven van de toepasbaarheid van kritieke technische hulpmiddelen die bij een daadwerkelijke implementatie een rol kunnen gaan spelen. Een interessant gebied voor verder onderzoek wordt gevormd door het experimenteren met niettraditionele routeplanningsalgoritmiek die aangepast is voor personalisatiedoeleinden. Het is interessant te onderzoeken wat de gevolgen zijn voor de kwaliteit, beoordeeld door representatieve groepen eindgebruikers, van complete routes wanneer ze op wegsegmentniveau worden opgebouwd met een routeplanningsalgoritme die rekening houdt met personalisatie aspecten, de routes voor meervoudige doelen (behalve reisafstand en/of reistijd) optimaliseert en performance technisch goed presteert. Een ander interessant onderzoeksgebied is het onderzoeken van de mogelijkheden om de routebegeleiding aan te passen aan de bekendheid van de gebruiker met het betreffende gebied. Dat wil zeggen wanneer de gebruiker bekend is met het gebied enkel op hoog niveau daar waar noodzakelijk de benodigde routebegeleiding geven. Een derde interessant onderzoeksgebied is het uitbreiden van de gepersonaliseerde selectieve route-informatiesysteem met andere modaliteiten. Met ander woorden het systeem wordt een soort reisassistent van de gebruiker. Behalve voor selectie van route-alternatieven voor een autoreis, kan het systeem de gebruiker ook helpen met selectie uit route-alternatieven voor een reis met openbaar vervoer of de fiets.

Pagina 66 van 79



- 67 -

Bijlagen Bijlage 1 – Geraadpleegde deskundigen –

Pagina 67 van 79

•

Eric van der Laan, voormalig Project Manager van Working Tomorrow, LogicaCMG.

•

Marco Pas, voormalig Architect Working Tomorrow, LogicaCMG.

•

Jan Peter Larsen, Research Consultant bij Almende.

•

Gerald de Jong, Almende.

•

Henk Cornelissen, Principal Consultant Geo-ICT, LogicaCMG. Binnen de competence Geo-ICT is het idee van de opdracht ontstaan.

•

Ben Rutten, Solution Management & Marketing Mobile Traffic Services, LogicaCMG



- 68 -

Bijlage 2 – De begrippen Graaf, Pad en het kortste pad probleem – Enkele begrippen en definities: Graaf Een graaf G = (V, E) bestaat uit een verzameling V, waarvan de elementen knopen worden genoemd en uit een verzameling E van paren van verschillende knopen uit V. Deze paren worden de takken van G genoemd. Als de paren niet geordend zijn, dan wordt G een ongerichte graaf genoemd; als de paren wel geordend zijn, dan wordt G een gerichte graaf genoemd. Pad Twee knopen in een ongerichte graaf heten verbonden als er een tak is van de eerste naar de tweede knoop. Een pad is een reeks van verschillende knopen, waarbij elke knoop verbonden is met de volgende knoop in de reeks. Een graaf is samenhangend wanneer er van iedere knoop in de graaf een pad bestaat. Voor een gerichte graaf zijn soortgelijke definities. Alle takken in een pad moeten dezelfde richting hebben. Zo’n pad wordt ook wel een gerichte pad genoemd. Een gerichte graaf is sterk samenhangend wanneer er een gericht pad bestaat tussen elk tweetal knopen van de graaf. Het kortste pad probleem Bij een kortste pad probleem is een gerichte graaf G = (V,E) gegeven. Aan iedere tak (i,j) є E worden kosten cij toegekend. Bij het kortste pad probleem is het de bedoeling om het pad te vinden van een knoop s naar een knoop t van de graaf, waarvoor geldt dat de gecumuleerde kosten van de takken op het pad minimaal is. Aangenomen wordt dat de kosten cij ≥ 0 zijn voor alle takken (i,j) є E. Tevens wordt aangenomen dat de graaf G sterk samenhangend is.

Pagina 68 van 79



- 69 -

Bijlage 3 – Huidige Routeringsalgoritmen – Hier worden de routeringsalgoritmen beschreven waarop de routeringsalgoritmen die in huidige routeplanners/navigatiesystemen worden gebruikt gebaseerd zijn. Het eerste algoritme dat hier wordt beschreven is het algoritme van Dijkstra. Het is voornamelijk geschikt voor een statische omgeving en het levert gegarandeerd de kortste paden op. Het algoritme van Dijkstra Het vinden van het kortste pad is een probleem dat de gemoederen lang bezig heeft gehouden en nog steeds houdt. E.W. Dijkstra heeft een enorme bijdrage geleverd aan het analyseren en oplossen van dit probleem. Het algoritme van Dijkstra lost het kortste pad probleem met één bronkoop op een gerichte graaf bestaande uit een verzameling knopen V en een verzameling takken E op. Aan de takken worden gewichten/kosten toegekend die binnen de context van routeplanning een afstand of reistijd kunnen weergeven. Uitgangspunt is dat de gewichten van de takken positieve statische waarden zijn. Het algoritme van Dijkstra vindt de kortste paden vanuit één bronknoop s naar alle overige bestemmingsknopen. De kortste paden vanuit alle bronknopen naar alle bestemmingsknopen kunnen vanzelfsprekend gevonden worden door het algoritme uit te voeren voor alle bronknopen. Het algoritme van Dijkstra gebruikt een verzameling knopen S waarvoor de definitieve kortste pad gewichten vanuit de bronkoop s van te voren zijn vastgelegd. Voor deze knopen v uit S wordt de schatting voor het kortste pad d[v] gelijkgesteld aan de waarde van het kortste pad van s naar v. Het algoritme selecteert herhaaldelijk één van de overgebleven knopen die niet in S zitten met de minimale kortste pad schatting. Deze knoop wordt aan S toegevoegd en alle uit deze knoop uitgaande takken worden eventueel bijgewerkt. Daarbij wordt getest of de kortste pad schatting van een knoop naar beneden kan worden bijgesteld door gebruik te maken van de huidig tak als zijnde de beste tak om de knoop in kwestie te bereiken. Als de test positief is dan wordt de kortste pad schatting d[v] naar beneden bijgesteld en de beste tak om de knoop in kwestie te bereiken wordt gelijkgesteld aan de huidige tak. Dit laatste gebeurt door middel van het toekennen van de voorgangereigenschap van de knoop π[v]. Deze wordt gelijkgesteld aan de knoop aan de overkant van de tak. In de volgende pseudo-code implementatie van het algoritme van Dijkstra wordt een kandidaatverzameling Q bijgehouden die alle knopen V die niet in S voorkomen, bevat samen met hun bijbehorende kortste pad schatting. De implementatie gaat uit van een zogenaamde sterk samenhangende graaf, dat wil zeggen dat er wordt aangenomen dat elke knoop in de graaf een verzameling buurknopen tot zijn beschikking heeft.

Pagina 69 van 79



- 70 -

Figuur B3.1: Het algoritme van Dijkstra in pseudo code

Op regel 1 lezen we dat Dijkstra aangeroepen wordt met drie parameters: G is een gerichte graaf met een verzameling knopen en takken, w is een functie dat het gewicht tussen twee buurknopen uitrekent, s is de bronknoop van de verzameling knopen. De procedure ‘InitializeSingleSource’ initialiseert alle kortste pad schattingen met oneindig en de voorganger knopen met de null waarde. Vervolgens wordt de kortste pad schatting voor de bronknoop s gelijkgesteld aan nul, het reizen van s naar s kost immers geen tijd/afstand. Op regel 4 wordt S geïnitialiseerd als een lege verzameling. Op regel 5 wordt de lege kandidatenlijst geïnitialiseerd. Vervolgens wordt Q gevuld met de knopen van de graaf G. De while loop op regel 7 wordt herhaaldelijk uitgevoerd totdat alle knopen zijn overgeheveld van Q naar S. Op regel 9 wordt de knoop met de laagste kortste pad schatting in Q toegekend aan u en verwijderd uit Q. Deze knoop wordt dan toegevoegd aan S op regel 10. Op regels 11 tot en met 14 worden alle takken (u,v) die uitgaan vanuit u bijgewerkt. Dat wil zeggen dat de kortste pad schatting d[v] en de voorganger π[v] worden geactualiseerd indien de kortste pad naar v verbeterd kan worden door via u te routeren. Dit algoritme berekent absolute kortste paden in een statische omgeving. Voor dynamische omgevingen spelen er echter tijdscomplexiteitsissues. Het A* algoritme Het A*-algoritme begint in een geselecteerde knoop. Van deze knoop bepaalt men de kosten om de knoop te bezoeken, voor de initiële knoop is dit gewoonlijk nul. A* schat dan de afstand vanaf de huidige knoop tot de bestemming. Deze schatting en de kost worden opgeteld, en vormen de heuristiek die aan het pad naar deze knoop wordt toegekend. De knoop wordt vervolgens toegevoegd in een prioriteitswachtlijn, die soms "open" genoemd wordt. Pagina 70 van 79



- 71 -

Het algoritme haalt vervolgens een knoop uit de prioriteitswachtlijn; door de werking van deze wachtlijn zal dit de knoop met de laagste heuristiek zijn. Wanneer de wachtlijn leeg is, is er geen pad van de startknoop naar de doelknoop en stopt het algoritme. Is de knoop die uit de wachtrij gehaald wordt de doelknoop, dan reconstrueert A* het succesvolle pad, geeft het weer, en stopt. Deze reconstructie van het pad uit de opgeslagen gesloten knopen betekent dat het niet nodig is om het voorlopig pad op te slaan in elke knoop. Wanneer de knoop die uit de wachtlijn gehaald wordt niet de doelknoop is, worden nieuwe knopen gecreëerd voor alle aanvaardbare aangrenzende knopen; de manier waarop dit precies gebeurt hangt af van het specifieke probleem. Voor elk van die knopen berekent A* de kosten om de knoop te bezoeken en slaat deze op in de knoop. Deze kost wordt berekend als de cumulatieve som van de kosten in de ouderknopen, plus de kost van de bewerking om de nieuwe knoop te bereiken. Het algoritme houdt ook een "gesloten" lijst bij met knopen die reeds gecontroleerd zijn. Wanneer een nieuw gegenereerde knoop al in de lijst staat met een gelijke of lagere kost, doet men verder niets met deze knoop of het pad dat ermee geassocieerd is. Wanneer de nieuwe knoop al in de gesloten lijst staat, maar nu een lagere kost heeft, wordt deze oude knoop uit de gesloten lijst verwijderd, en werkt men verder met de nieuwe knoop. Vervolgens wordt een schatting van de afstand van de nieuwe knoop naar de bestemming gemaakt, en wordt deze opgeteld om de heuristiek voor de nieuwe knoop te vormen. Deze wordt vervolgens aan de "open" prioriteitswachtlijn toegevoegd, tenzij hier al een identieke knoop met lagere of gelijke heuristiek in zit. Wanneer de vorige stappen herhaald zijn voor elke nieuwe aangrenzende knoop, kan de originele knoop uit de prioriteitswachtrij geschrapt worden en aan de "gesloten" lijst worden toegevoegd. Vervolgens haalt men de volgende knoop uit de prioriteitswachtlijn, en herhaalt men het proces.

Pagina 71 van 79



- 72 -

Bijlage 4 – Agents en Reinforcement Learning – Agents en Reinforcement Learning Zoals gezegd zijn de agents waarvan de AntNet algoritme gebruik maakt reinforcement leeragents, hier wordt uitgelegd wat reinforcement leren inhoudt en wat een reinforcement leeragent onderscheidt van andere agents. Wat is een agent? Het begrip agent wordt in het domein van de Kunstmatige Intelligentie (KI) onder meer als volgt beschreven: Een agent is iets, in dit verband een software systeem, wat zijn omgeving waarneemt met behulp van sensoren en op deze omgeving acties kan uitvoeren met actuatoren . De waarnemingen die een agent doet vormen zijn percept sequence. De door de agent te kiezen actie kan in principe van de hele rij percept sequence afhangen . De agent beeldt rijen percept sequences af op acties. Het gaat in de KI om rationele agents. Hoe rationeel een agent is, hangt af, van de performance maat die de mate van succes definieert, van wat de agent weet van zijn omgeving, van de mogelijke acties en tot slot de percept sequence op dat moment. Een ideale rationele agent moet voor iedere mogelijke percept sequence die actie uitvoeren waarvan verwacht wordt dat deze de performance maat maximaliseert, op basis van die percept sequence en alle ingebouwde kennis die de agent bezit. De ideale afbeelding van percept sequences naar acties specificeert welke actie de agent zou moeten nemen, gegeven een percept sequence. Dit levert een ideale agent. Vaak worden de volgende zeven eigenschappen aan agents toegeschreven . Een agent is reactief dat wil zeggen dat een agent reageert op externe asynchrone stimuli. Een agent is autonoom als zijn gedrag wordt bepaald door zijn eigen ervaring oftewel hij controleert zijn eigen acties zonder tussenkomst van anderen. Een agent is proactief, hij is doelgericht en neemt initiatieven. Een agent is continu en persistent, een agent wordt niet uitgevoerd maar hij “leeft”. Een agent is sociaal, hij communiceert met andere agenten, mensen en de buitenwereld. Een agent is lerend en adaptief, hij past zich aan op basis van ervaring. Ten slot kan een agent mobiel zijn, hij kan zich verplaatsen tussen verschillende hosts in een netwerk. Er kunnen drie grote domeinen worden genoemd waar tegenwoordig agents toegepast worden . De eerste is het domein van assisterende agents een voorbeeld hiervan is een agent die hotels boekt en een reis organiseert voor zijn eigenaar. De tweede toepassing is multi-agent beslissingssystemen met als voorbeeld componenten die in een netwerk samen uitzoeken hoe ze schaarse middelen van het netwerk kunnen verdelen. De derde toepassing is multi-agent simulatiesystemen welke worden gebruikt om complexe reële situaties te modelleren, een voorbeeld hiervan is een simulatie van ecosystemen. Pagina 72 van 79



- 73 -

Een agent is dus een ingecapsuleerd computersysteem gesitueerd in een omgeving en in staat tot het ondernemen van flexibele autonome acties in die omgeving om zodoende zijn ontwerpdoeleinden te realiseren. Interactie met de omgeving is noodzakelijk om individuele doeleinden te bereiken en om met onderlinge afhankelijkheden om te gaan . Wat is Reinforcement Leren? Reinforcement leren (RL) is leren wat te doen – hoe situaties af te beelden op acties - om een numerieke beloningssignaal te maximaliseren . Het wordt de leeragent niet verteld welke acties ondernomen moeten worden, zoals wel het geval is in de meeste vormen van machine learning, maar de agent moet zelf ontdekken welke acties de meeste beloning opbrengen door ze uit te proberen. In de meest interessante en uitdagende gevallen, zullen acties niet alleen de directe beloning beïnvloeden maar ook de volgende situatie en via deze alle volgende beloningen. Deze twee karakteristieken: trial-and-error zoeken en uitgestelde beloning zijn de twee meest belangrijke onderscheidende kenmerken van reinforcement leren. Reinforcement leren wordt niet gedefinieerd door het definiëren van leermethodes maar door het definiëren van een leerprobleem. De basis idee van RL is om de meest belangrijke aspecten van het echte probleem te achterhalen waarmee de leeragent te maken heeft in zijn interactie met zijn omgeving om een doel te bereiken. Een agent moet dus in staat zijn om de toestand van zijn omgeving te waarnemen en om acties te ondernemen die de toestand van de omgeving beïnvloeden. De agent moet ook een doel (of doelen) hebben die gerelateerd zijn aan de toestand van de omgeving. De drie kernbegrippen in RL zijn dus waarneming, actie en doelstelling. Reinforcement leren is anders dan gesuperviseerd leren. Gesuperviseerd leren is leren uit voorbeelden die worden aangeboden door een externe supervisor die over de nodige kennis beschikt. Het probleem met gesuperviseerd leren is dat het niet geschikt is voor leren uit interactie. In interactieve problemen is het vaak onpraktisch om voorbeelden te verkrijgen van gewenst gedrag die én correct zijn én representatief voor alle situaties waarin de agent geacht wordt te handelen. Op onbekend terrein moet een agent in staat zijn te leren uit eigen ervaring. Reinforcement leren (RL) of leren door bekrachtiging is dus een niet-gesuperviseerde on-line leertaak, waarbij een agent door middel van trial and error methoden en interactie met zijn omgeving een aangepaste (optimale) strategie dient te leren . Hierbij wordt een model beschouwd waarin een agent beloningen ontvangt voor acties die hij onderneemt in een bepaalde omgeving. Doordat goede acties (terecht komen in een gunstige situatie) goed beloond worden en neutrale of slechte acties minder beloond of afgestraft worden, dient de agent een verbeterd gedrag te leren. Exploration versus exploitation Pagina 73 van 79



- 74 -

Een uitdaging dat naar boven komt bij reinforcement leren en niet bij andere soorten leren is het spanningsveld tussen exploratie en exploitatie. Om een grotere beloning te ontvangen moet een agent acties de voorkeur geven die hij in het verleden heeft uitgeprobeerd en waarvan hij heeft uitgevonden dat ze een grote beloning opleveren. Maar om deze acties te ontdekken, moet een agent acties uitproberen die hij niet eerder heeft geselecteerd. De agent moet exploiteren wat hij al weet om beloning te ontvangen, maar het moet ook exploreren om betere actieselecties te kunnen doen in de toekomst. Het dilemma is dat geen van beide, exploratie of exploitatie, aangehouden kunnen worden zonder te mislukken in het uitvoeren van de taak. Reinforcement leren neemt als uitgangspunt een compleet interactieve doelgerichte agent. Reinforcement leeragents hebben expliciete doelen, kunnen aspecten van hun omgeving waarnemen en kunnen acties kiezen om hun omgeving te beïnvloeden. Bovendien, wordt er vaak aangenomen dat een agent vanaf het begin moet opereren ondanks de onzekerheid over de omgeving waarmee het te maken krijgt. Elementen van RL Behalve de agent en de omgeving, zijn er vier belangrijke subelementen te identificeren van een reinforcement leersysteem: een strategie of beleid (engels: policy), een beloningsfunctie (reward function), een nutsfunctie (value function) en optioneel een model van de omgeving. Strategie Een strategie definieert de wijze waarop een leeragent zich gedraagt op een gegeven moment. Een strategie is een afbeelding van waargenomen toestanden van de omgeving op acties die ondernomen moeten worden in deze toestanden. In sommige gevallen is de strategie een simpele functie of opzoektabel, in andere gevallen gaat het om uitvoerige berekeningen zoals een zoekproces. De strategie is de kern van een reinforcement leeragent in de zin dat de strategie op zich voldoende is om gedrag vast te leggen. Beloning Een beloningsfunctie definieert het doel in een reinforcement leerprobleem. Het beeldt ieder waargenomen toestand (of toestand-actie paar) van de omgeving af op een enkel getal, een beloning, waarbij het aangeeft wat de intrinsieke wenselijkheid van die toestand is. De enige doelstelling van een reinforcement leeragent is het maximaliseren van de totale beloning dat het ontvangt op de lange termijn. De beloningsfunctie definieert wat de goede en wat de slechte gevallen zijn voor de agent. Deze zijn de directe en definiërende kenmerken van het probleem waarmee de agent te maken heeft. Als zodanig, moet de beloningsfunctie niet wijzigbaar zijn door de agent. Het kan echter wel als basis dienen voor het wijzigen van de strategie. Als bijvoorbeeld een actie die geselecteerd is door de strategie als gevolg een lage beloning heeft, dan kan de Pagina 74 van 79



- 75 -

strategie gewijzigd worden zodat in de toekomst in een dergelijke situatie een andere actie geselecteerd wordt. Nutsfunctie Terwijl de beloningsfunctie aangeeft wat goed is in directe zin, geeft een nutsfunctie aan wat goed is op de lange termijn. De nutwaarde van een toestand is de totale waarde aan beloning dat een agent verwacht bij elkaar te verzamelen in de toekomst beginnende bij die toestand. Terwijl beloningen bepalen wat de directe intrinsieke wenselijkheid van de omgevingstoestand is, bepaalt de nutwaarde de lange termijn wenselijkheid van toestanden nadat de mogelijk opvolgende toestanden in beschouwing zijn genomen samen met de beloningen die beschikbaar zijn in die toestanden. Een toestand kan bijvoorbeeld altijd een lage directe beloning opleveren maar nog wel een hoge nutwaarde hebben omdat het regelmatig gevolgd wordt door andere toestanden die hoge beloningen opleveren. Ook het tegengestelde kan waar zijn. Model De vierde en laatste element van sommige reinforcement leersystemen is een model van de omgeving. Dit is iets dat het gedrag van de omgeving nabootst. Bijvoorbeeld, gegeven een toestand en een actie kan het model een resulterend volgende toestand en volgende beloning voorspellen. Modellen worden gebruikt voor planning, waarmee wordt bedoeld elke wijze van beslissing nemen over het verloop van een actie door mogelijke toekomstige situaties in beschouwing te nemen vóórdat ze daadwerkelijk ervaren worden. Het betrekken van modellen en planning in reinforcement leersystemen is een relatief nieuwe ontwikkeling. Vroegere reinforcement leersystemen waren expliciet trial-and-error leeragents; wat ze deden werd gezien als bijna het tegenovergestelde van planning. Moderne reinforcement leren gaat over het hele spectrum van laag-niveau trial-and-error leren tot hoog-niveau weloverwogen plannen.

Pagina 75 van 79



- 76 -

Bijlage 5 – Screenshots –

Figuur B5.1: Het scherm waar het routeplanningsverzoek en identificatie ingevoerd kunnen worden i.g.v. [2].

Figuur B5.2: Het hoofdscherm i.g.v. [2].

a: het hoofdscherm

b: scherm met routerepesentatie op een kaartje

Figuur B5.3: Een route met meer snelweg uit [2].

a. Een route met meer snelweg Pagina 76 van 79

b. Een route met meer snelweg Voorkeursroutes in Routenavigatie


- 77 -

Referenties [1] Letchner, J.; Krumm, J.; Horvitz, E. Trip Router with Individualized Preferences (TRIP): Incorporating Personalization into Route Planning. (2006). Proceedings of the 18th conference on Innovative applications of artificial intelligence , pp. 1795-1800. [2] Rogers, S.; Fiechter, C.; & Langley, P. (1999). An Adaptive Interactive Agent for Route Advice. Proceedings of the Third International Conference on Autonomous Agents (pp. 198205). Seattle: ACM Press. [3] C. -S, Chiu. Techniques And Algorithms For Solving The Multiobjective Path Optimisation Problem For Car Navigation (2009). The University of New South Wales. PhD thesis. [4] J. L. Schofer, F. S. Koppelman and W. A. Charlton. Perspectives on Driver Preferences for Dynamic Route Guidance Systems. (1997). Transportation Research Record: Journal of the Transportation Research Board. Transportation Research Board of the National Academies. Volume 1588 pages 26-31. [5] B. Smyth and L. Mc Ginty. The Route to Personalization: A Case-Based Reasoning Perspective. (2001). Portal [1449-2490] Smyth, B vol:2 pg:25. [6] Rogers, S.; Langley, P.; Johnson, B.; & Liu, A. (1997). Personalization of the Automotive Information Environment. Proceedings of the Workshop on Machine Learning in the Real World: Methodological Aspects and Implications. Nashville, TN. [7] Balke, W. -T.; Kieβling, W. ; Unbehend, C. A situation-aware mobile traffic information system prototype. In Proceedings of the 36th Hawaii International Conference on System Sciences (HICSS-36), Big Island, Hawaii, USA, IEEE Computer Society Press, 2003. [8] Pang, G. K. H.; Takahashi, K.; Yokota, T. ; Takenaga, H. Adaptive Route Selection for Dynamic Route Guidance System Based on Fuzzy-Neural Approaches. IEEE Transactions on vehicular technology, vol. 48, no. 6, November 1999. [9] Balke, W. F.; Kieβling, W. ; Unbehend, C. Performance and Quality Evaluation of a Personalized Route Planning System. (2003). Proceedings of the Brazilian Symposium on Databases (SBBD), pages 328-340. [10] Rogers, S.; & Langeley, P. (1998). Interactive Refinement of Route Preferences for Driving. Proceedings of the AAAI Spring Symposium on Interactive and Mixed-Initiative DecisionTheoretic Systems (pp. 109-113). Stanford, CA: AAAI Press. [11] Flinsenberg, I.C.M. Route planning algorithms for car navigation. (2004). Technische Universiteit Eindhoven. Proefschrift. - ISBN 90-386-0902-7. Pagina 77 van 79



- 78 -

[12] Fiechter, C. -N. & Rogers, S. (2000). Learning Subjective Functions with Large Margins. Proceedings of the Seventeenth International Conference on Machine Learning (pp. 287-294). Stanford, CA. [13] Haigh, K. Z.; Shewchuk, J. R.; Veloso, M. Route Planning and Learning for Execution. (1994). In Working notes from the AAAI Fall Symposium Planning and Learning: On to Real Applications, pages 58-64, New Orleans, LA, November 1994. AAAI Press. [14] Haigh, K. Z.; Shewchuk, J. R.; and Veloso, M.M. Exploiting Domain Geometry in Analogical Route Planning. Journal of Experimental and Theoretical AI, 1997. 9(4): p. 509-541. [15] McGinty, L. and Smyth, B. Personalised Route Planning: A Case-Based Approach. In E. Blanzieri and L. Portinale, editors, Advances in Case-Based Reasoning: Proceedings of the Fifth European Workshop of Case-Based Reasoning, pages 431-442. Springer-Verlag, 2000. Trento, Italy. [16] Schroedl, S.; Wagstaff. K.; Rogers, S.; Langley, P.; Wilson, C. Mining GPS Traces for Map Refinement. Data Mining and Knowledge Discovery, Volume 9, Issue 1, July 2004, pp. 59-87. [17] Verkeersbegeleidingssystemen, collegediktaat. Ir. J.J. Reijmers. 1997. [18] P. Bovy and E. Stern. Route Choice: Wayfinding in Transport Networks (1990). Kluwer Academic Publisher. ISBN: 0-7923-0812-3. [19] Optimal Route Search in Car Navigation Systems by Multi-objective Genetic Algorithms. (2009). International Journal of Information Systems for Logistics and Management. Vol. 4, No. 2. pages 9-18. De websites in referenties [20] tot en met [44], [46] en [47] zijn voor het laatst gecontroleerd op 14 september 2006. De websites in referenties [45] en [48] zijn voor het laatst gecontroleerd op 16 augustus 2012. [20] http://eddiepoppe.cambridgelaan.nl [21] http://nl.wikipedia.org [22] www.tomtom.com [23] www.invent-online.de [24] www.pioneerelectronics.com [25] www.cdrinfo.com [26] www.toyota.co.jp Pagina 78 van 79



- 79 -

[27] www.japancorp.net [28] http://press.nissan-global.com [29] www.mts-live.com [30] www.decell.com/autoroute1 [31] www.iteris.com/itsarch/html/mp/mpatis4.htm [32] www.kew.nl [33] http://www03.ibm.com/industries/automotive [34] www.denso-europe.com [35] www.aisin-aw.co.jp [36] www.garmin.com/ [37] www.mio-tech.be [38] www.viamichelin.com [39] www.vdodayton.com [40] www.cdrinfo.com [41] www.alturion.com/ [42] www.navigon.com/ [43] www.fujitsu-ten.co.jp/english/ [44] www.panasonic.nl [45] www.ndw.nu [46] www.connekt.nl/ [47] www.ertico.com [48] http://en.wikipedia.org/w/index.php?oldid=494907605

Pagina 79 van 79


Afstudeerverslag: Voorkeursroutes in Routenavigatie

Recommend Documents