Distributed machine learning framework for shortest path problems with stochastic weights

Abstract

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.