ML for Graph Reduction
Abstract
As society transitions toward sustainable mobility, efficient planning of electric vehicle fleets becomes crucial for reducing emissions, managing energy demand, and enabling greener logistics. Developing more efficient methods for these problems can help companies operate more sustainably while meeting growing transportation needs. Within this context, we focus on solving the Electrical Vehicle Routing Problem, an NP-hard optimization problem, which is about coordinating a fleet of electric vehicles to serve several customers as effectively as possible. When solving this in an exact way one of the most common approaches is to solve the problem by something called column generation where the solution is built up part by part by generating possible routes one by one, hopefully only enumerating a small subset of all possible routes. The problem of finding the next route is an elementary shortest path problem which can be solved by a labelling algorithm (dynamic programming). However, in larger graphs this can be quite computationally demanding. In this project we want to explore how ML-methods can be used to speed this up and by this accelerate the solving process of the vehicle routing problem and enabling more complex problems to be solved.
