SMARTRANS - Literature Review

Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση

Βιβλιογραφική Ανασκόπηση
Οι Εμπορευματικές Μεταφορές σε Αστικές Περιοχές

Οι εμπορευματικές μεταφορές αφορούν την μεταφορά των προϊόντων από τα κέντρα διανομής στα
διάφορα σημεία παράδοσης. Η κυκλοφοριακή συμφόρηση στις αστικές περιοχές, λόγω καιρικών
συνθηκών, έκτακτων γεγονότων, την ώρα της ημέρας αλλά και την περίοδο του χρόνου, επηρεάζει
τους χρόνους διέλευσης και συνεπώς τον προγραμματισμό των παραδόσεων και τη δρομολόγηση
του στόλου των οχημάτων (Groß et al., 2015). Οι υπεύθυνοι δρομολόγησης αναθέτουν σε πολλά
οχήματα πολλές παραγγελίες καθώς και την σειρά με την οποία θα εκτελούνται ώστε να συνδυάζουν
τις αξιόπιστες χρονικά με τις οικονομικά αποδοτικές παραδόσεις. Για την εξισορρόπηση μεταξύ των
δύο πρέπει να ληφθούν υπόψη περιορισμοί για την εύρεση της καλύτερης δυνατής λύσης, όπως
είναι το βάρος ή η χωρητικότητα του οχήματος, ο διαθέσιμος χρόνος για την παράδοση, οι χρόνοι
φόρτωσης και εκφόρτωσης, οι ώρες εργασίας των οδηγών, οι διαφορετικές ταχύτητες των
οχημάτων, η κυκλοφοριακή συμφόρηση, οι περιορισμοί πρόσβασης και οι περιβαλλοντικοί
περιορισμοί (Saeheaw and Charoenchai, 2016). Ο κύριος σκοπός του προτεινόμενου ερευνητικού
έργου είναι να αναπτύξει ένα ολοκληρωμένο λογισμικό μέσω διαδικτύου, για την υποστήριξη των
αναγκών των σύγχρονων εταιρειών αποθήκευσης και διανομής, ώστε να προγραμματίζει αποδοτικά
τις παραδόσεις και να υπολογίζει τις διαδρομές στα αστικά περιβάλλοντα λαμβάνοντας υπόψη
χρονικά εξαρτημένους περιορισμούς, όπως οι παραδόσεις συγκεκριμένου χρόνου, η κυκλοφοριακή
συμφόρηση, το ωράριο εργασίας αλλά και οι περιβαλλοντικές επιπτώσεις.

Οι οδικές μεταφορές συνεχίζουν να έχουν το μεγαλύτερο μερίδιο των Ευρωπαϊκών εμπορευματικών
μεταφορών μεταξύ των τριών τρόπων χερσαίων μεταφορών (οδικές, εσωτερικές πλωτές και
σιδηροδρομικές) σε ποσοστό 74,9%, το 2014. Τα συγκεντρωτικά στοιχεία για τις χώρες τις
Ευρωπαϊκής Ένωσης δείχνουν ότι μεταφέρθηκαν 2236 δις τόνοι αγαθών ανά χιλιόμετρο (t/Km) στις
χερσαίες μεταφορές που αντιστοιχούν σε 1675 t/Km για το οδικό δίκτυο. Ο συνολικός κύκλος
εργασιών αυτών των μεταφορών κυμαίνεται από 0,8% έως 7,9% των συνολικών κύκλων εργασιών
των διάφορων χωρών στην Ευρωπαϊκή Ένωση. Ο συνολικό τζίρος που προέρχεται από τις μεταφορές
του οδικού δικτύου, ανέρχεται σε 300 δις ευρώ, ποσοστό 2% του ακαθάριστου εγχώριου προϊόντος
για την Ευρώπη για το 2014. Επιπλέον, τα κόστη μεταφοράς συνιστούν το 4% έως 10% της τιμής
πώλησης ενός προϊόντος ανάλογα με τον κλάδο δραστηριοποίησης (Coyle et al., 1996). Συνεπώς, ο
αποδοτικός προγραμματισμός των δρομολογίων των οχημάτων που μειώνει τις διανυόμενες
αποστάσεις και τους χρόνους διέλευσης στο ελάχιστο, έχει μεγάλη επιρροή στην κερδοφορία των
εταιρειών του μεταφορικού τομέα και μεγάλο αντίκτυπο στις εθνικές οικονομίες.

Σήμερα, είναι κοινώς αποδεκτό πως η χρήση καυσίμων με βάση τον άνθρακα αποτελεί μια από τις
σημαντικότερες απειλές του περιβάλλοντος λόγω του φαινομένου του θερμοκηπίου. Στην Ευρώπη,
οι μεταφορές αντιστοιχούν στο 25% των εκπομπών των αερίων του θερμοκηπίου (Green House Gas

                                               1
Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση
emission) και, συγκεκριμένα, οι οδικές μεταφορές είναι υπεύθυνες για το 70% των παραγόμενων
εκπομπών που οφείλονται στις μεταφορές, όπως αναφέρει σχετική αναφορά της Ευρωπαϊκής
Επιτροπής. Έχει προβλεφθεί πως οι οδικές μεταφορές θα αυξηθούν κατά 33% τα επόμενα 30 χρόνια
(Sbihi και Eglese 2007). Καθίσταται αναγκαία, λοιπόν, η αποδοτική δρομολόγηση και ο
προγραμματισμός με συνθήκες κυκλοφοριακής συμφόρησης, ώστε να μειωθούν οι περιβαλλοντικές
επιπτώσεις, αφού οι εκπομπές CO2 είναι συνυφασμένες με τους χρόνους διέλευσης, την ταχύτητα
των οχημάτων και τις διάφορες συνθήκες συμφόρησης. Στο προτεινόμενο έργο, θα εξεταστεί
ενδελεχώς το πρόβλημα δρομολόγησης οχημάτων και προγραμματισμού παραδόσεων με χρονικούς
περιορισμούς σε συνδυασμό με τις εκπομπές CO2, λόγω της χρονικής εξάρτησης τους με τις
ταχύτητες (Qian and Eglese, 2016).

Στις αστικές περιοχές, η κυκλοφοριακή συμφόρηση είναι ο πιο ισχυρός περιορισμός. Ως αποτέλεσμα
της κυκλοφοριακής συμφόρησης, οι χρόνοι διέλευσης εξαρτώνται από τον χρόνο εκκίνησης.
Συνεπώς, η δρομολόγηση των οχημάτων περιλαμβάνει το υπο-πρόβλημα της βελτιστοποίησης του
χρόνου αναχώρησης κάθε οχήματος (από την αποθήκη και από τον πελάτη). Ένας ακόμα χρονικός
περιορισμός είναι η συμμόρφωση με τους κανονισμούς του ωραρίου οδήγησης. Αν αυτός ο
περιορισμός συνδυαστεί με την κυκλοφοριακή συμφόρηση, το πρόβλημα δρομολόγησης και
προγραμματισμού γίνεται πολύ δύσκολο να επιλυθεί (AbdAllah, 2017; Wen and Eglese,2015). Τις
τελευταίες δεκαετίες, τα μοντέλα δρομολόγησης στόλου οχημάτων έχουν εξελιχθεί και είναι πιο
ρεαλιστικά. Παρόλα αυτά, έχουν αγνοηθεί οι πραγματικοί περιορισμοί κυκλοφοριακής συμφόρησης.
Εκτός των χρόνων διέλευσης, πρέπει να ληφθούν υπόψη οι χρόνοι αναμονής, ειδικά για παραδόσεις
με αυστηρούς χρονικούς περιορισμούς, αφού οι μεγάλοι χρόνοι αναμονής δημιουργούν υψηλά
κόστη μίσθωσης των οχημάτων ή μισθοδοσίας των οδηγών των φορτηγών και κάνουν τα οχήματα μη
διαθέσιμα για άλλες υπηρεσίες.

Στην Ελλάδα, η απελευθέρωση της αγοράς των μεταφορών θα μετατρέψει το συγκεκριμένο μοντέλο
των ανεξάρτητων μεταφορέων σε ένα πλήθος οργανωμένων εταιρειών αποθήκευσης και διανομής
με μεγάλους στόλους και πολύπλοκα φορτία μεταφοράς. Αυτή η νέα κατάσταση θα αυξήσει τη
σημασία δημιουργίας κατάλληλων μεθόδων και εργαλείων λογισμικού που μπορούν να
υποστηρίξουν τις αποφάσεις δρομολόγησης στόλου οχημάτων και προγραμματισμού παραδόσεων
που εξαρτώνται από χρονικούς περιορισμούς, ειδικά στα ελληνικά αστικά κέντρα που η συμφόρηση
είναι ένα σύνηθες και απρόβλεπτο φαινόμενο.

Η κυκλοφοριακή συμφόρηση σε αστικές περιοχές δεν έχει αντιμετωπιστεί αποτελεσματικά για
χρονικά εξαρτώμενα προβλήματα δρομολόγησης στόλου οχημάτων και προγραμματισμού
παραδόσεων, όπως προκύπτει από την ανάλυση της βιβλιογραφίας (Sohr, 2016). Εάν προστεθούν
περεταίρω χρονικοί περιορισμοί, όπως η οδήγηση και οι χρόνοι εργασίας, η βελτιστοποίηση των
αναχωρήσεων και χρόνων παράδοσης γίνεται εξαιρετικά δύσκολη. Παρ’ όλα αυτά, πλέον είναι πιο
εύκολη η συλλογή δεδομένων πραγματικού χρόνου (μέσω κινητών τηλεφώνων, GPS) και
                                              2
Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση
ιδιομορφίας του οδικού δικτύου μέσω GIS (Geographical information System) οι οποίες δίνουν την
δυνατότητα πρόβλεψης των χρόνων διέλευσης στα αστικά περιβάλλοντα. Επιπλέον, οι περιορισμοί
των περιβαλλοντικών επιπτώσεων άρχισαν πρόσφατα λαμβάνονται υπόψη στα προβλήματα
εμπορευματικών μεταφορών με σκοπό να ελαχιστοποιούνται οι εκπομπές του διοξειδίου του
άνθρακα (CO2), οι οποίες εξαρτώνται από τους χρόνους διέλευσης και τις ταχύτητες των φορτηγών
(Qian nd Eglese, 2016). Οι εταιρείες, λειτουργώντας σε ένα εξαιρετικά ανταγωνιστικό περιβάλλον,
πρέπει να διαχειριστούν πολλούς και αντικρουόμενους στόχους σχετικά με τον προγραμματισμό της
διανομής, τη μείωση του κόστους διανομής, την καλύτερη εξυπηρέτηση πελατών, τη συμμόρφωση
με τους νόμους και τους κανονισμούς και τη μείωση των περιβαλλοντικών επιπτώσεων. Έτσι, η
έρευνα σχετικά με την κυκλοφοριακή συμφόρηση μέσω του εξαρτημένου χρονικά προβλήματος
δρομολόγησης και προγραμματισμού παρουσιάζει ένα ακαδημαϊκό ενδιαφέρον και πρακτικά
απασχολεί της εταιρείες εφοδιαστικής και έχει μεγάλο αντίκτυπο στην εθνική οικονομία, που μπορεί
να επωφεληθεί της έκβασης της.



Το Πρόβλημα Δρομολόγησης του Στόλου Οχημάτων σε Συγκεκριμένα Χρονικά Περιθώρια
(Vehicle Routing Problem with Time Windows - VRPTW)

Από το ξεκίνημα της χρήσης φορτηγών οχημάτων για τις παραδόσεις των παραγγελιών των
πελατών, οι υπεύθυνοι της εφοδιαστικής αντιμετωπίζουν στην πράξη το πρόβλημα
δρομολόγησης του στόλου οχημάτων (Vehicle Routing Problem – VRP). Από την στιγμή που οι
Dantzig και Ramser έθεσαν το «πρόβλημα αποστολής φορτηγών», έχει μετατραπεί σε ένα από
τα NP-hard προβλήματα που έχουν αναλυθεί περισσότερο. Μετά από 60 χρόνια, το βασικό
πρόβλημα έχει επεκταθεί και εξελιχθεί, λαμβάνοντας υπόψιν περισσότερους παράγοντες που
μετατρέπουν το πρόβλημα σε πιο δύσκολο προς επίλυση, οδηγώντας έτσι στην ανάπτυξη νέων
θεωριών του VRP και άλλων τομέων συνδυαστικών βελτιστοποιήσεων. Οι Bodin, Golden, Assad
και Ball (1983), Christofides (1985), Golden και Assad (1986), Christofides και Mingozzi (1990),
Ball (1995) παρέχουν ένα σύνολο ερευνητικών άρθρων για ειδικά θέματα δρομολόγησης
οχημάτων σε επιστημονικά περιοδικά και βιβλία. Οι Laporte και Osman (1995) έχουν
βιβλιογραφία με παραπάνω από 500 άρθρα που αφορούν τη δρομολόγηση του στόλου
οχημάτων. Παρόλα αυτά, το πρόβλημα προγραμματισμού παραδόσεων (Vehicle Scheduling
Problem - VSP) εστιάζει στους περιορισμούς που προκύπτουν είτε από τον πελάτη είτε από τις
πηγές που επηρεάζουν την παράδοση. Όταν οι ακαδημαϊκοί ερευνητές προσπαθούν να
εντοπίσουν το πρόβλημα του προγραμματισμού παραδόσεων και δρομολόγησης του στόλου
οχημάτων (Vehicle Routing and Scheduling Problem - VRSP), τείνουν να απομονώνουν τα
επιμέρους ζητήματα (και περιορισμούς) που τίθενται και να αντιμετωπίζουν μόνο έναν κάθε
φορά έτσι ώστε να ελαχιστοποιήσουν τον αριθμό των μεταβλητών που χρησιμοποιούν.
                                               3
Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση
Παρά το μεγάλο όγκο έρευνας που έχει πραγματοποιηθεί στη δρομολόγηση στόλου οχημάτων,
δεν υπάρχει ένας αλγόριθμος που μόνος του να λύνει με βέλτιστο τρόπο κάθε πρόβλημα
δρομολόγησης οχημάτων και προγραμματισμού παραδόσεων. Οι αλγόριθμοι και οι μέθοδοι
έχουν αναπτυχθεί για να λύνουν με βέλτιστο τρόπο συγκεκριμένες κατηγορίες προβλημάτων
δρομολόγησης οχημάτων και προγραμματισμού παραδόσεων, αντιμετωπίζοντας ένα ζήτημα τη
φορά ώστε να ελαχιστοποιήσουν τον αριθμό μεταβλητών που χρησιμοποιούν. Οι πρακτικές
εφαρμογές σε προβλήματα δρομολόγησης στόλου οχημάτων με συγκεκριμένα χρονικά
περιθώρια χρησιμοποιούν ευρετικούς αλγορίθμους για την εξεύρεση λύσεων. Τα διαστήματα
που ο πελάτης είναι διαθέσιμος ή επιθυμεί να λάβει μια παράδοση καθορίζουν τους
περιορισμούς στους χρόνους παράδοσης. Αυτοί ακριβώς οι περιορισμοί εκφράζονται σε όρους,
ενός ή πολλών, χρονικών διαστημάτων μέσα στα οποία πρέπει να εξυπηρετηθεί ο κάθε πελάτης.
Σε περίπτωση που κάποιο όχημα φτάσει σε έναν πελάτη πριν την έναρξη του χρόνου
παράδοσης, τότε θα πρέπει να περιμένει για να παραδώσει το εμπόρευμα που μεταφέρει.
Άλλες περιπτώσεις αντιμετωπίζουν τα χρονικά περιθώρια ως πιο χαλαρούς περιορισμούς, όπου
η εξυπηρέτηση επιτρέπεται να γίνει νωρίτερα ή αργότερα από τον προκαθορισμένο χρόνο, αλλά
με το κόστος κάποιας ποινής. Δεδομένων των απαιτήσεων τόσο για την καλύτερη εξυπηρέτηση
των πελατών όσο και για την ελαχιστοποίηση του κόστους μεταφοράς, έχουν αναπτυχθεί
αρκετοί αλγόριθμοι που επιδιώκουν στην ταυτόχρονη ικανοποίηση των απαιτήσεων. Πιο
συγκεκριμένα οι Beheshti, Hejazi και Alinaghian (2015) πρότειναν την τοποθέτηση με σειρά
προτεραιότητας (prioritize) από τους πελάτες των καλύτερων για τους ίδιους ωρών παράδοσης
των παραγγελιών, ώστε να καταφέρουν να συνθέσουν την αντικειμενική συνάρτηση της
βέλτιστης εξυπηρέτησης. Οι Saeheaw και Charoenchai     et al. (2016) προτείνουν τρεις
μεταευρετικούς αλγορίθμους τους οποίους ταυτόχρονα αξιολογούν, αναγνωρίζοντας τα δυνατά
και αδύναμα σημεία τους.



Δυναμικά και Πραγματικού Χρόνου Προβλήματα Δρομολόγησης

Πολλά μοντέλα έχουν αναπτυχθεί για να βοηθήσουν στον έλεγχο και στη διαχείριση των
εμπορευματικών μεταφορών σε πραγματικό χρόνο. Ο κύριος στόχος παραμένει ίδιος, δηλαδή
να ελαχιστοποιείται το κόστος μεταφοράς. Για να επιτευχθεί κάτι τέτοιο, πρέπει να
δημιουργούνται αποδοτικές και αξιόπιστες διαδρομές κάτι το οποίο έρχεται σε αντίθεση με τις
συνεχώς αυξανόμενες απαιτήσεις εξυπηρέτησης των πελατών καθώς και με την αβεβαιότητα
των χρόνων μεταφοράς λόγω κυκλοφοριακής συμφόρησης, σύμφωνα με την έρευνα των Groß,
Ulmer, Ehmke, Mattfeld (2015). Τα μοντέλα αυτά εξαρτώνται από πληροφορίες που
ενημερώνονται συνεχώς ώστε να είναι πιο αποτελεσματικά, και επομένως θεωρείται

                                             4
Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση
απαραίτητη η ενσωμάτωση πληροφοριών πραγματικού χρόνου σχετικά με την τοποθεσία των
οχημάτων και τις τρέχουσες πληροφορίες για την κατάσταση του οδικού δικτύου (όπως
απρόσμενη συμφόρηση λόγω ατυχήματος ή κακών καιρικών συνθηκών) κατά την υλοποίηση
του έργου. Όταν συμβαίνουν τέτοια γεγονότα, οι υπεύθυνοι δρομολόγησης πρέπει να έχουν τη
δυνατότητα να επαναδρομολογήσουν τα οχήματα, υπό το πρίσμα νέων και ενημερωμένων
πληροφοριών, τα οποία τελικά παρέχουν τις υπηρεσίες στους προκαθορισμένους χρόνους. Τα
μοντέλα που εντοπίζονται στην παραπάνω κατάσταση αποτελούν τυπικές μεταβλητές του
προβλήματος δρομολόγησης οχημάτων και προγραμματισμού παράδοσης, που αναγνωρίζονται
στην βιβλιογραφία ως «πρόβλημα δυναμικής δρομολόγησης στόλου οχημάτων» (Dynamic
Vehicle Routing and Scheduling Problem - DVRSP) (Minkoff, 1993). Το δυναμικό πρόβλημα
απαιτεί αλγορίθμους που επεξεργάζονται τα άμεσα αιτήματα που πρέπει να εξυπηρετηθούν σε
πραγματικό χρόνο, εφόσον αυτό είναι δυνατό. Τα συμβατικά στατικά προβλήματα
δρομολόγησης οχημάτων χαρακτηρίζονται ως “NP-hard” που σημαίνει ότι δεν είναι πάντα
εφικτό να βρεθούν βέλτιστες λύσεις για προβλήματα με πραγματικά μεγέθη σε ένα λογικό
υπολογιστικό χρόνο. Συνεπώς, το δυναμικό πρόβλημα δρομολόγησης στόλου οχημάτων και
προγραμματισμού παραδόσεων ανήκει επίσης στην τάξη των NP-hard προβλημάτων, αφού ένα
στατικό πρόβλημα θα μπορούσε να επιλύεται κάθε φορά που ένα νέο αίτημα λαμβάνεται.
Γενικά, όσο πιο περιορισμένο και περίπλοκο είναι το κάθε πρόβλημα, τόσο πιο περίπλοκη
γίνεται και η εισαγωγή των πελατών με δυναμικό τρόπο (βλ. Hvattum et al., (2006)). Για
παράδειγμα, η ένταξη νεοεισερχόμενης ζήτησης πελατών με τον περιορισμό προκαθορισμένων
χρόνων θα είναι ένα πιο δύσκολο πρόβλημα στην επίλυση από ότι αυτό στο οποίο δεν
υπάρχουν περιορισμοί χρόνων (Larsen et al., 2008). Έτσι λοιπόν, στο πρόβλημα του δυναμικού
προγραμματισμού παρότι οι παραγγελίες των πελατών λαμβάνονται ενώ έχει ξεκινήσει η
διαδικασία, μοντελοποιείται ως στατικό VRP στο οποίο θα περιέχονται μόνο οι γνωστοί μέχρι
εκείνη την στιγμή πελάτες, οι οποίοι δεν έχουν εξυπηρετηθεί (Montemanni et al., 2005). Σε αυτή
την βάση λοιπόν έχουν δημιουργηθεί αρκετοί γενετικοί αλγόριθμοι οι οποίοι δίνουν λύση στο
πρόβλημα του δυναμικού προγραμματισμού όπως των AbdAllah και Sarker (2017), Hanshar και
Ombuki-Berman (2006) και Montemanni 2005.



Προβλήματα Δρομολόγησης και Προγραμματισμού Παραδόσεων Εξαρτημένα από τον Χρόνο

Το χρονικά εξαρτημένο πρόβλημα δρομολόγησης στόλου οχημάτων και προγραμματισμού
παραδόσεων (Time Dependent Vehicle Routing and Scheduling Problem - TDVRSP) ασχολείται με
το βέλτιστο τρόπο δρομολόγησης ενός στόλου οχημάτων σταθερής χωρητικότητας, όταν οι
χρόνοι διέλευσης μεταξύ των κόμβων μίας διαδρομής εξαρτώνται από την ώρα της ημέρας που

                                              5
Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση
ξεκίνησε το ταξίδι σε αυτή τη διαδρομή. Δεδομένου ότι οι χρόνοι διέλευσης έχουν σημαντικό
αντίκτυπο στην αποδοτικότητα και την αξιοπιστία των προγραμματισμένων διαδρομών, είναι
απαραίτητες οι πληροφορίες που αφορούν τους χρόνους αυτούς. Καινούριες εξελίξεις στις
τεχνολογίες τηλεματικής δίνουν την δυνατότητα εξαγωγής χρονικών δεδομένων       από
πραγματικά δεδομένα (όπως για παράδειγμα το Floating Car Data (Shor και Brockfeld et al.
2016)). Η βελτιστοποίηση έγκειται στην εύρεση της λύσης που ελαχιστοποιεί και τον αριθμό
ταξιδιών που εκτελούν τα οχήματα και το συνολικό χρόνο διέλευσης ή το συνολικό κόστος. Δύο
αλγόριθμοι που λειτουργούν πάνω στην ίδια βάση είναι ο LANTIME (Wen & Eglese 2015) και ο
LANCOST (Maden 2010) που πέρα από την ελαχιστοποίηση των ταξιδιών, στοχεύουν στην
ελαχιστοποίηση του συνολικού χρόνου και του συνολικού κόστους αντίστοιχα. Η διάρκεια του
ταξιδιού υπολογίζεται βάσει του χρόνου αναχώρησης, που είναι μία γνωστή παράμετρος, και
έχοντας μία ακριβή εκτίμηση της μέσης ταχύτητας του οχήματος κατά την διάρκεια του ταξιδιού
του. Αυτή η περίπτωση του προβλήματος δρομολόγησης είναι πολύ σημαντική για την πρακτική
υποστήριξη της διανομής, αφού στις περισσότερες των περιπτώσεων οι κυκλοφοριακές
συνθήκες δεν είναι δυνατόν να αγνοηθούν, ειδικά τις ώρες αιχμής που η κυκλοφοριακή
συμφόρηση σε κεντρικούς δρόμους θα προκαλέσει, εξ’ ορισμού σημαντικές καθυστερήσεις.
Ελαχιστοποιώντας τον συνολικό χρόνο διέλευσης, οι λύσεις που δημιουργούνται τείνουν να
κατευθύνουν τα οχήματα σε δρόμους στους οποίους μπορούν να ταξιδέψουν με μεγαλύτερη
ταχύτητα. Από αυτή την οπτική, οι λύσεις του προβλήματος προγραμματισμού των παραδόσεων
και δρομολόγησης των οχημάτων μπορεί, σε κάποιες περιπτώσεις, να προτείνουν διαδρομές
μεγαλύτερης, συνολικά, απόστασης. Ακόμα και έτσι, πρέπει να συνυπολογίζονται τα
περιβαλλοντικά οφέλη, γιατί όταν τα οχήματα ταξιδεύουν λιγότερο χρόνο και με
περιβαλλοντικά φιλικές ταχύτητες προκαλείται λιγότερη μόλυνση. Παραδείγματα αυτής της
προσέγγισης αναφέρονται από τους Donati et al. (2008), Maden και Eglese et al (2010),
Malandraki και Daskin (1992) και Qian και Eglese et al. (2015). Στην πραγματικότητα, όταν
απαιτείται διαχείριση χρονικών περιορισμών, όπως είναι τα αυστηρά χρονικά περιθώρια (HTW)
παραδόσεων στους πελάτες, οι λύσεις κλασσικών προβλημάτων δρομολόγησης οχημάτων δεν
μπορούν να εφαρμοστούν, γεγονός που εντείνεται από την μεταβλητότητα των κυκλοφοριακών
συνθηκών. Από την άλλη ακόμα και εάν δεν υπήρχαν αυστηροί χρονικοί περιορισμοί, οι
κλασσικές μέθοδοι επίλυσης του προβλήματος δρομολόγησης θα έδιναν σχεδόν βέλτιστες
λύσεις. Έτσι, ένα επιπρόσθετο πλεονέκτημα αυτής της προσέγγισης (της ελαχιστοποίησης του
χρόνου διέλευσης) είναι πως επιτρέπει να ικανοποιηθούν με μεγαλύτερη αξιοπιστία οι χρονικοί
περιορισμοί παράδοσης. Για ένα εξαρτημένο από το χρόνο μοντέλο, οι χρόνοι διέλευσης μπορεί
να εξαρτώνται επίσης και από άλλους παράγοντες, όπως η μέρα της εβδομάδας ή η εποχή του
χρόνου. Με αυτές τις ιδέες ασχολήθηκαν οι Haghani και Jung (2005) και Chen et al., (2005),

                                             6
Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση
Eglese et al., (2006), που μελέτησαν τα θέματα που εμπλέκονται στην κατασκευή μιας βάσης
δεδομένων για χρόνους διέλευσης ενός συγκεκριμένου οδικού δικτύου και πάνω στην οποία
βασίζονται οι αλγόριθμοι LANTIME και LANCOST.

Για να λυθεί το πρόβλημα με συγκεκριμένα χρονικά περιθώρια, οι απαιτήσεις δεδομένων είναι
εξαιρετικά υψηλότερες απ’ ότι αυτές των συμβατικών προβλημάτων. Αντί να απαιτείται απλώς
η απόσταση μεταξύ των κόμβων του γράφου που αναπαριστά το οδικό δίκτυο, απαιτείται
επιπλέον ένα σύνολο χρόνων διέλευσης των οδικών δικτύων για κάθε χρονικό διάστημα που
ορίζεται. Η συντομότερη διαδρομή μεταξύ δύο κόμβων μπορεί να διαφέρει, ανάλογα με το
χρόνο διέλευσης (Fu και Rilett, 2000). Για την παροχή αξιόπιστων αποτελεσμάτων, η προσέγγιση
του προβλήματος με συγκεκριμένα χρονικά περιθώρια χρειάζεται έναν αρκετά ακριβή
υπολογισμό των οδικών χρόνων διέλευσης. Υπάρχουν πολλές ερευνητικές προσπάθειες που
ασχολούνται με μεθόδους πρόγνωσης των χρόνων διέλευσης, χρησιμοποιώντας αρκετές
γνωστές τεχνικές, όπως αυτή του Eliasson, (2006): εγγραφές ιστορικού οδικών χρόνων
διέλευσης, μοντέλα χρονολογικής σειράς, νευρωνικά δίκτυα, μη παραμετρικά μοντέλα
παλινδρόμησης, μοντέλα προσομοίωσης της κυκλοφορίας, δυναμικά μοντέλα καταμερισμού της
κυκλοφορίας ή μεθόδους πρόγνωσης του πραγματικού χρόνου διέλευσης βασιζόμενες στη
γνώση όπως αυτές περιγράφονται από τους Lee et al. (2009). Επιπλέον, στοχαστικά μοντέλα που
χρησιμοποιούν σύνθετες κατανομές (Burr III Type XII) δίνουν αποτελέσματα κοντά στους
πραγματικούς χρόνους διέλευσης (Susilawati et al. 2013), σε αντίθεση με ντετερμινιστικά που
δεν παρέχουν πληροφορίες αβεβαιότητα των χρόνων διέλευσης (Groß, Ulmer, Ehmke, Mattfeld
et al., 2015).

Οι ερευνητές συμπεραίνουν πως η μεταβλητότητα που εισάγεται από την κυκλοφοριακή
συμφόρηση δεν αντιμετωπίζεται επαρκώς από τα υπάρχοντα χρονικά εξαρτώμενα μοντέλα
δρομολόγησης στόλου οχημάτων και προγραμματισμού παραδόσεων (Kok et al., 2009). Αυτό το
συμπέρασμα έχει σημαντικές επιπτώσεις στους χρόνους παράδοσης, στην εξυπηρέτηση των
πελατών και στην συνολική απόδοση του συστήματος μεταφοράς. Η κυκλοφοριακή συμφόρηση
εξαρτάται κυρίως από την τοποθεσία του οδικού τμήματος και από τον χρόνο της ημέρας που
γίνεται η διέλευση. Συνεπώς, η αποφυγή της συμφόρησης εξαρτάται μόνο από το να μη
βρίσκεται κάποιος στο λάθος σημείο τη λάθος στιγμή. Υπάρχουν πολλές στρατηγικές για να
επιτευχθεί αυτό. Για παράδειγμα, η αλλαγή της σειράς παραδόσεων ενός οχήματος μπορεί να
το οδηγήσει στην αποφυγή μεγάλης κυκλοφοριακής συμφόρησης. Μια διαφορετική τεχνική
αποφυγής του κυκλοφοριακού φόρτου είναι η μετατόπιση ενός πελάτη από μια διαδρομή
οχήματος σε μια άλλη. Αυτές οι στρατηγικές μπορούν να βελτιστοποιηθούν λύνοντας ένα
πρόβλημα δρομολόγησης οχημάτων με εξαρτημένους χρόνους διέλευσης (TDVRSP). Οι εξελίξεις


                                             7
Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση
της τεχνολογίας καθώς και η ανάγκη λύσης του χρονικά εξαρτημένου προβλήματος έχουν
οδηγήσει τα τελευταία χρόνια σε μεγάλη ανάπτυξη και έρευνα, δημιουργώντας αναλόγως
μεγάλο όγκο βιβλιογραφίας. Ορισμένες προσπάθειες έχουν γίνει από τους Huang και Zhao et al.
(2016), Kok et al. (2012) και Jiang et al. (2015). Μια επιπλέον στρατηγική αποφυγής της
συμφόρησης είναι η επιλογή εναλλακτικών διαδρομών μεταξύ δυο πελατών σε περιόδους
υψηλής κυκλοφοριακής συμφόρησης (Huang και Zhao et al., 2016). Αυτή η στρατηγική
συνεπάγεται πως η διαδρομή μεταξύ δυο πελατών εξαρτάται από τον επιλεγόμενο χρόνο
αναχώρησης, η οποία μπορεί να βελτιστοποιηθεί λύνοντας ένα πρόβλημα συντομότερης
διαδρομής με εξαρτημένους χρόνους διέλευσης (Time Dependent Shortest Path Problem -
TDSPP). Οι Orda και Rom (1990) όπως επίσης και οι Brodal και Jacob (2004) υποστηρίζουν πως η
λύση ενός χρονικά εξαρτώμενου προβλήματος συντομότερης διαδρομής (SPP) για συγκεκριμένο
χρόνο αναχώρησης μπορεί να γίνει με τη χρήση ενός τροποποιημένου αλγορίθμου Dijkstra
(1959), ο οποίος ανήκει στην κατηγορία των κλασικών αλγορίθμων δρομολόγησης.


Βιβλιογραφία
AbdAllah A.M.F.M., Essam D.L. and Sarker R.A., (2017) On solving periodic re-optimization
dynamic vehicle routing problems, Applied Soft Computing Journal, Vol. 55, pp. 1–12.

Bagchi P.K., Nag B.N., (1991) Dynamic vehicle scheduling: An expert systems approach,
International Journal of Physical Distribution and Logistics Management 21, pp. 10–18.

Ball M. (1995) Handbooks in OR and MS, Vol 8 Network Routing, Elsevier, North Holland,
Amsterdam.

Ball, M., Golden, B., Assad, A. and Bodin, L. (1983) Planning for truck fleet size in the presence of
a common-carrier option, Decision Sciences, Vol. 14, pp. 103-120.

Beheshti A.K., Hejazi S.R. and Alinaghian M., (2015) The vehicle routing problem with multiple
prioritized time windows: A case study, Computers & Industrial Engineering, vol. 90, pp. 402–413.

Bertsimas D. and Simchi-Levi D. (1996) A new generation of vehicle routing research: robust
algorithms, addressing uncertainty, Operations Research, vol. 44, pp. 286-304, 1996.

Braysy, O., (2002) Fast local searches for the vehicle routing problem with timewindows.INFOR,
40, pp. 319-330.

Chen, H.K., Hsueh, C.F. and Chang, M.S., (2005) The real-time time-dependent vehicle routing
problem. Transportation Research Part E-Logistics and Transghaportation Review, 42(5), pp. 383-
408.

Christofides, N., (1985) The Vehicle Routing, in Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and
Shmoys, D.B. (eds.), The Travelling Salesman Problem, John Wiley & Sons, NY

Christofides, N., A. Mingozzi (1990) Vehicle routing: Practical and algorithm aspects. C. F. H. van
Rijn, ed. LOGISTICS: Where Ends Have to Meet. Pergamon Press, Oxford, U.K.


                                                  8
Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση
Coyle, J.J., Bardi E.J. and Langley J.C (1996) The Management of Business Logistics, 6th edition, St.
Paul, MN: West Publishing Company.

Dantzig, G.B., Ramser, H.J., (1959) The truck dispatching problem, Management Science 6 (1), pp.
80–91.

Dijkstra, E. W. (1959) A note on two problems in connexion with graphs, Numerische Mathematik
pp. 269–271.

Donati A.V., Montemanni R., Casagrande N., Rizzoli A.E., Gambardella L.M. (2008) Time
dependent vehicle routing problem with a multi ant colony system, European Journal Of
Operational Research, Volume 185, Issue 3, Elsevier, pp. 1174-1191.

Eglese, R.W., Maden, W. and Slater, A., (2006) A road timetable to aid vehicle routing and
scheduling. Computers and Operations Research, 33, pp. 3508- 3519.

Eliasson, J. (2006) Forecasting travel time variability. Proceedings of the 2006 European Transport
Conference.

Ericsson, E., Larsson, H., and Brundell-Freij, K. (2006) Choice for lowest fuel consumption
potential effects of a new driver support tool. Transportation Research Part C, 14, 369-383.

Fleischmann, B., Gietz, M. and Gnutzmann, S. (2004). Time-varying travel times in vehicle routing,
Transportation science 38(2), pp. 160–173.

Fu, L.P. and Rilett, L.R., (2000) Estimation of time-dependent, stochastic route travel times using
artificial neural networks. Transportation Planning and Technology 24(1), pp. 25-48.

Gendreau M., J. Potvin, (1998) Dynamic Vehicle Routing and Dispatching. In: Crainic, T.G. and
Laporte, G., (editors), Fleet Management and Logistics, Kluwer Academic Publishers, pp. 115-226.

Ghiani G, Guerriero F, Laporte G, Musmanno R. (2003) Real-time vehicle routing: Solution
concepts, algorithms and parallel computing strategies, European Journal of Operational
Research, 151, pp. 1–11.

Golden, B., and Assad, A. (1986), Perspectives on vehicle routing: Exciting new developments,
Operations Research 34, 803-810.

Golden, B.L. and Assad A.A. (eds.) (1988) Vehicle Routing: Methods and Studies, Elsevier Science,
North Holland, Amsterdam.

Groß P.O., Ulmer M.W., Ehmke J.F. and Mattfeld D.C., (2015) Exploiting travel time information
for reliable routing in city logistics, Transportation Research Procedia, vol. 10, no. July, pp. 652–
661.

Haghani, A. and Jung, S. (2005) A dynamic vehicle routing problem with time-dependent travel
times, Computers & operations research 32(11), pp. 2959–2986.

Hanshar F.T. and Ombuki-Berman B.M., (2007) Dynamic vehicle routing using genetic algorithms,
Applied Intelligence, vol. 27, no. 1, pp. 89–99.

Hashimoto, H., Yagiura, M. and Ibaraki, T. (2008) An iterated local search algorithm for the time-
dependent vehicle routing problem with time windows, Discrete Optimization 5, pp. 434–456.




                                                  9
Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση
Huang Y., Zhao L., Van Woensel T. and Gross J-P., (2017) Time-dependent vehicle routing
problem with path flexibility, Transportation Research Part B: Methodological, vol. 95, pp. 169–
195.

Hvattum, L.M., Løkketangen, A. and Laporte,G. (2006) Solving a dynamic and stochastic vehicle
routing problem with a sample scenario hedging heuristic. Transportation Science, 40(4), pp. 421-
438

Ichoua, S., Gendreau, M. and Potvin, J. (2003) Vehicle dispatching with time-dependent travel
times, European journal of operational research 144(2), pp. 379–396.

Kallehauge, B., Larsen, J. and Madsen, O.B.G. (2006) Lagrangean duality ap-plied to the vehicle
routing with time windows. Computers & Operations Research.

Kolen, A.W.J., Rinnooy Kan, A.H.G. and Trienekens, H.W.J.M. (1987) Vehicle routing withtime
windows, Operations Research 35(2), pp. 266–273.

Kok, A.L. and Hans, E.W. and Schutten, J.M.J. (2009) Vehicle routing under time-dependent travel
times: the impact of congestion avoidance, Internal Report, Faculty: Management and
Governance (SMG), University of Twente, Netherlands, http://doc.utwente.nl/70218.

Kok A.L., Hans E.W. and Schutten J.M.J., (2012) Vehicle routing under time-dependent travel
times: The impact of congestion avoidance, Computers & Operations Research, vol 39, no. 5, pp
910–918.

Laporte, G. and Osman, I.H. (1995) Routing problems: A bibliography, Annals of Operations
Research, 61, pp. 227-262.

Larsen, A., Madsen, O., Solomon, M. (2008) Recent Developments in Dynamic Vehicle Routing
Systems, In Golden, B., Raghavan, S., and Wasil, E. (eds), The Vehicle Routing Problem: Latest
Advances and New Challenges, Berlin: Springer, Operations Research/Computer Science
Interfaces Series, pp. 199-220.

Lau, H.C., Sim, M. and Teo, K.M., (2003) Vehicle routing problem with timewindows and a limited
number of vehicles. European Journal of OperationalResearch, 148, pp. 559-569.

Lee W.-H., Tseng S.-S. and Tsai S.H. (2009) A knowledge based real-time travel time prediction
system for urban network, Expert Systems with Applications, Volume 36, Issue 3, Part 1, pp.
4239-4247.

Maden W., Eglese R. and Black D., (2009) Vehicle Routing and Scheduling with Time Varying Data:
A Case Study, Journal of the Operational Research Society, vol. 61, no. 3, pp 515–522.

Malandraki, C., and Daskin, M.S. (1992) Time Dependent Vehicle Routing Problems:
Formulations, Properties and Heuristic Algorithms. Transportation Science, 26(3), pp. 185-200.

Minkoff, Alan S. (1993) A Markov Decision Model and Decomposition Heuristic for Dynamic
Vehicle Dispatching, Oper. Res., Vol. 41, No. 1, pp. 77-90.

Montemanni, R., Gambardella, L.M., Rizzoli, A.E., Donati, A.V., (2005) AntColony System for a
Dynamic Vehicle Routing Problem. Journal of Combi-natorial Optimization, 10(4), pp. 327-343.

Orda, A. and Rom, R. (1990) Shortest-path and minimum-delay algorithms in networks with time-
dependent edge-length, Journal of the Association for Computing Machinery 37(3), pp. 607–625.


                                               10
Πρόταση Έργου στο Πλαίσιο της Δράσης: «ΕΡΕΥΝΩ – ΔΗΜΙΟΥΡΓΩ – ΚΑΙΝΟΤΟΜΩ»
Ακρωνύμιο Έργου: SMARTRANS
Έντυπο 1: Συνοπτική Έκθεση
Qian J. and Eglese R., (2016) Fuel emissions optimization in vehicle routing problems with time-
varying speeds, European Journal of Operational Research, vol. 248, no. 3, pp. 840–848.

Saeheaw T. and Charoenchai N., (2016) Comparison of Meta-heuristic Algorithms for Vehicle
Routing Problem with Time Windows BT - Advanced Computer and Communication Engineering
Technology: Proceedings of ICOCOE 2015. In: Sulaiman HA, Othman MA, Othman MFI, Rahim YA,
Pee NC (eds). Springer International Publishing, Cham, pp 1263–1273

Sbihi, A and Eglese, RW (2007) The relationship between vehicle routing and scheduling and
green logistics - a literature survey. Working Paper. The Department of Management Science,
Lancaster University, http://eprints.lancs.ac.uk/7042.

Sohr A., Brockfeld E., Sauerländer A. and Melde E., (2016) Traffic Information System for Hanoi,
Procedia Engineering, vol. 142, pp 221–228.

Susilawati S., Taylor M.A.P. and Somenahalli S.V.C., (2013) Distributions of travel time variability
on urban roads, Journal of Advanced Transportation, vol. 47, no. 8, pp. 720–736.

Toth, P. and Vigo, D. (2002) Models, relaxations and exact approaches for the capacitated vehicle
routing problem, Discrete Applied Mathematics, Vol. 123, No. 1–3, pp. 487– 512.

Wen L. and Eglese R., (2015) Minimum cost VRP with time-dependent speed data and congestion
charge, Computers and Operations Research, vol. 56, pp. 41–50.

You J. and Kim T.Y. (1998) Toward developing an expert GIS-Based travel time forecasting model
with congestion pattern analysis, technical report, http://trid.trb.org/view.aspx?id=513958.

Woensel, Van T., Kerbache, L., Peremans, H. and Vandaele, N. (2008) Vehicle routing with
dynamic travel times: A queueing approach, European journal of operational research 186(3), pp.
990–1007.

Zeimpekis, V., and Giaglis, G.M., (2006) Urban dynamic real-time distribution services: Insights
from SMEs. Journal of Enterprise Information Systems, 19(4), pp. 367-388, 2006.




O πλήρης κατάλογος των βιβλιογραφικών αναφορών που αξιοποιήθηκαν στην πρόταση είναι
διαθέσιμος στην ηλεκτρονική διεύθυνση: http://apps.simor.ntua.gr/smartrans_references.




                                                 11