Applying machine learning in route optimization

Applying machine learning in route optimization: Predicting construction algorithm performance for the vehicle routing problem using neural networks

Burgers, Nienke (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Discrete Mathematics and Optimization)

van Essen, J.T. (mentor)
Heinlein, A. (graduation committee)
Cederhout, Quinten (mentor)

Delft University of Technology

Applied Mathematics

2023-06-12

The real-life Vehicle Routing Problem (VRP) is the problem in which a set of vehicles needs to perform a set of tasks such that we have a shortest total driving distance. Such problems can be solved using construction algorithms. Finding the best-performing construction algorithm is time-consuming because these algorithms consist of many different elements, which differ between algorithms. In this thesis, a Neural Network (NN) model is built that predicts the best-performing algorithm from a pre-determined set of algorithms for a specific input case. These predictions are based on problem features extracted from real-life data. For our first NN model, we evaluate the best settings with a grid search, which leads to a model with a mean-squared error of 0.147 and an accuracy of $58.6\%$. We try to improve this original model by data balancing and varying the input features. First, we balance the data using downsampling and oversampling performed by an Integer Linear Program (ILP), which does not lead to a better-performing NN. Secondly, we add more input features to the model, which leads to a slight improvement because the model has more information about the problem at hand. After, we perform an elaborate feature analysis using permutation feature importance, SHAP, and Greenwell numbers. Based on this analysis, we reduce the number of input features to only 12. This reduction leads to the best-performing model with a mean-squared error loss of 0.125 and an accuracy of 61.7\%. To investigate whether our prediction model indeed improves the routes using the predicted algorithm, we look at the distribution of predictions. For each company, we replace the algorithm in use with the algorithm most often predicted by our model. This replacement indeed improves the results for most of the considered companies.

VRP
Neural networks
Algorithm selection

http://resolver.tudelft.nl/uuid:33ba6733-cd14-44e2-a051-5504b2fa7541

Student theses

master thesis

© 2023 Nienke Burgers