Machine learning for routing problems: the case of vehicle routing problem (VRP)

Abstract

This thesis investigates the integration of machine learning (ML) techniques with classical optimization methodologies to address the Capacitated Vehicle Routing Problem (CVRP), a well-known NP-hard problem in logistics and operations research. Traditional approaches to solving VRPs rely on heuristics and metaheuristics, which, while effective, often lack adaptability and efficiency when faced with complex, large-scale datasets. Recent advancements in ML, and particularly deep learning, offer new opportunities to enhance these classical methods by leveraging data-driven insights. The research introduces a hybrid methodology that combines the Greedy Randomized Adaptive Search Procedure (GRASP) with Variable Neighborhood Descent (VND) and augments it with a Graph Isomorphism Network with edge features (GINE), a type of Graph Neural Network (GNN). The proposed model classifies initial solutions generated by the GRASP procedure as either promising or unpromising before applying local search optimization. This approach aims to reduce computational effort by selectively refining only those initial solutions likely to yield significant improvements. The methodology was evaluated using benchmark CVRP instances from the CVRPLIB dataset. Experimental results show that the hybrid GINE-GRASP-VND approach achieved moderate classification accuracy (60.12%) and demonstrated its ability to generalize to instances larger than those used in training. While the performance gains were limited in smaller instances, significant improvements were observed in larger-scale problems, validating the potential of ML-enhanced optimization methods and the feasibility of incorporating GNNs into metaheuristics frameworks for complex routing problems.

Η παρούσα διπλωματική εργασία εξετάζει την ενσωμάτωση τεχνικών μηχανικής εκμάθησης (Machine Learning – ML) με κλασικές μεθοδολογίες βελτιστοποίησης για την αντιμετώπιση του Προβλήματος Δρομολόγησης Οχημάτων με Περιορισμένη Χωρητικότητα (Capacitated Vehicle Routing Problem – CVRP), ενός γνωστού NP-hard προβλήματος στην εφοδιαστική και την επιχειρησιακή έρευνα. Οι παραδοσιακές προσεγγίσεις επίλυσης VRP βασίζονται σε ευρετικές (heuristics) και μεταευρετικές (metaheuristics) μεθόδους, οι οποίες, παρότι αποτελεσματικές, συχνά στερούνται προσαρμοστικότητας και αποδοτικότητας όταν εφαρμόζονται σε πολύπλοκα και μεγάλου μεγέθους σύνολα δεδομένων. Οι πρόσφατες εξελίξεις στη μηχανική εκμάθηση, και ιδιαίτερα στη βαθιά εκμάθηση (deep learning), προσφέρουν νέες δυνατότητες ενίσχυσης αυτών των κλασικών μεθόδων αξιοποιώντας γνώση που προέρχεται από δεδομένα. Η έρευνα εισάγει μια υβριδική μεθοδολογία που συνδυάζει τον αλγόριθμο Greedy Randomized Adaptive Search Procedure (GRASP) με την τεχνική Variable Neighborhood Descent (VND) και τον εμπλουτίζει με ένα Graph Isomorphism Network με χαρακτηριστικά ακμών (GINE), έναν τύπο Graph Neural Network (GNN). Το προτεινόμενο μοντέλο ταξινομεί τις αρχικές λύσεις που παράγονται από τη διαδικασία GRASP ως υποσχόμενες ή μη υποσχόμενες πριν από την εφαρμογή τοπικής βελτιστοποίησης. Η προσέγγιση αυτή επιδιώκει τη μείωση του υπολογιστικού κόστους, επιλέγοντας να βελτιστοποιήσει μόνο τις λύσεις που είναι πιθανό να αποδώσουν σημαντικές βελτιώσεις. Η μεθοδολογία αξιολογήθηκε χρησιμοποιώντας κλασικά παραδείγματα CVRP από τη βιβλιοθήκη CVRPLIB. Τα πειραματικά αποτελέσματα δείχνουν ότι η υβριδική προσέγγιση GINE-GRASP-VND πέτυχε μέτρια ακρίβεια ταξινόμησης (60,12%) και έδειξε ικανότητα γενίκευσης σε προβλήματα μεγαλύτερου μεγέθους από αυτά που χρησιμοποιήθηκαν κατά την εκπαίδευση. Παρότι οι επιδόσεις ήταν περιορισμένες σε μικρότερου μεγέθους περιπτώσεις, παρατηρήθηκαν σημαντικές βελτιώσεις σε μεγάλης κλίμακας προβλήματα, επιβεβαιώνοντας το δυναμικό των μεθόδων βελτιστοποίησης ενισχυμένων με ML και τη δυνατότητα ενσωμάτωσης GNNs σε μεταευρετικές δομές για την επίλυση σύνθετων προβλημάτων δρομολόγησης.