Τομέας Θεωρητικής Πληροφορικής
Βιβλιοθήκη Σχολής Θετικών Επιστημών

2015-08-19

2015

Αγγελίδης Ιωσήφ

Αλέξιος Δελής

Δρομολόγηση Οχημάτων Περιορισμένης Χωρητικότητας με Χρονικά Όρια

Ελληνικά

Capacitated Vehicle Routing with Time Windows

Το Πρόβλημα Δρομολόγησης Οχημάτων Περιορισμένης Χωρητικότητας με Χρονικά Όρια
(Capacitated Vehicle Routing Problem with Time Windows, CVRPTW) έχει
απασχολήσει την ακαδημαϊκή κοινότητα για πολλά χρόνια λόγω της δυσκολίας του
(ανήκει στην κλάση NP) και έχουν δοθεί πολλές προσεγγιστικές λύσεις που είναι
επαρκώς ικανοποιητικές. Φυσικά, υπάρχει μια πληθώρα εφαρμογών των λύσεων αυτών
σε πρακτικές εφαρμογές.
Στόχος του προγράμματος που τεκμηριώνεται στην παρούσα πτυχιακή είναι να λύνει
αρχικά το πρόβλημα ακολουθώντας κλασσικές μεθόδους της βιβλιογραφίας
χρησιμοποιώντας πραγματικά γεωγραφικά δεδομένα σε συντεταγμένες Γης. Στην
συνέχεια, επικοινωνεί με μια σχεσιακή βάση (relational database) που περιέχει
όλους του δρόμους της Αθήνας και πληροφορίες για την κατεύθυνσή τους (μονής ή
διπλής).
Επιπλέον, επικοινωνεί με μια αποθήκη κλειδού-τιμής στην μνήμη (in-memory
key-value store) η οποία περιέχει επιπλέον δυναμικές πληροφορίες που αφορούν
δρόμους. Πιο συγκεκριμένα, περιέχει θετικά και αρνητικά ποσοστιαία βάρη που
δηλώνουν δυναμικά δεδομένα δρόμων. Θετικά βάρη σημαίνουν κίνηση και παίρνουν
τιμές στο διάστημα (0.0,1.0). Αρνητικά βάρη σημαίνουν εμπειρία οδηγών που τους
επηρεάζει να ακολουθήσουν συγκεκριμένους δρόμους γιατί ξέρουν ότι θα φτάσουν
πιο γρήγορα και παίρνουν τιμές στο διάστημα ([-0.5,0.0]). Τα αρνητικά δεν έχουν
το ίδιο εύρος τιμών σε σχέση με τα θετικά για διαισθητικούς λόγους αφού η
κίνηση δρόμων επηρεάζει την λήψη απόφασης πολύ περισσότερο από την εμπειρία του
οδηγού αφού μπορεί ένας δρόμος να έχει μποτιλιάρισμα που δεν είναι αναμενόμενο.
Κατά την εκτέλεση του προγράμματος εκτυπώνονται μηνύματα που εξηγούν τις
αλγοριθμικές αποφάσεις που λαμβάνονται σε κρίσιμα βήματα και αποθηκεύονται
ενδιάμεσα αρχεία για μελέτη των αποτελεσμάτων αφού τελειώσει η εκτέλεση. Τέλος,
παράγονται ένα αρχείο kml και ένα αρχείο html για να είναι δυνατόν το τελικό
αποτέλεσμα να μπορεί να προβληθεί σε οποιαδήποτε εφαρμογή χειρίζεται kml αρχεία
(ή html αν θέλουμε να δούμε την οπτικοποίηση στο Διαδίκτυο). Συνήθεις εφαρμογές
είναι το Google Earth, το Google Maps και το Marble.

δρομολόγηση οχημάτων, χρονικά όρια, δρομολόγηση, μεταφορά, κατευθυνόμενη τοπική αναζήτηση

Ναι

7-11`

Ναι

12

59

https://pergamos.lib.uoa.gr/uoa/dl/object/1324180/file.pdf

https://pergamos.lib.uoa.gr/uoa/dl/object/1324180