Στην παρούσα μεταπτυχιακή διπλωματική εργασία μελετήθηκε το πρόβλημα
Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου (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.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/8327 |
| Date | 05 February 2015 |
| Creators | Γκορτσίλας, Δημήτριος |
| Contributors | Ζαρολιάγκης, Χρήστος, Gkortsilas, Dimitrios, Ζαρολιάγκης, Χρήστος, Γαλλόπουλος, Ευστράτιος, Κοντογιάννης, Σπυρίδων |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
Page generated in 0.002 seconds