Snelle en realistische routeplanning voor GPS-toestellen

Snelle en realistische routeplanning voor GPS-toestellen Jeroen Verbrugghe

Promotoren: prof. dr. ir. Didier Colle, dr. Pieter Audenaert Begeleiders: Ine Melckenbeeck, prof. dr. Jan Cnops Masterproef ingediend tot het behalen van de academische graad van Master of Science in de industriële wetenschappen: informatica

Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël De Zutter Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2014-2015

Snelle en realistische routeplanning voor GPS-toestellen Jeroen Verbrugghe

Promotoren: prof. dr. ir. Didier Colle, dr. Pieter Audenaert Begeleiders: Ine Melckenbeeck, prof. dr. Jan Cnops Masterproef ingediend tot het behalen van de academische graad van Master of Science in de industriële wetenschappen: informatica

Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël De Zutter Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2014-2015

Toelating tot bruikleen “De auteur geeft de toelating deze masterproef voor consultatie beschikbaar te stellen en delen van de masterproef te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de bepalingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze masterproef.”

Jeroen Verbrugghe, mei 2015

Woord vooraf Een masterproef maken lukt niet alleen. Vanaf het uitkiezen van het onderwerp tot het indienen van de definitieve versie, zonder de steun en hulp van vele mensen is het niet mogelijk. Een aantal van deze mensen wil ik dan graag langs deze weg nog eens extra bedanken.

Ten eerste wil ik dr. Pieter Audenaert bedanken. Zonder uw concept was dit alles niet mogelijk geweest. Verder was uw enthousiasme over het onderwerp enorm aanstekelijk. Vervolgens gaat mijn dank uit naar Ine Melckenbeeck. De vele voorstellen voor extra testen en het vele nalezen hebben dit werk naar een hoger niveau getild. Ook prof. dr. Jan Cnops wil ik bedanken voor de begeleiding vanuit de faculteit. De afspraken doorheen het jaar hebben voor een nuttig extra perspectief op het project gezorgd. Verder wil ik prof. dr. ir. Didier Colle en prof. Mario Pickavet bedanken voor hun kritische blik en suggesties. Wie zeker ook niet mag ontbreken zijn de mensen van het bedrijf Be-mobile. Zonder hun data zou deze masterproef onmogelijk zijn geweest. Ten slotte wil ik nog mijn vrienden en familie bedanken. Zowel voor motivatie als het nalezen van stukken tekst waren jullie een spontane hulp.

Jeroen Verbrugghe, mei 2015

Snelle en realistische routeplanning voor GPS-toestellen Jeroen Verbrugghe Promotoren: prof. dr. ir. Didier Colle, dr. Pieter Audenaert Begeleiders: Ine Melckenbeeck, prof. dr. Jan Cnops Abstract— Van een wegennetwerk zijn voor elk moment van de dag de werkelijke rijtijden van alle straten gekend. Vertragingen door file, ongevallen en de hoeveelheid auto’s tijdens de spitsuren zorgen dat deze rijtijden niet constant blijven doorheen de dag. Met behulp van deze data kan met een tijdsafhankelijke variant van het algoritme van Dijkstra perfect de kortste weg en reistijd tussen twee kruispunten bepaald worden voor een willekeurig starttijdstip. In deze scriptie wordt een benadering voorgesteld van dit model omdat de geheugenvereisten te groot zijn om al de werkelijke rijtijden op te slaan. In plaats van alle rijtijden bij te houden wordt er gewerkt met twee penalties. De eerste penalty die gebruikt wordt is de locatiepenalty. Deze penalty bepaalt voor elk straatdeel hoeveel vertragingen er zijn doorheen de dag. De tweede penalty die gebruikt wordt is de tijdspenalty. Deze bepaalt voor elk tijdstip hoeveel vertragingen er zijn op het volledige wegennetwerk. De twee penalties worden gecombineerd om voor elk straatdeel op elk moment tot een benaderende rijtijd te komen.

I. I NLEIDING AN het bedrijf Be-mobile [1] werd een definitie van het wegennetwerk van België gekregen. Deze bestaat uit de coördinaten van kruispunten en de verbindingen tussen de kruispunten. Van deze verbindingen is de afstand en optimale rijtijd gekend. Voor de straten in en rond Gent is nog extra informatie beschikbaar. Voor elke minuut van de dag is geweten wat de werkelijke tijd is om de volledige straat af te leggen. Deze tijd varieert immers doorheen de dag. Indien voor alle straten deze variabele rijtijden beschikbaar zijn kan perfect berekend worden hoe lang een rit tussen twee kruispunten zal duren. Door een tijdsafhankelijke variant te gebruiken van het algoritme van Dijkstra [2] kan voor elk moment deze optimale weg berekend worden [3]. Het grote probleem hierbij is dat het niet haalbaar is om voor al de straten alle werkelijke rijtijden op te slaan. Dit vereist te veel geheugenruimte. In deze scriptie wordt een methode voorgesteld om de benodigde geheugenruimte te beperken door niet alle rijtijden op te slaan, maar hiervoor een benadering te gebruiken.

V

II. B ENADERING A. Algemeen De verschillende rijtijden per straatdeel worden in de benadering niet meer bijgehouden. In de plaats hiervan wordt gebruik gemaakt van twee penalties. De eerste penalty, de locatiepenalty, wordt toegekend aan elk straatdeel. De grootte van deze penalty hangt af van hoeveel vertraging er is op dat straatdeel doorheen de dag. Straten waar gedurende de hele dag geen vertraging is krijgen een zeer kleine penalty, straten met enorm veel vertraging een grote. De tweede penalty die gebruikt wordt is de tijdspenalty. Deze

wordt aan elke minuut van de dag toegekend. Ze bepaalt hoeveel problemen er zijn doorheen het hele netwerk op dat specifieke moment. ‘s Nachts, wanneer er weinig problemen zijn, zal deze zeer klein zijn. Tijdens de twee spitsmomenten moet deze echter zeer groot zijn. Deze penalties worden gebruikt om samen met de optimale rijtijd voor elk straatdeel op elk moment een nieuwe kost te bekomen. Er moet op gelet worden dat de twee penalties slechts een grote impact hebben als ze beide groot zijn. Zelfs tijdens het spitsuur zal een straat op het platteland immers weinig vertraging hebben. Zo zal ook een straat in het centrum ‘s nachts weinig tot geen vertraging hebben. De locatie- en tijdspenalty kunnen beide zowel absoluut als relatief berekend worden. Indien ze absoluut berekend worden moet er gekeken worden naar hoeveel effectieve vertraging er is. Bij de relatieve methode wordt gekeken hoeveel vertraging er is ten opzichte van de normale rijtijden. Een vertraging van 20 seconden heeft immers meer impact op een straat met een optimale rijtijd van e´ e´ n minuut dan een straat met een optimale rijtijd van vijf minuten. B. Locatiepenalty Een eerste mogelijke manier om de locatiepenalty te bepalen wordt beschreven in formule (1). L1 =

P

t∈T ijden (K(t)

− Kmin )

#tijden

(1)

Hierbij is T ijden de verzameling van alle minuten in de dag. K(t) is de werkelijke rijtijd op tijdstip t. De variabele Kmin stelt de optimale rijtijd voor. Deze penaltymethode is absoluut. Ze kan waarden aannemen tussen 0 en ∞. Een relatieve manier om de locatiepenalty te bepalen wordt voorgesteld in formule (2). P t∈T ijden (K(t) − Kmin ) L2 = (2) (#tijden) ∗ Kmin Deze methode lijkt goed op de absolute methode. Er wordt nu nog extra gedeeld door de minimale rijtijd. Hierdoor worden relatieve penalties bekomen. Hoewel in theorie nog steeds penalties tussen 0 en ∞ bekomen kunnen worden, liggen de meeste penalties tussen 0 en 1. Er zijn enkele uitschieters tot maximaal 2, 5. De meeste plattelandswegen hebben met deze methode een zeer kleine straf. Straten in het centrum van Gent en op- en afritten van snelwegen hebben een eerder grote straf.

C. Tijdspenalty De tijdspenalty bepaalt voor elke minuut van de dag hoeveel vertraging er op dat moment is over het gehele wegennetwerk. Een absolute manier om deze te berekenen wordt voorgesteld in formule (3). P (Ks (t) − Ks (min)) (3) Ts1 (t) = s∈Straten #straten Hierbij is Straten de verzameling van alle straten waarvoor de variabele rijtijden gekend zijn. De rijtijd van straat s op tijdstip t wordt weergegeven door Ks (t). De optimale rijtijd van straat s wordt voorgesteld door Ks (min). Deze manier om tijdpenalties te berekenen resulteert in waarden tussen 0 en 2000. De berekende tijdspenalties worden weergegeven op figuur 2. Hierop kunnen duidelijk twee pieken gezien worden. Deze staan voor de ochtend- en avondspits. Verder valt op dat de penalties overdag veel hoger zijn dan deze ‘s nachts. De tijdspenalty kan ook op een relatieve manier berekend worden. Dit wordt getoond in formule (4). P Ks (t)/Ks (min) (4) Ts2 (t) = s∈Straten #straten Voor het gebruikte wegennetwerk geeft deze formule tijdspenalties weer tussen 1 en 1, 3.

1,500

straf

K = Kopt + Ts1 (t)α ∗ Lβ2

(6)

K = Kopt × (Ts2 )α × (1 + L3 )β

(7)

Ten slotte kan nog een combinatie gemaakt worden van de relatieve locatiepenalty L2 en de relatieve tijdspenalty Ts2 (t). Hierbij moet de optimale rijtijd vermenigvuldigd worden. Dit wordt ge¨ıllustreerd in formule (7). Bij deze formule wordt bij de locatiepenalty e´ e´ n opgeteld. Dit is nodig want indien de locatiestraf nul is moet de berekende rijtijd altijd gelijk zijn aan de optimale rijtijd en niet aan nul. Omdat het onwaarschijnlijk is dat enkel optellen of vermenigvuldigen tot een zeer goed resultaat zullen leiden, worden twee parameters ingevoegd: α en β. De berekende tijdspenalty wordt altijd tot een macht α verheven. De berekende locatiepenalty wordt tot de macht β verheven. Door deze parameters te wijzigen wordt de impact van een van de twee penalties vergroot of verkleind. In de volgende sectie wordt besproken hoe hiermee de beste benadering kan bepaald worden. III. E VALUATIE EN OPTIMALISATIE

2,000

1,000

500

0 0

:0 00

20

:0

0

:0

:0

0

0 :0

0 :0 0

:0

:0 0 16

0 :0 12

0

:0 0

:0 0

:0

0

04

:0 00

08

:0 0

0

.

Hierbij is K de berekende rijtijd per straatdeel op elk moment, Kopt is de optimale rijtijd van het straatdeel. Het doel van de α en β zal besproken worden in sectie III. Een tweede mogelijkheid om de werkelijke rijtijd te benaderen is door de relatieve locatiepenalty L2 en de absolute tijdspenalty Ts1 (t) te combineren. Dit wordt dan formule (6).

Fig. 1: De evolutie van de tijdspenalty doorheen de dag.

D. Kost bepalen De twee penalties worden samengevoegd met de optimale rijtijd om voor elk straatdeel op elk moment een berekende rijtijd te bekomen. Er worden drie verschillende mogelijkheden voorgesteld om dit te doen. De eerste mogelijkheid is door gebruik te maken van de absolute locatiepenalty L1 en de relatieve tijdspenalty Ts2 (t). Dit wordt weergegeven in formule (5). K = Kopt + Ts2 (t)α ∗ Lβ1

(5)

Door het aanpassen van α en β worden de gebruikte kostbepalingsmethodes uit II-D verfijnd. De berekende kost moet altijd zo goed mogelijk aansluiten bij de werkelijke kosten. De mate waarin dit gebeurt kan weergegeven worden aan de hand van een evaluatiefunctie. Het optimaliseren van de α- en β-waarden kan gebeuren voor verschillende situaties. Zo kan geprobeerd worden om voor e´ e´ n specifiek straatdeel de rijtijden doorheen de hele dag te benaderen. Hetzelfde kan voor de kortste weg tussen twee kruispunten doorheen de dag. Een andere mogelijk doel bij het optimaliseren zijn verzamelingen van straatdelen of kortste wegen tussen twee kruispunten. Elk van de elementen uit deze verzameling krijgt dan ook een specifiek starttijdstip. Om deze verzameling representatief te laten zijn voor het volledige wegennetwerk moet er voldoende variatie inzitten. Daarom moet de verzameling elementen bevatten vanuit zowel stad als platteland. Er moeten ook stukken snelweg inzitten, evenals kleine wegen. Verder moeten de starttijdstippen voldoende verdeeld zijn doorheen de dag. Rekening houdend met deze vereisten kunnen de verzamelingen van straatdelen of routes op ongeveer dezelfde manier geconstrueerd worden. Eerst wordt een verzameling gemaakt van alle straatdelen of kruispunten. Hieruit wordt dan respectievelijk een straatdeel of een starten eindpunt gekozen. Daarna krijgt deze nog een starttijdstip toegewezen. Er wordt voor gekozen om dit tijdstip tussen 5u en 20u te houden, dit omdat ‘s nachts de rijtijden zo goed als niet variëren. Deze tijdstippen zijn minder interessant om rekening te houden voor het opstellen van de benadering. De optimalisatie gebeurt aan de hand van een evaluatiefunctie. Deze functie bepaalt hoe goed de benadering overeen komt

·106

met de werkelijke rijtijden. Voor e´ e´ n specifiek straatdeel of een specifieke route kan gebruik gemaakt worden van formule (8). D=

X

t∈T ijden

| Kw (t) − Kb (t) |

Hierbij is Tijden de verzameling van alle tijden waarvoor geëvalueerd moet worden. Kw (t) en Kb (t) zijn respectievelijke de werkelijke rijtijd en de benaderende rijtijd. Indien geoptimaliseerd wordt voor een verzameling van routes of straatdelen moet formule (9) gebruikt worden. D=

X

v∈V erzameling

| Kw (v) − Kb (v) |

4

(8)

(9)

Hierbij is Verzameling de gebruikte straatdelen- of routeverzameling. Verder zijn Kw (v) en Kb (v) de werkelijke en benaderende rijtijden voor route of straatdeel v op het gegeven starttijdstip. De waarde van D geeft het totaal verschil weer tussen de werkelijke en benaderende rijtijden. De parameters α en β zijn optimaal wanneer de D-waarde minimaal is. Om deze optimale α- en β-waarden te bekomen krijgen α en β een startwaarde van 1. Alternerend wordt de ene waarde constant gehouden en voor de andere een betere waarde gezocht. Dit wordt herhaald totdat er geen betere waarde meer kan gevonden worden voor zowel α als β. Het belangrijkste geval waarvoor de optimale α en β berekend worden is dat van de verzameling van meerdere routes. De verzameling van geteste routes bestaat uit 1800 routes met een gemiddelde rijtijd van 32 minuten. Er wordt op deze manier geoptimaliseerd omdat het uiteindelijke doel is om voor een willekeurige route in het wegennetwerk een zo goed mogelijke benadering te krijgen van de werkelijke rijtijd. Na optimalisatie blijkt dat formule (5) en (6) een bijna gelijkaardige nauwkeurigheid hebben. Ze hebben een respectievelijk gemiddelde afwijking van 4,45% en 4,40%. Formule (7) heeft een iets slechtere nauwkeurigheid met een gemiddelde afwijking van 4,5%. Ter vergelijking: tussen de werkelijke rijtijden en de optimale rijtijden is er voor de verzameling een gemiddelde afwijking van 16%. Op figuur 2 staan voor formule (5) de resultaten van deze optimalisatie weergegeven. De rode curve stelt de werkelijke rijtijden voor. De zwarte punten zijn de benaderende rijtijden. IV. OVERDRAAGBAARHEID Het is interessant om te kijken of de bekomen α en β overdraagbaar zijn. Om dit te testen wordt het wegennetwerk in twee gelijkaardige delen verdeeld. Voor beide delen wordt een verzameling van 900 routes opgesteld. Daarna worden de optimale α en β bepaald voor de eerste verzameling. Na optimalisatie is er een gemiddelde afwijking van 4,7% tussen de werkelijke en benaderende rijtijden. De gevonden α en β worden nu gebruikt om de gemiddelde afwijking te berekenen voor de tweede verzameling. Deze bedraagt 4,5%. Er is hier dus een kleine daling van de gemiddelde afwijking. De bekomen α en β mogen dus overgedragen worden naar andere gelijkaardige delen van het wegennetwerk.

3 rijtijd (ms)

2 1 0 0

500

1,000

1,500

Testnummer Fig. 2: Optimalisatie voor 1800 routes met behulp van formule (5). . R EFERENCES [1] Be-mobile, http://www.be-mobile-international.com, Geraadpleegd op: 13/05/2015 [2] I. Chabini Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time, 1998 [3] A. Orda & R. Rom Shortest-path and minimum-delay algorithms in networks with time-dependent edge length, 1990

Fast and realistic route planning for GPS-devices Jeroen Verbrugghe Promoters: prof. dr. ir. Didier Colle, dr. Pieter Audenaert Supervisors: Ine Melckenbeeck, prof. dr. Jan Cnops Abstract—The actual travel times throughout the day are provided for a road network. Delays caused by traffic, accidents and a large number of cars during rush hours make that this travel time changes during the day. With this data and a time dependant variant of the Dijkstra algorithm the shortest path and real travel time can be constructed between two crossroads at a given start time. In this thesis an approximation is presented for this road network. This is necessary because it is infeasible to store all the different travel times due to memory constraints. Instead of storing all the travel times, two penalties are introduced. The first penalty that is used is the location penalty. This penalty, which is assigned to every road segment, decides the amount of delay throughout the day. The second penalty calculates the amount of delay in the entire network for every moment of the day. These two penalties will be combined to calculate an approximate travel time for each road segment at any moment of the day.

I. I NTRODUCTION HE company Be-mobile [1] provided a definition for the Belgian road network. This definition consists of the coordinates for all the intersections and the road sections that connect them. The lengths and optimal travel times are also known for all these road sections. For the road sections around the city of Ghent there is extra data provided. For all these road sections the actual travel time for each minute of the day is also known. This duration changes throughout the day because of traffic delay and road congestion. These variable travel times can be used to calculate the fastest travel time between two crossroads. by using a time-dependant variant of the Dijkstra algorithm [2], the shortest path between the two crossroads can be constructed for every minute of the day [3]. The problem with this approach is that it isn’t feasible to save all the actual travel times for the entire road network. This requires way to much memory space. In this thesis a method is presented to reduce the required memory space by not saving all the individual travel times. Instead, an approach is presented that makes an approximation of the actual travel times.

T

II. A PPROXIMATION A. Concept The actual travel times are no longer stored. Instead two penalties are introduced. the first penalty, the location penalty, is allocated to each road section. The size of this penalty is based on the amount of delay there is on the road section throughout the day. Road sections that have almost no delay receive a low penalty. Road sections with a lot of delay throughout the day receive a big penalty. The second penalty that is used is the time penalty. This penalty is assigned to every minute of the day. The size of the penalty depends on the amount of delay there is on the entire road network at the specific moment. At night, when there isn’t a lot of traffic, the penalty should be low. The penalty should

be high during the two rush ours. These two penalties are combined with the optimal travel time for each road section to calculate a new actual travel time for every moment of the day. When choosing the methods to assign the penalties, there should be paid attention to the fact that there should only be a large increase in travel time when both penalties are high. Even during the rush hours, a road on the countryside won’t have a significant increase in travel time. In the same way a road in the city won’t have a lot of delays in the middle of the night. The location penalty and time penalty can both be assigned in an absolute or relative manner. If they are calculated in an absolute way, only the amount of delay is accounted for. When they are calculated in a relative manner, the optimal travel time is also taken into account. This is because a delay of 20 seconds is more significant on a road section with an optimal travel time of 1 minute then on a road section with an optimal travel time of 5 minutes. B. Location penalty A first possible way to calculate the location penalty is described in formula (1).

L1 =

P

− Kmin ) #times

t∈T imes (K(t)

(1)

In this formula T imes is the collection of every minute of the day. The actual travel time is represented by K(t). The variable Kmin represents the optimal travel time of the road section. This method gives absolute penalties. The possible values lie between 0 and ∞. A relative variant of this method is described in formula (2). P (K(t) − Kmin ) L2 = t∈T imes (2) (#times) ∗ Kmin This method closely resembles the absolute method. There just is an extra division by the optimal travel time. Because of this the results are relative penalties. In theory, the results are still between 0 and ∞. In practice most of the penalties are between 0 and 1. There are a few exceptions with penalties up to 2,5. Most of the rural road sections have a very small penalty with this method. Roads in the centre of Ghent and entrances or exits of highways have a big penalty. C. Timepenalty The timepenalty gives an indication of the amount of delay in the entire road network for every minute of the day. An

absolute way to calculate the penalty is described in formula (3). P (Ks (t) − Ks (min)) Ts1 (t) = s∈Sections (3) #Sections In this formula Sections is the collection of all road sections of which the variable travel times are known. The actual travel time for road section s at time t is given by Ks (t). The optimal travel time for s is represented by Ks (min). This method of calculating penalties gives results between 0 and 2000. The penalties for the given road network throughout the day are shown on figure 2. Two obvious peaks can be detected on the image, These represent the two rush hours. Furthermore, the penalties during the day are always higher then the penalties at night. The timepenalty can also be calculated in a relative manner. This is shown in formula (4). This method gives penalties between 1 and 1,3 and has mostly the same shape as the absolute method. P Ks (t)/Ks (min) (4) Ts2 (t) = s∈Sections #Sections 2,000

be talked about later. A second way to approach the actual travel time is by combining the relative locationpenalty L2 and the absolute timepenalty Ts1 (t). This is shown in formula (6). K = Kopt + Ts1 (t)α ∗ Lβ2

(6)

A final way to calculate the approaching travel time is by using the relative locationpenalty L2 and the relative timepenalty Ts2 (t). The optimal travel time is multiplied by this penalty. This is shown in formula (7). K = Kopt × (Ts2 )α × (1 + L3 )β

(7)

In this formula, 1 is added to the locationpenalty. This is necessary because if the locationpenalty is zero, the approaching travel time should be equal to the optimal travel time and not to zero. It is unlikely that just adding or multiplying the penalties will lead to a good result. For this reason two variables are added:α and β. The calculated timepenalty is always raised to a power α. The calculated locationpenalty is raised to a power β. By adjusting these parameters, the impact of each of the penalties can be increased or decreased. In the next section there will be discussed how this can be used to increase the accuracy of the approximation. III. E VALUATION AND OPTIMIZATION

timepenalty

1,500

1,000

500

.

0

:0

0

0 :0

:0 00

0 20

:0

:0

0

0

:0

0 :0 0

:0 12

0 :0 08

16

:0 0

0 :0 0

:0 04

00

:0

0

:0

0

0

Fig. 1: Evolution of the timepenalty throughout the day.

D. Calculating travel times The two penalties are combined with the optimal travel time to calculate an approximate travel time for each road section at every moment. There will be three methods presented to achieve this. The first way to do this, is using the absolute locationpenalty L1 and the relative timepenalty Ts2 (t). This is illustrated in formula (5). K = Kopt + Ts2 (t)α ∗ Lβ1

(5)

In this formula K is the approached travel time and Kopt is the optimal travel time. The purpose of the variables α and β will

The methods to calculate the approximate travel time from II-D can be refined by modifying α and β. The goal is to make the difference between the actual and approximate travel time as small as possible. This can be attempted for different use cases. The first possible use case is to attempt to optimize the approximation for a single road section throughout the day. The same can be attempted for a single route between two intersections throughout the day. A different use case is to look at groups of road sections or shortest routes. Each of the elements in these groups receives a start time. To make such a group representative for the entire road network, there should be enough variance in elements. The collection should contain roads from the city and from rural areas. There should also be highways and little roads on the countryside. Finally, there should be enough difference in start times. Taking these demands in account, both the groups of road sections and routes can be constructed in almost the same way. First a collection is made of all road sections or crossroads. From these collections a road section or a start and end crossroad for a route are selected. After that the element gets assigned a start time. This time is limited between 5am and 8pm. This was decided because the travel times don’t vary much at night. For that reason, they are less interesting to take into account for the optimization. The optimization uses an evaluation function. This function decides how good the approximation matches the actual travel times. For one road section or one specific route formula (8) can be used. X D= | Kact (t) − Kapp (t) | (8) t∈T imes

The collection of all times for which evaluations is necessary is represented by T imes. The actual travel time is represented by Kact (t). The approximate travel times are shown by Kapp (t). Formula (9) should be used when optimizing for a group of routes or road sections. X D= | Kact (g) − Kapp (g) | (9) g∈Group

Here Group is the collection with the road sections or routes. The actual and approximate travel times are represented by Kact (g) and Kapp (g) for route or road section g at the given start time. The value of D represents the total difference between the actual and approximate travel times. The parameters α and β are optimal when this D-value is minimal. To achieve this both α and β get an initial value of 1. alternately one of the parameters is kept constant and a better value is searched for the other parameter. This is repeated until no better value is found for either α or β. The main use case for which the optimization will be performed is the collection of multiple routes. This is because the main goal is to get a correct approximation for a random route. De collection of routes used to optimize contains 1800 routes with an average travel time of 32 minutes. Formulas (5) and (6) give similar results after optimization. They respectively have an average deviation of 4,45% and 4,40%. Formula (7) has a slightly worse accuracy with 4,50%. In comparison: the difference between the actual travel times and the optimal travel times for the routes is 16%. Figure 2 show for formula (5) the results after optimization. The red curve represents the actual travel times, the black dots represents the approximate travel times. ·106 4 3 travel time (ms) 2 1 0 0

500

1,000

1,500

Testnumber .

Fig. 2: Optimization for 1800 routes using formula (5).

IV. TRANSFERABILITY It is interesting to look if the resulting α and β are transferable throughout the network. To test this, the road network is

divided in two equal parts. a collection of 900 routes is constructed for both parts.The optimal α and β are calculated for the first collection. After optimization the average deviation between actual and approximate travel times is 4,7%. The values found for α and β are then used for the second collection of routes. The average deviation for this group is 4,5%. The resulting difference is actually slightly lower. When the α and β are found, they can be transferred to similar parts of the road network. R EFERENCES [1] Be-mobile, http://www.be-mobile-international.com, Geraadpleegd op: 13/05/2015 [2] I. Chabini Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time, 1998 [3] A. Orda & R. Rom Shortest-path and minimum-delay algorithms in networks with time-dependent edge length, 1990

i

INHOUDSOPGAVE

Inhoudsopgave Woord vooraf Uitgebreid abstract Extended abstract Symbolen

iii

1 Inleiding

1

2 Wegennetwerk

5

2.1

Vertrekpunt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2

Aanpassingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3 Kortste weg

9

3.1

Constante kosten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2

Variabele kosten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

4 3D-voorstelling

13

5 Benadering

15

5.1

5.2

Locatiepenalties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

5.1.1

Minimum-Maximummethode . . . . . . . . . . . . . . . . . . . .

16

5.1.2

Totaalverschilmethode . . . . . . . . . . . . . . . . . . . . . . . .

17

5.1.3

Gemiddeldverschilmethode . . . . . . . . . . . . . . . . . . . . .

19

Tijdspenalty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

5.2.1

Absolute methode . . . . . . . . . . . . . . . . . . . . . . . . . .

20

5.2.2

Relatieve methode . . . . . . . . . . . . . . . . . . . . . . . . . .

21

INHOUDSOPGAVE

5.3

ii

Kost berekenen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

5.3.1

Absolute combinaties

. . . . . . . . . . . . . . . . . . . . . . . .

23

5.3.2

Relatieve combinaties . . . . . . . . . . . . . . . . . . . . . . . .

23

6 Evaluatie en optimalisatie

25

6.1

Eén straatdeel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

6.2

Meerdere straatdelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

6.3

Eén route . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

6.4

Meerdere routes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

6.5

Evaluatie meerdere routes . . . . . . . . . . . . . . . . . . . . . . . . . .

33

7 Analyse van de oplossing

37

7.1

Andere verzameling routes . . . . . . . . . . . . . . . . . . . . . . . . . .

37

7.2

Dal- en piekuren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

7.3

Dorp en stad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

7.4

Overdraagbaarheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

7.5

Aantal routes in de verzameling . . . . . . . . . . . . . . . . . . . . . . .

44

8 Applicatie

47

8.1

Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

8.2

Kortste routes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

8.3

Benaderende kosten . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

8.4

Andere packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

9 Conclusie en uitbreidingen

51

9.1

Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

9.2

Mogelijke uitbreidingen . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

A Voorstelling File

55

B Grafieken bij Totaal Verschil Locatiestraffen

59

C Grafieken bij Straatdeel optimalisatie

61

Lijst van figuren

63

iii

Symbolen

Symbolen

Kopt

De optimale rijtijd van een straatdeel.

K

De rijtijd van een straatdeel.

L1

De relatieve locatiepenalty berekend met de minimummaximummethode.

L2

De absolute locatiepenalty berekend met de totaalverschilmethode.

L3

De relatieve locatiepenalty berekend met de totaalverschilmethode.

L4

De relatieve locatiepenalty berekend met de gemiddeldverschilmethode.

Ts1 (t)

De absolute tijdspenaltymethode.

Ts2 (t)

De relatieve tijdspenaltymethode. .

Symbolen

iv

1

INLEIDING

Hoofdstuk 1

Inleiding Routeplanners en GPS-toestellen zijn hulpmiddelen die in de huidige samenleving niet meer weg te denken zijn. Deze toestellen worden elke dag gebruikt om bestuurders de optimale route te tonen naar hun bestemming. Er bestaan wel verschillende interpretaties over wat nu precies de optimale route is. Zo kan het bijvoorbeeld over de kleinste afstand gaan, maar kan het ook over de kortste reistijd gaan. Figuren 1.1 en

Figuur 1.1: Kortste route

Figuur 1.2: Snelste route

1.2 tonen aan dat dit niet noodzakelijk dezelfde weg is. Op de figuren werd de optimale route bepaald tussen twee straten. Op figuur 1.1 werd als criterium de kortste afstand gebruikt. Figuur 1.2 gebruikt daarentegen de kleinste tijdsduur. De route op figuur 1.1 loopt recht door het centrum van Gent, hier zijn veel lagere snelheidslimieten dan op de autosnelweg die op de tweede figuur gebruikt wordt. Daarom zal deze weg toch een langere tijdsduur hebben. Tegenwoordig wordt ook nog met andere factoren rekening gehouden. Zo kan de gebruiker bijvoorbeeld instellen om zo lang mogelijk op snelwegen te willen rijden. Ook kunnen moderne routeplanners hun route in realtime aanpassen indien er zich verkeers-

INLEIDING

2

problemen voordoen verder op de geplande weg. Ten slotte kan ook rekening gehouden worden met de werkelijke rijtijd van straten. Het zal immers niet op elk moment van de dag even lang duren om een route af te leggen. Figuur 1.3 toont bijvoorbeeld de veranderende rijtijden voor een straat in het centrum van Gent. Wat opvalt is dat de

Figuur 1.3: Verloop van de werkelijke rijtijden doorheen de dag. De blauwe curve is de werkelijke rijtijd, de groene de optimale rijtijd. De rijtijden worden weergegeven in milliseconden.

rijtijd tijdens de ochtend- en avondspits veel groter is dan de rijtijd ’s nachts. In deze scriptie zal dieper worden ingegaan op hoe deze data gebruikt kunnen worden om de route met de snelste rijtijd te bepalen. Als voor alle straten in een wegennetwerk op elk moment van de dag de werkelijke rijtijd gekend is, kan heel nauwkeurig de verwachte rijtijd berekend worden. Natuurlijk is de werkelijke rijtijd voor de toekomst nog niet gekend, maar door data van de vorige dagen te combineren kan er toch voor elk moment van de dag een voorspelling voor gemaakt worden. Het probleem hierbij is dat er enorm veel geheugenruimte nodig is om al deze rijtijden op te slaan. Indien voor elke minuut van de dag een rijtijd wordt bijgehouden zijn dat 1440 tijden per straatdeel. Dit kan aanzienlijk verminderd worden door enkel de tijdstippen bij te houden waarop de rijtijd verandert, maar dan nog is er veel geheugenruimte hiervoor nodig. Het is dan ook niet haalbaar om deze gegevens op te slaan voor alle straten van bijvoorbeeld België. Dit probleem wordt aangepakt in deze scriptie. Er wordt gezocht naar een manier om deze wisselende rijtijden te benaderen, maar zonder deze tijden effectief op te slaan. Het eerste wat besproken wordt in hoofdstuk 2 is het wegennetwerk en de tijdsinfor-

3

INLEIDING

matie die gebruikt wordt om deze benadering te bepalen. In dit hoofdstuk wordt ook besproken welke aanpassingen er op het wegennetwerk zijn uitgevoerd. Hoofdstuk 3 gaat over het zoeken van de kortste weg. Eerst wordt besproken hoe dit gebeurt indien geen rekening gehouden wordt met de variabele kosten van straten. Daarna wordt besproken hoe dit gebeurt als er hier wel rekening mee gehouden wordt. Hoofdstuk 4 introduceert een nieuwe voorstelling voor het wegennetwerk. Deze voorstelling wordt gebruikt om de gebruikte benaderingsmethode uit te leggen. Dit gebeurt in hoofdstuk 5. Eerst wordt de benadering zelf uitgelegd, daarna wordt er dieper ingegaan op de verschillende onderdelen ervan. Hoofdstuk 6 beschrijft hoe de benadering geoptimaliseerd kan worden voor verschillende situaties. Eenmaal deze optimale benadering bepaald is wordt deze in hoofdstuk 7 getest voor verschillende situaties. In hoofdstuk 8 wordt extra uitleg gegeven over de applicatie die ontwikkeld werd om alles te testen. Hoofdstuk 9 geeft tenslotte een conclusie en beschrijft enkele mogelijke uitbreidingen.

INLEIDING

4

5

WEGENNETWERK

Hoofdstuk 2

Wegennetwerk 2.1

Vertrekpunt

In deze scriptie wordt gewerkt met een wegennetwerk van België, Nederland, Duitsland, Frankrijk en Luxemburg. Voor elk van de straten in dit wegennetwerk is de optimale rijtijd gekend. Dit is hoe lang het duurt om de volledige straat af te leggen als er geen verkeer is. De straten waarvan deze info beschikbaar is, zijn blauw gekleurd op figuur 2.1. Voor de straten in en rond Gent is er nog extra informatie beschikbaar. Voor elk van deze straten is de effectieve rijtijd gekend voor elke minuut van de dag. Deze gegevens, verkregen van het bedrijf Be-Mobile, zijn berekend door verschillende technieken te combineren. Ten eerste wordt er gebruik gemaakt van trackingsystemen. Deze systemen volgen auto’s die gebruik maken van bepaalde GPS- en GSM-toestellen. Zo kan voor elke auto zijn afgelegde route en corresponderende rijtijd afgeleid worden. Verder staan er langs grote wegen vaste sensors opgesteld. Deze meten vooral de intensiteit en densiteit van het verkeer in een bepaald straatdeel. De intensiteit is het aantal auto’s dat per uur over dat stuk weg rijdt. De densiteit is het aantal auto’s per kilometer weg. Door de routes, rijtijden, intensiteit en densiteit te combineren wordt voor elk straat een werkelijke rijtijd berekend [3]. Omdat de tijdsdata enkel beschikbaar zijn van straten in en rond Gent zullen de benaderingen dan ook voornamelijk hier getest worden. Deze straten zijn blauw gekleurd op figuur 2.2

2.2 Aanpassingen

Figuur 2.1: Volledig netwerk

2.2

6

Figuur 2.2: Netwerk met tijdsdata

Aanpassingen

In de applicatie wordt het wegennetwerk voorgesteld door een graaf. Deze graaf is gericht. Voor een straat met tweerichtingsverkeer zijn er dus twee verbindingen. Door gebruik te maken van een graaf kunnen heel wat graaf-algoritmes eenvoudig op het wegennetwerk toegepast worden. Verder in deze thesis zal veel gezocht worden naar de kortste weg tussen twee knopen. Daarom is het Kosaraju-algoritme op de graaf toegepast [1]. Dit algoritme deelt de oorspronkelijke graaf op in zijn verschillende sterk samenhangende componenten. Binnen een sterk samenhangende component is voor elk willekeurig knopenpaar een weg gegarandeerd. Er wordt verder gewerkt met de grootste sterk samenhangende component. Het oorspronkelijk wegennetwerk bestaat uit 720147 knopen, de grootste sterk samenhangende component uit 717604. Door enkel met deze grootste sterk samenhangende component te werken is het zeker dat elke poging om een weg te vinden tussen twee knopen succesvol zal zijn. Het algoritme van Kosaraju maakt gebruik van een stack. Deze wordt initieel leeg gemaakt. Daarna wordt de stack opgevuld op de volgende manier: zo lang de stack niet alle knopen van de graaf bevat, wordt een nieuwe willekeurige knoop gekozen die nog niet op de stack zit. Vanaf deze knoop wordt de graaf depth first afgelopen. Telkens wanneer een knoop afgewerkt is, wordt deze op de stack geduwd. Wanneer alle knopen op de stack zitten wordt de richting van alle verbindingen omgedraaid. Alle knopen worden nu gemarkeerd als onbezocht. Zolang de stack niet leeg is,

7

2.2 Aanpassingen

wordt nu de bovenste knoop van de stack gehaald. Is deze onbezocht, dan wordt deze knoop depth first afgelopen. Alle knopen die hierbij worden tegengekomen behoren tot dezelfde sterk samenhangende graaf.

2.2 Aanpassingen

8

9

KORTSTE WEG

Hoofdstuk 3

Kortste weg

3.1

Constante kosten

Er zal verder veel gezocht worden naar de kortste weg tussen twee knopen. Dit is niet de route met de kleinste afstand, maar wel de route die het minst tijd in beslag neemt. Indien enkel rekening gehouden wordt met constante kosten kan het algoritme van Dijkstra hiervoor gebruikt worden [5]. Dit is het geval wanneer er enkel met de optimale rijtijden gewerkt wordt. Het algoritme van Dijkstra wordt weergegeven in algoritme 1. Als parameters krijgt de methode de graaf en de starten eindknoop. Het algoritme maakt gebruik van drie datastructuren. De eerste is een tabel van tijdsduren. Deze houdt per knoop de huidige minimale tijd vanaf de startknoop bij. Er wordt ook gebruik gemaakt van een tabel die voor elke knoop de voorganger bijhoudt voor deze minimale afstand. Eenmaal de kortste weg is gevonden kan via deze tabel het pad worden opgesteld. Dit gebeurt door te vertrekken van de eindknoop en herhaaldelijk de vorige knoop te nemen totdat de startknoop bereikt is. Ten slotte wordt nog een wachtrij gebruikt. In deze wachtrij komen alle knopen die nog geen kortste weg hebben. De wachtrij wordt bovendien gesorteerd op basis van tijd vanaf de startknoop. Hierdoor wordt telkens de volgende knoop bepaald die de kleinste totale rijtijd heeft vanaf de startknoop.

3.1 Constante kosten

10

Algorithm 1 Kortste afstand met Dijkstra 1:

function bepaalKortsteAfstand(Graaf m, Knoop start, Knoop einde)

2:

PriorityQueue teVerwerkenKnopen

3:

Node[] vorigeKnoop

4:

long[] tijdsduren

5:

for all Knoop k ∈ map.Knopen() do

6: 7: 8: 9: 10: 11:

if k ! = start then tijdsduren[k] ← ∞ else tijdsduren[k] ← 0 teVerwerkenKnopen.add(k) end if

12:

end for

13:

while teV erwerkenKnopen.size() > 0 do

14:

Knoop k ← teV erwerkenKnopen.f irst()

15:

if k = einde then

16:

# kortste weg gevonden

17:

break

18: 19:

else for all Knoop buur ∈ k.buren() do

20:

long tijdsduur ← (tijdsduren[k] + k.tijdT ot(buur))

21:

if tijdsduur < tijdsduren[buur] then

22:

tijdsduren[buur] ← tijdsduur

23:

vorige[buur] ← k

24:

teVerwerkenKnopen.add(buur) end if

25: 26: 27:

end for end if

28:

end while

29:

# Geen weg van Start naar Einde. Onmogelijk dankzij algoritme van Kosaraju

30:

assert false

31:

end function

11

3.2 Variabele kosten

3.2

Variabele kosten

Het algoritme van Dijkstra gaat ervan uit dat de kost van alle verbindingen constant blijft. In het gebruikte wegennetwerk is dit echter niet zo. Elke verbinding heeft een TimeProvider. Deze houdt voor een verbinding voor elk tijdstip de actuele rijtijd bij. Het standaard algoritme van Dijkstra kan dan niet meer gebruikt worden. Het volstaat ook niet om de kost op te vragen voor het tijdstip waarop in het startpunt vertrokken wordt. Het zal immers al een tijd duren om bij het startpunt van de verbinding te komen, regel 19 uit algoritme 1 moet dus zeker aangepast worden. Dit wordt weergegeven in algoritme 2. Ook moet nu het starttijdstip meegegeven worden als parameter voor de methode. Algorithm 2 Tijdsafhankelijke variant van het Dijkstra algoritme 1:

huidigT ijdstip ← startT ijdstip + tijdsduren[k]

2:

tijdsduur ← tijdsduren[k] + k.tijdT ot(buur, huidigT ijdstip)

Het werken met tijdsafhankelijke kosten brengt extra problemen met zich mee. Zo is het mogelijk dat iemand op een later tijdstip vertrekt eerder de volledige verbinding heeft afgelegd. Het First-In-First-Out-principe is dus niet altijd geldig. Als dit kan, is het soms voordelig om te wachten in knopen. In [6] wordt beschreven dat als wachten toegelaten wordt in knopen, dit probleem nog steeds oplosbaar is met het Dijkstra algoritme. Er moeten dan extra gegevens worden opgeslagen in de knopen. In [6] wordt ook beschreven dat als wachten niet toegelaten wordt in knopen en het FIFO-principe niet geldig is, het probleem NP-hard is. Het wegennetwerk waar verder mee gewerkt wordt, voldoet wel aan het FIFO-principe. Chabini zegt in [4] dat hiervoor wel de tijdsafhankelijke variant van het Dijkstraalgoritme gebruikt mag worden. Dit FIFO-principe wordt bekomen door voor elk van de verbindingen te controleren of per minuut de werkelijke rijtijd niet met meer dan 60s daalt. Verder is de rijtijd gekend per minuut. Om tot de rijtijd te komen per seconde wordt tussen twee minuten ge¨ınterpoleerd. Als verder in deze scriptie verwezen wordt naar een route tussen twee punten, dan is deze berekend met dit alogritme.

3.2 Variabele kosten

12

13

3D-VOORSTELLING

Hoofdstuk 4

3D-voorstelling Een wegennetwerk bestaat uit een verzameling van straten en kruispunten. Deze straten kunnen nog in kleinere delen worden opgedeeld: de straatdelen. Een straatdeel is een verbinding tussen twee kruispunten. Ieder straatdeel heeft ook een optimale rijtijd. Dit is de tijd om van het ene kruispunt naar het andere te rijden als er geen verkeersproblemen zijn. Verder wordt dit vaak de kost van een straatdeel genoemd. Een kruispunt heeft een co¨ ordinaat, uitgedrukt in lengte- en breedtegraad. Voor de eenvoud worden hiervoor X en Y gebruikt. Dit zorgt dat een wegennetwerk in twee dimensies kan worden voorgesteld, zoals op bijvoorbeeld kaarten in een atlas gebeurt. Dit wordt ge¨ıllustreerd in figuur 4.1. Dit model houdt geen rekening met de variatie in reistijd. De werkelijke rijtijd van een straat verandert echter doorheen de dag. Indien hier rekening mee moet worden gehouden volstaat een model in twee dimensies niet meer. Daarom wordt er een derde dimensie aan toegevoegd: de tijd. In plaats van een kaart met de optimale rijtijd voor elk straatdeel, bestaan er nu verschillende kaarten. Elk van deze kaarten heeft dezelfde straten en kruispunten maar een verschillende kost voor de straten. Deze kunnen in de voorstelling boven elkaar worden gelegd. Zo wordt een voorstelling in drie dimensies bekomen met de volgende assen: de X-, Y- en Tijdsas. Dit wordt weergegeven op figuur 4.2. In deze voorstelling kunnen verkeersproblemen door files voorgesteld worden als een uitgerekte bol. Als voorbeeld wordt de ochtendspits van een stad gebruikt. De eerste verkeershinder zal ontstaan bij het begin van de spits, in een ovaal rond het centrum van de stad. Naarmate de tijd verder gaat, zal deze ovaal groter worden, tot hij op een

3D-VOORSTELLING

14

bepaald moment een maximum bereikt. Op dat moment is er de grootste hoeveelheid file. Daarna zal de ovaal weer in grootte afnemen totdat zo goed als alle verkeersproblemen door de file weg zijn. Dit principe wordt voor de stad Gent ge¨ıllustreerd in bijlage A. Het grote nadeel van dit model is dat er enorm veel geheugenruimte nodig is om al deze verschillende kosten op te slaan. Op elke laag moeten alle effectieve kosten per straatdeel opgeslagen worden, en voor elke minuut van de dag een laag.

Figuur 4.1: 2D-voorstelling

Figuur 4.2: Lagen in de 3D-voorstelling

15

BENADERING

Hoofdstuk 5

Benadering Er wordt nu geprobeerd om een model te maken dat gelijkaardig is aan de werkelijkheid, maar veel kleiner in geheugenomvang. Dit kan bekomen worden door niet alle effectieve reistijden voor elk moment op te slaan. Wel zal een benadering gebruikt worden voor de effectieve kost door aan elke verbinding op elk moment een penalty toe te kennen. Deze penalty bestaat uit twee delen: een locatie- en een tijdspenalty. Afzonderlijk hebben deze twee penalties geen grote invloed. Op drukke wegen zal er immers om 2u ‘s nachts weinig verkeershinder zijn. Ook zal zelfs tijdens de spitsuren op een plattelandsweg geen vertraging zijn. Pas als de twee penalties samen groot zijn zal er een grote vertraging en dus ook een grote totale penalty zijn. Om de locatiepenalties te bepalen moet per straatdeel gekeken worden hoeveel vertraging er is op een hele dag. Straatdelen waar gedurende de dag veel vertragingen zijn moeten een grotere penalty krijgen dan een straat waarvan de kost op elk moment van de dag gelijk is. In de 3D-voorstelling komt dit overeen met alle kaarten samen te drukken en een afdruk hiervan te maken op één kaart. Het zelfde principe wordt ook toegepast voor de tijdspenalties. Per minuut wordt gekeken hoeveel vertraging er is op het hele wegennetwerk. Als er veel vertragingen zijn, zoals bijvoorbeeld tijdens de ochtendspits, moet er een grotere penalty zijn dan bijvoorbeeld ‘s nachts, wanneer er zo goed als geen vertragingen zijn. Op de 3D-voorstelling komt dit overeen met aan elke kaart afzonderlijk één straf toe te kennen. Deze penalties kunnen op twee mogelijke methoden berekend worden: absoluut en relatief. De absolute methode kijkt naar hoeveel tijd er effectief verloren gaat door

5.1 Locatiepenalties

16

vertragingen, onafhankelijk van de normale rijtijden. De relatieve methode gaat eerder kijken naar hoeveel dit tijdsverschil is ten opzichte van de kortste rijtijd van een verbinding. Zo zal een vertraging van één minuut minder impact hebben op een stuk weg waarbij de optimale rijtijd 10 minuten is, dan wanneer deze 2 minuten is. Verder in dit hoofstuk worden eerst een aantal mogelijkheden gegeven om de locatiepenalty te berekenen. Vervolgens wordt gekeken hoe de tijdspenalty kan opgesteld worden. Tenslotte zal besproken worden hoe er uit deze penalties rijtijden kunnen berekend worden.

5.1

Locatiepenalties

Hier zullen een aantal mogelijkheden besproken worden voor het bepalen van de locatiepenalties. Deze locatiepenalties geven per straatdeel aan hoeveel vertraging er is gedurende de hele dag. In formules zal deze penalty steeds L genoemd worden. Verder zal bij elke methode een afbeelding van de straten in en rond Gent getoond worden. Elke straat krijgt hierbij een kleur afhankelijk van zijn berekende locatiepenalty. Straten die groen gekleurd zijn hebben een heel lage penalty, terwijl straten in het rood een heel grote penalty hebben.

5.1.1

Minimum-Maximummethode

Een eerste mogelijke relatieve benadering kijkt enkel naar de verhouding van de minimale en maximale rijtijd. Ze kan voorgesteld worden als: L1 = 1 −

M in M ax

(5.1)

Hierbij is M in de minimum rijtijd en M ax de maximum rijtijd van de straat. Deze methode zal een straf geven tussen 0 en 1. Hierbij is 0 geen enkele vertraging over heel de dag, terwijl 1 oneindig veel vertraging is. Figuur 5.1 toont deze methode toegepast op de omgeving van Gent. De kleuren op deze figuur worden gegeven op een schaal van 0 tot 1. Het valt op dat er veel straten zijn met een oranje en rode kleur. Dit zijn straten waarbij er een groot verschil is tussen de minimale en maximale rijtijd. Het probleem met deze methode is dat er geen rekening gehouden wordt met hoe lang deze vertraging duurt en of er nog op andere momenten

17


Figuur 5.1: Straffen bij Minimum-Maximummethode. Een groene straat heeft een lage straf, gele straten een gemiddelde straf en rode straten een grote straf.

van de dag vertragingen zijn. Deze methode is dus vooral handig om te kijken op welke plaats er een echt groot verschil is tussen minimale en maximale rijtijd. Ook al geeft deze methode niet echt een goed beeld, kunnen er toch al enkele conclusies uit getrokken worden. Zo zijn vooral straatdelen binnen het stadscentrum en op drukke snelwegen rood gekleurd. Plattelandswegen zijn daarentegen echter voornamelijk groen. Er zijn binnen de stad dus veel grotere verschillen in rijtijd dan op het platteland.

5.1.2

Totaalverschilmethode

Een tweede mogelijke benadering is om op elk moment van de dag het verschil te nemen tussen de effectieve rijtijd en de minimale rijtijd. Om hieruit de locatiepenalty af te leiden wordt dan het gemiddelde genomen van al deze verschillen:

L2 =

P

t∈T ijden (K(t)

− Kmin )

totale aantal tijden

(5.2)


18

Hierbij is T ijden de verzameling van alle tijdstippen waarvoor er tijdsdata beschikbaar zijn. Verder is K(t) de effectieve rijtijd voor het tijdstip t, Kmin is de optimale kost voor het straatdeel. Deze methode geeft een juister beeld dan de eerste omdat deze rekening houdt met elk moment waarop er vertraging is. Ze kan waarden opleveren van 0 tot oneindig. Ze is bovendien absoluut, omdat alle effectieve vertragingen opgeteld worden. Deze formule kan nog uitgebreid worden om naar een relatieve benadering te gaan. De penalty wordt dan nog extra gedeeld door de minimale tijd:

L3 =

P

t∈T ijden (K(t)

− Kmin )

(totale aantal tijden) ∗ Kmin

(5.3)

Door de relatieve benadering te gebruiken is het makkelijker om verschillende straten met elkaar te vergelijken. Deze methode kan in theorie nog altijd waarden aannemen van 0 tot oneindig, maar in de praktijk liggen zo goed als alle waarden tussen 0 en 1, met wat uitschieters tot maximaal 2,5.

Figuur 5.2: Straffen bij de relatieve Totaalverschilmethode. Een groene straat heeft een lage straf, gele straten een gemiddelde straf en rode straten een grote straf.

19

5.2 Tijdspenalty

Figuur 5.2 maakt gebruik van deze relatieve methode. Het grootste deel van de straten is nu groen. Het centrum van Gent heeft nog steeds een gele tot rode kleur, wat wijst op veel problemen. Verder zijn ook opritten en afritten van de meeste snelwegen niet groen gekleurd. Deze methode geeft een beter beeld weer van de werkelijkheid dan de Minimum-Maximumstraf. De hoge penalties worden immers toegekend aan straatdelen waar er gedurende grote tijd veel vertraging is. In bijlage B wordt voor enkele straatdelen de actuele rijtijden doorheen de dag weergegeven. De straatdelen werden zo geschaald zodat de optimale rijtijd 10s is. Ze worden weergegeven volgens stijgende locatiestraf L. Het valt duidelijk op dat voor een stijgende L, de afwijking ten opzichte van de optimale kost steeds toeneemt.

5.1.3

Gemiddeldverschilmethode

Deze methode is een variant op deze uit 5.1.1. Ze houdt echter geen rekening met het maximale verschil, maar berekent eerst het gemiddelde van alle kosten. Hiervan wordt de verhouding genomen met de kleinste kost: L4 = 1 −

Kmin P

Ki totale aantal tijden

(5.4)

i∈T ijden

Deze methode zal penalties bekomen die tussen 0 en 1 liggen. Wat opvalt uit figuur 5.3 is dat de spreiding van de penalties veel kleiner is. Er is veel minder, bijna geen rood meer zichtbaar. Het grootste deel van de bekomen penalties ligt tussen de 0 en 0,4. Deze methode kan gebruikt worden om te detecteren op welke plaatsen er gedurende de hele dag vertragingen zijn. Straten waar er slechts één moment van de dag veel problemen voorkomen worden hierop veel minder zwaar afgerekend dan bij de totaalverschilmethode uit 5.1.2

5.2

Tijdspenalty

De tijdsstraf (verder Ts genoemd) bepaalt hoeveel vertragingen er zijn in het gehele netwerk op een bepaald tijdstip.

5.2 Tijdspenalty

20

Figuur 5.3: Straffen bij gemiddeldverschilmethode. Een groene straat heeft een lage straf, gele straten een gemiddelde straf en rode straten een grote straf.

5.2.1

Absolute methode

Een eerste methode om een tijdspenalty toe te kennen is om voor alle straten de kost op het tijdstip te verminderen met de minimale kost, dit wordt dan vervolgens gedeeld door het totaal aantal straten. Ts1 (t) =

P

− Ks (min)) aantal straten

s∈Straten (Ks (t)

(5.5)

Waarbij Straten de verzameling is van alle straten waarvan de tijdsdata gekend is. Ks (min) is de minimale kost van straat s. Verder is t het tijdstip waarvoor de straf berekend wordt. Deze methode zal dus tijdspenalties geven tussen 0 en oneindig. Alle vertragingen worden opgeteld, dus is het een absolute methode. Uit figuur 5.4 kan afgeleid worden dat de straf in het gebruikte wegennetwerk ligt tussen 0 en 2000. Als de grafiek van dichterbij bekeken wordt, kunnen twee pieken vastgesteld worden: de eerste rond 7u30 en de 2de rond 16u30. Dit komt mooi overeen met de ochtend- en avondspits. Verder kan opgemerkt worden dat de straf overdag veel hoger ligt dan deze ‘s nachts. Ook dit kan logisch verklaard worden: ‘s nachts rijden er veel minder auto‘s dan tijdens de dag.

21

5.2 Tijdspenalty

Figuur 5.4: Penalties bij de absolute methode

5.2.2

Relatieve methode

De relatieve methode neemt de som van de verhoudingen tussen de effectieve rijtijd en de optimale rijtijd.

Ts2 (t) =

P

s∈Straten Ks (t)/Ks (min)

aantal straten

(5.6)

Deze methode kan in theorie waarden aannemen tussen 1 en oneindig, maar in de praktijk neemt deze waarden aan tussen 1 en 1,25.

Figuur 5.5: Penalties bij de relatieve methode

Wat opvalt aan deze twee methoden is dat het resultaat een heel gelijkaardige vorm

5.3 Kost berekenen

22

heeft. Het grootste verschil is een lichte daling van de relatieve methode om 16u30. Deze komt bij de absolute methode niet voor. Verder is de verhouding tussen de straf overdag en tijdens een piek bij de absolute methode kleiner dan bij de relatieve.

5.3

Kost berekenen

De twee penalties worden samengevoegd met de optimale kost om zo voor elk straatdeel op elk moment een nieuwe rijtijd te bekomen. De manier waarop deze combinatie gebeurt, is afhankelijk van de gebruikte methodes. Er zijn hier twee verschillende mogelijkheden. Als een van de twee penalties absoluut is, dan worden de penalties met elkaar vermenigvuldigd en opgeteld bij de optimale kost. Dit wordt weergegeven in formule (5.7). In deze formule is Straf het product van de twee penalties. Dit wordt verder besproken in 5.3.1.

K = Kopt + Straf

(5.7)

Als beide penalties echter relatief zijn, en dus de totale straf ook, dan moet deze vermenigvuldigd worden met de optimale kost. Dit wordt getoond in formule (5.8). Ook hier is Straf het product van de twee penalties. Deze straf wordt met 1 verhoogd want indien er geen straf is, wordt de kostprijs van een straatdeel de optimale rijtijd. Op deze relatieve combinatie wordt verder ingegaan in 5.3.2.

K = Kopt × (1 + Straf )

(5.8)

Omdat het onwaarschijnlijk is dat enkel optellen of vermenigvuldigen tot een zeer goed resultaat zullen leiden worden hier twee extra parameters ingevoegd: α en β. De berekende tijdsstraf zal tot een macht α verheven worden, idem voor de locatiestraf en β. Door deze α en β aan te passen wordt de impact van de tijds- of locatiestraf aangepast.

23

5.3.1

5.3 Kost berekenen

Absolute combinaties

Om bij deze combinaties tot de berekende rijtijd te komen worden deze opgeteld bij de optimale kost. Ze zullen dan ook allemaal van volgende vorm zijn: K = Kopt + Tsα × Lβ

(5.9)

De eerste manier om dit te realiseren is door gebruik te maken van een absolute locatiepenalty en een relatieve tijdspenalty. Dit kan bijvoorbeeld door gebruik te maken van locatiepenalty L2 uit formule 5.2. Als tijdsstraf wordt dan T s2 gebruikt. Hiernaar zal verder verwezen worden als methode met absolute tijden relatieve locatiestraf. Dit wordt weergegeven in formule (5.10). K = Kopt + Ts2 (t)α × Lβ2

(5.10)

Een andere manier om hiertoe te komen is door een relatieve locatiepenalty en een absolute tijdspenalty te gebruiken. Dit gebeurt door gebruik te maken van locatiepenalty L3 beschreven in formule (5.3). Deze kan gecombineerd worden met tijdspenaltymethode T s1 . Zo ontstaat er weer een combinatie van absolute en een relatieve straf. Deze methode zal verder methode met relatieve tijden absolute locatiestraf genoemd worden. Formule (5.11) geeft deze methode weer.

K = Kopt + Ts1 (t)α × Lβ3

5.3.2

(5.11)

Relatieve combinaties

Deze combinatie bestaat uit twee relatieve penalties. De optimale kost wordt hier dan ook mee vermenigvuldigd: K = Kopt × (Ts2 )α × (1 + L3 )β

(5.12)

Dit kunnen we bekomen door locatiepenaltymethode L3 met één te verhogen. Hierdoor wordt de totale kost nooit kleiner dan de optimale kost. Verder wordt ook de relatieve tijdspenaltybepalingsmethode gebruikt. Hiernaar zal verder verwezen worden als relatieve tijd en locatie straf methode.

5.3 Kost berekenen

24

25

EVALUATIE EN OPTIMALISATIE

Hoofdstuk 6

Evaluatie en optimalisatie De methodes om de kost te bepalen uit het vorig hoofdstuk kunnen nog verder verfijnd worden. De α en β moeten zo bepaald worden dat de benadering zo goed mogelijk overeen komt met de werkelijkheid. Dit kan op verschillende niveaus getest worden. Ten eerste zal geprobeerd worden om voor één straatdeel doorheen de dag de rijtijd zo goed mogelijk te laten overeenstemmen met de werkelijke rijtijd. Vervolgens zal hetzelfde gebeuren, maar dan voor één route bestaande uit meerdere straatdelen. Ten slotte zal een verzameling van verschillende routes, elk met een eigen starttijdstip bekeken worden. Hier wordt voor alle routes samen een zo goed mogelijke benadering gezocht. Voor elk van deze niveaus wordt een evaluatieformule ingevoerd. Met deze formule kan berekend worden hoe veel de benadering verschilt van de werkelijkheid. De parameters α en β worden aangepast totdat deze formule een minimum waarde terug geeft. Voor de gebruikte test zijn de α en β dan ideaal.

6.1

E´ en straatdeel

Het eerste geval waarvoor geëvalueerd zal worden is het niveau van één straatdeel. Voor elke minuut van de dag wordt het verschil genomen tussen de werkelijke rijtijd en de berekende rijtijd. Dit verschil moet zo klein mogelijk zijn. Er kan gebruik gemaakt worden van formule (6.1). D=

X

t∈T ijden

| Kw (t) − Kb (t) |

(6.1)

6.1 Eén straatdeel

26

Waarbij T ijden de verzameling van tijden doorheen de dag is. De werkelijke kost voor tijd t wordt voorgesteld door Kw (t). De kost berekend met bovenstaande methodes voor tijd t wordt weergegeven door Kb (t). Hierbij is D dus het totale verschil tussen de werkelijke en berekende kost. De parameters α en β zijn optimaal wanneer D minimaal is. Het optimaliseren van α en β verloopt voor alle optimalisatiemethoden op dezelfde manier. Eerst krijgen α en β een startwaarde. Vervolgens wordt β constant gehouden, en α aangepast tot een minimum D-waarde bekomen wordt. Dit door bij α een waarde op te tellen. Deze waarde, verder de stap genoemd, begint bij 1. De D-waarde bekomen met de nieuwe α wordt dan vergeleken met de vorige. Is deze groter, dan wordt de stap er nog eens bij opgeteld. Dit wordt herhaald zolang de D-waarde kleiner is dan de vorige. Is de nieuwe D-waarde groter, dan wordt de stap gehalveerd en wisselt ze van teken. Dit wordt herhaald zolang de absolute waarde van de stap groter is dan 0,0001. Daarna wordt α op deze waarde constant gehouden en β op dezelfde manier aangepast tot weer een minimum D-waarde gevonden is. Deze twee stappen worden herhaald tot de D-waarde na optimalisatie voor zowel α en β niet meer verder daalt. Dit is dan de optimale waarde. Dit proces wordt weergegeven op figuren 6.1 en 6.2. Na elke optimalisatie voor α of β wordt een lijn getrokken tussen de nieuwe en de oude α en β. Op de x- en y-as worden α en β weergegeven, op de z-as de overeenkomstige D-waarde. De twee figuren behoren tot dezelfde optimalisatie. Figuur 6.1 toont een zijaanzicht waarop kan gezien worden dat de D-waarde eerst snel daalt. De daling verkleint altijd tot uiteindelijk een minimum wordt bekomen. Figuur 6.2 toont een bovenaanzicht van deze optimalisatie. Hierop kan duidelijk gezien worden dat er telkens slechts één van de twee parameters wijzigt.

Omdat slechts voor één straatdeel geoptimaliseerd wordt, is het onwaarschijnlijk dat dit een goede benadering is van het hele netwerk. Optimaliseren op dit niveau is dan ook niet echt interessant. Ter illustratie staan in bijlage C de grafieken voor elk van de kostbepalingsmethodes. Deze zijn met de hierboven beschreven methode geoptimaliseerd.

27

6.2 Meerdere straatdelen

Figuur 6.1: Zijaanzicht voor een

Figuur 6.2: Bovenaanzicht van een

optimalisatie

6.2

optimalisatie

Meerdere straatdelen

Een betere manier om te optimaliseren is door gebruik te maken van meerdere straatdelen. Om representatief te zijn voor het hele netwerk moet er ten eerste variatie zitten in de geografische locatie van de straten. Zo moeten er zowel in het centrum als op het platteland straatdelen aanwezig zijn. Verder moet er ook variatie zijn in het type weg. Er moeten stukken snelweg aan bod komen, evenals een aantal kleine wegen. Ten slotte moet er ook variatie zijn op gebied van starttijdstip. Zo moeten er straatdelen aanwezig zijn waar wordt vertrokken ’s nachts, tijdens de twee spitsmomenten en overdag. Rekening houdend met deze vereisten moet een verzameling van straatdelen bepaald worden. Hierin kan nog afgewisseld worden in het aantal straatdelen dat tot deze verzameling behoort. Er zal verder getest worden voor verzamelingen van verschillende groottes. Om een verzameling van straatdelen samen te stellen wordt uit alle straten waarvoor de tijdsdata gekend is een aantal straatdelen willekeurig gekozen. Aan elk van deze straten wordt dan een willekeurig starttijdstip toegekend. Dit tijdstip bevindt zich tussen 5u ‘s ochtends en 8u ‘s avonds. Er wordt niet gekeken naar tijdstippen in het midden van de nacht omdat hier zo goed als geen variatie in rijtijd is. Deze tijdstippen zijn dus minder interessant om te bestuderen. Om de verschillende groottes van verzamelingen met elkaar te kunnen vergelijken met elkaar wordt geëvalueerd met formule (6.2). D=

P

| Kw (s) − Kb (s) | #Straatdelen

s∈Straatdelen

(6.2)

6.2 Meerdere straatdelen

28

Hierbij is Straatdelen de verzameling van straatdelen waarover geoptimaliseerd wordt. Verder zijn Kw (s) en Kb (s) respectievelijk de werkelijke en berekende rijtijd van straatdeel s op het gegeven starttijdstip. Deze formule geeft voor de verzameling het gemiddelde verschil in rijtijd tussen de werkelijke en berekende rijtijd. De optimale α en β worden op dezelfde manier bepaald als in 6.1. Figuur 6.3 toont voor verschillende groottes van verzamelingen straatdelen de resultaten van de optimalisatie. Voor elk van de verschillende groottes wordt 50 keer een willekeurige verzameling gemaakt. Daarna wordt geoptimaliseerd met behulp van formule (6.2). Na de optimalisatie worden de D-waarden weergegeven. Een eerste opmerking die hier kan worden gemaakt is dat indien er geoptimaliseerd wordt voor een verzameling van één route, het gemiddeld verschil altijd 0 is. In dit geval kan de optimalisatie immers omgevormd worden tot één vergelijking met twee onbekenden, waarvoor altijd een oplossing kan gevonden worden. Verder is er voor kleinere verzamelingen een veel grote spreiding op de mogelijke waarden. Dit komt omdat bij kleinere verzamelingen elke straat veel harder doorweegt op het gemiddelde. Een straatdeel waarvoor de bekomen optimalisatie niet zo goed is weegt dan veel harder door op de totale straf. Verschillende verzamelingen van 500 of meer straatdelen sluiten zo veel dichter bij elkaar aan. Zelfs voor grotere verzamelingen zijn er wel nog uitspringers die een veel groter gemiddeld verschil hebben.

Figuur 6.3: Optimalisatie voor meerdere straatdelen.

29

6.3

6.3 Eén route

E´ en route

Een heel andere benadering is optimaliseren voor routes. In plaats van te optimaliseren voor verzamelingen van straatdelen wordt gekeken naar de snelste route tussen twee knopen. Dit is in feite ook een verzameling van straatdelen. De verschillende straatdelen horen nu echter wel bij elkaar in plaats van willekeurig verspreid over het wegennetwerk. Formule (6.1) kan ook hiervoor gebruikt worden om α en β te optimaliseren. In plaats van de kost van een straatdeel te nemen, moet nu de kost genomen worden om van het startpunt naar het eindpunt te gaan. De reistijd wordt berekend met de tijdsafhankelijke variant van Dijkstra beschreven in 3.2. Het is interessanter om voor een route te optimaliseren. Er wordt immers gebruik gemaakt van meer straatdelen, waardoor een beter beeld van de werkelijkheid verkregen wordt. De route die gebruikt werd om te optimaliseren is een route die vertrekt ten westen van Gent en eindigt in Destelbergen. Deze route werd getest voor elke minuut van de dag. De gebruikte route wordt getoond op figuur 6.4.

Figuur 6.4: Het starten eindpunt van de testroute. Het startpunt is de linkse cirkel, het eindpunt de rechtse.

6.3 Eén route

30

Figuur 6.5: Optimalisatie voor één route bij de methode met absolute tijd en relatieve locatie

Figuur 6.6: Optimalisatie voor één route bij de methode met relatieve tijd en absolute locatie.

31

6.3 Eén route

Figuur 6.7: Optimalisatie voor één route bij de relatieve tijd en locatie methode

Figuren 6.5, 6.6 en 6.7 geven de resultaten weer van deze optimalisatie voor de verschillende methoden die eerder zijn besproken. Voor elke minuut van de dag wordt de rijtijd weergegeven. De blauwe curve is op elke grafiek de werkelijke rijtijd. Deze is berekend aan de hand van de beschikbare tijdsdata. De paarse curve op figuur 6.5 maakt gebruik van de methode met absolute tijd en relatieve locatie. De oranje curve op figuur 6.6 maakt gebruik van de tweede absolute kostbepalingsmethode: de methode met relatieve tijd en absolute locatie. Figuur 6.7 maakt daarentegen gebruikt van de relatieve tijd en locatie methode. Dit is terug te vinden op de gele curve. De curves nemen ongeveer dezelfde vorm aan als de effectieve waarden. Wel kan opgemerkt worden dat de berekende waarden veel minder variëren dan de effectieve waarden. Dit kan verklaard worden door de vorm van de tijdsstraf. De vorm van alle curves komen overeen met Figuren 5.4 en 5.5. Afhankelijk van de α parameter wordt deze vorm versterkt of afgevlakt. Figuur 6.8 toont de verschillende methodes samen. Hierbij kan opgemerkt worden dat de gele en paarse curve vrij dicht bij elkaar aansluiten. Ze starten ‘s nachts beide iets boven de effectieve waarden. Tijdens de ochtendspits stijgen de rijtijden, maar minder scherp dan bij de werkelijke waarden. Tot aan de avondspits komen de waarden vrij goed overeen, waarna ze samen met de effectieve waarden weer dalen, om ‘s nachts

6.4 Meerdere routes

32

Figuur 6.8: De verschillende methodes samen

weer iets hoger te liggen. De absolute tijd en relatieve locatie methode die wordt voorgesteld door de oranje curve begint ‘s ochtends iets onder de werkelijke waarden, maar volgt tijdens de ochtendspits bijna perfect de werkelijke rijtijden. Het piekmoment komt bij de benadering op een iets later tijdstip, maar de waarde ligt even hoog als de werkelijke waarden. Tot aan de avondspits volgt deze ook mooi de werkelijke waarden. Tijdens de avondspits is er wel een iets te grote stijging. Naar ‘s nachts toe komen de twee curves weer mooi op elkaar te liggen. De paarse en gele curve zijn veel vlakker dan de oranje. Ze reageren veel minder op de stijging en daling van de werkelijke rijtijd. Het totale verschil, berekend aan de hand van formule (6.1), is ook veel kleiner.

6.4

Meerdere routes

Om te zorgen dat de benadering een zo goed mogelijk beeld geeft van de werkelijkheid, kan het best gebruik gemaakt worden van een verzameling met meerdere routes. Binnen deze routes moet dan variatie zitten op gebied van starttijd, lengte en geografische locatie van starten eindpunten. Zo moeten er zowel in steden, als op het platteland

33

6.5 Evaluatie meerdere routes

meerdere routes zijn. ‘s Nachts variëren de rijtijden minder dan overdag. Deze tijdstippen zijn daardoor minder belangrijk. Om een uniforme verzameling van routes te verkrijgen worden alle kruispunten in en rond Gent aan een verzameling toegevoegd. Uit deze verzameling wordt telkens een willekeurig starten eindpunt gekozen. Aan deze route wordt ook een tijdstip toegekend. Dit is het moment waarop vanuit het startpunt vertrokken wordt. Er wordt geoptimaliseerd voor 1800 routes. Dit komt overeen met twee routes voor elke minuut van 5u ‘s ochtends tot 20u ‘s avonds. Figuren 6.9 en 6.10 tonen al deze starten eindpunten.

Figuur 6.9: Alle startpunten

Figuur 6.10: Alle eindpunten

Optimalisatie gebeurt met formule (6.3). Deze lijkt op de formule die gebruikt is bij optimalisatie voor één straat of route. X D=

r∈Routes

| Kw (r) − Kb (r) |

(6.3)

Hierbij is Kw (r) de werkelijke kost van route r op zijn gegeven starttijdstip. Kb (r) is

de kost berekend met de benaderingsmethode. In de volgende sectie zullen voor de verschillende kostbepalingsmethodes de resultaten voor deze optimalisatie besproken worden.

6.5

Evaluatie meerdere routes

Tabel 6.1 toont voor de verschillende kostbepalingsmethoden de resultaten voor de optimalisatie met meerdere routes. De waarden voor de optimale α en β worden ook


34

weergegeven. De totale rijtijd voor alle 1800 routes is ongeveer 988 uur. Dit zorgt voor een gemiddelde rijtijd van 32 minuten. Figuren 6.11, 6.12 en 6.13 geven deze resultaten grafisch weer. In de figuren toont de blauwe curve telkens de werkelijke rijtijd. De punten er rond tonen de berekende rijtijden. De routes werden gesorteerd op werkelijke rijtijd om zo een overzichtelijk beeld te bekomen. Als tabel 6.1 geanalyseerd wordt, blijkt dat de twee absolute methodes nagenoeg dezelfde nauwkeurigheid hebben. De relatieve methode heeft een iets slechtere nauwkeurigheid dan de absolute methoden, maar benadert nog steeds heel goed de werkelijkheid. Wat ook nog opvalt, is dat de α-waarde voor de eerste methode heel groot is. Dit komt omdat als tijdsstraf formule Ts2 gebruikt wordt. Uit figuur 5.5 blijkt dat er slechts een klein verschil is tussen de minimale en maximale relatieve straf. Dit wordt gecompenseerd door de kleine strafverschillen tot een hoge macht α te verheffen. Tabel 6.1: Vergelijking van de verschillende kostbepalingsmethoden Methode

Abs. Loc. & Rel. Tijd

Rel. Loc & Abs. Tijd

Rel. Loc & Tijd

Alpha

5.296875

1.23828

0.859375

Beta

0.947266

0.91016

0.597656

Totaal verschil

43u 56’

44u 1’

44u 57’

gemiddeld Verschil

4,451%

4,440%

4,53%

Figuur 6.11: Optimalisatie voor meerdere routes voor de absolute locatie en relatieve tijd methode.

35


Figuur 6.12: Optimalisatie voor meerdere routes voor de relatieve locatie en absolute tijd methode.

Figuur 6.13: Optimalisatie voor meerdere routes voor de relatieve locatie en tijd methode.


36

37

ANALYSE VAN DE OPLOSSING

Hoofdstuk 7

Analyse van de oplossing Eenmaal α en β bepaald zijn voor de 1800 routes uit hoofdstuk 6, kan worden gekeken hoe goed deze een benadering geven voor routes die niet gebruikt werden om te optimaliseren. Een eerste vergelijking die wordt gemaakt is met een andere verzameling van 1800 willekeurig gekozen routes. Vervolgens wordt er gekeken of er een verschil is tussen routes in dalen piekuren. Daarna wordt een vergelijking gemaakt tussen routes in de stad en op het platteland. Hierna worden nog twee testen uitgevoerd waarvoor een aantal nieuwe α- en β-waarden berekend worden. Er wordt eerst gekeken of de bekomen oplossing overdraagbaar is. Daarna wordt gekeken welke invloed de grootte van de routeverzameling heeft.

7.1

Andere verzameling routes

Er wordt op dezelfde manier als in 6.4 een verzameling van 1800 routes aangemaakt. In plaats van voor deze routes een optimale α en β te bepalen, worden de α en β die bepaald zijn in het vorige hoofdstuk gebruikt. De test bestaat uit het vergelijken van de werkelijke rijtijd en de berekende rijtijd. Figuur 7.1 toont de resultaten van deze test. Ze lijkt sterk op de resultaten na optimalisatie van de eerste routeverzameling. Er is een zeer minimale daling van de correlatiecoëfficient. 0,98890 bij de geoptimaliseerde routes tegenover 0,98886 bij de nieuwe verzameling. Er is zo goed als geen verschil bij de niet geoptimaliseerde routes omdat het gaat om een groot aantal routes. Zo goed als alle straatdelen die voorko-

7.1 Andere verzameling routes

38

Figuur 7.1: Resultaten voor een andere verzameling routes

men in de nieuwe routeverzameling komen ook voor in de originele verzameling. Dit wordt getoond op figuur 7.2. De straatdelen die rood gekleurd zijn komen zowel in de oorspronkelijke en de nieuwe routeverzameling voor. De bekomen α en β kunnen dus goed gebruikt worden voor elke mogelijke route in het netwerk.

Figuur 7.2: Gemeenschappelijke straatdelen tussen de twee routeverzamelingen.

39

7.2

7.2 Dal- en piekuren

Dal- en piekuren

Deze test bestaat uit 1000 willekeurig gekozen routes. Er wordt voor elk van de routes eens gestart om 2u ‘s nachts en eens om 7u ‘s ochtends. Er wordt dus gekeken hoe goed de oplossing zich gedraagt wanneer er zo goed als geen vertraging is, en wanneer er enorm veel vertraging is.

Figuur 7.3: Vertrek om 2u ‘s morgens

Figuur 7.3 toont alle rijtijden voor de routes met vertrektijd 2u. Het eerste dat opvalt hierbij is dat zo goed als alle berekende waarden boven de werkelijke waarden liggen. Dit komt omdat ‘s nachts de werkelijke rijtijd meestal gelijk is aan de optimale rijtijd. Bij het berekenen van de kost met een benaderende methode wordt er echter altijd een straf opgeteld bij deze optimale kost. Voor wegen met een kleine locatiestraf is die niet groot, en deze zullen dus dichter bij de werkelijke rijtijd liggen. Wegen met een grote locatiestraf krijgen een grotere straf, deze zullen dus een groter verschil hebben met de werkelijke tijd.

7.3 Dorp en stad

40

Figuur 7.4: Vertrek om 7u ‘s morgens

Op figuur 7.4 staan de rijtijden voor dezelfde routes, maar met vertrektijd 7u. Dit is 15 minuten voor het ergste punt van de ochtendspits waardoor er gedurende de hele route vertragingen zullen zijn. Het eerste dat hieruit kan opgemerkt is een stijging van de gemiddelde rijtijd ten opzichte van het vertrek om 2u. Om 2u is de gemiddelde rijtijd 27 minuten en 32 seconden tegenover 36 minuten en 6 seconden wanneer men start om 7u. De berekende waarden liggen nu meer verspreid rond de werkelijke waarden. Er liggen wel opvallend meer waarden onder de werkelijke waarden. Dit is omdat voor de echt grote pieken, de berekende waarde onvoldoende mee stijgt. De correlatiecoëfficient tussen de twee curven om 2u ‘s nachts is 0,992. Om 7u ‘s ochtends is deze 0,985. De berekende waarden om 2u komen dus beter overeen met de werkelijke waarden dan deze om 7u. Dit kan verklaard worden door de kleinere gemiddelde vertraging.

7.3

Dorp en stad

Deze test kijkt of er een verschil is tussen een route gereden op het platteland en een route gereden in een stad. Er wordt dus een vergelijking gemaakt van routes met een gemiddeld lage locatiestraf tegenover routes met een gemiddeld hoge locatiestraf. Om dit te realiseren worden er twee even grote zones aangeduid. De ene zone omkadert de stad Gent en de andere een stuk platteland.

41

7.3 Dorp en stad

Figuur 7.5: De twee zones. De bovenste is de zone in de stad, de onderste is de zone op het platteland.

Figuur 7.6: Routes op het platteland

Binnen deze zones wordt voor elke minuut van 5u tot 20u een willekeurige route gekozen. Voor elk van de tests zijn er dus 900 routes. Figuur 7.7 toont de resultaten voor de testen op het platteland. De berekende waarden liggen verspreid rond de werkelijke waarden. Er zijn ongeveer evenveel waarden die hoger liggen als er waarden zijn die lager zijn. Het gemiddelde van de berekende rijtijden ligt wel iets onder dat van de werkelijke rijtijden.

7.4 Overdraagbaarheid

42

Figuur 7.7: Routes in de stad

Bij de test in de stad zien we een veel grotere spreiding dan bij de test op het platteland. In de stad is de correlatiecoëfficient 0,950. Op het platteland is deze 0,990. Dit komt omdat er op het platteland bijna enkel over wegen wordt gereden die niet tot weinig veranderen in de tijd. Deze wegen met onveranderlijke kosten kunnen veel beter benaderd worden dan de wegen in een stad die, doorheen de dag, enorm veel variëren in rijtijd. Dit komt doordat de locatiestraf hiervan bijna 0 is. Hierdoor wordt zelfs tijdens de spitsuren bijna geen straf opgeteld bij de optimale rijtijd.

7.4

Overdraagbaarheid

De test uit 7.1 maakt gebruik van andere routes, maar gebruikt dezelfde straatdelen als de geoptimaliseerde routes. Het is ook interessant om na te gaan of de benadering overdraagbaar is. Er zal dus gekeken worden of als een α en β bepaald zijn voor een verzameling routes, deze ook een goede benadering geven voor een verzameling routes die geen gemeenschappelijke straatdelen hebben met de verzameling waarvoor geoptimaliseerd wordt. Dit wordt getest door twee routeverzamelingen te definiëren die niet overlappen. De omgeving rond Gent wordt in twee driehoeken verdeeld. Hierbij is erop gelet dat in beide driehoeken dezelfde omgevingen zaten. Zo zit er in beide driehoeken een stuk van het centrum van Gent, autosnelwegen en platteland. Binnen

43

7.4 Overdraagbaarheid

de driehoeken worden 900 routes op dezelfde manier als in 6.4 gekozen, één voor elke minuut tussen 5u en 20u. De startpunten van de routes zijn te zien op figuren 7.8 en 7.9.

Figuur 7.8: De startpunten van de

Figuur 7.9: De startpunten van de

routes in de bovenste driehoek

routes in de onderste driehoek

De parameters α en β worden geoptimaliseerd voor de routes in de bovenste driehoek. De resultaten hiervan worden getoond in figuur 7.10. Deze resultaten komen ongeveer overeen met de optimalisatie gedaan in 6.4. Er is een gemiddelde afwijking van 4,72% per route.

Figuur 7.10: Optimalisatie bij de bovenste verzameling routes

Eenmaal α en β bepaald zijn voor de bovenste driehoek, worden deze overgenomen en geëvalueerd op de onderste driehoek. De werkelijke en berekende rijtijden met deze α en β voor de onderste driehoek worden weergegeven op figuur 7.11. Deze grafiek neemt ongeveer de zelfde vorm aan als de vorige. Er is hier een gemiddeld verschil

7.5 Aantal routes in de verzameling

44

van 4,5%. Dit is zelfs iets lager dan het verschil bij de bovenste verzameling. Er kan dus besloten worden dat eenmaal α en β berekend zijn, deze overdraagbaar zijn naar andere gelijkaardige delen van het wegennetwerk. Hier moet wel opgelet worden dat de structuur van het wegennetwerk ongeveer gelijk is. De optimalisatie vanuit een omgeving met enkel stad zal niet goed overeen komen met een omgeving op het platteland.

Figuur 7.11: R bij de onderste route

7.5

Aantal routes in de verzameling

Een van de belangrijkste parameters bij het bepalen van de optimale waarden voor α en β is het aantal routes dat gebruikt wordt in de routeverzameling. In deze test zal onderzocht worden hoeveel routes er zeker moeten worden gebruikt om altijd tot een goede oplossing te komen. Voor deze test werd gebruik gemaakt van de 900 routes uit de bovenste driehoek. De startpunten hiervan worden getoond op figuur 7.10. Uit deze verzameling wordt tien keer een deelverzameling genomen met een kleiner aantal routes. Dit aantal routes staat op de x-as in grafiek 7.12. Voor deze deelverzameling wordt dan de optimale α en β bepaald. Deze α en β worden dan gebruikt om met behulp van formule (6.3) het totale verschil te berekenen. Bij het bepalen van de deelverzameling wordt geprobeerd met verschillende tijdstippen rekening te houden. Er wordt gebruik

45


gemaakt van pseudocode 3. Op deze manier worden de routes evenwichtig verdeeld doorheen de dag. De waarde van offset krijgt voor elk van de tien pogingen een andere waarde, zo worden verschillende verzamelingen bekomen. Algorithm 3 Bepalen of een route gebruikt wordt 1:

function optimaliseer(int aantalTeGebruikenRoutes, int offset)

2:

teller ← 0

3:

f ilter ← routeT ests.size() ÷ aantalT eGebruikenRoutes

4:

for all RouteT est rt ∈ routeT ests do

5: 6:

if ((teller mod f ilter) = of f set) then # gebruik route

7:

end if

8:

teller+ = 1

9:

end for

10:

end function

Het resultaat van deze test wordt getoond op figuur 7.12. Uit deze figuur kunnen een aantal conclusies getrokken worden. Zo daalt de spreiding van de resultaten naar gelang er meer routes gebruikt worden. De verschillende resultaten voor de test van 90 routes liggen zo goed als allemaal op elkaar. Bij de resultaten voor de testen met minder dan 10 routes liggen deze veel verder van elkaar. Wat wel opvalt is dat zelfs voor een heel klein aantal routes een goede benadering kan gemaakt worden. Het is echter geen goed idee om voor een klein aantal routes te optimaliseren want de kans dat er een slecht resultaat bekomen wordt, is veel groter.


Figuur 7.12: Optimalisatie bij kleinere routeverzameling

46

47

APPLICATIE

Hoofdstuk 8

Applicatie De applicatie is geprogrammeerd in Java. Voor het maken van enkele grafieken zijn ook Perl en Python scripts gemaakt. Eerst zal dieper ingegaan worden op enkele van de belangrijkste packages van de applicatie. Zo wordt eerst het model besproken. Daarna wordt beschreven hoe de kortste routes op verschillende manieren kunnen bepaald worden. Vervolgens wordt nog getoond hoe de verschillende penalties gecombineerd worden tot berekende kosten. Ten slotte wordt de inhoud en functie van een aantal andere packages ook nog besproken.

8.1

Model

Het model van de applicatie bestaat uit een vijftal klassen. Dit wordt weergegeven op figuur 8.1. De graaf van het wegennetwerk wordt bijgehouden in de klasse Map. De kruispunten worden bijgehouden in de Node klasse. De straatdelen worden voorgesteld door de Link klasse. Elke Link houdt 2 Nodes bij: het starten eindpunt van het straatdeel. De Links waarvoor tijdsdata gekend is, hebben nog een extra veld: een TimeProvider. Deze houdt de werkelijke rijtijden voor elk moment bij. Door deze in een SortedMap te steken, moeten niet alle rijtijden bijgehouden worden. Enkel de tijdstippen waarop de rijtijd verandert moeten dan opgeslagen worden. De MapFactory stelt de volledige Map op. Aan de methode giveMap kunnen 3 parameters meegegeven worden. Zo kan bepaald worden of de werkelijke rijtijden moeten toegevoegd worden aan de Links. Verder wordt ook bepaald of het algoritme van Kosaraju moet worden

8.2 Kortste routes

48

toegepast. Ten slotte is er nog de mogelijkheid om van de werkelijke rijtijden een glijdend gemiddelde te maken. Dit werd oorspronkelijk gedaan om de ruis op de tijdsdata te verminderen. Voor het volledige netwerk is dit echter niet haalbaar, omdat er dan te veel geheugenruimte nodig is.

Figuur 8.1: Klassendiagram van het model

8.2

Kortste routes

De code voor het algoritme van Dijkstra is te vinden in het Pathfinder package. Ze bestaat uit één abstracte klasse en meerdere implementaties. In de abstracte Pathfinder klasse is de volledige logica voor het algoritme van Dijkstra te vinden. Ze maakt echter gebruik van de abstracte methode getWeight(Link). Deze methode wordt door de subklassen op verschillende manieren ingevuld. Zo gebruikt de DistancePathfinder de afstand als gewicht. De TimeDependentPathFinder gebruikt als gewicht de werkelijke rijtijden. De WeightProviderPathFinder wordt gebruikt om de kortste afstand te berekenen met de benaderende rijtijden.

8.3

Benaderende kosten

Zoals op figuur 8.2 wordt weergegeven is de AbstractWeightProvider is het toegangspunt voor het opvragen van de berekende kosten. De PathFinder kan hieraan de gewichten vragen voor een bepaalde link op een specifiek tijdstip. Deze bestaat uit 3 componenten. Zo kan aan de ILocationPenaltyProvider de locatiepenalty van een specifieke Link gevraagd worden. Aan de ITimePenaltyProvider kan de tijdspenalty voor een specifiek moment gevraagd worden. Deze worden gecombineerd in één van de implementaties

49

8.4 Andere packages

van de AbstractWeightProvider. Afhankelijk van de gebruikte implementaties worden deze opgeteld of vermenigvuldigd met de optimale rijtijd. De WeightProviderFactory leest uit een configuratiebestand welke implementatie er gebruikt moet worden. Uit dit configuratiebestand wordt ook gehaald welke locatie- en tijdspenalties moeten gebruikt worden. Indien op deze straffen geen extra bewerkingen moeten uitgevoerd worden, worden deze in de DefaultLocationPenaltyProvider of DefaultTimePenaltyProvider opgeslagen. Deze initialiseren in de constructor een tabel waarin al de penalties worden opgeslagen.

Figuur 8.2: Klassendiagram voor de Weightproviders.

8.4

Andere packages

ParameterOptimalisation en ParameterTesters In deze packages zitten de klassen die gebruikt worden voor de bepaling van de optimale α en β. In de ParameterOptimalisation package zitten de mechanismes om de α en β aan te passen zoals beschreven in hoofdstuk 6.1. In de ParameterTesters package zitten de verschillende manieren om de D-waarde te berekenen.

Guis.LocationPenalties De klassen hierin worden gebruikt voor de grafische weergave van de locatiepenalties. Om de kaart weer te geven wordt het JMapViewer package gebruikt [2]. Om hieraan extra features toe te voegen zijn verschillende klassen van de JMapViewer overschreven.

8.4 Andere packages

50

PenaltyDetection De inhoud hiervan bestaat uit 2 packages. In de LocationPenaltyDetection package staan de klassen die verantwoordelijk zijn voor het berekenen van de locatiepenalties uit hoofdstuk 5.1. In de timePenaltyDetection package staan de klassen die verantwoordelijk zijn voor het berekenen van de tijdspenalties uit hoofdstuk 5.2.

Properties Hierin staat het configuratiebestand met de locatie voor de netwerkdefinitie. Verder staat hierin ook het configuratiebestand dat bepaalt welke kostbepalingsmethode gebruikt moet worden. In de package properties.propertiesProviders staan de klassen die deze configuratiebestanden beschikbaar maken voor de rest van de applicatie.

DataSetGeneration De klassen uit deze package worden gebruikt om de verschillende datasets te genereren. Deze datasets kunnen ingeladen worden als Routetest of LinkTest. Ze worden onder andere gebruikt voor de optimalisatie met meerdere straatdelen of routes en de tests uit hoofdstuk 7.

51

CONCLUSIE EN UITBREIDINGEN

Hoofdstuk 9

Conclusie en uitbreidingen 9.1

Conclusie

In deze scriptie wordt geprobeerd een oplossing te vinden voor de grote geheugenvereisten die nodig zijn om nauwkeurig routes te vinden indien rekening gehouden wordt met tijdsafhankelijke kosten. Omdat deze kost niet consistent verandert doorheen de dag moet immers voor elk moment de tijd bijgehouden worden. Door het gebruik van een gesorteerde map kan dit enigszins beperkt worden tot de tijdstippen waarop de werkelijke rijtijd verandert. Dit is echter nog steeds niet haalbaar voor het volledige Belgische wegennetwerk. Om dit probleem op te lossen werd er afgestapt van het idee om alle tijdsdata bij te houden. In de plaats krijgen alle straatdelen een penalty toegekend. Deze bepaalt, per straatdeel, het aantal en de grootte van de vertragingen doorheen de dag. Dit wordt gecombineerd met een tijdspenalty. Deze tijdspenalty bepaalt op elk tijdstip hoeveel vertragingen er zijn op het volledige wegennetwerk. Er zijn 4 manieren voorgesteld om de locatiepenalties te berekenen. Hieruit zijn uiteindelijk één absolute en één relatief locatiepenalty gekozen waarmee verder gewerkt wordt: locatiepenalty L2 en L3 . Deze werden gekozen omdat ze een grote spreiding in waarden hebben. Verder geven deze locatiepenalties ook het beste beeld van de werkelijkheid weer: straatdelen met veel vertraging verkrijgen bij deze manieren altijd hoge straffen. Het tegenovergestelde gebeurt voor straten met weinig vertraging: deze krijgen een zeer lage straf.

9.2 Mogelijke uitbreidingen

52

Voor de tijdspenalties kwamen twee methodes aan bod: één absolute en één relatieve. De resulterende tijdspenalties kennen hetzelfde verloop op een factor na. De beide tijdspenalties worden dan ook verder gebruikt. De verschillende penalties worden op drie manieren gecombineerd tot kostbepalingsmethoden. De eerste twee gebruiken één absolute en één relatieve straf, de derde methode gebruikt twee relatieve straffen. Bij deze kostbepalingsmethoden wordt telkens een parameter α en β ingevoegd. Door het aanpassen van deze α en β kan de invloed van één van de twee penalties vergroot of verkleind worden. De verschillende kostbepalingsmethoden kunnen geëvalueerd worden in verschillende situaties. Zo kan gekeken worden hoe goed de kostbepalingsmethode overeen komt met de werkelijke rijtijden voor één straatdeel doorheen de hele dag. Hetzelfde kan bepaald worden voor één route. Er kan ook gekeken worden naar een verzameling van straatdelen of routes. Elk van de elementen in deze verzameling krijgt dan ook een starttijdstip. Voor elk van deze situaties kunnen de optimale α en β bepaald worden. Met deze optimale waarden is het verschil tussen een kostbepalingsmethode en de werkelijke rijtijden zo klein mogelijk. Bij analyse van de optimalisatie voor een verzameling van meerdere routes blijkt dat alle kostbepalingsmethodes een goede benadering maken van de werkelijke rijtijden. Ze hebben elk een verschil van ongeveer 4,5% van de totale rijtijd. De benodigde geheugenruimte is voor deze benadering veel kleiner. In plaats van voor elk straatdeel de verschillende rijtijden bij te houden moeten nu slechts twee waarden bijgehouden worden: de optimale rijtijd en de locatiepenalty. Voor het gehele netwerk wordt dit aangevuld met 1440 waarden: één tijdspenalty voor elke minuut van de dag. Ten koste van een gemiddelde afwijking van 4,5% voor een willekeurige route wordt dus een aanzienlijke geheugenruimte bespaard.

9.2

Mogelijke uitbreidingen

Er zijn een aantal mogelijke uitbreidingen om nog nauwkeuriger de werkelijke rijtijden te benaderen. Een eerste manier, die geen extra geheugenruimte vereist, is door gebruik te maken van tijdsdata van meer dan één dag. Door op voorhand de rijtijden

53


van meerdere dagen te combineren aan de hand van een gemiddelde of mediaan kunnen onregelmatigheden door bijvoorbeeld ongevallen op kleinere wegen beter weggewerkt worden. Hierbij moet er wel op gelet worden welke dagen gecombineerd worden. Zo zal de vertraging in het weekend en op feestdagen een ander patroon volgen dan op een doorsnee weekdag.

Een tweede mogelijkheid om de benadering nauwkeurig te houden, is door meer dan één tijdspenalty bij te houden. Zo kunnen de straatdelen geklasseerd worden volgens type weg. Er kan bijvoorbeeld voor alle autostrades, wegen in het centrum en de wegen op het platteland een aparte tijdspenalty bepaald worden. Elk van deze tijdspenalty’s moet dan ook een eigen parameter α krijgen. Optimaliseren moet dan gebeuren voor elke verzameling straatdelen afzonderlijk. Indien hiermee rekening gehouden moet worden moet elk straatdeel zijn type bijhouden. Per ingevoerd type moeten ook 1440 tijdspenalties en één factor α extra bijgehouden worden. Dit gaat dus ten koste van geheugenruimte.

Gelijkaardig aan de vorige uitbreiding kunnen meerdere locatiepenalties ingevoerd worden. Zo kan een dag ingedeeld worden in verschillende delen. Voor elk deel kan dan een aparte locatiestraf berekend worden. Zo kan bijvoorbeeld een dag ingedeeld worden in 5 delen: ‘s nachts, ochtendspits, overdag, avondspits en ‘s avonds. Elk van deze groepen krijgt dan een eigen factor β. De optimale α en β berekenen moet dan gebeuren per tijdsdeel. Dit vereist wel extra geheugenruimte. Per deel dat wordt toegevoegd moet voor elk straatdeel een extra waarde worden bijgehouden. Het aantal delen dat gekozen wordt moet afhangen van de beschikbare geheugenruimte.

Tenslotte kunnen de verschillende uitbreidingen nog gecombineerd worden met elkaar. Er kunnen meerdere locatiepenalty’s en tijdspenalty’s samen voorkomen. De uitdaging hierbij ligt dan bij het optimaliseren. Er moet een combinatie gemaakt worden van elk type weg voor de tijdspenalty en elk tijdsdeel voor de locatiepenalty. Voor elk van deze combinaties moet dan apart de optimale α en β berekend worden.


54

55

VOORSTELLING FILE

Bijlage A

Voorstelling File

Figuur A.1: Gent om 5u30 ’s ochtends. Straten in het rood hebben een grote vertraging.

Figuur A.2: Gent om 6u ’s ochtends. Straten in het rood hebben een grote vertraging.

VOORSTELLING FILE

56

Figuur A.3: Gent om 7u ’s ochtends. Straten in het rood hebben een grote vertraging.

Figuur A.4: Gent om 7u30 ’s ochtends. Dit is het moment met het meeste vertragingen. Straten in het rood hebben een grote vertraging.

57

VOORSTELLING FILE

Figuur A.5: Gent om 8u30 ’s ochtends. Straten in het rood hebben een grote vertraging.

Figuur A.6: Gent om 9u30 ochtends. Straten in het rood hebben een grote vertraging.

VOORSTELLING FILE

58

59

GRAFIEKEN BIJ TOTAAL VERSCHIL LOCATIESTRAFFEN

Bijlage B

Grafieken bij Totaal Verschil Locatiestraffen

Figuur B.1: L=0,02

Figuur B.2: L=0,27

GRAFIEKEN BIJ TOTAAL VERSCHIL LOCATIESTRAFFEN

Figuur B.3: L=0.65

Figuur B.4: L=1,40

60

61

GRAFIEKEN BIJ STRAATDEEL OPTIMALISATIE

Bijlage C

Grafieken bij Straatdeel optimalisatie

Figuur C.1: Straatdeel optimalisatie met de methode met relatieve tijd en absolute locatie

Figuur C.2: Straatdeel optimalisatie met de methode met absolute tijd en relatieve locatie

GRAFIEKEN BIJ STRAATDEEL OPTIMALISATIE

Figuur C.3: Straatdeel optimalisatie met relatieve tijd en locatie methode

62

63

LIJST VAN FIGUREN

Lijst van figuren 1.1

Kortste route . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Snelste route . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.3

Verloop van de werkelijke rijtijden doorheen de dag. De blauwe curve is de werkelijke rijtijd, de groene de optimale rijtijd. De rijtijden worden weergegeven in milliseconden. . . . . . . . . . . . . . . . . . . . . . . . .

2

2.1

Volledig netwerk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2

Netwerk met tijdsdata . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

4.1

2D-voorstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

4.2

Lagen in de 3D-voorstelling . . . . . . . . . . . . . . . . . . . . . . . . .

14

5.1

Straffen bij Minimum-Maximummethode. Een groene straat heeft een lage straf, gele straten een gemiddelde straf en rode straten een grote straf. 17

5.2

Straffen bij de relatieve Totaalverschilmethode. Een groene straat heeft een lage straf, gele straten een gemiddelde straf en rode straten een grote straf. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3

18

Straffen bij gemiddeldverschilmethode. Een groene straat heeft een lage straf, gele straten een gemiddelde straf en rode straten een grote straf. .

20

5.4

Penalties bij de absolute methode . . . . . . . . . . . . . . . . . . . . . .

21

5.5

Penalties bij de relatieve methode . . . . . . . . . . . . . . . . . . . . . .

21

6.1

Zijaanzicht voor een optimalisatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

LIJST VAN FIGUREN

6.2

64

Bovenaanzicht van een optimalisatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

6.3

Optimalisatie voor meerdere straatdelen. . . . . . . . . . . . . . . . . . .

28

6.4

Het starten eindpunt van de testroute. Het startpunt is de linkse cirkel, het eindpunt de rechtse. . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.5

Optimalisatie voor één route bij de methode met absolute tijd en relatieve locatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.6

29

30

Optimalisatie voor één route bij de methode met relatieve tijd en absolute locatie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

6.7

Optimalisatie voor één route bij de relatieve tijd en locatie methode . .

31

6.8

De verschillende methodes samen . . . . . . . . . . . . . . . . . . . . . .

32

6.9

Alle startpunten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

6.10 Alle eindpunten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

6.11 Optimalisatie voor meerdere routes voor de absolute locatie en relatieve tijd methode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

6.12 Optimalisatie voor meerdere routes voor de relatieve locatie en absolute tijd methode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

6.13 Optimalisatie voor meerdere routes voor de relatieve locatie en tijd methode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

7.1

Resultaten voor een andere verzameling routes . . . . . . . . . . . . . .

38

7.2

Gemeenschappelijke straatdelen tussen de twee routeverzamelingen. . .

38

7.3

Vertrek om 2u ‘s morgens . . . . . . . . . . . . . . . . . . . . . . . . . .

39

7.4

Vertrek om 7u ‘s morgens . . . . . . . . . . . . . . . . . . . . . . . . . .

40

7.5

De twee zones. De bovenste is de zone in de stad, de onderste is de zone op het platteland. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

7.6

Routes op het platteland . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

7.7

Routes in de stad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

7.8

De startpunten van de routes in de bovenste driehoek . . . . . . . . . .

43

65

LIJST VAN FIGUREN

7.9

De startpunten van de routes in de onderste driehoek . . . . . . . . . . .

43

7.10 Optimalisatie bij de bovenste verzameling routes . . . . . . . . . . . . .

43

7.11 R bij de onderste route . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

7.12 Optimalisatie bij kleinere routeverzameling . . . . . . . . . . . . . . . .

46

8.1

Klassendiagram van het model . . . . . . . . . . . . . . . . . . . . . . .

48

8.2

Klassendiagram voor de Weightproviders. . . . . . . . . . . . . . . . . .

49

A.1 Gent om 5u30 ’s ochtends. Straten in het rood hebben een grote vertraging. 55 A.2 Gent om 6u ’s ochtends. Straten in het rood hebben een grote vertraging. 55 A.3 Gent om 7u ’s ochtends. Straten in het rood hebben een grote vertraging. 56 A.4 Gent om 7u30 ’s ochtends. Dit is het moment met het meeste vertragingen. Straten in het rood hebben een grote vertraging. . . . . . . . . . .

56

A.5 Gent om 8u30 ’s ochtends. Straten in het rood hebben een grote vertraging. 57 A.6 Gent om 9u30 ochtends. Straten in het rood hebben een grote vertraging. 57 B.1 L=0,02 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

B.2 L=0,27 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

B.3 L=0.65 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

B.4 L=1,40 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

C.1 Straatdeel optimalisatie met de methode met relatieve tijd en absolute locatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

C.2 Straatdeel optimalisatie met de methode met absolute tijd en relatieve locatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

C.3 Straatdeel optimalisatie met relatieve tijd en locatie methode . . . . . .

62

LIJST VAN FIGUREN

66

67

BIBLIOGRAFIE

Bibliografie [1] Advanced graph algorithms. https://cw.felk.cvut.cz/wiki/_media/courses/ ae4m33pal/lectures/2012pal03.pdf. Geraadpleegd op: 14/08/2014. [2] Jmapviewer. http://wiki.openstreetmap.org/wiki/JMapViewer. Geraadpleegd op: 12/02/2014. [3] Traffic technology. http://www.be-mobile-international.com. Geraadpleegd op: 23/03/2015. [4] Ismail Chabini. Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time. Transportation Research Record: Journal of the Transportation Research Board, 1645(1):170–175, 1998. [5] Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269–271, 1959. [6] Ariel Orda and Raphael Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM (JACM), 37(3):607– 625, 1990.

Snelle en realistische routeplanning voor GPS-toestellen

Recommend Documents