Λεπτομέρειες

ΕίδοςΔημοσίευση
ΚωδικόςTR-2011-3
ΤίτλοςΔυναμικό Πρόβλημα Παραλαβών και Παραδόσεων με Μεταφορτώσεις
ΣυγγραφέαςΠαναγιώτης Μπούρος, Δημήτρης Σαχαρίδης, Θοδωρής Δαλαμάγκας, Τίμος Σελλής
Έτος2011
Λέξεις κλειδιά-
ΠερίληψηΣτο Δυναμικό Πρόβλημα Παραλαβών και Παραδώσεων με Μεταφορτώσεις ένα σύνολο από αιτήματα μεταφοράς καταφθάνουν σε τυχαίες χρονικές στιγμές και πρέπει να εξυπηρετηθούν από το στόλο των οχημάτων μιας εταιρίας. Στα πλαίσια αυτού του προβλήματος εισάγουμε δύο κόστη που ορίζουν την ποιότητα της λύσης για την εξυπηρέτηση ενός αιτήματος, τόσο από την πλευρά της εταιρίας όσο και από την πλευρά των πελατών. Κατά κανόνα τα περισσότερα παρόμοια προβλήματα λύνονται με την εφαρμογή ενός αλγόριθμου τοπικής αναζήτησης που λειτουργεί σε δύο φάσεις και ο οποίος προτείνει μια ευριστική λύση. Αντίθετα η παρούσα δουλειά μοντελοποιεί το πρόβλημα ως ένα πρόβλημα σε γράφο και προτείνει μία λύση που αντιμετωπίζει κάθε αίτημα ξεχωριστά. Εν συντομία ο στόχος είναι να βρεθεί το συντομότερομονοπάτι από τονκόμβο στο γράφο που αντιπροσωπεύει την τοποθεσία παραλαβής προς τον κόμβο της τοποθεσίας παράδοσης. Ωστόσο, δείχνουμε ότι για την εύρεση του συνομότερου μονοπατιού δεν μπορούν να χρησιμοποιηθούν αποδοτικοί αλγόριθμοι όπως ο Bellman-Ford ή ο Dijkstra. Παρόλ' αυτά, η μέθοδός μας μπορεί να βρει τη λύση σε ένα αίτημα σημαντικά γρηγορότερα από ένα αλγόριθμο τοπικής αναζήτησης σε δύο φάσεις, ενώ παράλληλα η ποιότητα της λύσης είναι μόνο οριακά χαμηλότερη.
ΚατηγορίαSpatiotemporal Databases
ΔημοσίευσηProceedings of the 12th International Symposium on Spatial and Temporal Databases (SSTD), Minneapolis, MN, USA, August 24-26, 2011
Αρχείο Επισκόπηση


Επιστροφή στην αρχική σελίδα