Machine Learning for combinatorial optimization: the case of Vehicle Routing

Mazzieri, Diego (2021) Machine Learning for combinatorial optimization: the case of Vehicle Routing. [Laurea magistrale], Università di Bologna, Corso di Studio in Artificial intelligence [LM-DM270]
Documenti full-text disponibili:
[img] Documento PDF (Thesis)
Disponibile con Licenza: Creative Commons: Attribuzione - Non commerciale - Condividi allo stesso modo 4.0 (CC BY-NC-SA 4.0)

Download (2MB)


The Vehicle Routing Problem (VRP) is one of the most intensively studied combinatorial optimization problems in the Operations Research (OR) community. Its relevance is not only related to the various real-world applications it deals with, but to its inherent complexity being an NP-hard problem. From its original formulation more than 60 years ago, numerous mathematical models and algorithms have been proposed to solve VRP. The most recent trend is to leverage Machine Learning (ML) in conjunction with these traditional approaches to enhance their performance. In particular, this work investigates the use of ML-driven components as destroy or repair methods inside the Large Neighborhood Search (LNS) metaheuristic, trying to understand if, where, and when it is effective to apply them in the context of VRP. For these purposes, we propose NeuRouting, an open-source hybridization framework aimed at facilitating the integration between ML and LNS. Regarding the destroy phase, we adopt a Graph Neural Network (GNN) assisted heuristic, which we hybridize with a neural repair methodology taken from the literature. We investigate this integration both on its own and as part of an Adaptive Large Neighborhood Search (ALNS), performing an empirical study on instances of various sizes and against some traditional solvers.

Tipologia del documento
Tesi di laurea (Laurea magistrale)
Autore della tesi
Mazzieri, Diego
Relatore della tesi
Corso di studio
Ordinamento Cds
Parole chiave
operations research,combinatorial optimization,vehicle routing problem,capacitated vehicle routing problem,mixed-integer linear programming,heuristics,hybrid approaches,large neighborhood search,adaptive large neighborhood search,neural large neighborhood search,artificial intelligence,machine learning,reinforcement learning,deep learning,attention mechanisms,graph neural networks
Data di discussione della Tesi
3 Dicembre 2021

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento