Technical University of Crete (TUC)
Ευφυής συλλογή και μεταφορά απορριμμάτων με χρήση εξελικτικών τεχνικών
Abstract
dc:descriptionThe 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.
Degree
thesis:*- Grantor dc:publisher
- Technical University of Crete (TUC)
- Year dc:date
- 2016
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Bertsoulaki, Olga
- Μπερτσουλάκη, Όλγα
Subjects
dc:subject × 14- Ενεργειακό πρόβλημα δρομολόγησης οχημάτων συλλογής απορριμμάτων
- Μη συμμετρικό πρόβλημα δρομολόγησης οχημάτων συλλογής
- Μη συμμετρικό πρόβλημα δρομολόγησης οχημάτων στοχαστικής συλλογής
- Μη συμμετρικό πρόβλημα δρομολόγησης οχημάτων στοχαστικής ζήτησης
- Αλγόριθμοι, εξελικτικοί
- Pickup energy vehicle routing problem
- Asymmetric pickup vehicle routing problem
- Asymmetric vehicle routing problem with stochastics pick ups
- Asymmetric vehicle routing problem with stochastics demands
- Εvolutionary algorithms
- Επιστήμες Μηχανικού και Τεχνολογία
- Άλλες Επιστήμες Μηχανικού και Τεχνολογίες
- Engineering and Technology
- Other Engineering and Technologies
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/39449