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

 
This item is provided by the institution :

Repository :
Institutional Repository Hellanicus
see the original item page
in the repository's web site and access all digital files if the item*
share





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

Σαρρής, Δημήτριος

aegean

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

masterThesis

Δρομολόγηση οχήματος (EL)
Ευρετικοί αλγόριθμοι (EL)
Μαρκοβιανές διαδικασίες αποφάσεων (EL)
Δυναμικός προγραμματισμός (EL)
Heuristic algorithm (EL)
Στοχαστικά μοντέλα (EL)
Dynamic programming (EL)
Προβλήματα βελτιστοποίησης (EL)


2017-03-02


2017-10-26T12:19:56Z

Σάμος




*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)