Online αλγόριθμοι δρομολόγησης για στοχαστικά δίκτυα σε πραγματικό χρόνο

Abstract

This thesis investigates the general truck dispatching problem known as the “Vehicle Routing Problem” (VRP). It is one of the most frequently studied problems in the field of applied mathematics and perhaps the most renowned problem of operational research in the transport sector. It is defined as the determination of the least cost distribution plans of a fleet of vehicles to a network of customers, while concurrently ensuring indicative systematic constraints. Applications range from fleet management and product distribution to bus school routing and waste collection.The primary goals of this study are to analyze the VRP under uncertainty (e.g. demand variation) and embed stochasticity in the development of the corresponding mathematical models and algorithms. When an optimization problem is solved under uncertainty the goal is to determine the policies that minimize the cost of initial decisions and the cost of feasible recourse actions. Taking into account the necessity of robust assessments of revealed choices in the optimization model under uncertainty, it is crucial to clearly formulate (mathematical modeling) all possible future decisions – outcomes and to incorporate their effect into a priori decisions. The initial methodological pillars that are settled for the investigation of the VRP under uncertainty in this study are stochastic programming and on line optimization. The first part of the research thesis focused on investigating exact algorithms for the VRP. Extended literature review is performed focusing on alternative model formulation.With focus to freight transportation, the aim is to identify a route plan for delivering products fulfilling demand and minimizing transportation cost. When the demand of products varies the problem of determining route plans from deterministic becomes stochastic. Stochastic demand is directly related to product absorption rate, level of inventory control as well as their correlation. Concentrating interest to stochasticity of demand in coherent to factors affected (capacity of inventories, product absorption rate) the dissertation is studying the collaboration of transportation management and inventory control, known as “Inventory routing problem”.In the second part of this thesis an extended review of the relevant literature of inventory routing problem is performed. Excluding the basic assumption of all previous proposed models it was proved that a new policy called proactive deliveries was powerful in the framework of deterministic modeling. Aiming to solve the inventory routing problem under uncertainty and securing flexibility, a recourse action of the transshipment was proposed in the framework of two stage stochastic programming model. An innovative model was developed of two stage recourse action for the stochastic inventory routing problem. An L – Shaped decomposition method was adopted to solve the problem exactly. The proposed model was tested using a modification of known benchmark instances (Arhetti et al). Conclusively, the decision of formulating the inventory routing problem under uncertainty in the framework of stochastic programming of two stage recourse action model gave us the opportunities to clearly state the tradeoff between transshipment cost in combination with proactive distribution plans and increased inventory levels.

Η παρούσα διδακτορική διατριβή πραγματεύεται το γενικό πρόβλημα δρομολόγησης στόλου, γνωστό στην ξένη βιβλιογραφία ως “Vehicle Routing Problem”. Νοείται ως ένα από τα πιο σημαντικά προβλήματα των εφαρμοζομένων μαθηματικών της σύγχρονης εποχής και ίσως το δημοφιλέστερο πρόβλημα επιχειρησιακής έρευνας στον τομέα των μεταφορών. Ορίζεται ως το πρόβλημα του σχεδιασμού διαδρομών ελάχιστου κόστους ενός στόλου οχημάτων από ένα κεντρικό σημείο σε ένα δίκτυο πελατών, ικανοποιώντας ταυτόχρονα κάποιους συστημικούς περιορισμούς. Το φάσμα των εφαρμογών του εκτείνεται από τη διαχείριση στόλων διανομής προϊόντων έως τη σχολική μετακίνηση, αλλά και τη συλλογή απορριμμάτων.Η μελέτη του προβλήματος της δρομολόγησης σε συνθήκες αβεβαιότητας (πχ. μεταβαλλόμενη ζήτηση), καθώς και η ανάλυση και ενσωμάτωση της στοχαστικότητας στην ανάπτυξη μαθηματικών προτύπων (μοντέλων) και αλγορίθμων, τέθηκαν πρωταρχικοί στόχοι της έρευνας που εκπονήθηκε. Όταν ένα πρόβλημα βελτιστοποίησης επιλύεται υπό συνθήκες αβεβαιότητας, το ζητούμενο είναι η διαμόρφωση της πολιτικής που ελαχιστοποιεί το κόστος των αποφάσεων αλλά και το κόστος των εφικτών μέτρων αναπροσαρμογής των αρχικών επιλογών. Με γνώμονα την εύρωστη αξιολόγηση των επιλογών που προκύπτουν στο μοντέλο βελτιστοποίησης σε συνθήκες αβεβαιότητας, καθοριστικό ρόλο λαμβάνει η σαφής διατύπωση (μαθηματική τεκμηρίωση) των δυνατών μελλοντικών αποφάσεων – προοπτικών, αλλά και η διαδικασία ενσωμάτωσής τους στις εκ των προτέρων επιλογές. Οι μεθοδολογικοί πυλώνες διερεύνησης του προβλήματος της δρομολόγησης σε συνθήκες αβεβαιότητας, ήταν αρχικά η προσέγγιση του στοχαστικού προγραμματισμού και η “online“ βελτιστοποίηση. Το πρώτο μέρος της εργασίας επικεντρώνεται στους ακριβείς αλγορίθμους επίλυσης του γενικού προβλήματος της δρομολόγησης στόλου. Εστιάζοντας στις εμπορευματικές μεταφορές, η στοχαστικότητα της ζήτησης συσχετίζεται άμεσα με το ρυθμό απορρόφησης των προϊόντων, τις δυνατότητες διατήρησης αποθεμάτων, αλλά και τη μεταξύ τους αλληλεπίδραση. Επικεντρώνοντας το ενδιαφέρον στη στοχαστικότητα της ζήτησης σε συνάφεια με τους παράγοντες που την επηρεάζουν (δηλ. χωρητικότητα αποθηκών, ρυθμός απορρόφησης προϊόντων), εξετάζεται στο διδακτορικό η συνδυαστική διαχείριση της διανομής προϊόντων και εφοδιασμού αποθηκών γνωστή στην ξένη βιβλιογραφία ως “Inventory Routing Problem”, η οποία αποτελεί επέκταση του κλασσικού προβλήματος δρομολόγησης.Στο δεύτερο μέρος της εργασίας γίνεται εκτενής αναφορά των επιστημονικών συγγραμμάτων της συνδυαστικής διαχείρισης διανομής προϊόντων και εφοδιασμού των αποθηκών, επικεντρώνοντας και πάλι το ενδιαφέρον σε ακριβείς μεθόδους επίλυσης του προβλήματος. Με αφορμή την αναθεώρηση βασικής υπόθεσης των έως τώρα προτεινόμενων μαθηματικών προτύπων αναδείχτηκε η δυναμική μιας νέας πολιτικής, των προληπτικών διανομών όταν το μοντέλο εξετάζεται σε συνθήκες βεβαιότητας. Με γνώμονα την προοπτική επίλυσης του προβλήματος της συνδυαστικής διαχείρισης διανομής προϊόντων και εφοδιασμού αποθηκών σε συνθήκες αβεβαιότητας και στόχο τη δημιουργία ενός ευέλικτου συστήματος αποφάσεων, η διαδικασία της μεταφόρτωσης εισάγεται ως διορθωτική πολιτική ενός μοντέλου στοχαστικού προγραμματισμού. Αναπτύχθηκε ένα καινοτόμο μοντέλο δύο σταδίων στοχαστικού προγραμματισμού δρομολόγησης στόλου σε συνθήκες αβεβαιότητας. Η επίλυσή του επιτεύχθηκε εφαρμόζοντας τη μεθοδολογική προσέγγιση της αποσύνθεσης «L – Shaped». Το προτεινόμενο στοχαστικό μοντέλο αξιολογήθηκε επιλύοντας κατάλληλες τροποποιήσεις πρότυπων προβλημάτων ( Archetti et al.) . Συμπερασματικά, η απόφαση της πλαισίωσης του προβλήματος υπό το πρίσμα του στοχαστικού προγραμματισμού των μοντέλων δύο σταδίων, μας έδωσε τη δυνατότητα να οριοθετήσουμε την αλληλεπίδραση του κόστους της μεταφόρτωσης σε συνάφεια με το κόστος των προληπτικών διανομών και την αύξηση των επιπέδων διατήρησης των αποθεματικών.