As society transitions toward sustainable mobility, efficient planning of electric vehicle fleets is important for reducing emissions and enabling greener logistics. This project focuses on the Electric Vehicle Routing Problem, where a fleet of electric vehicles must serve a set of customers while respecting practical constraints such as battery capacity, charging opportunities, and time windows.
Exact solution methods for these problems often use column generation, in which promising vehicle routes are generated as needed instead of considering all possible routes from the start. At each step, finding a new route corresponds to solving a constrained shortest-path problem. This problem is solved using a labelling algorithm, a dynamic-programming method that systematically extends partial routes. For larger instances, this step can be computationally demanding because the number of possible partial routes grows quickly.
The aim of this project is to investigate how machine-learning methods, in particular Generative Flow Networks, can identify smaller and more promising parts of the underlying graph before solving the shortest-path problem. This may reduce the computational effort needed by the labelling algorithm and make it possible to study larger and more realistic problem instances.
The project combines GPU-based training of machine-learning models with CPU-based generation of training data and large-scale computational experiments. The results will be evaluated on benchmark instances using exact optimisation methods.
Main supervisor: Elina Rönnberg, Linköping University