Optimal Cost Prediction in the Vehicle Routing Problem Through Supervised Learning

Optimal Cost Prediction in the Vehicle Routing Problem Through Supervised Learning

Bellan, Daniele (TU Delft Mechanical, Maritime and Materials Engineering; TU Delft Delft Center for Systems and Control)

Alonso Mora, J. (mentor)

Delft University of Technology

Mechanical Engineering | Systems and Control

2018-07-11

Machine learning techniques aim to train a model in such a way that it can approximate complex dynamics like the vehicle routing problem. In the recent years, combinatorial neural networks and deep learning methods have been used to predict the solution of routing problems. However, the approaches investigated so far in literature could be cumbersome to apply and replicate. Although such methods obtained good results in predicting the solutions of simple routing problems, their structures are complex and they do not consider any sort of precedence constraints, an aspect that is crucial in passenger transportation. The goal of this thesis is to apply supervised learning to predict the optimal cost of single-vehicle pick-up and delivery problem, leading to a simpler implementation compared with combinatorial neural networks. First, the most suitable machine learning model able to approximate problem is chosen as a neural network with one hidden layer and a ReLu activation function. Then, the input features that improve the prediction accuracy are searched. In particular, very good results are observed by feeding the solutions of heuristic algorithm as input to the neural network. Compared to baseline prediction method which returns the length of the route computed by greedy heuristic, an improvement of 40\% in prediction accuracy is obtained with the proposed approach. Finally, the model is improved to achieve better generalization properties with respect to a higher number of requests, by using the average optimal length as an additional input feature.

Pick-up and Delivery Problem
cost prediction
neural networks
greedy heuristic

http://resolver.tudelft.nl/uuid:4461e3dd-0ba3-4d18-a9dc-88c31b43a36f

Student theses

master thesis

© 2018 Daniele Bellan