ʼρθρο του Παντελή Γιαννέλου*
Η διαχείριση στόλου οχημάτων αποτελούσε πάντα έναν «πονοκέφαλο» για τις μεταφορικές και τις logistics εταιρείες. Σήμερα όμως που τα καύσιμα είναι πανάκριβα και οι αστοχίες απαγορεύονται, η ορθή διαχείριση στοχεύει όχι μόνο στην απρόσκοπτη λειτουργία, αλλά και στον περιορισμό του κόστους.
Η μεταφορά και διανομή προϊόντων είναι από τις σημαντικότερες δραστηριότητες της εφοδιαστικής αλυσίδας και συνήθως αντιστοιχούν στο μεγαλύτερο ποσοστό των δαπανών logistics μιας εμπορικής ή βιομηχανικής επιχείρησης. Η διανομή προϊόντων αφορά την εξυπηρέτηση, σε μια δεδομένη χρονική περίοδο, ενός συνόλου από πελάτες μέσω ενός πλήθους οχημάτων, τα οποία έχουν αφετηρία τους μια συγκεκριμένη τοποθεσία (λ.χ. μια αποθήκη), χρησιμοποιούνται από δεδομένο αριθμό οδηγών και πραγματοποιούν τις κινήσεις τους χρησιμοποιώντας ένα συγκεκριμένο οδικό δίκτυο.
Δρομολόγηση σε οδικό δίκτυο
Το πρόβλημα της βέλτιστης δρομολόγησης εμφανίζεται σε πολλές μορφές, ανάλογα με το πόσο περίπλοκο είναι το επιχειρηματικό περιβάλλον, και επιλύεται με διάφορους τρόπους που περιλαμβάνουν πλήθος αλγορίθμων βελτιστοποίησης ακέραιου προγραμματισμού. Οι αλγόριθμοι αυτοί προτείνουν βέλτιστες λύσεις δρομολόγησης ή λύσεις που πλησιάζουν τη βέλτιστη δρομολόγηση, λαμβάνοντας υπόψη πολλαπλά κριτήρια και περιορισμούς. Ο πίνακας 1 παρουσιάζει μια καταγραφή των βασικών χαρακτηριστικών των προβλημάτων διανομών.
Ένα πλήθος αστάθμητων γεγονότων (όπως καιρικά φαινόμενα, έλλειψη χώρων στάθμευσης, βλάβες οχημάτων, καθυστερήσεις στην παράδοση, συνεισφέρουν στην πολυπλοκότητα του προβλήματος των αστικών διανομών). Αυτοί οι παράγοντες μπορούν να αλλοιώσουν την ποιότητα ενός βέλτιστου ή σχεδόν βέλτιστου δρομολογίου, με αποτέλεσμα να υπάρχουν σημαντικές αποκλίσεις από το προσχεδιασμένο δρομολόγιο.
Συνήθης οργάνωση δρομολόγησης
Στις περισσότερες εταιρείες, η συνήθης διαδικασία οργάνωσης των δρομολογίων περιλαμβάνει τα ακόλουθα στάδια:
* Καθημερινή ομαδοποίηση πελατολογίου με χρήση κριτηρίων όπως η οδική απόσταση μεταξύ των πελατών, η επιθυμητή ώρα παράδοσης προϊόντων και ο χρόνος παραμονής ανά πελάτη.
* Καθημερινή δημιουργία λίστας κατάταξης πελατολογίου με χρήση κριτηρίων όπως είναι η βέλτιστη δρομολόγηση οχημάτων με βάση τη συνολική διανυομένη απόσταση και η βέλτιστη σειρά εξυπηρέτησης πελατολογίου ανά όχημα.
* Δημιουργία βέλτιστων διαδρομών εξυπηρέτησης πελατολογίου (χρονική ή χιλιομετρική) με χρήση κριτηρίων όπως είναι οι υπάρχουσες μονοδρομήσεις και απαγορεύσεις καθώς και η προσπελασιμότητα του οδικού δικτύου.
Δρομολόγηση & επιχειρησιακή έρευνα
Στο Πρόβλημα Δρομολόγησης Οχημάτων (Vehicle Routing Problem [VRP]) επιδιώκεται ο προσδιορισμός των βέλτιστων δρομολογίων στόλου οχημάτων για τη μεταφορά αγαθών από την κεντρική αποθήκη στις τοποθεσίες των πελατών. Η δρομολόγηση ενός στόλου οχημάτων αναφέρεται σε προβλήματα διανομών στα οποία η πληροφορία που απαιτείται για το σχεδιασμό των δρομολογίων αποκαλύπτεται με δυναμικό τρόπο στον υπεύθυνο δρομολόγησης. Το πρόβλημα της δρομολόγησης περιλαμβάνει αρκετές στατικές και δυναμικές παραμέτρους, οι οποίες αυξάνουν την πολυπλοκότητα της διαδικασίας προγραμματισμού των δρομολογίων:
Αριθμός σταδίων: Πολλά προβλήματα δρομολόγησης ενσωματώνουν ένα ή δύο διακριτά στάδια (απλή παράδοση ή παράδοση και παραλαβή εμπορευμάτων στο ίδιο δρομολόγιο).
Χρονικά παράθυρα διανομών: Σε αρκετές περιπτώσεις, κυρίως μεγάλων πελατών (π.χ. μεγάλα σούπερ μάρκετ), ορίζονται χρονικά παράθυρα παραδόσεων, κατά τη διάρκεια των οποίων και μόνο, είναι σε θέση να παραλάβει ο πελάτης.
Δυναμικοί χρόνοι ταξιδίου και στάσεων για εκφόρτωση: Τυπικά προβλήματα (καθυστερήσεις λόγω κυκλοφοριακής συμφόρησης, έλλειψης χώρων στάθμευσης, βλάβης των οχημάτων, φυσικών αιτιών) μεταβάλλουν τους χρόνους των δρομολογίων παράδοσης, με αποτέλεσμα να υπάρχει ανάγκη επαναδρομολόγησης.
Απρόσμενη ζήτηση: Κατά την παραλαβή μίας νέας, έκτακτης παραγγελίας, η οποία πρέπει να διεκπεραιωθεί την ίδια μέρα, δημιουργείται η ανάγκη επαναδρομολόγησης.
Ποσότητα ζήτησης: Λόγω απρόσμενης ζήτησης, το όχημα μπορεί να διαθέσει όλο το απόθεμα στα πρώτα στάδια της διανομής, με αποτέλεσμα να υπάρχει ανάγκη επιστροφής στην αποθήκη για ανεφοδιασμό ή επαναδρομολόγησης ενός δεύτερου οχήματος.
Περιορισμοί δρομολόγησης
Με βάση περισσότερο πραγματικά επιχειρησιακά προβλήματα δικτύων δρομολόγησης, στα μοντέλα που τα περιγράφουν εμφανίζονται συνήθως αρκετοί περιορισμοί που πρέπει να λαμβάνονται υπόψη.
Σημεία παραγωγής: Στην απλούστερη περίπτωση, υπάρχει ένα σημείο διάθεσης που εξυπηρετεί κάποιο συγκεκριμένο αριθμό πελατών κάνοντας χρήση συγκεκριμένου αριθμού οχημάτων. Μπορεί όμως να υπάρχουν περισσότερα σημεία παραγωγής, ή να υπάρχει διαφοροποίηση ως προς τα προϊόντα που είναι διαθέσιμα στα διάφορα σημεία παραγωγής.
Στόλος οχημάτων: Ο περιορισμός αυτός αφορά οχήματα με διαφορετική χωρητικότητα ή εξοπλισμό, τον τρόπο κοστολόγησης (ιδιόκτητα ή μισθωμένα οχήματα) και τις διανυόμενες αποστάσεις.
Χρόνος επίσκεψης: Τα οχήματα πρέπει να εξυπηρετήσουν κάποια σημεία του δικτύου μεταξύ κάποιων χρονικών ορίων (χρονικά παράθυρα).
Χρόνος εξυπηρέτησης: Ο χρόνος αυτός συνήθως είναι σταθερός. Στην πράξη όμως εξαρτάται από τον πελάτη, αλλά και από την ποσότητα η οποία παραδίδεται.
Παραλαβή προϊόντων: Ορισμένοι πελάτες μπορεί να απαιτούν την επιστροφή κάποιων προϊόντων, ή τη συσκευασία τους.
Εξάρτηση σημείων διάθεσης και παραγωγής με τα οχήματα: Είναι δυνατό να υπάρχουν περισσότερα είδη οχημάτων, καθώς και περιορισμοί στο ποιος πελάτης θα εξυπηρετηθεί και από ποιο όχημα και στο από ποια αποθήκη είναι εφικτό να ξεκινήσουν και /ή να επιστρέψουν τα διάφορα οχήματα.
Εξάρτηση πελατών – οχημάτων: Σε πραγματικά προβλήματα καθημερινής δρομολόγησης υπάρχουν λόγοι που επιβάλλουν την προτίμηση κάποιων πελατών σε συγκεκριμένους οδηγούς λόγω της σχέσης που έχουν αναπτύξει αλλά και λόγω των ιδιαιτεροτήτων των πελατών που γνωρίζει ο οδηγός.
Ασυμβατότητες μεταξύ πελατών: Λόγω ανταγωνισμού μεταξύ γειτονικών πελατών, πολλές φορές η επιχείρηση προσπαθεί να τους εξυπηρετεί από διαφορετικά δρομολόγια.
Σημαντικότητα πελατών: Για την κατάστρωση πραγματικών επιχειρησιακών δικτύων δεν λαμβάνεται με τον ίδιο τρόπο υπόψη ο εκάστοτε πελάτης. Συνήθως δίνεται προτεραιότητα στην εξυπηρέτηση πελατών που δημιουργούν μεγαλύτερο τζίρο.
Χαρακτηριστικά δικτύου: Ένα πραγματικό δίκτυο δρομολόγησης δεν έχει κάθε χρονική στιγμή την ίδια συμπεριφορά. Για τη μοντελοποίηση του πραγματικού δικτύου με τον καλύτερο τρόπο, πρέπει να λαμβάνεται υπόψη η στοχαστικότητα των χρόνων μεταφοράς που εξαρτάται από εξωγενείς παράγοντες.
Στο ‘Πρόβλημα Δρομολόγησης Οχημάτων’ (Vehicle Routing Problem [VRP]) επιδιώκεται ο προσδιορισμός των βέλτιστων δρομολογίων στόλου οχημάτων για τη μεταφορά αγαθών από την κεντρική αποθήκη στις τοποθεσίες των πελατών.
Παραλλαγές του προβλήματος
Οι πρακτικές εφαρμογές που αφορούν προβλήματα βέλτιστης δρομολόγησης χαρακτηρίζονται από διάφορους παράπλευρους περιορισμούς από τους οποίους προκύπτουν παραλλαγές του βασικού προβλήματος (βλ. διάγραμμα 1). Τέτοιοι παράπλευροι περιορισμοί είναι:
* Η χωρητικότητα των οχημάτων (Capacitated Vehicle Routing Problem, CVRP).
* Η απόσταση που μπορεί να διανυθεί (Distance Constrained Vehicle Routing Problem, DCVRP).
* Η χωρητικότητα οχημάτων και η χρήση πολλαπλών αποθηκών (Multi – Depot Vehicle Routing Problem, MDCVRP).
* Η ανομοιογένεια της χωρητικότητας των οχημάτων (Heterogeneous Capacitated Vehicle Routing Problem, HCVRP).
* Η χωρητικότητα των οχημάτων και το χρονικό πλαίσιο της επίσκεψης των πελατών – χρονικά παράθυρα (Capacitated Vehicle Routing Problem with Time Windows, CVRPTW).
* Η χωρητικότητα των οχημάτων και οι παραλαβές (Capacitated Vehicle Routing Problem with Backhauls, CVRPB).
* Η χωρητικότητα των οχημάτων, οι παραλαβές και η διανομή προϊόντων (Capacitated Vehicle Routing Problem with Pick up & Delivery, CVRPD).
* Η χωρητικότητα των οχημάτων με δυνατότητα εξυπηρέτησης πελατών σε πολλαπλές χρονικές περιόδους (Multi-Period Capacitated Vehicle Routing Problem, MPCVRPD).
Επιπλέον, η ζήτηση των πελατών στα παραπάνω προβλήματα θεωρείται γνωστή εκ των προτέρων, όπως επίσης και ο αριθμός των πελατών που πρέπει να επισκεφθεί κάθε όχημα. Συνεπώς, μια μεταβολή της ζήτησης ή των πελατών ή και των δύο μαζί, από γνωστή παράμετρο του προβλήματος σε τυχαία μεταβλητή, μετατρέπει ουσιαστικά τα προαναφερθέντα προβλήματα σε νέα προβλήματα. Πρόκειται για τα στοχαστικά προβλήματα δρομολόγησης (Stochastic VRP – SVRP).
Τεχνικές επίλυσης του VRP
Οι μέθοδοι επίλυσης του VRP χωρίζονται σε τρεις κατηγορίες: τις ακριβείς (exact), τις ευρετικές (heuristic) και τις μεθευρετικές (metaheuristic). Οι περισσότερες μέθοδοι είναι ευρετικές και μεθευρετικές, δεδομένου ότι κανείς ακριβής αλγόριθμος δεν μπορεί να εγγυηθεί την εύρεση της βέλτιστης λύσης, ειδικά όταν το πλήθος των κόμβων είναι μεγάλο. Το διάγραμμα 2 είναι ένα σχεσιακό διάγραμμα μεθόδων βελτιστοποίησης προβλημάτων δρομολόγησης
Ακριβείς μέθοδοι. Οι μέθοδοι αυτές προβλέπουν τη συστηματική απαρίθμηση κάθε πιθανής λύσης μέχρις ότου βρεθεί η βέλτιστη. Συνήθως επιλύουν προβλήματα περιορισμένων διαστάσεων και απαιτούν σημαντικό υπολογιστικό χρόνο. Μια από τις πιο γνωστές ακριβείς τεχνικές για το CVRP είναι η K-tree μέθοδος, η οποία μπορεί να γενικευτεί προκειμένου να επιλύσουμε πιο ρεαλιστικά σενάρια VRP με ασύμμετρα κόστη, χρονοπαράθυρα και οχήματα διαφορετικής χωρητικότητας.
Ευρετικές μέθοδοι. Οι ευρετικές μέθοδοι επιτελούν μια σχετικά περιορισμένη εξερεύνηση του χώρου των λύσεων και παράγουν αποτελεσματικές προσεγγίσεις, οι οποίες χαρακτηρίζονται από χαμηλή υπολογιστική πολυπλοκότητα. Ορισμένες βασικές ευρετικές τεχνικές που χρησιμοποιούνται στο VRP είναι:
* Οι κατασκευαστικές μέθοδοι, όπου σταδιακά χτίζεται μια εφικτή λύση, ενώ ταυτόχρονα παρατηρούνται οι μεταβολές στο κόστος.
* Ο αλγόριθμος 2 φάσεων με τον οποίο το πρόβλημα αποσυντίθεται στα δύο βασικά του χαρακτηριστικά: τη διαμέλιση του συνόλου των κορυφών σε υποσύνολα εφικτών διαδρομών και την κατασκευή της διαδρομής με πιθανούς βρόχους ανάδρασης ανάμεσα στις δύο φάσεις.
Μεθευρετικές μέθοδοι. Οι μεθευρετικοί αλγόριθμοι διερευνούν λύσεις σε μη εφικτές περιοχές ή ακόμη και σε περιοχές που χειροτερεύουν την τιμή της αντικειμενικής συνάρτησης. Σκοπός είναι η αποφυγή του εγκλωβισμού του αλγορίθμου σε τοπικά ελάχιστα, επιτυγχάνοντας λύσεις οι οποίες είναι πλησιέστερα στις βέλτιστες. Η ποιότητα των λύσεων που παράγουν οι μεθευρετικές μέθοδοι είναι αρκετά πιο υψηλή συγκριτικά με τις ευρετικές μεθόδους. Οι κυριότεροι μεθευρετικοί αλγόριθμοι είναι: οι αλγόριθμοι τοπικής βελτιστοποίησης, οι γενετικοί αλγόριθμοι, οι αλγόριθμοι προσομοίωσης αποικίας μυρμηγκιών, η αιτιοκρατική αλλά και η προσομοιωμένη ανόπτηση, οι αλγόριθμοι τοπικής αναζήτησης με απαγόρευση κινήσεων αλλά και υβρίδια των παραπάνω μεθόδων. Στον πίνακα 2 παρατίθενται ενδεικτικοί ακριβείς μέθοδοι αλλά και ευρετικοί και μεθευρετικοί αλγόριθμοι που χρησιμοποιούνται για την επίλυση του VRP.
* Ο Παντελής Γιαννέλος είναι χημικός μηχανικός ΕΜΠ με μεταπτυχιακές σπουδές στη Διοίκηση Επιχειρήσεων. Έχει εργαστεί σε μεγάλες ελληνικές βιομηχανίες στην παραγωγή και την κοστολόγηση. Είναι εκπαιδευτής του ΕΦΕΤ κι έχει συμμετάσχει σε ερευνητικά προγράμματα του Εργαστηρίου Καυσίμων Και Λιπαντικών του ΕΜΠ. Είναι επίσης μέλος της Μόνιμης Επιτροπής Βιομηχανικής Διοίκησης και Εφοδιαστικής Μηχανικής του Πανελληνίου Συλλόγου Χημικών Μηχανικών.
