Distributed machine learning framework for shortest path problems with stochastic weights
Ladda ner
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Program
Complex adaptive systems (MPCAS), MSc
Publicerad
2023
Författare
Aspegrén, Gabriel
Nilsson Dahlberg, Olle
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Range anxiety is one of the most common reasons why customers hesitate to buy an electric car. At the same time, the European Union strives toward a fully electric car fleet. Previous work has shown promising results in designing a self-learning shortest path algorithm for finding the most energy efficient path for an electric vehicle through a road network, using combinatorial multi-armed bandit methods. However, it is desirable to scale the methods for larger networks, for example countries and continents. In this project, we design a distributed framework for shortest path computations on a road network, over a computer cluster, using combinatorial multi-armed bandit methods and machine learning. The system is distributed with Apache Spark and GraphX’s version of the Pregel algorithm. An experimental study is performed to investigate the impact of partition strategy, number of partitions,
network size and latency between computer nodes on the total run-time. The results show that partitioning strategy has an significant impact on the run-time and that larger networks benefit more from being partitioned.
Beskrivning
Ämne/nyckelord
Shortest path problems , distributed computing , multi-armed bandits