Creating a framework for analyzing historical travel data of electric vehicles and identifying heavily used parts of a road network using skyline queries

Shkodrov, Dimitar Atanasov

4. term

Data Engineering, MSc

2016

2016-06-12

16

Electric vehicles have limited range and often require en-route charging, creating a need to understand and optimize routes that include charging stops. Because realistic historical travel data are unavailable, this thesis presents a framework that both synthesizes travel data and analyzes it to identify frequently used, potentially inconvenient charging routes and the most heavily used parts of a road network. The network is modeled as a directed graph with multiple weights per edge (distance, time, and energy). Vehicle autonomy is modeled in kWh with speed-dependent discharge and losses (e.g., aerodynamics), yielding more realistic data. Synthetic charging routes are constructed by combining classical routing algorithms and heuristics (including A* and Dijkstra variants) with dynamic programming. For each charging route, the deviation from the shortest path and its support (occurrence as a route or subroute) are computed using ideas from sequential pattern mining (SPADE). Skyline queries over deviation and support expose routes that are both frequent and significantly deviant. In addition, the framework proposes a method to detect heavily used road segments that do not appear as independent routes (e.g., a bridge). An implementation demonstrates the framework and its algorithms; experimental details and outcomes are discussed in the thesis but are not included in this excerpt. The framework can inform charging infrastructure planning and EV routing analysis.

Elbiler har begrænset rækkevidde og kræver ofte opladning undervejs, hvilket skaber behov for at forstå og optimere ruter med ladestop. Da realistiske historiske rejsedata mangler, præsenterer afhandlingen et rammeværk, der både genererer syntetiske rejsedata og analyserer dem for at identificere hyppigt anvendte, potentielt ubelejlige laderuter og de mest belastede dele af vejnettet. Vejnettet modelleres som en rettet graf med flere vægte per kant (afstand, tid og energiforbrug). Autonomi behandles energibevidst i kWh og afhænger af hastighed og tab (fx aerodynamik), hvilket gør datasættet mere realistisk. Syntetiske laderuter konstrueres ved at kombinere klassiske rutealgoritmer og heuristikker (herunder A* og varianter af Dijkstra) samt dynamisk programmering. For hver laderute beregnes afvigelsen fra den korteste rute samt dens støtte (forekomst som rute eller delrute) inspireret af sekvensmønster-mining (SPADE). Skyline-forespørgsler over dimensionerne afvigelse og støtte fremhæver ruter, der er både hyppige og afviger væsentligt. Derudover foreslås en metode til at identificere hårdt brugte vejsegmenter, som ikke fremstår som selvstændige ruter (fx en bro). En implementering demonstrerer rammeværket og dets algoritmer; eksperimentelle detaljer og resultater omtales i afhandlingen, men fremgår ikke af dette uddrag. Rammeværket kan støtte planlægning af ladeinfrastruktur og ruteanalyse for elbiler.

[This apstract has been generated with the help of AI directly from the project full text]

Download PDF
View record in AAU Student Projects