Skyline Query Framework for the Analysis of Electric Vehicle Trajectories
Authors
Sanporean, Ion-Anastasiu ; Galinauskas, Paulius
Term
4. term
Education
Publication year
2016
Abstract
Elbilers kørsel påvirkes af batterikapacitet, afstand og tilgængelige ladestationer. For at planlægge opladningsstop eller placere nye stationer må vi finde ruter, der skaber omveje for mange bilister. Denne afhandling præsenterer en ramme, der identificerer trajektorier i et datasæt, som både er besværlige (har høj omvejstid i forhold til den hurtigste rute) og vigtige (forekommer ofte). Rammen bruger Skyline Queries Algorithm (SQA) og introducerer også en metode til at generere data under forskellige betingelser. Skyline-forespørgslerne anvender to kriterier: afvigelse (ekstra omvejstid på den hurtigste rute fra start til mål) og support (hvor ofte en trajektorie optræder i historiske data). Skyline-metoden udvælger trajektorier, der udgør de bedste kompromiser på tværs af kriterierne, og fremhæver ofte benyttede ruter, der alligevel indebærer omveje. Vi testede rammen på to kortstørrelser: det centrale Aalborg (lille kort) og Nordøst-Canada (stort kort), og sammenlignede SQA med to baseline-algoritmer: brute force skyline og sort filter skyline (SFS). Resultaterne viser, at SQA kører hurtigere end de andre på det store kort, mens køretiden på det lille kort er sammenlignelig med brute force. Ved hjælp af effektive pruning-teknikker identificerer SQA skyline-sættet på under tre fjerdedele af den tid, brute force bruger. På begge korttyper viser skylines for forskellige antal ruter, at jo større support-værdier, desto mindre afvigelse. Samlet set er rammen effektiv til analyse af store datasæt, men vi observerede negativ performancepåvirkning ved små datasæt.
Electric vehicle travel depends on battery capacity, trip distance, and the availability of charging stations. To plan charging stops or decide where to place new stations, we need to find routes that cause detours for many drivers. This thesis presents a framework that identifies trajectories in a dataset that are both inconvenient (high detour time compared to the fastest path) and important (appear frequently). It uses the Skyline Queries Algorithm (SQA) and also introduces a method to generate data under different conditions to test the approach. Our skyline queries use two criteria: deviation (extra detour time on the fastest route from origin to destination) and support (how often a trajectory appears in historical data). The skyline selects trajectories that represent the best trade-offs across these criteria, highlighting commonly used routes that still involve detours. We evaluated the framework on two map scales: central Aalborg (small) and North East Canada (large), and compared SQA with two baselines: brute force skyline and sort filter skyline (SFS). Results show that on the large map, SQA runs faster than the others; on the small map, its runtime is comparable to brute force. Thanks to efficient pruning techniques, SQA finds the skyline set in less than three quarters of the time required by brute force. Across both map types, skylines generated for different numbers of routes indicate that higher support values tend to come with lower deviation values. Overall, the framework is efficient for analyzing large datasets, but we observed a negative impact on performance for small datasets.
[This abstract was generated with the help of AI]
Documents