Προβλήματα βέλτιστης δρομολόγησης ενός οχήματος

Abstract

Σκοπός της παρούσας μεταπτυχιακής διατριβής είναι η μελέτη του Προβλήματος Δρομολόγησης Οχημάτων (Vehicle Routing Problem – VRP), από θεωρητικής πλευράς, αλλά και η πρακτική αντιμετώπιση τέτοιων προβλημάτων. Στα πλαίσια αυτά, μελετήθηκε σχετική βιβλιογραφία και αρθρογραφία και έγινε μια ανάλυση του προβλήματος, των περιορισμών του, διάφορων παραλλαγών του, καθώς και των μεθόδων επίλυσής του. Το πρόβλημα δρομολόγησης είναι ένα συνδυαστικό πρόβλημα βελτιστοποίησης, που προκύπτει πολύ συχνά σε καθημερινές εφαρμογές σχετικές με τις μεταφορές, τα logistics και στη χρονοδρομολόγηση. Έχει να κάνει με την εύρεση αποδοτικών διαδρομών για τη διανομή ή περισυλλογή αγαθών σε συγκεκριμένα σημεία ενός δικτύου. Η οικογένεια των προβλημάτων VRP ανήκει στην κατηγορία των NP-hard (Nondeterministic Polynomial Time Hard) προβλημάτων τα οποία είναι πολύ δύσκολα στην επίλυσή τους ειδικότερα όταν αυξάνει το πλήθος των πελατών. Έχουν αντιμετωπισθεί με πολλές τεχνικές συμπεριλαμβάνοντας τόσο ακριβείς όσο και ευρετικές μεθόδους όμως το πολύ υψηλό υπολογιστικό κόστος των πρώτων μεθόδων και η πολύ χαμηλή απόδοσή τους σε μεγάλα προβλήματα έχει οδηγήσει την έρευνα να επικεντρωθεί στους στοχαστικούς αλγόριθμους που είναι ικανοί να προσφέρουν λύσεις ικανοποιητικές σε μεγάλα προβλήματα, όχι κατά ανάγκη βέλτιστες σε σχετικά καλό υπολογιστικό χρόνο. Εξαιτίας της πληθώρας παραλλαγών του προβλήματος οι μεθοδολογίες που προτείνονται στην παρούσα εργασία παρουσιάζουν την απαραίτητη ευελιξία αντιμετώπισης και πιο πολύπλοκων προβλημάτων, ενώ οι αλγόριθμοι θα μπορούσαν να είναι τμήματα πιο σύνθετων αλγορίθμων, με την ενσωμάτωση επιπλέον περιορισμών, παραμέτρων και αντικειμένων βελτιστοποίησης.