The Load-Dependent Vehicle Routing Problem (LDVRP) (an optimization approach)

Abstract

The Load-Dependent Vehicle Routing Problem (LDVRP) is a variant of the classical Capacitated VRP in which transportation cost depends not only on distance but also on the remaining load carried by the vehicle. This reflects real-world freight operations, where heavier vehicles consume more fuel and generate higher operational costs. This thesis develops a complete heuristic and metaheuristic framework for solving the LDVRP efficiently. The methodology begins with a Sweep heuristic that produces spatially coherent and capacity-feasible routes. This initial solution is refined using a load‑dependent Clarke–Wright Savings algorithm, followed by a multi-operator Local Search procedure employing 2‑opt, relocation, and swap moves to improve route structure and sequencing. To escape local optima and explore a wider solution space, an Adaptive Large Neighborhood Search with a Simulated Annealing acceptance criterion (ALNS‑SA) is implemented. The framework is evaluated on benchmark instances from the Golden dataset under different levels of load dependency. Results show that constructive heuristics significantly improve over geometric routing, while Local Search and ALNS provide additional gains through iterative refinement. The study demonstrates that incorporating load-dependent costs leads to more realistic routing decisions while remaining computationally tractable.Το Load-Dependent Vehicle Routing Problem (LDVRP) αποτελεί παραλλαγή του κλασικού Capacitated VRP, όπου το κόστος μετακίνησης εξαρτάται όχι μόνο από την απόσταση αλλά και από το φορτίο που μεταφέρει το όχημα. Αυτό αντανακλά την πραγματικότητα των μεταφορικών λειτουργιών, όπου τα πιο βαριά οχήματα καταναλώνουν περισσότερα καύσιμα και έχουν υψηλότερο λειτουργικό κόστος. Η εργασία αναπτύσσει ένα πλήρες πλαίσιο ευρετικών και μεταευρετικών μεθόδων για την αποδοτική επίλυση του LDVRP. Η μεθοδολογία ξεκινά με το Sweep heuristic, το οποίο δημιουργεί χωρικά συνεκτικές και capacity‑feasible διαδρομές. Η λύση αυτή βελτιώνεται μέσω του load‑dependent Clarke–Wright Savings αλγορίθμου και στη συνέχεια με Local Search που χρησιμοποιεί 2‑opt, relocation και swap κινήσεις. Για την αποφυγή τοπικών βέλτιστων και την εξερεύνηση μεγαλύτερου χώρου λύσεων, εφαρμόζεται Adaptive Large Neighborhood Search με κριτήριο αποδοχής Simulated Annealing. Το προτεινόμενο πλαίσιο αξιολογείται σε benchmark instances του Golden dataset για διαφορετικές τιμές load dependency. Τα αποτελέσματα δείχνουν ότι οι κατασκευαστικές ευρετικές προσφέρουν σημαντικές βελτιώσεις, ενώ το Local Search και το ALNS επιτυγχάνουν περαιτέρω μείωση κόστους μέσω επαναληπτικής βελτιστοποίησης. Η μελέτη αποδεικνύει ότι η ενσωμάτωση load‑dependent κόστους οδηγεί σε πιο ρεαλιστικές και αποδοτικές λύσεις.