Νέες ευρετικές προσεγγίσεις για δρομολόγηση στόλου οχημάτων
Στην παρούσα μεταπτυχιακή διπλωματική εργασία μελετήθηκε το πρόβλημα Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου (VRPTW) κάτω από ένα φιλικό προς το περιβάλλον πρίσμα που απαιτεί την δημιουργία ισορροπημένων και συμπαγών συστάδων. Παρουσιάζεται μια νέα ευρετική προσέγγιση που αποτελείται από...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2015
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/8327 |
| id |
nemertes-10889-8327 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-83272022-09-05T05:37:32Z Νέες ευρετικές προσεγγίσεις για δρομολόγηση στόλου οχημάτων Γκορτσίλας, Δημήτριος Ζαρολιάγκης, Χρήστος Ζαρολιάγκης, Χρήστος Γαλλόπουλος, Ευστράτιος Κοντογιάννης, Σπυρίδων Gkortsilas, Dimitrios Δρομολόγηση στόλου οχημάτων Ευρετικό Παράθυρα χρόνου Δυναμικά σενάρια Vehicle routing problem Heuristic Time windows Dynamic scenarios 006.3 Στην παρούσα μεταπτυχιακή διπλωματική εργασία μελετήθηκε το πρόβλημα Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου (VRPTW) κάτω από ένα φιλικό προς το περιβάλλον πρίσμα που απαιτεί την δημιουργία ισορροπημένων και συμπαγών συστάδων. Παρουσιάζεται μια νέα ευρετική προσέγγιση που αποτελείται από τρεις φάσεις: (i) συσταδοποίηση των πελατών με συμβατά παράθυρα χρόνου, (ii) συσταδοποίηση των πελατών που βρίσκονται γεωγραφικά κοντά χρησιμοποιώντας διάφορες μεθόδους (φυσικές αποκοπές, KaHIP, τετραδικά δένδρα), (iii) μια φάση εκλέπτυνσης που είτε χωρίζει μια συστάδα σε μικρότερες, είτε συγχωνεύει συστάδες δημιουργώντας μια συμπαγή μεγαλύτερη συστάδα. Η νέα προσέγγιση αποδίδει πολύ καλά όταν χρησιμοποιείται σε δυναμικά σενάρια στα οποία ζητούνται αλλαγές στην αρχικά υπολογισμένη διαδρομή (προσθήκη μιας νέας παραγγελίας ή ακύρωση κάποιας παραγγελίας). Η νέα μέθοδος αποτελεί ένα πολύ καλό σημείο εκκίνησης για επανεξέταση και περαιτέρω βελτιστοποίηση της λύσης του προβλήματος Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου. Πειράματα που έγιναν με πραγματικά σύνολα δεδομένων δείχνουν ότι η νέα προσέγγιση υπερέχει σε σχέση με τις συνήθεις προσεγγίσεις που ξεκινούν από μία βασική λύση. We investigate the Vehicle Routing Problem with Time Windows (VRPTW) under a new approach, consisting of three major phases: (i) a first clustering of customers with compatible time windows; (ii) a second clustering of customers with close geographic proximity based on various methods (natural cuts, KaHIP, quad trees); (iii) a refinement phase that either splits a cluster into smaller ones, or merges clusters to form a bigger compact cluster. Our approach turns out to be beneficial when used in an on-line environment, where changes to the initial tour are requested (add a new customer to the tour or drop some customers). The new method serves as a warm starting point for re-evaluating and further optimizing the solution of VRPTW. Experiments with real data sets demonstrate that our approach compares favorably with standard approaches that start from a basic (cold) solution. 2015-02-05T16:17:53Z 2015-02-05T16:17:53Z 2014-10-20 2015-02-05 Thesis http://hdl.handle.net/10889/8327 gr 0 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Δρομολόγηση στόλου οχημάτων Ευρετικό Παράθυρα χρόνου Δυναμικά σενάρια Vehicle routing problem Heuristic Time windows Dynamic scenarios 006.3 |
| spellingShingle |
Δρομολόγηση στόλου οχημάτων Ευρετικό Παράθυρα χρόνου Δυναμικά σενάρια Vehicle routing problem Heuristic Time windows Dynamic scenarios 006.3 Γκορτσίλας, Δημήτριος Νέες ευρετικές προσεγγίσεις για δρομολόγηση στόλου οχημάτων |
| description |
Στην παρούσα μεταπτυχιακή διπλωματική εργασία μελετήθηκε το πρόβλημα
Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου (VRPTW) κάτω από ένα
φιλικό προς το περιβάλλον πρίσμα που απαιτεί την δημιουργία
ισορροπημένων και συμπαγών συστάδων. Παρουσιάζεται μια νέα ευρετική
προσέγγιση που αποτελείται από τρεις φάσεις: (i) συσταδοποίηση των πελατών με
συμβατά παράθυρα χρόνου, (ii) συσταδοποίηση των πελατών που βρίσκονται
γεωγραφικά κοντά χρησιμοποιώντας διάφορες μεθόδους (φυσικές αποκοπές,
KaHIP, τετραδικά δένδρα), (iii) μια φάση εκλέπτυνσης που είτε χωρίζει
μια συστάδα σε μικρότερες, είτε συγχωνεύει συστάδες δημιουργώντας μια
συμπαγή μεγαλύτερη συστάδα. Η νέα προσέγγιση αποδίδει πολύ καλά όταν
χρησιμοποιείται σε δυναμικά σενάρια στα οποία ζητούνται αλλαγές στην
αρχικά υπολογισμένη διαδρομή (προσθήκη μιας νέας παραγγελίας ή ακύρωση
κάποιας παραγγελίας). Η νέα μέθοδος αποτελεί ένα πολύ καλό σημείο
εκκίνησης για επανεξέταση και περαιτέρω βελτιστοποίηση της λύσης του
προβλήματος Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου. Πειράματα
που έγιναν με πραγματικά σύνολα δεδομένων δείχνουν ότι η νέα
προσέγγιση υπερέχει σε σχέση με τις συνήθεις προσεγγίσεις που ξεκινούν
από μία βασική λύση. |
| author2 |
Ζαρολιάγκης, Χρήστος |
| author_facet |
Ζαρολιάγκης, Χρήστος Γκορτσίλας, Δημήτριος |
| format |
Thesis |
| author |
Γκορτσίλας, Δημήτριος |
| author_sort |
Γκορτσίλας, Δημήτριος |
| title |
Νέες ευρετικές προσεγγίσεις για δρομολόγηση στόλου οχημάτων |
| title_short |
Νέες ευρετικές προσεγγίσεις για δρομολόγηση στόλου οχημάτων |
| title_full |
Νέες ευρετικές προσεγγίσεις για δρομολόγηση στόλου οχημάτων |
| title_fullStr |
Νέες ευρετικές προσεγγίσεις για δρομολόγηση στόλου οχημάτων |
| title_full_unstemmed |
Νέες ευρετικές προσεγγίσεις για δρομολόγηση στόλου οχημάτων |
| title_sort |
νέες ευρετικές προσεγγίσεις για δρομολόγηση στόλου οχημάτων |
| publishDate |
2015 |
| url |
http://hdl.handle.net/10889/8327 |
| work_keys_str_mv |
AT nkortsilasdēmētrios neeseuretikesprosengiseisgiadromologēsēstolouochēmatōn |
| _version_ |
1771297157284888576 |
