Genetic algorithm for waste collection in smart cities : case of Campolide

i Genetic Algorithm for Waste Collection in Smart Cities Evandro da Silva Mendonça Case of Campolide Project Work presented as requirement for obtaining the Master’s degree in Information Management i MEGI 2018 Title: Genetic Algorithm for Waste Management in Smart Cities Subtitle: Case of Campolide Evandro da Silva Mendonça MGI i ii NOVA Information Management School Instituto Superior de Estatística e Gestão de Informação Universidade Nova de Lisboa GENETIC ALGORITHM FOR WASTE COLLECTION IN SMART CITIES by Evandro da Silva Mendonça Project Work presented as requirement for obtaining the Master’s degree in Information Management, with a specialization in Knowledge Management and Business Intelligence Advisor: Professor Miguel de Castro Neto, PhD October 2018 iii ABSTRACT Smarts cities are becoming an important concept in the cities, it tries to discover methods to interact with the environment in sustainable ways inside urban areas. This concept emerged to deal with the growing urbanization faced by the cities around the globe. Within problems brought by the urbanization, waste management is one of the hardest and most impactful. The collection stage of the waste management is the costliest and the route planning for the garbage trucks is a well-known hard problem. In this project, a genetic algorithm is proposed to deal with the waste collection routing problem using a heterogeneous fleet of trucks. As the population in the city is expected to grow over the years, the project adapts to the current state of the city, because it uses the concept of open data from the municipality to feed itself with the garbage collection information and generate its results. Multiple runs were performed to define its parameters. The algorithm was tested in the simplified real case of Campolide, in the municipality of Lisbon, and proved to be feasible for application on realworld scenarios relying only on actual data of the cities’ waste collection. KEYWORDS Arc Routing Problem; Genetic Algorithm; Smart Cities; Waste Management iv INDEX 1. Introduction .................................................................................................................. 1 1.1. Cities urbanization and waste management problem .......................................... 1 1.2. Smart cities role in waste management ................................................................ 2 1.3. Garbage truck routes planning .............................................................................. 3 1.4. Project goals .......................................................................................................... 5 2. Literature review .......................................................................................................... 6 2.1. Open data .............................................................................................................. 6 2.2. Capacitated arc routing problem .......................................................................... 7 2.3. Overview over genetic algorithms ........................................................................ 7 2.3.1. Fitness function .............................................................................................. 9 2.3.2. Initialization .................................................................................................... 9 2.3.3. Selection ......................................................................................................... 9 2.3.4. Reproduction ................................................................................................ 10 2.3.5. Termination .................................................................................................. 12 3. Methodology .............................................................................................................. 14 4. Development .............................................................................................................. 16 4.1. A brief word on OpenStreetMap ......................................................................... 16 4.2. Distance Matrix ................................................................................................... 18 4.3. GENETIC ALGORITHM .......................................................................................... 19 4.3.1. Chromosome Representation ...................................................................... 20 4.3.2. Fitness function ............................................................................................ 21 4.3.3. Initialization .................................................................................................. 22 4.3.4. Operations .................................................................................................... 22 4.3.5. Termination conditions ................................................................................ 25 5. Results and discussion ................................................................................................ 26 5.1. Parameters definition .......................................................................................... 26 5.2. Defining the garbage weight to be collected ...................................................... 29 5.3. Results evaluation ............................................................................................... 30 6. Conclusions ................................................................................................................. 33 7. Limitations and recommendations for future works ................................................. 34 8. Bibliography ................................................................................................................ 35 v LIST OF FIGURES Figure 2.1 – Tournament selection .......................................................................................... 10 Figure 2.2 – One-point crossover ............................................................................................. 11 Figure 2.3 – Two-point crossover ............................................................................................. 11 Figure 2.4 – Swap mutation ..................................................................................................... 12 Figure 4.1 – OSM’s node example............................................................................................ 16 Figure 4.2 – OSM’s way example ............................................................................................. 17 Figure 4.3 – Campolide representation with OSMnx ............................................................... 17 Figure 4.4 – Graph with Campolide’s data after removing highways ...................................... 18 Figure 4.5 – Chromosome representation ............................................................................... 20 Figure 4.6 – Chromosome data structure ................................................................................ 20 Figure 4.7 – Truck data explanation ......................................................................................... 21 Figure 4.8 – Path distance calculation example ....................................................................... 22 Figure 4.9 – Crossover operation ............................................................................................. 24 Figure 5.1 – GA parameters choice .......................................................................................... 28 Figure 5.2 – Combination 26 fitness evolution ........................................................................ 29 Figure 5.3 – Example of route .................................................................................................. 30 Figure 5.4 – Route 1 ................................................................................................................. 31 Figure 5.5 – Route 2 ................................................................................................................. 31 Figure 5.6 – Route 3 ................................................................................................................. 31 Figure 5.7 – Route 4 ................................................................................................................. 31 Figure 5.8 – Piece of route 1 highlighting road without red highlight ..................................... 32 vi LIST OF TABLES Table 1.1 – Waste generation projection for 2025 by region. Adapted from Hoornweg, D., & Bhada-Tata, P. (2012) ......................................................................................................... 2 Table 2.1 – Genetic Algorithm concepts .................................................................................... 8 Table 5.1 – GA parameters combinations ................................................................................ 27 Table 5.2 – Routes trucks information ..................................................................................... 32 vii LIST OF ABBREVIATIONS AND ACRONYMS ARP Arc routing problem CARP Capacitated arc routing problem GA Genetic Algorithm GVR Genetic Vehicle Representation ICT Information and communication technology OSM OpenStreetMap TSP Traveling Salesman Problem VRP Vehicle routing problem 7 kind of project ensure the share of data overall levels and, as open data initiatives from government, motivates innovation, because more people will have access to data once in few hands. 2.2. CAPACITATED ARC ROUTING PROBLEM The routing problem addressed by this project matches the issues that the CARP algorithm proposes to deal with. The CARP is about serving a set of streets with a fleet with limited capacity starting and ending at a deposit, this problem has been proved to be an NP-hard problem (Wøhlk, 2008). This algorithm can and actually integrate many more limitations, like the vehicle size for a street, the total amount of distance allowed on a trip, the time windows. For each one of these nuances, the researchers develop variations of the CARP with different limitation. Formally, Lacomme et al. (2001) define the Capacitated Arc Routing Problem as: An undirected network 𝐺 = (𝑉,𝐸) where 𝑉 is a set of 𝑛 nodes and 𝐸 a set of 𝑚 edges. A fleet with 𝑘 identical vehicles of capacity 𝑄 based at the depot node 𝑠. A subset 𝑅 ⊂ 𝐸 of edges that must be served by exactly one vehicle. All edges can be traversed any number of times. Each edge (𝑖,𝑗)∈ 𝐸 has a traversal cost 𝑐𝑖𝑗 ≥ 0 and a demand 𝑒𝑖𝑗 ≥ 0. The CARP consists in determining a set of vehicles routes with minimal total cost, such as each trip start and ends at the depot 𝑠, each required edge (𝑖,𝑗)∈ 𝑅 is serviced by one single trip, and the total served edges by any vehicle does not exceed the capacity 𝑄. This undirected version can be used on roads that can be traveled by a vehicle in any direction, these cases occur mostly in low-density areas with very low-traffic (Lacomme et al., 2001). In bigger cities, as the case of this project that deals with Lisbon city, the directed version must be applied. In a directed version of the CARP, each edge represents a street or one side of a street, in the case of it allow traveling using both directions, with mandatory direction for servicing it (Lacomme et al., 2001). The CARP problem can be represented in a variety of ways. There are CARP with intermediate facilities (CARPIF) where the graph has recharging nodes, CARP with vehicle-site dependency (CARPVSD) in which only a certain class of vehicles are allowed to transverse some roads because of some limitation, there are also a few studies where external factors are considered (Fadzli et al., 2015). The problem of waste collection in Lisbon using the CARP on mixed graphs called MCARP using a heuristic method was also studied (Mourão, Nunes, & Prins, 2009). According to Wøhlk (2008), besides heuristics, researchers are also applying metaheuristics to deal with it the CARP problem. Simulated annealing, Tabu Search, and Genetic Algorithm are some of the metaheuristic’s algorithms used to find a solution. These methods have been producing good results, being on the most performance algorithms for the CARP (Wøhlk, 2008). 2.3. OVERVIEW OVER GENETIC ALGORITHMS Genetic algorithm is a metaheuristic that imitates the biological process of reproduction and natural selection (Carr, 2014). It was described by John Holland in the early 1960s (Mitchell, 1995) and belongs to the class of evolutionary algorithms (Carr, 2014; Whitley, 1994). These algorithms are commonly used as functions optimizer, and it has been applied in a broad range of known problems (Whitley, 1994). One of the greatest barriers of software design, that is to fully understand the structure of complex problems can be solved mimicking natural selection, the specification of every feature of the problems and how to deal with them are not an impediment to search for a solution using this approach (Holland, 1992). 8 Given its nature, genetic algorithms have been used to find solution for hard problems like the Travelling Salesman Problem (TSP), VRP (Pereira et al., 2002), CARP (Deng et al., 2007) and many other problems that due to their complexity don’t have an algorithm that produces exact solutions. This is possible because these algorithms tend to explore a far greater range of potential solutions in the search space (Holland, 1992). Genetic algorithms for the CARP was created, tested, and compared with real case scenarios over the world. To the problem of sprinkler cars routing in Chongqing City in China, taking 37 vertexes and 1 deposit into consideration, the GA reduced the travel distance by 33%, also giving a better result than other algorithms (Deng et al., 2007). CARP with time windows GA where developed and compared with heuristics (Ramdane-Cherif, 2006). This research also concluded a superior performance of the evolutionary algorithm when compared with the heuristics. Because genetic algorithms are based on biological evolution, the terminology used is the same as the one used in biology, although representing fairly simpler concepts than their biological counterpart. Most GA share commons elements, like populations of solutions, selection, crossover, and mutation (Mitchell, 1995). To move forward on understanding genetic algorithms, the concepts attached with their nomenclature must be defined, these common elements are described in table 2.1. Concept Definition Gene A variable (parameter) of the chromosome Chromosome Set of genes, is a candidate solution for the problem, the representation of the phenotype on a data structure that can be understood by the algorithm Fitness function A function to measure the fitness of a solution compared with others, this is the function that must be maximized or minimized depending on the algorithm objective Population Set of chromosomes with possibility to be selected to breed the next generation Crossover Combination of chromosomes to generate the offspring for the next generation Mutation Random changes of genes in the chromosome Table 2.1 – Genetic Algorithm concepts Summarizing the steps followed by a common genetic algorithm as stated by Jebari & Madiafi (2013), at the principle, a population of chromosomes are generated at random or by some criteria, this stage is called initialization. Then each individual in the population is evaluated by the fitness function and receive a fitness value. A selection mechanism takes place and select, using specifics techniques, parents that will be crossed to generate an offspring for the next generation of chromosomes that can also be mutated. These steps, excluding the initialization, are repeated until some condition is reached (Jebari & Madiafi, 2013). Must be noticed that some parameters are required to be defined prior the running of the algorithm, they are the population size, mutation, and crossover rates, the GA makes use of these variables in its operations. 9 This whole process will be discussed in deeper details in the next sections. Each step of a common GA discussed in this summary will be addressed in more details. Different techniques will also be addressed to give an overview of the variety of approach each operation in a GA can have. 2.3.1. Fitness function The fitness function is one of the most important parts of the genetic algorithm approach as it is the only one method of evaluating the quality of the solution and measure the improvement through the generations. Because of its importance, the fitness function must be addressed before going through every step that composes the GA. A number called fitness is assigned to each chromosome in the population using the fitness function. The fitness of the chromosome depends on how well it solves the problem that the GA is supposed to solve (Mitchell, 1995). The fitness function must be more sensitive than just measuring good or bad results, it needs to be able to define where the chromosomes stand in the fitness range and compare it with other solutions presented in the population (Carr, 2014). Fitness function can be the most limiting factor to a genetic algorithm. As addressed above, the fitness function must translate how the solution performs, and this, in most cases, is not straightforward. Generating complex and expansive fitness functions that are not computational efficient and require hours to complete, as cases of real-world simulations, can be prohibitive in the development of a genetic algorithm. Need to be considered that the fitness function will be evaluated for each chromosome of the population for every new generation produced. 2.3.2. Initialization The GA is based on evolving every population until some condition is reached. The initial population must be generated to let the evolution iteration begins. There are some different ways of generating the first population, it is normally generated randomly (Whitley, 1994), but some knowledge can be applied to the generation. The size of the population depends on a previously defined parameter. This size is preserved through the entire life of the algorithm. The initialization can be done totally random or applying some previous knowledge of the problem, in this case, some chromosomes can be included with known genes that makes sense to the problem (M. Kumar, Husian, Upreti, & Gupta, 2010), this can lead the algorithm to converge faster to areas where optimal solutions are more likely to be found. From this early step, the evolutionary process begins. 2.3.3. Selection A subset of the population is then selected and used to breed a new generation, that said, this step is critical since it needs to select good individuals trying to keep the diversity of the selected chromosomes. The subset size is also a parameter that must be set into the algorithm. The selection step can take place using a variety of techniques. Some methods focus on the fitness of the individual, where chromosomes with the best fitness are the one to be selected. Other methods are based on randomness selection or combination of these techniques. No method is guaranteeing to be the best one, and the choice must be problem specific. 10 There are many selection methods, the most used are the roulette wheel and tournament selection (Saini, 2017). But other methods like Stochastic Universal Sampling, Rank Selection and Random Selection can be found in the literature. The tournament selection and roulette wheel will be addressed in this research. Both methods provide good and diverse parents in most cases because they give the possibility of poorer fit chromosomes to be chosen and still rely on the fitness value to decide on which individual to choose in their deterministic steps. In the tournament selection, the selection process that is used in this project, K different individuals are randomly selected from the population as shown in figure 2.1. Within this set, the chromosome with the best fitness is then selected to reproduce. This process is done once more to select the next parent. Figure 2.1 – Tournament selection The roulette wheel selection gives each chromosome in the population a probability of being selected. This probability is proportional to its fitness. To select one individual, a random number is generated, simulating a roulette, and the generated number will define which chromosome will be chosen to produce the offspring. Again, this process is repeated to select the next parent. 2.3.4. Reproduction Once the parents are selected, the reproduction step takes place. The parents are combined using a crossover to generate the offspring. Then, the generated chromosomes can have its genes randomly mutated by the mutation process at a certain rate, this helps the algorithm to run away from local optimum and have a broader exploratory range in the search space. These steps and their probability rates are also problem specifics, giving that each problem will use the crossover and mutation methods that make sense. 2.3.4.1. Crossover Crossover is a vital process in the generation of new chromosomes. It exchanges genetic material (genes) from two or more chromosomes hoping that can generate individuals with better fitness in the next population (V. Kumar & Panneerselvam, 2017). Usually, the crossover is applied with a high probability, it means that in most cases the genetic material of the parents will be recombined to generate the children, less likely, they will just be copied to the next generation as they are. Using a 11 crossover rate of 100% means that every chromosome in the offspring was generated using at least the crossover. As the selection phrase, there are multiple methods to apply crossover, some of the most known and generic are one-point crossover and two-point crossover, among others. This project uses a different type of crossover that does not share the behavior of these generic methods and will be further explained in chapter 4. Because of that, only these two crossover techniques will be explained. These crossover methods will be addressed here to give an overview of how this process takes place in the majority of the cases and illustrate the crossover operation. The simplest crossover operator is the one-point crossover. In this type of crossover according to Kumar & Panneerselvam (2017), a random point is selected within the limits of the parent, this point is called the cut point. Every point possible to be selected have an equal chance of being selected. To illustrate, in figure 2.2, two parents represented by an array of characters with a total size of 6 elements each, the cut point would be any number between 0 and 4, and in this case, the point 3 was selected. The cut point splits the parents into two halves each. The first part is every array element which its index in the array is less or equal the cut point, the second part obeys the opposite rule where the elements with an index greater than the point are considered. To generate the children, the algorithm copies the first part of the parent one and insert in the offspring, then get the second part of the other parent and insert in the offspring. Changing the order of the parents and doing the same operation generates the second child (V. Kumar & Panneerselvam, 2017). Figure 2.2 – One-point crossover There are cases where elements within a chromosome cannot be repeated, as routing problems where a city must be visited only once, and all cities must be visited. In these cases, while applying the onepoint crossover, instead of just blindly copy the half of the second parents, the algorithm must copy the genes one by one in order, avoiding the elements that are already in the child until it is fulfilled. The two-point crossover is a generalization of one-point crossover. The difference between them is that the two-point crossover chooses two cut point instead of just one, this will split the parents into 3 parts. As a reference, multi-point crossover also exists, everything depends on the number of cut points selected. Figure 2.3 – Two-point crossover 12 Two-point crossover mixes the parts of each parent in the child. Each part is alternately selected and inserted into the child following a specific order. Using an example illustrated in figure 2.3 that is similar to the one previously saw in the one-point, the first part of the parent 1 goes first in the child, then the second part of the parent 2 is inserted, finally, the last part of the parent 1 is inserted. Repeating this operation interchanging the order of the parents generate the second offspring. 2.3.4.2. Mutation Mutations are small random changes in the genetic material of a chromosome. Mutations itself is not supposed to carry the solution to a better fitness in purpose, but they provide an insurance policy against the development of uniform populations that are less likely to improve themselves in the next iteration (Holland, 1992). Typically, the mutation rate is applied with a low probability of 1% or less in many cases (Whitley, 1994), because with very right probability, the algorithm could be reduced to a random search over the space. Common mutation methods are bit flip, swap, inversion, among many others that can be found in the literature. In the example below in figure 2.4, the swap mutation is shown. In this mutation technique, two genes of the chromosome are randomly selected and swapped between them, these cases are useful when repeating a gene is not allowed, as the case of the TSP. In the bit flip mutation, for each gene in the solution, there is a chance of change the data of the gene to other random data with the possibility to be inserted in the chromosome. Figure 2.4 – Swap mutation 2.3.5. Termination Genetic algorithms create population after population iterating until some condition, or conditions, have been reached. Conditions must be pre-defined by the developer of the algorithm, usually, they rely on time, the number of iterations, minimum criteria found. Kumar et al. (2010) described some techniques used as stop conditions listed below. ▪ Found a solution that satisfies a minimum criterion; ▪ Number of iterations reached; ▪ Computational time reached (budget); ▪ The algorithm has reached the highest fitness solution and no longer is producing a better solution for a number of iterations; ▪ Manual inspection; ▪ Combination of the previous methods or any other method created. 13 Once the termination condition is reached, the chromosome with the best fitness of the last population, or the chromosome with the best fitness found overall iteration is selected as the best solution found by the GA. 14 3. METHODOLOGY This project will follow the design science research methodology to accomplish its final goal. This research methodology requires that the motivation, problem, and objectives of the project must be clearly defined. Then with those steps accomplished, the development of the project is described based on the theory previously analyzed. With the completion of the project test cases take place to measure the performance and feasibility or the solution reached. In the case of this project, the test case was created using data from the Campolide parish’s waste collection, in the municipality of Lisbon, Portugal. The next paragraphs describe the steps of the methodology applied in more details, relating where each piece of the process can be found in this written research. Following this methodology, the first chapter presents the motivation and the problem of the study, specifically the subchapters 1.1 and 1.2. These subsections give a broad contextualization in the inherent nature of the population growth problem in the urban areas. Relating it to the sustainability concern in these cities and the waste management problem. Then it shows how the emerging concept of smarts cities came to deal with the overpopulation and overgeneration of waste, focusing on the use of ICT in approaches to deal with the waste collection, and describing the problems and limitation of basing every solution upon technological equipment. Still, in the subsection 1.3, the problem that this project aims to solve is presented, on how to optimize waste collection routes on the door-to-door collection without relying purely on ICT. This subsection explains the importance and challenges of the garbage truck routing problem giving an overview of the currently available solutions found in the literature that approach this problem, that is defined as a CARP. In the latest paragraphs, meta-heuristics are introduced as a possible way to deal with these kinds of problem, mostly the genetic algorithm, also describing the benefits of the application of these methods. On the subchapter 1.4, the objectives of this project are defined. On this section, a wider vision of the project’s aim and each step that will lead to the goal is defined, trying to follow a train of thought on how each step connects to each other to accomplish the final goal of having a genetic algorithm to deal with the routing of garbage trucks in a city, using the parish of Campolide at the Lisbon municipality as a model to validate the solution. The problem definition and motivation, besides having some theory to be based, was explained in a broader aspect because was not the main proposal of this project. In chapter 2, a literature review of the theory used to accomplish the research project was analyzed in a deeper way, presenting each topic that is important to the development of this project with more details. First, on section 2.1, the concept of open data was addressed. Since this project relies on data from governments departments, this concept was analyzed, and a state of the art was built on how the world deals with open data. This is important to make viable that the approach applied in this research can be replicated in other areas. In the subchapter 2.2, a literature review was made on the CARP algorithms and the current solutions available. The definition of the CARP is formally presented, as a variety of works about different algorithms to solve the CARP and its extensions. Then, in the subchapter 2.3, the genetic algorithm is described, with explanations of its core concepts. The subchapter 2.3 has subsections that explain in detail each step that most genetic algorithms have in common, like how to generate the offspring using crossover and mutation operations. 15 Following the chosen research methodology, chapter 4 describes in detail every aspect of the development of the project. The subchapters 4.1 and 4.2 define the tools utilized to accomplish the final goal, and how these tools were applied in the context of the project. Then, in the subchapter 4.3 the genetic algorithm built to deal with the CARP problem is described, specifically the garbage trucks routing problem in Campolide. The construction of the genetic algorithm follows every aspect presented in the literature review, adapting some steps that in order to solve the routing problem. In chapter 5, some tests are performed, and the results are described. The subchapters 5.1 and 5.2 discusses multiple tests made in order to define the parameters and conditions that best fit the GA developed, and the definition of waste weight that will be considered in each served street for the algorithm. Later, on the subchapter 5.3, the algorithm is executed with the best-found parameters and the results are assessed. Some discussion and analysis on the best result found can be found at the end of the subchapter 5.3. The conclusion, limitations and future developments can be found in the chapters 6 and 7. The chapters summarize the comprehension on the results found and its feasibility on real case scenarios including entire cities, taking into consideration the current limitations and future works to be done in the project to solve these limitations. 16 4. DEVELOPMENT This project aims to develop a genetic algorithm to deal with the problem of planning efficient routes to garbage trucks in a city. This problem, as stated before, is closely related with the CARP problem. But in real case scenarios, and in the Campolide’s case, the available trucks don’t have the same capacity. To deal with this difference some adjustments in the algorithms found in the literature must be made. This section gives an overview of the entire development of the project, the problems faced, the solution applied to solve these problems and why the reason on the way the problems were approached. The next subchapters will briefly contextualize the tools that were used to assist in the GA construction. This is important to understand the structure of data that are gathered and explain the choices on how to deal with this data. 4.1. A BRIEF WORD ON OPENSTREETMAP OpenStreetMap (OSM) is a collaborative mapping project where volunteers are free to create and edit geographic map information over the world to an open database. This database is also available for free under the Open Database License. The street data from OSM, that are relevant to this project, are organized in nodes and ways. The node is the smallest point of data in the map, it represents a single point by defining its latitude and longitude, figure 4.1 shows an example of a node in OSM. The nodes can also contain more information inside it, called tags. The tags are used to better qualify the node when it makes sense, for example, if the node represents a pedestrian crossing or bus stops, this information will be referred in tags. Some nodes have no tags, which is not a problem as they are used to represent a path. Figure 4.1 – OSM’s node example Streets in the OSM are represented using one or more ways. Ways are an ordered list of nodes, the way direction is defined by the order of the nodes in the way, having that the way starts at the first node and end at the last. The way representation can be seen at figure 4.2 Tags are also presented in ways to define things like the street name, the possible directions of the road, among other relevant information. Nodes shared between two or more ways define intersections between streets. Not all nodes are shared, there are nodes that are solely included in one way, for example, a node representing a pedestrian crossing may not also represent a street connection, among other cases. OSM is a powerful collaborative project that allows a variety of applications and studies on its data. There are much more about nodes, ways and how they relate to each other than discussed above, but those are not relevant to this project and therefore will not be addressed here. 23 chromosome of the group wins the tournament and is selected to be a parent in the crossover. The process repeats to generate the next parent. This tournament selection does not remove already selected parents from the population, so the same chromosome that just won a tournament can be selected again in the next tournament. In this project the lower distance is the best fitness, them even if very low fitness solution appears in the tournament group, they are very likely to lose against better fit solutions with lower distance, but this also gives a chance to not so good solutions, as it can happen to select a group where none of the best fit chromosomes are presented. Additionally, to always carry over the chromosome from the current generation with the best fitness to the next generation of individuals, a method known as elitism or elitist selection will be applied. This method guarantees a spot in the next population to the best individual of the current population, the solution will be carried unchanged, but still can suffer with a mutation in the construction of the offspring. The best solution will be inserted once more in the end of the evolution, to guarantee that it is not changed by the mutation step. This is done to make sure that there is a chance on evolving by mutation the best solution, and to prevent the best solution to be lost in case of the genetic operations change it into a higher fitness solution. 4.3.4.2. Crossover The crossover operation, as one of the most important operations in a GA, must work with the representation chosen on the chromosomes. In this project it works differently of the common crossover from most of the literature, the genetic material is not exchanged between parents, but a piece of the route is given by one of the parents, while the remaining genetic material is totally got from the other parent. This generates only one child in the crossover operations, because of that, more crossovers must be done to complete the next population. This crossover methods follows the one proposed by Pereira, Tavares, Machado & Costa (2002) but applying small changes on how to generate new routes on truck’s capacity overflow. The crossover randomly selects a sub-route of one of the parents and insert it on the other parent. The insertion point is defined to be just after the way which has the minimum distance between itself and the first way in the sub-route. This operation must guarantee that every solution generated from it is a valid solution. 24 Figure 4.9 – Crossover operation Summarizing the crossover process, two parents are previously selected in the selection step of the algorithm and a new chromosome is created to store the data generated by the crossover. A sub-route is randomly selected from one of the trucks of the second parent, this sub-route must have at least one edge. The selected sub-route weight is calculated and stored in a variable. One time only, the algorithms verify which edge has the lower distance between itself and the first edge of the sub-route, this verification is done accessing the distance matrix. From now one, the method will go through every truck from the parent 1, and consequently every edge each truck servers. This iteration will append new edges in the child path, and new trucks on the child used trucks array. It is important to notice that if the current edge of the iteration is presented inside the sub-route selected in the first parent, the edge will be not considered, because it would generate duplicated edges when the sub-route is inserted in the new solution. When the iteration finds the edge that is closest to the first edge of the sub-route, the edge will be normally appended in the solution and the sub-route will be inserted just after it. After the insertion of the sub-route in the child chromosome, the process continues until every edge is served by the child. An example can be observed in figure 4.9. In this example, the sub-route [ARC2, ARC9] is selected from the parent 1. With the distances’ matrix was discovered that the ARC8 was the closest edge before the ARC2. While copying the parent 2 edges to the child, the ARCs presented in the sub-route must be skipped, the first one was the ARC9 from the second truck. After that, the ACR8 was reached in the third truck, inserted as normal, followed by the sub-route selected. Having the sub-route inserted in the child, the process continues normally still skipping the ARCs present in the sub-route. Notice that fourth truck was removed from the solution because it became with no edges to serve. Capacities overflow can happen multiple times in this algorithm, to manage that, there is a list that stores every edge that could not be served for some reason. Once the previous process is complete, an iteration over the edges not served will take place assigning each edge to a truck as it is done in the initialization process of the GA. This guarantee that all edges are served by a truck. 25 4.3.4.3. Mutations As the crossover, the mutation step must be specific for this problem being able to deal with the chromosome representation. The mutation is applied to every member of a new population with a low probability. This project implements three kinds of mutation, called swap mutation, inverse mutation, and insertion mutation, each of them have their own probability of being applied. Mutation operators, as the crossover ones, can only generate valid solutions. In the swap mutation, a truck is randomly select from the chromosome, then a random edge served by this truck in the solution is selected. The same occurs once more in the chromosome. Even if the edges are inside an array without the truck’s array influence, is crucial to first select the truck so the capacity and the load of the truck are previously known for the mutation, this information is then utilized to only generate a valid solution. Having that two edges from the chromosome were randomly selected, a swap operation is done, the first edge takes the place of the second edge and the second edge is placed on the first’s spot. The swap is done with validation to stop weight overflows from occurring. In the case of the validation fails, the swap process is repeated until the validation is successful, with a maximum of ten attempts. After that, if the validation fails more than ten times, the mutation swap is not done. The inverse mutation acts just in a sub-route of a truck in the solution. Like the sub-route selection in the crossover step, a sub-route is selected in this mutation. Then the order of the sub-route in inverted and inserted again in the path. This type of mutation differently of the swap mutation can not generate invalid solutions, as the number and weight of the ways are not changed and only the distance can change, if this GA had other limitations like the total length a truck can travel because of its fuel, this could generate an invalid solution and would require a validation. New limitations can be developed and will be discussed in the future works section. The last type of mutation implemented in this GA is the insertion mutation. This mutation acts on the chromosome changing the position of one way. First, it selects randomly a single way server by a truck, then this way is removed from that truck and inserted in a new truck. This mutation is the only of all three that has a chance of creating a new route in the solution by adding a new truck. The probability of adding a new route is defined as 1 2𝑡 where 𝑡 is the number of trucks used in the solution. Like the other types of mutation, this one also guarantees that the solutions are valid in order to be executed. 4.3.5. Termination conditions The termination condition can be defined using several techniques, as the number of iterations, some criteria, and the fitness evolution. In this project, after the definition of the parameters the termination conditions were defined based on tests done using the algorithm execution. Was defined that this project will have two different termination conditions methods, one with the maximum number of iterations, and another one that analyzes the evolution of the fitness of the best solution in the population. The maximum number of iterations was set to 4000. In the fitness evolution, if the best fitness does not improve within 800 iterations, the GA will stop and take the best chromosome as the solution found. The first of the two conditions that are reached stop the algorithms, and the best solution will be the chromosome with the best fitness in the end. 26 5. RESULTS AND DISCUSSION In order to validate the proposed project, this chapter discusses the results obtained by applying it in the real case scenario of Campolide. The implementation and tests of the proposed GA were done using the Python 2.7 programming language on a MacBook Pro from late 2013 with the following specifications: 2.4Ghz Core i5-4258U processor with 3MB L3 cache, 4GB of 1600MHz DDR3 RAM and macOS 10.13 High Sierra. To decide on the genetic algorithm required parameters addressed in the previous chapter, multiple runs were made, and their results were analyzed. The next paragraphs will present the chosen test cases over the possible parameters combinations and the result of the algorithm execution with these combinations of parameters. 5.1. PARAMETERS DEFINITION The parameters to be defined are the population size, the tournament size, the crossover rate, and the mutation rate. In the literature a variety of combinations of these parameters can be found, mostly of them set a high probability of crossover, and low probabilities for mutation. Following the parameters adjustment in Pereira et al. (2002) and Karadimas et al. (2007) a set of values for each parameter were chosen based on the value range found in the literature review. There where proposed 2 different values for the population size, two values for the tournament size, three distinct crossover rates, and three values for the mutation rate. This generates a total of 36 different combinations, presented in table 5.1. # Population size Tournament size Crossover rate Mutation rate Initial fitness (km) Iteration 200 (km) Iteration 600 (km) 1 76 10% 75% 0% 544 273 180 2 76 10% 75% 1% 540 277 182 3 76 10% 75% 5% 542 266 177 4 76 10% 85% 0% 544 266 178 5 76 10% 85% 1% 545 271 177 6 76 10% 85% 5% 541 271 177 7 76 10% 100% 0% 541 244 163 8 76 10% 100% 1% 542 248 154 9 76 10% 100% 5% 545 242 165 10 76 20% 75% 0% 539 254 173 11 76 20% 75% 1% 540 274 185 12 76 20% 75% 5% 539 258 172 13 76 20% 85% 0% 540 241 159 14 76 20% 85% 1% 538 244 163 15 76 20% 85% 5% 542 250 162 16 76 20% 100% 0% 536 231 163 27 17 76 20% 100% 1% 540 236 169 18 76 20% 100% 5% 538 233 158 19 126 10% 75% 0% 537 240 158 20 126 10% 75% 1% 537 248 166 21 126 10% 75% 5% 540 238 154 22 126 10% 85% 0% 537 238 159 23 126 10% 85% 1% 539 229 159 24 126 10% 85% 5% 537 231 157 25 126 10% 100% 0% 537 223 156 26 126 10% 100% 1% 539 214 148 27 126 10% 100% 5% 540 227 149 28 126 20% 75% 0% 536 224 154 29 126 20% 75% 1% 539 235 160 30 126 20% 75% 5% 539 228 159 31 126 20% 85% 0% 534 214 151 32 126 20% 85% 1% 540 225 161 33 126 20% 85% 5% 536 238 164 34 126 20% 100% 0% 537 222 153 35 126 20% 100% 1% 538 222 152 36 126 20% 100% 5% 537 214 152 Table 5.1 – GA parameters combinations For each one of the 36 combinations, the genetic algorithm was executed 10 times performing 10,000 iterations in each run. In total, the algorithm was executed 360 times and performed 3,600,000 iterations. The last three columns from table 5.1 show the average of the ten executions of each combination for the initial population, that was randomly generated, the iteration 200 and 600. In the initial population, the values oscillated 11km between the best (minimum) and worst fitness. In the iterations 200 and 600, the range goes from 11km to 64km and 38km respectively, showing that the parameters indeed influence in the convergence of the solutions. From the data can be seen that the population size and the crossover rate are the parameters that most influence the solutions’ convergence of the algorithm. In figure 5.1 a chart with the iterations of each previously present combination is shown, in this chart can be seen that the combination number 26, represented with a thicker pink line, is the one that has a higher performance on the tests, and its parameters will be used to run the GA. Giving that, the default parameters are set as 126 chromosomes in the population, the tournament size will have 10% of the total size of the population with 13 chromosomes. Every child from the evolved populations will be generated using the crossover, except the two children that have a spot in the next population due to the elitism approach, being that one of them is prone to mutation to give an opportunity to improve its fitness due to mutation. 28 Figure 5.1 – GA parameters choice Besides the GA’s parameters also have to be defined the termination condition of the algorithm. As can be seen in figure 5.1, the convergence of the algorithm is concentrated basically on the first 1000 runs. From 1000 iterations onward the best fitness suffers little changes in its values. Using the chosen combination 26, from the iteration number 1000 to the iteration number 10,000, the fitness dropped from 139 kilometers to 130, a drop of 10 kilometers only, while from the iteration 600 to 1000, the drop was 9km from 148km to 139km. The same approximate amount decreased in the fitness that was observed during 9000 iterations happened in the previous 400 iterations. This leads that the first 1000 iterations must be within the range of the termination condition, but still, that the search is not stagnated and given enough time to the algorithm it still can explore the search space looking for best solutions. Based on the execution results data, the number of 4000 iterations was chosen to be the maximum number of iterations in the termination condition allowed in the GA. The second termination condition defined in this project is the number of iterations without improvement on the best fitness. This number was defined based on the runs of the GA with the combination 26. The executions show that if 800 iterations have been performed since the last best fitness, it will be hard or take a longer time to find the next best fitness that in all cases do not improve the solution as much to justify the time it takes to compute. Figure 5.2 shows the average evolution of the combination number 26, in the graph can be seen the stated before that the bigger improvement of the GA is located on the first iterations, and as soon it reaches a certain number of iterations, the improvement drops until become irrelevant to the amount of time it needs to be computed. 100 150 200 250 300 350 400 450 500 0 200 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 2600 2800 3000 3200 3400 3600 3800 4000 4200 4400 4600 4800 5000 5200 5400 5600 5800 6000 6200 6400 6600 6800 7000 7200 7400 7600 7800 8000 8200 8400 8600 8800 9000 9200 9400 9600 9800 10000 Fitness (km) GA parameters tests 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 29 Figure 5.2 – Combination 26 fitness evolution 5.2. DEFINING THE GARBAGE WEIGHT TO BE COLLECTED Besides having the termination condition and parameters defined, the actual weight of each edge must be defined in order to relate the roads collections with the truck’s capacities. Fadzli et al. (2015) state that managers usually find it is hard to send the ideal number of vehicles to perform the waste collecting due to the fact that guessing the waste weight to be collected is a difficult process. In the residential door-to-door waste collection, the total garbage weight of each street for collection is unknown, methods to determine the amount of garbage can be found in the literature as the case of CARP with stochastic demands (CARPSD) (Fadzli et al., 2015). To solve this issue and create a solution that actually meets the reality of the city, this project makes use of open data from the government. Having the collection data from the preceding months, a good approximation can the done on the amount of garbage the city generates, and how it is distributed along the roads. The collected data of the past months provided by the Câmara Municipal de Lisboa is organized by collection route, which means that each current route traveled in a day have the collected weight amount measured. A route is defined as a set of streets traveled by the garbage truck. The routes that contain streets of Campolide can also pass through other parishes. A percentage of the weight collected by the route was measured considering only the streets within Campolide. With the measure of weight collected only in Campolide, a mean of the amount of weight per meter is done for each route in the parish. With that mean calculated, the distance of a way can be used to set the garbage weight of each served street in the problem. In this real case scenario, the plastic and metal household collection in a period of 4 months was analyzed in order to assign each road the corresponding amount of weight that it will have. Then, the 0 100 200 300 400 500 600 0 65 130 195 260 325 390 455 520 585 650 715 780 845 910 975 1040 1105 1170 1235 1300 1365 1430 1495 1560 1625 1690 1755 1820 1885 1950 2015 2080 2145 2210 2275 2340 2405 2470 2535 2600 2665 2730 2795 2860 2925 2990 3055 3120 3185 3250 3315 3380 3445 3510 3575 3640 3705 3770 3835 3900 3965 Fitness (km) Combination 26 average Average 30 solutions found in the tests are aiming the recyclable collection of plastic and metal only. For other types of waste, different information needs to be loaded into the weight of the edges according to the objective. Using the real amount of garbage collected, the solution implicitly considers the streets population density and its residents’ habits of garbage disposal. 5.3. RESULTS EVALUATION With the GA operations and parameters defined, the algorithm was executed 10 times in order to get the best result of these runs. Using the best chromosome, the routes can be calculated and plotted on a map allowing to access a visual representation of the solution. The best solution found has a fitness of 113,378.20 meters, using 4 trucks to collect the garbage from the city. The distance traveled going back and forward to the deposit in the route is 57,639.47 meters, and the actual distance used in the collection step is 56,738.73 meters. The route is represented in the map of Lisbon, as can be seen in figure 5.3. Figure 5.3 – Example of route The routes, as stated before, starts and end a deposit, the deposit can be observed in figure 5.3 as a big red dot in the top of the figure, can be clearly observed a path going and return from the deposit to the parish of Campolide. To better visualization of the routes found by the GA execution, the map was zoomed in to show only Campolide and the four routes were plotted, figures 5.4, 5.5, 5.6 and 5.7 shows the path that each garbage truck needs to travel in order to perform the collection from every edge defined in the GA. The routes built by the algorithm clearly shows that the served edges create groups in specifics areas of the Campolide region. Even if it is possible to improve even more the solution, this is a good approximation on which path a set of trucks must travel to serve the city. The actual path can be seen just looking at the edges in the route and listing it in the order it appears in the route, so the driver can follow the directions using both the map and the list of streets that need to be traveled. 31 Figure 5.4 – Route 1 Figure 5.5 – Route 2 Figure 5.6 – Route 3 Figure 5.7 – Route 4 Table 5.2 shows the final results for the routes constructed. As can be observed, only one class of truck was chosen to be a part of the solution, which make sense, as the classes on the current stage are not limited by streets constraints, which is one of the limitations and future works that will be discussed further. But the table also shows that the algorithm takes advantage of trucks capacities to allocate the required edges, the percentage of use is greater than 97% in three cases, and 74% in one, probably because it run out of edges that required to be served. The project maximized the use of each truck in the solution, also searching for the shortest distance that each truck needs to travel to complete the collection on all the required streets. 32 Route Number of edges served Truck capacity Truck load % load 1 75 1456 1421 97,63 2 70 1456 1439 98,87 3 78 1456 1082 74,32 4 86 1456 1442 99,08 Table 5.2 – Routes trucks information As this project deals with a simplification of the Lisbon waste collection, addressing just a central region of the entire city of Lisbon, the comparison with the actual routes can not give the exact result on which method is better to deal with the waste collection. The routes within Lisbon are not exclusively in some region and can pass through several regions instead on focus only inside one. This leads that routes serving only Campolide do not exist in the current context. Even more, the actual data do not address the streets covered by the route 2 of the GA’s best solution, represented in figure 5.5. As an addendum, one can realize that the edge highlighted in figure 5.8 was not served by any routes displayed in the figures 5.4 to 5.7. This happens because to plot the graph with the path, the python function receives a list of nodes and draws a red line through the shortest path between each pair of nodes. That edge that is never highlighted, share its two nodes with another road, that tends to always be the shortest between these nodes. So, even if the edge that represents that street is within a route, and it indeed is, it will not show highlighted with red in the map using the current plot function. Figure 5.8 – Piece of route 1 highlighting road without red highlight Even that on this project only the data from Campolide, which is a region inside the city of Lisbon, was used to evaluate the algorithm, the project showed itself feasible for approaching large instances as a city. Because only within Campolide the GA had to deal with 473 edges, and there is still space for optimization on performance.