Ευφυής συλλογή και μεταφορά απορριμμάτων με χρήση εξελικτικών τεχνικών

Abstract

The initial idea of ​​this thesis was to develop a vehicle routing model for solving urban garbage collection problems.It is evident that a garbage collection problem belongs to the arc routing problems (arc routing problem), because if you represent a city or area where the garbage collection will be done in a chart, the amount to be collected (ie waste ) will be in the graph arcs, since there are houses, shops or the overall waste production points. Solving the problem as arc routing problem is complicated for several reasons. For example, we know if the waste production on a daily basis from the production, the exact quantities of waste and the exact coordinates of output points. To better understand the objective difficulties to mention that for example in the case of a three-story building or a building will have to decide whether all the building departments will be addressed as separate customers or as one.But if we consider that the quantity of waste collected by the center of the arc of the same chart, which is more realistic, since the waste is collected from large bins are discrete points of routes (arcs) tries this problem is transformed into node routing problem (node ​​routing problem), when solved as a vehicle routing problem (vehicle routing problem - VRP), where the network nodes are the waste collection points and the arcs are the roads of the area waste collected.During the modeling of the problem was found that the main feature of the collection of waste in urban environments is that the network is asymmetric as there is one-way, etc transit prohibitions .. In-depth study of the literature observed that this is a field with which researchers have no special attention, when there was ground for further investigation, which caused major research challenge. Thus, the study focused on the modeling of unsymmetrical vehicle routing problem (asymmetric vehicle routing problem), which constitutes one of the basic characteristics - originality of this thesis.Subsequently, these environmental - economic - social conditions for reduction of carbon dioxide (CO2) emissions imperative showed the need to us, our routing problem in an urban environment be approached in the light of reducing the energy consumption of vehicles, which also was virgin territory for further study and promotion of new techniques, constituting a further key feature - originality of this thesis.Thus, the first original problem studied, resolved and named based on the characteristics of being: Asymmetric Energy Pick up Vehicle Routing Problem - AEPVRP.Obviously the test vehicle routing problems in the perspective of non-symmetric network and the reduction of energy consumption could be extended to distribution problems.This examination is as important as urban distribution of goods is a very common procedure, so the second prototype routing problem studied, resolved and named based on the characteristics of being:Asymmetric Energy Delivery Vehicle Routing Problem - AEDVRP.Furthermore, we had the opportunity to expand into a research area that has not only researched by academia but also has practical significance as it covers the largest vehicle routing range whereas in everyday life most routes related products distribution.Wanting to expand our research in realistic vehicle routing problems always urban modeling expanded our third original routing problem, which is none other than:Asymmetric Time Reduction Delivery Vehicle Routing Problem - ATRDVRP,which we investigated, resolved and named based on its characteristics.The above modeling was a double challenge for us: when solving a routing problem by minimizing the time two goals are achieved. First, the service time is reduced, which is the basic goals of every decision maker and secondly by minimizing vehicle movement time achieved a reduction in fuel consumption and thus emissions of carbon dioxide (CO2). In this respect again the original problem under consideration has energy characteristicsAlso, since the study realistic problems and the main objective of this thesis is to give an as possible most realistic and representative modeling of the problem you solve, reducing vehicle movement time is more important than reducing the distance . This is documented if we consider that a realistic vehicle traffic conditions on a road if the same route several times while always having the same total distance, the this running time is different because of the external factors affecting the road network congestion , weather conditions, eg rain or wind, etc.further enriching our study around the vehicle routing problems in the urban environment we considered the key factor of the unknown quantity in the collection or distribution of products.Given therefore that realistically waste collection routing problems generally have stochastically attributes (quantities in waste collection is unknown until the time reaches the garbage in the drum) developed the fourth original routing problem, namely:Asymmetric Stochastic Pickup Vehicle Routing Problem - ASPVRP.which we investigated, resolved and named based on its characteristics, extending it along and product distribution problems since in this case there are many situations of everyday life where in distribution quantity of product is only known when the vehicle reaches the customer .So, according to these assumptions of modeled and solved the fifth original routing problem:Asymmetric Stochastic Delivery Vehicle Routing Problem - ASDVRP.In particular, for Asymmetric Stochastic Vehicle Routing Problem whether distribution (delivery) whether collection (Pick up) no equivalent approaches - modeling problems so again our problems have an original character created during the preparation of this thesis.The originality of this study is not based only on the modeling of these routing problems, but extended to the creation of the data used in solving them.This does not happen by accident. With all due respect to the international literature, it was found that there were no tables - data that could be used in this modeling asymmetric routing problems. Direct effect of all the above is that all the data used in the preparation of this thesis were created from the beginning to cover this thesis needs.More specifically, to solve the proposed models of collection and distribution of products created a new set of non-symmetric cost tables based on sets of examples An # -k # [177], which is the most well known and often used examples sets solving routing problems and their variants.This process was designing cost tables where the values ​​are above the main diagonal consisted of the distances of the nodes of an example (eg An # 1-k # 1) while the values ​​were below the main diagonal of the distances of the nodes of another example (e.g. an # 2-k # 2).Subsequently, all test problems were solved using evolutionary algorithms. As illustrative advantages may for example be mentioned that make better search space solutions may be many local minima and because solutions population can easily escape from them, etc.After extensive review of the literature found that algorithms inspired by nature and, more specifically, the Algorithm Optimization Cluster Particles (Particle Swarm Optimization (PSO)), solves very effective vehicle routing problems (VRP), giving results better or equivalent to the best algorithms literature. The most important routing problems are solved by using the algorithm above is the vehicle routing problem with limited capacity, the open vehicle routing problem, vehicle routing problem with time constraints and the vehicle routing problem with stochastic demand.So, according to all the above, we implemented various innovative variations of that algorithm to solve the problems addressed in this thesis.The algorithms therefore proposed are as follows: Hybrid Adaptive Constriction Particle Swarm Optimization-HybACPSO Hybrid Particle Swarm Optimization - HybPSO Hybrid Inertia Particle Swarm Optimization - HybiPSO Hybrid Constriction Particle Swarm Optimization - HybCPSO Hybrid Local Neighborhood topology Particle Swarm Optimization - HybLPSOWhen examining the produced results found that the algorithm works more efficiently in solving the above problems is the routing: Hybrid Adaptive Algorithm Particle Swarm Optimization - Hybrid Adaptive Constriction Particle Swarm Optimization - HybACPSO,which is then marked as "proposed algorithm."Having examined in detail all the above field collection and distribution of products, and what algorithms are best solve such problems, modeled and solved a realistic vehicle routing problem for garbage collection, which also formed and the initial target - concept of this PhD thesis.The realistic routing problem chosen to be resolved is that of the 'DOOR - DOOR "of the old town of Chania, applied by DEDISA SA, which is the competent waste management company of Chania. The selection came after careful consideration, since its characteristics, and hence the modeling, is quite different from a conventional waste collection problem, for which there have been several reports in the literature, while a problem with these characteristics not was corresponding.It is worth noting that the resolution of this complex realistic problem has a direct economic, social and environmental impact and a part of the old town has great historical significance and is one of the main tourist parts of Chania.The realistic our problem was approached from two different angles, to consider the different needs that arise during realistic waste collection routing problems, when solved using two different modeling.Since our problem evolves in an urban environment and in both cases taking into account the non-symmetry of the distances, while the parameters are varied:In the first modeling of the need to minimize the energy consumption of the fleet vehicles, which is directly linked to carbon dioxide (), fuel costs and other factors which the administration wants to minimize lead in modeling as:Waste Collection Asymmetric Pickup Energy Vehicle Routing Problem - WCAPEVRPIn the second modeling where unforeseen - stochastic quantities waste give stochastic characteristics of the collection and waste transportation problem, when treated as:Waste Collection Asymmetric Stochastic Pickup Vehicle Routing Problem - WCASPVRP.To solve our waste collection realistic problem in the old town of Chania quantitative data as well as the bucket seats of system DOOR - DOOR given by the Directorate of DEDISA SA after our request.Subsequently placed on a map using the Google maps, taking coordinates and distances between points. Because of the one-way system, the specificity of the buildings, the narrow streets, sidewalks, etc. Table representing the points considered - bins hence garbage route from one point to another is non-symmetrical. The algorithms resolved this problem are none other than those mentioned just before, since it proved to have excellent performance in vehicle routing problems in the urban environment.Through the practical application of these evolutionary techniques pursued in parallel, proof that the modeling and solving the waste disposal problem has not only theoretical but also practical.Using the aforementioned evolutionary techniques for applying them to the collection and waste transport systems, seeks to identify the most acceptable and economic solutions of waste collection problem, given both the perpetual production themselves and the increasing need for the optimal collection, taking into account factors such as environmental, economic, technical, institutional and political.Finally, according to the above, achieved the ultimate goal of this thesis, which is none other than the analysis, design and implementation of a model of resolving computer vehicle routing procedures for collecting not only waste but products in general, in realistic environment, taking into account the characteristics that govern it.The structure of the thesis is as follows:The first chapter is a brief reference to the theoretical background and literature review governing vehicle routing problems, mathematical modeling of these, litter and modeling of garbage collection problems.The second chapter refers to energy vehicle routing problems and the stochastic routing problems, the collection and distribution of products.Then comes the third chapter which refers to the evolutionary optimization algorithms and, more specifically, the particle swarm optimization algorithm and several variations of this, they proposed specific algorithm for solving waste collection vehicle routing problems and more.The fourth chapter is modeled and solved by us the unbalanced energy waste collection routing problem, the unbalanced energy product distribution problem and the non-symmetric product distribution vehicle routing problem by minimizing the time. All the above are solved by the algorithms have been proposed in the third chapter, using fictitious data, and analyzes the results in several ways by highlighting a single algorithm as predominant, which is none other than the proposed algorithm.The fifth chapter modeled the asymmetric stochastic routing problems collection vehicles and product distribution, where again solved with the algorithms have been proposed in the third chapter, using fictitious data.The sixth chapter is modeled and solved the realistic vehicle routing problem of the 'DOOR - DOOR "in the old town of Chania using evolutionary techniques developed in the previous chapters and using real data.Finally, the thesis concludes with the seventh chapter, which is a review and summary of results in accordance with standardized and highlights the objectives of this thesis, while proposed future research fields.

Η αρχική ιδέα της παρούσας διδακτορικής διατριβής ήταν η ανάπτυξη ενός μοντέλου δρομολόγησης οχημάτων για την επίλυση προβλημάτων συλλογής απορριμμάτων σε αστικό περιβάλλον.Είναι εμφανές ότι ένα πρόβλημα συλλογής απορριμμάτων ανήκει στην κατηγορία των προβλημάτων δρομολόγησης τόξων (arc routing problem), λόγω του ότι εάν αναπαραστήσουμε την πόλη ή την περιοχή όπου θα γίνει η συλλογή των απορριμμάτων με ένα γράφημα, η ποσότητα που θα συλλεγεί (δηλαδή τα απορρίμματα) θα βρίσκονται στα τόξα του γραφήματος, μιας και εκεί βρίσκονται τα σπίτια, καταστήματα ή τα εν γένει σημεία παραγωγής των απορριμμάτων. Η επίλυση του προβλήματος ως πρόβλημα δρομολόγησης τόξων είναι περίπλοκη για διάφορους λόγους. Λόγου χάρη, πρέπει γνωρίζουμε εάν η παραγωγή απορριμμάτων γίνεται σε καθημερινή βάση από τα σημεία παραγωγής, τις ακριβείς ποσότητες απορριμμάτων καθώς και τις ακριβείς συντεταγμένες των σημείων παραγωγής. Για να γίνουν πιο κατανοητές οι αντικειμενικές δυσκολίες αναφέρουμε ότι για παράδειγμα στην περίπτωση ενός τριώροφου κτιρίου ή μιας πολυκατοικίας θα πρέπει να αποφασίσουμε εάν όλα τα διαμερίσματα του οικοδομήματος θα αντιμετωπισθούν ως χωριστοί πελάτες ή ως ένας.Εάν όμως θεωρήσουμε ότι οι ποσότητες των απορριμμάτων συλλέγονται από το κέντρο του τόξου του ίδιου γραφήματος, το οποίο είναι και πιο ρεαλιστικό, δεδομένου ότι τα απορρίμματα συλλέγονται από μεγάλους κάδους που βρίσκονται σε διακριτά σημεία των οδών (τόξων) εύκολα το εν λόγω πρόβλημα μετατρέπεται σε πρόβλημα δρομολόγησης κόμβων (node routing problem) , οπότε και επιλύεται ως ένα πρόβλημα δρομολόγησης οχημάτων (Vehicle Routing Problem - VRP), όπου οι κόμβοι του δικτύου είναι τα σημεία συλλογής των απορριμμάτων ενώ τα τόξα είναι οι δρόμοι της περιοχής που συλλέγονται τα απορρίμματα.Κατά τη μοντελοποίηση του προβλήματος διαπιστώθηκε ότι το βασικό χαρακτηριστικό της συλλογής απορριμμάτων σε αστικό περιβάλλον είναι ότι το δίκτυο είναι μη συμμετρικό καθώς υπάρχουν μονοδρομήσεις, απαγορεύσεις διέλευσης κ.λ.π.. Κατά την ενδελεχή μελέτη της διεθνούς βιβλιογραφίας παρατηρήθηκε ότι πρόκειται για ένα πεδίο με το οποίο οι ερευνητές δεν έχουν ασχοληθεί ιδιαίτερα, οπότε και υπήρχε έδαφος για περαιτέρω έρευνα, πράγμα που προκάλεσε μεγάλη ερευνητική πρόκληση. Έτσι, η μελέτη στράφηκε στη μοντελοποίηση του μη συμμετρικού προβλήματος δρομολόγησης οχημάτων (asymmetric vehicle routing problem), το οποίο και αποτελεί ένα από τα βασικά χαρακτηριστικά – πρωτοτυπία της παρούσας διδακτορικής διατριβής.Εν συνεχεία, οι παρούσες περιβαλλοντικές – οικονομικές – κοινωνικές συνθήκες για μείωση των εκπομπών του διοξειδίου του άνθρακα (CO2 ) εμφάνισαν επιτακτική την ανάγκη σε εμάς, το πρόβλημα δρομολόγησής μας σε αστικό περιβάλλον να προσεγγισθεί υπό το πρίσμα της μείωσης της ενεργειακής κατανάλωσης των οχημάτων, το οποίο επίσης είχε παρθένο έδαφος προς περαιτέρω μελέτη και ανάδειξη νέων τεχνικών, αποτελώντας ένα επιπλέον βασικό χαρακτηριστικό – πρωτοτυπία της παρούσας διδακτορικής διατριβής. Έτσι, το πρώτο πρωτότυπο πρόβλημα το οποίο μελετήσαμε, επιλύσαμε και ονομάσαμε βάση των χαρακτηριστικών του είναι το:Μη Συμμετρικό Ενεργειακό Πρόβλημα Δρομολόγησης Οχημάτων Συλλογής Προϊόντων -Asymmetric Energy Pick up Vehicle Routing Problem – AEPVRP.Είναι προφανές ότι η εξέταση προβλημάτων δρομολόγησης οχημάτων υπό τη σκοπιά του μη συμμετρικού δικτύου και της ελάττωσης της ενεργειακής κατανάλωσης μπορούσε να επεκταθεί και σε προβλήματα διανομής. Η εξέταση αυτή είναι εξίσου σημαντική δεδομένου ότι σε αστικό περιβάλλον η διανομή προϊόντων είναι μια διαδικασία πολύ σύνηθες, οπότε το δεύτερο πρωτότυπο πρόβλημα δρομολόγησης το οποίο μελετήσαμε, επιλύσαμε και ονομάσαμε βάση των χαρακτηριστικών του είναι το: Μη Συμμετρικό Ενεργειακό Πρόβλημα Δρομολόγησης Οχημάτων Διανομής Προϊόντων - Asymmetric Energy Delivery Vehicle Routing Problem – AEDVRP.Επιπλέον, μας δόθηκε η δυνατότητα να επεκταθούμε σε ένα χώρο έρευνας ο οποίος όχι μόνο δεν έχει ερευνηθεί από την ακαδημαϊκή κοινότητα αλλά έχει και πρακτική σημασία καθώς καλύπτει το μεγαλύτερο φάσμα δρομολόγησης οχημάτων λαμβάνοντας υπόψη ότι στην καθημερινή ζωή τα περισσότερα δρομολόγια αφορούν διανομή προϊόντων.Θέλοντας να επεκτείνουμε την έρευνά μας στα ρεαλιστικά προβλήματα δρομολόγησης οχημάτων πάντοτε σε αστικό περιβάλλον η μοντελοποίησή μας επεκτάθηκε στο τρίτο πρωτότυπο πρόβλημα δρομολόγησης, που δεν είναι άλλο από το:Μη Συμμετρικό Πρόβλημα Δρομολόγησης Οχημάτων Διανομής Προϊόντων, Ελαχιστοποιώντας το Χρόνο - Asymmetric Time Reduction Delivery Vehicle Routing Problem – ATRDVRP,το οποίο μελετήσαμε, επιλύσαμε και ονομάσαμε βάση των χαρακτηριστικών του.Η παραπάνω μοντελοποίηση αποτέλεσε διπλή πρόκληση για εμάς: κατά την επίλυση ενός προβλήματος δρομολόγησης ελαχιστοποιώντας το χρόνο επιτυγχάνονται δύο στόχοι. Πρώτον, μειώνεται ο χρόνος εξυπηρέτησης, κάτι που είναι στις βασικές επιδιώξεις του κάθε αποφασίζοντα και δεύτερον, κατά την ελαχιστοποίηση του χρόνου κίνησης των οχημάτων επιτυγχάνεται ελάττωση της κατανάλωσης καυσίμου, άρα και εκπομπών του διοξειδίου του άνθρακα (CO2). Υπό αυτή τη σκοπιά και πάλι το πρωτότυπο πρόβλημα που εξετάζεται έχει ενεργειακά χαρακτηριστικά. Επίσης, από τη στιγμή που μελετάμε ρεαλιστικά προβλήματα και ο βασικός στόχος της εν λόγω διδακτορικής διατριβής είναι να δοθεί μια όσον το δυνατόν πιο ρεαλιστική και αντιπροσωπευτική μοντελοποίηση του προβλήματος που επιλύουμε, η μείωση του χρόνου κίνησης των οχημάτων είναι πιο σημαντική από τη μείωση της απόστασης. Αυτό τεκμηριώνεται εάν αναλογισθούμε ότι σε ρεαλιστικές συνθήκες κίνησης οχημάτων σε οδικό δίκτυο η πραγματοποίηση της ίδιας διαδρομής, αρκετές φορές αν και έχει πάντοτε την ίδια συνολική απόσταση, ο χρόνος εκτέλεσης αυτής είναι διαφορετικός λόγω των εξωτερικών παραγόντων που επηρεάζουν το οδικό δίκτυο, όπως η κυκλοφοριακή συμφόρηση, οι καιρικές συνθήκες, π.χ. βροχή ή άνεμος, κ.λ.π.Εμπλουτίζοντας περαιτέρω τη μελέτη μας γύρω από τα προβλήματα δρομολόγησης οχημάτων σε αστικό περιβάλλον λάβαμε υπόψη το βασικό παράγοντα της άγνωστης ποσότητας των υπό συλλογή ή διανομή προϊόντων.Δεδομένου λοιπόν ότι τα ρεαλιστικά προβλήματα δρομολόγησης συλλογής απορριμμάτων, εν γένει, έχουν στοχαστικά χαρακτηριστικά (οι υπό συλλογή ποσότητες απορριμμάτων είναι άγνωστες μέχρι τη στιγμή που το απορριμματοφόρο φτάσει στον κάδο) αναπτύξαμε το τέταρτο πρωτότυπο πρόβλημα δρομολόγησης, ήτοι το:Μη Συμμετρικό Στοχαστικό Πρόβλημα Δρομολόγησης Οχημάτων Συλλογής Προϊόντων -Asymmetric Stochastic Pickup Vehicle Routing Problem - ASPVRP.το οποίο μελετήσαμε, επιλύσαμε και ονομάσαμε βάση των χαρακτηριστικών του, επεκτείνοντάς το παράλληλα και σε προβλήματα διανομής προϊόντων μια και σε αυτή την περίπτωση υπάρχουν πολλές περιπτώσεις της καθημερινής ζωής όπου η υπό διανομή ποσότητα προϊόντος γίνεται γνωστή μόνο τη στιγμή που το όχημα θα φτάσει στον πελάτη. Σύμφωνα λοιπόν με αυτές της παραδοχές μοντελοποιήθηκε και επιλύθηκε το πέμπτο πρωτότυπο πρόβλημα δρομολόγησης, το:Μη Συμμετρικό Στοχαστικό Πρόβλημα Δρομολόγησης Οχημάτων Διανομής Προϊόντων -Asymmetric Stochastic Delivery Vehicle Routing Problem – ASDVRP. Ειδικότερα, για τα μη συμμετρικά στοχαστικά προβλήματα δρομολόγησης (Asymmetric Stochastic Vehicle Routing Problem) είτε πρόκειται για διανομή (delivery) είτε πρόκειται για συλλογή (Pick up) δεν υπάρχουν αντίστοιχες προσεγγίσεις – μοντελοποιήσεις των προβλημάτων οπότε και πάλι τα προβλήματά μας έχουν πρωτότυπο χαρακτήρα και δημιουργήθηκαν κατά την εκπόνηση της παρούσας διδακτορικής διατριβής.Η πρωτοτυπία της παρούσας διατριβής δε στηρίχθηκε μονάχα στην μοντελοποίηση των παραπάνω προβλημάτων δρομολόγησης αλλά επεκτάθηκε και στη δημιουργία των δεδομένων που χρησιμοποιήθηκαν κατά την επίλυση αυτών. Αυτό βέβαια δε συνέβη τυχαία. Με όλο το σεβασμό στη διεθνή βιβλιογραφία, διαπιστώθηκε ότι δεν υπήρχαν πίνακες – δεδομένα τα οποία θα μπορούσαν να χρησιμοποιηθούν στη συγκεκριμένη μοντελοποίηση των μη συμμετρικών προβλημάτων δρομολόγησης. Άμεσο αποτέλεσμα όλων των παραπάνω ήταν ότι όλα τα δεδομένα που χρησιμοποιήθηκαν κατά την εκπόνηση της παρούσας διδακτορικής διατριβής δημιουργήθηκαν εξ αρχής για την κάλυψη των αναγκών της εν λόγω διατριβής.Πιο συγκεκριμένα, για την επίλυση των προτεινόμενων μοντέλων συλλογής και διανομής προϊόντων δημιουργήθηκε ένα νέο σετ μη-συμμετρικών πινάκων κόστους βασισμένο στο σετ των παραδειγμάτων A-n#-k# [177], τα οποία και είναι από τα πιο γνωστά και συχνά χρησιμοποιημένα σύνολα παραδειγμάτων για την επίλυση προβλημάτων δρομολόγησης και παραλλαγών τους.Η συγκεκριμένη διαδικασία έγινε σχεδιάζοντας πίνακες κόστους όπου οι τιμές που βρίσκονται πάνω από την κύρια διαγώνιο αποτελούνταν από τις αποστάσεις των κόμβων ενός παραδείγματος (π.χ. A-n#1-k#1) ενώ οι τιμές που βρίσκονταν κάτω από την κύρια διαγώνιο από τις αποστάσεις των κόμβων ενός άλλου παραδείγματος (π.χ. A-n#2-k#2).Εν συνεχεία, όλα τα υπό εξέταση προβλήματα, επιλύθηκαν με χρήση εξελικτικών αλγορίθμων. Ως χαρακτηριστικά πλεονεκτήματά τους μπορούν, για παράδειγμα να αναφερθούν ότι κάνουν καλύτερη αναζήτηση του χώρου λύσεων, μπορούν να βρουν πολλά τοπικά ελάχιστα και λόγω του πληθυσμού λύσεων μπορούν να ξεφύγουν εύκολα από αυτά, κ.λ.π.Μετά από εκτενή ανασκόπηση της βιβλιογραφίας διαπιστώθηκε ότι οι αλγόριθμοι εμπνευσμένοι από τη φύση και, πιο συγκεκριμένα, ο Αλγόριθμος Βελτιστοποίησης Σμήνους Σωματιδίων (Particle Swarm Optimization (PSO)), επιλύει πολύ αποτελεσματικά προβλήματα δρομολόγησης οχημάτων (VRP), δίνοντας αποτελέσματα καλύτερα ή ισοδύναμα με τους καλύτερους αλγόριθμους της βιβλιογραφίας. Τα πιο σημαντικά προβλήματα δρομολόγησης που έχουν επιλυθεί κάνοντας χρήση του παραπάνω αλγορίθμου είναι το πρόβλημα δρομολόγησης οχημάτων με περιορισμένη χωρητικότητα, το ανοικτό πρόβλημα δρομολόγησης οχημάτων, το πρόβλημα δρομολόγησης οχημάτων με χρονικούς περιορισμούς και το πρόβλημα δρομολόγησης οχημάτων με στοχαστική ζήτηση.Σύμφωνα λοιπόν με όλα τα παραπάνω, υλοποιήσαμε διάφορες πρωτότυπες παραλλαγές του συγκεκριμένου αλγορίθμου για την επίλυση των προβλημάτων που αντιμετωπίζονται στη συγκεκριμένη διατριβή.Οι αλγόριθμοι, λοιπόν, που προτείνονται είναι οι εξής: Υβριδικός Προσαρμοστικός Αλγόριθμος Βελτιστοποίησης Σμήνους Σωματιδίων -Hybrid Adaptive Constriction Particle Swarm Optimization-HybACPSOΥβριδικός Αλγόριθμος Βελτιστοποίησης Σμήνους Σωματιδίων – Hybrid Particle Swarm Optimization – HybPSOΥβριδικός Αλγόριθμος Βελτιστοποίησης Σμήνους Σωματιδίων εισάγοντας Βάρος αδράνειας – Hybrid Inertia Particle Swarm Optimization – HybiPSOΥβριδικός Αλγόριθμος Βελτιστοποίησης Σμήνους Σωματιδίων χρησιμοποιώντας παράγοντες περιορισμού στις ταχύτητες των σωματιδίων - Hybrid Constriction Particle Swarm Optimization – HybCPSOΥβριδικός Αλγόριθμος Βελτιστοποίησης Σμήνους Σωματιδίων λαμβάνοντας υπόψη την τοπολογία της γειτονιάς αναζήτησης - Hybrid Local Neighborhood topology Particle Swarm Optimization - HybLPSOΚατά την εξέταση των παραγόμενων αποτελεσμάτων διαπιστώθηκε ότι ο αλγόριθμος που λειτουργεί πιο αποτελεσματικά κατά την επίλυση των προαναφερόμενων προβλημάτων δρομολόγησης είναι ο: Υβριδικός Προσαρμοστικός Αλγόριθμος Βελτιστοποίησης Σμήνους Σωματιδίων - Hybrid Adaptive Constriction Particle Swarm Optimization – HybACPSO,ο οποίος στη συνέχεια χαρακτηρίσθηκε και ως «προτεινόμενος αλγόριθμος».Έχοντας εξετάσει εκτενώς όλο το παραπάνω πεδίο συλλογής και διανομής προϊόντων καθώς και ποιοι αλγόριθμοι είναι εκείνοι που επιλύουν καλύτερα τέτοιου είδους προβλήματα, μοντελοποιήθηκε και επιλύθηκε ένα ρεαλιστικό πρόβλημα δρομολόγησης οχημάτων για τη συλλογή απορριμμάτων, το οποίο εξάλλου αποτελούσε και τον αρχικό στόχο – ιδέα της παρούσας διδακτορικής διατριβής.Το ρεαλιστικό πρόβλημα δρομολόγησης που επιλέχθηκε να επιλυθεί είναι εκείνο του συστήματος «ΠΟΡΤΑ – ΠΟΡΤΑ» της παλιάς πόλης του Δήμου Χανίων, που εφαρμόζεται από τη ΔΕΔΙΣΑ ΑΕ, που είναι η αρμόδια εταιρεία διαχείρισης απορριμμάτων του Νομού Χανίων. Η επιλογή του προέκυψε μετά από ώριμη σκέψη, μια και τα χαρακτηριστικά του, άρα και η μοντελοποίηση του, διαφέρει αρκετά από ένα κλασσικό πρόβλημα συλλογής απορριμμάτων, για τα οποία έχουν γίνει αρκετές αναφορές στη διεθνή βιβλιογραφία, ενώ για ένα πρόβλημα με αυτά τα χαρακτηριστικά δεν υπήρχε αντίστοιχη.Αξίζει να σημειωθεί ότι η επίλυση αυτού του σύνθετου ρεαλιστικού προβλήματος έχει άμεσο οικονομικό, κοινωνικό και περιβαλλοντικό αντίκτυπο μια και το τμήμα αυτό της παλιάς πόλης έχει μεγάλη ιστορική σημασία και αποτελεί ένα από τα σημαντικότερα τουριστικά τμήματα του Νομού Χανίων.Το ρεαλιστικό πρόβλημά μας προσεγγίστηκε από δύο διαφορετικές οπτικές γωνίες, ώστε να εξετασθούν διαφορετικές ανάγκες που προκύπτουν κατά τα ρεαλιστικά προβλήματα δρομολόγησης συλλογής απορριμμάτων, οπότε και επιλύθηκε χρησιμοποιώντας δύο διαφορετικές μοντελοποιήσεις.Δεδομένου ότι το πρόβλημά μας εξελίσσεται σε αστικό περιβάλλον και στις δύο περιπτώσεις λαμβάνονται υπόψη η μη συμμετρικότητα των αποστάσεων, ενώ οι παράμετροι που διαφοροποιούνται είναι:Στην 1η μοντελοποίηση του, η ανάγκη ελαχιστοποίησης της ενέργειας που καταναλώνουν τα οχήματα του στόλου, η οποία συνδέεται άμεσα με εκπομπές διοξειδίου του άνθρακα ( ), το κόστος καυσίμων και άλλους παράγοντες όπου η διοίκηση επιθυμεί να ελαχιστοποιήσει, οδηγούν στην μοντελοποίηση του ως:Μη Συμμετρικό Ενεργειακό Πρόβλημα Δρομολόγησης Οχημάτων Συλλογής Απορριμμάτων - Waste Collection Asymmetric Pickup Energy Vehicle Routing Problem - WCAPEVRPΣτην 2η μοντελοποίηση του, όπου οι απρόβλεπτες – στοχαστικές ποσότητες απορριμμάτων δίνουν στοχαστικά χαρακτηριστικά στο πρόβλημα συλλογής και μεταφοράς απορριμμάτων, οπότε και αντιμετωπίζεται ως:Μη Συμμετρικό Στοχαστικό Πρόβλημα Δρομολόγησης Οχημάτων Συλλογής Απορριμμάτων - Waste Collection Asymmetric Stochastic Pickup Vehicle Routing Problem - WCASPVRP.Για την επίλυση του ρεαλιστικού μας προβλήματος συλλογής απορριμμάτων στην παλιά πόλη των Χανίων τα ποσοτικά δεδομένα καθώς και οι θέσεις των κάδων του συστήματος ΠΟΡΤΑ – ΠΟΡΤΑ δόθηκαν από τη Διεύθυνση της ΔΕΔΙΣΑ ΑΕ, μετά από σχετικό αίτημά μας.Εν συνεχεία, τοποθετήθηκαν σε χάρτη κάνοντας χρήση του Google maps, παίρνοντας συντεταγμένες και αποστάσεις των σημείων. Λόγω των μονοδρομήσεων, της ιδιαιτερότητας των κτισμάτων, των στενών δρόμων, των πεζόδρομων κ.λπ. ο πίνακας που αναπαρίστανε τα υπό εξέταση σημεία – κάδους άρα και δρομολόγια των απορριμματοφόρων από το ένα σημείο στο άλλο, είναι μη-συμμετρικός. Οι αλγόριθμοι που επίλυσαν το εν λόγω πρόβλημα δεν είναι άλλοι από εκείνους που αναφέρθηκαν λίγο πριν, δεδομένου ότι αποδείχθηκε ότι έχουν άριστη συμπεριφορά σε προβλήματα δρομολόγησης οχημάτων σε αστικό περιβάλλον.Μέσω της πρακτικής εφαρμογής των παραπάνω εξελικτικών τεχνικών επιδιώκεται, παράλληλα, η απόδειξη ότι η μοντελοποίηση και επίλυση του προβλήματος συλλογής απορριμμάτων δεν έχει μόνο θεωρητική αλλά και πρακτική εφαρμογή.Κάνοντας χρήση των προαναφερόμενων εξελικτικών τεχνικών για την εφαρμογή τους σε συστήματα συλλογής και μεταφοράς απορριμμάτων, επιδιώκεται ο εντοπισμός των πλέον αποδεκτών και οικονομικών λύσεων του προβλήματος συλλογής απορριμμάτων, δεδομένης τόσο της αέναης παραγωγή τους όσο και της αυξανόμενης ανάγκης για την βέλτιστη συλλογή τους, λαμβάνοντας υπόψη παράγοντες, όπως περιβαλλοντικούς, οικονομικούς, τεχνικούς, θεσμικούς και πολιτικούς. Τέλος, σύμφωνα με όλα τα παραπάνω, επιτυγχάνεται ο απώτερος στόχος της παρούσας διδακτορικής διατριβής, ο οποίος δεν είναι άλλος από την ανάλυση, σχεδίαση και υλοποίηση ενός μοντέλου επίλυσης μέσω υπολογιστή των διαδικασιών δρομολόγησης οχημάτων για τη συλλογή όχι μόνο απορριμμάτων αλλά προϊόντων γενικότερα, σε ρεαλιστικό περιβάλλον, λαμβάνοντας υπόψη τα χαρακτηριστικά που το διέπουν.Η δομή της διδακτορικής διατριβής είναι η ακόλουθη:Στο πρώτο κεφάλαιο γίνεται μια σύντομη αναφορά στο θεωρητικό υπόβαθρο και τη βιβλιογραφική ανασκόπηση που διέπει τα προβλήματα δρομολόγησης οχημάτων, τη μαθηματική μοντελοποίηση αυτών, τα απορρίμματα και τη μοντελοποίηση των προβλημάτων συλλογής απορριμμάτων.Το δεύτερο κεφάλαιο αναφέρεται στα ενεργειακά προβλήματα δρομολόγησης οχημάτων καθώς και στα στοχαστικά προβλήματα δρομολόγησης, τόσο συλλογής όσο και διανομής προϊόντων.Ακολουθεί το τρίτο κεφάλαιο όπου γίνεται αναφορά στους εξελικτικούς αλγορίθμους βελτιστοποίησης και, πιο συγκεκριμένα, στον αλγόριθμο βελτιστοποίησης σμήνους σωματιδίων και διάφορες παραλλαγές αυτού, όπου και προτείνεται συγκεκριμένος αλγόριθμος για την επίλυση προβλημάτων δρομολόγησης οχημάτων συλλογής απορριμμάτων και όχι μόνο.Στο τέταρτο κεφάλαιο μοντελοποιείται και επιλύεται από εμάς το μη συμμετρικό ενεργειακό πρόβλημα δρομολόγησης συλλογής απορριμμάτων, το μη συμμετρικό ενεργειακό πρόβλημα διανομής προϊόντων καθώς και το μη συμμετρικό πρόβλημα δρομολόγησης οχημάτων διανομής προϊόντων ελαχιστοποιώντας το χρόνο. Όλα τα παραπάνω επιλύονται με τους αλγόριθμους που έχουν προταθεί στο τρίτο κεφάλαιο, κάνοντας χρήση πλασματικών δεδομένων, ενώ γίνεται ανάλυση των αποτελεσμάτων, με διάφορους τρόπους αναδεικνύοντας έναν και μοναδικό αλγόριθμο ως επικρατέστερο, ο οποίος δεν είναι άλλος από τον προτεινόμενο αλγόριθμο.Στο πέμπτο κεφάλαιο μοντελοποιούνται τα μη συμμετρικά στοχαστικά προβλήματα δρομολόγησης οχημάτων συλλογής και διανομής προϊόντων, όπου και πάλι επιλύονται με τους αλγόριθμους που έχουν προταθεί στο τρίτο κεφάλαιο, κάνοντας χρήση πλασματικών δεδομένων.Στο έκτο κεφάλαιο μοντελοποιείται και επιλύεται το ρεαλιστικό πρόβλημα δρομολόγησης οχημάτων του συστήματος «ΠΟΡΤΑ – ΠΟΡΤΑ» στην παλιά πόλη των Χανίων κάνοντας χρήση των εξελικτικών τεχνικών που αναπτύχθηκαν στα προηγούμενα κεφάλαια και με χρήση πραγματικών δεδομένων.Τέλος, η διδακτορική διατριβή κλείνει με το έβδομο κεφάλαιο, όπου γίνεται μια ανασκόπηση και σύνοψη των αποτελεσμάτων σύμφωνα με τα οποία ανάγεται και αναδεικνύεται η επίτευξη των στόχων της παρούσας διδακτορικής διατριβής, ενώ παράλληλα προτείνονται πεδία μελλοντικής έρευνας.