Keywords

1 Introduction

In Latin America and the Caribbean, households continue to form the primary source of production and composition of urban solid waste, so real communication about production and composition is essential for their management, because they often lack the necessary infrastructure for the correct treatment of these.

The generation of garbage in Peru and the world is linked to practically anything we do, and it is only in Peru that more than 18 thousand tons of garbage are generated every day; This garbage produced must be collected and properly treated by the municipalities and institutions in charge of it. In Peru, the collection of household solid waste has been the work of the municipalities, which are in charge of assigning routes for the collection of waste, these being empirically designated without a formal optimization study. (Manrique 2020, p. 5).

The figures are not encouraging at all. If humans do not change our habits, it is estimated that by 2050 there will be more plastic than fish in the ocean and that 99% of marine animals will have ingested it, according to the United Nations Environment Program.

In 2018, the city of Huánuco reported to the National Institute of Statistics and Informatics that per day it collected 282,181 kg of garbage, this collection represents, according to data from the Ministry of the Environment, 70% of the garbage produced daily, that is, approximately 120 934 kg of garbage remains on the streets, this is due to different factors, the main cause being the poor distribution of solid waste collectors.

The city of Huánuco collects solid waste constantly and through defined routes, although it is true at first glance this method seems to work without problems, the reality is that it does not, this because there are places in the city. city where there is a greater concentration of people, which leads to a greater generation of waste in the main areas of the city, such as the popular markets (Mercado Modelo de Huánuco), parks and squares (Plaza Mayor and Plaza de Armas), among other areas.

The degree of awareness achieved in society on the issue of ecology requires that solid waste management take care of the environmental environment; Therefore, citizens demand superior and important controls and regulations. On the other hand, Hermitaño (2019), argues that The VRP (Vehicle Routing Problem, in English) is one of the best known problems, as well as captivating and challenging of the integer combinatorial optimization, it is placed in the category of problems Called NP - Complete, it is a large set of problem variants and customizations. From those that are simpler to some that today are still a matter of research (p. 13).

In turn, the New Law of Integral Solid Waste in Peru Legislative Decree No. 1278, establishes that solid waste is an input for other industries where it is no longer considered as garbage and is now considered as raw material in other industries that can give value to waste. Another contribution of the new Comprehensive Solid Waste Law is that it lays the foundations for the development of a large recycling industry at the international level, in such a way that Peru could become a regional solid waste treatment hub, generating higher income, investment, higher employment and high standards of environmental management. However, this law has not yet been applied in the city of Huanuco, where a reality different from that supported by the Law is reflected, main streets with excess garbage and uncontrolled traffic that does not meet planning standards.

Finding the shortest route from a certain source to a certain destination is a well-known and widely applicable problem. Most of the work done in the area has used static route planning algorithms such as A*, Dijkstra, the Bellman-Ford algorithm. Although these might be optimal algorithms, they are not capable of dealing with certain real-life scenarios. (Nanayakkara et al. (2007)).

In turn, Li et al. (2006). Argues that algorithms allow various acceptable solutions that will depend on the problem treated, operations such as encoding, crossing and mutation are adapted to adapt to the optimal route planning. The simulation results show that the specific genetic algorithm has advantages such as a fast calculation speed and a high probability of an optimal solution, however each of the methods to be applied has its own advantages and disadvantages. (Li et al. 2006).

2 Theoretical Framework

2.1 Genetic Algorithm

The so-called evolutionary genetic algorithms (GA) work with a population of individuals, who represent possible solutions to a problem. This population undergoes certain transformations and subsequently a selection process, which favors the best individuals. (Petriv 2012, p.7). In turn, genetic algorithms (GA) address a wide range of concepts, and are thus a useful tool for the detection of optimized solutions. They are inspired by biological evolution and its genetic basis, evidenced in the evolutionary traits of a population.

These individuals are subjected to random actions similar to those that act in nature (genetic recombinations and mutations), developing through iterations called generations. (Petriv 2012, p.7).

For Goldberg (1989), he argues that a genetic algorithm consists of a population of solutions encoded in a similar way to chromosomes. Each of these chromium-somes will have an associated adjustment, goodness or fitness value, which quantifies its validity as a solution to the problem.

Genetic algorithms require that solutions to the problem can be represented in some binary format, that two or more of these solutions can be significantly combined, and that an objective function value can be evaluated for each of these solutions.

2.2 Structure of the Genetic Algorithm

A genetic algorithm requires the following structures: a genetic representation and an objective function.

Genetic representation refers to the way to represent individuals or solutions, in genetic representation information on the characteristics of individuals must be included.

The objective function is used to determine how fit an individual is based on what you want to achieve in the final solution. The objective function evaluates the performance of individuals and this is how the fittest can be determined. (Castillo 2018, p. 18).

2.3 Characteristics of the Genetic Algorithm

The characteristics of the proposed AG were taken as a reference from (Nanayakkara et al. 2007), (Moratilla et al., 2014) and (Ikeda & Inoue, 2016) since they demonstrated optimal results in their investigations of vehicular routing problems.

The simplest meta description for a genetic sequence.

The algorithm has the following steps:

  1. 1)

    Coding

  2. 2)

    Initial population generation

  3. 3)

    Repeat until completion criteria are met

  4. a)

    Evaluation

  5. b)

    Crossing

  6. c)

    Mutation

  7. 4)

    Decoding

More detailed description of genetic and evolutionary algorithmic approaches, and applications of such approaches can be found in Mitchell M. (1998) in (Nanayakkara et al. 2007).

2.4 Stages of a Genetic Algorithm

The stages of a GA, defined by Schmitt (2001), are:

Initialization: Form the initial population of possible solutions.

Selection: The selection process consists of executing the objective function in each one of the individuals to determine their level of aptitude.

Genetic operations: It is the stage in which the subset of the population selected in the previous stage is altered to obtain a new population, it may be by the Crossover or Mutation methods.

Termination: It is defined when a solution is obtained that satisfies certain criteria, a certain number of iterations is reached, or when the iterations no longer produce better results.

2.5 Graph Theory

The theory of graphs is used in the treatment of various problems, the graphs constitute a useful abstraction to model various real situations such as the problem of vehicle routes, and its greatest importance is manifested in the theory of networks, in the computer science and telecommunications, among others. (Hermitaño 2019, p. 8).

A graph G = (V, E) is an ordered pair in which V is a nonempty set of elements called vertices and E is a set of elements called edges, consisting of unordered pairs of vertices, such that yes {x, y ⊂ E}, then we say that x and y are adjacent vertices; it is represented by an unoriented line that joins these vertices. (Hermitaño 2019, p. 8).

  • Given a graph G = (V, E), then it is said that:

  • It is a lasso or loop to all edges of the form with (v ∈ V)

  • The edges are multiple when the edges that appear repeated in E.

  • Vertices are adjacent if they are joined by an edge.

  • Edges are adjacent if they have a common vertex.

  • An edge and a vertex are incidents if the vertex is extreme of the edge.

  • A vertex is isolated if it is not adjacent to any other vertex.

  • A graph is simple if it has no loops or multiple edges. (Hermitaño 2019, p. 9).

2.6 Metaheuristics

Metaheuristics is a kind of special method or strategy that performs an intensive exploration of the solution space. (Hermitaño 2019, p. 9).

Metaheuristic Techniques

The best known metaheuristic methods are:

  • Simulated Annealing (Simulated Annealing, 1993)

  • Genetic algorithms (Holland, 1960)

  • Taboo search (Glover, 1986)

  • Greedy random adaptive search procedure (Horowitz, 1978)

  • Ant colony algorithms (Dorigo, 1999)

  • Guided local search (1999)

  • Search for the neighborhood of a variable (2003)

Route Planning

It is the procedure of creating the most profitable route possible, minimizing the distance or travel time we need to get to our set of planned stops.

Planning is a critical process within logistics both due to the existing competition and the reduction of margins of action in the market. A high expenditure on vehicles, boats or any type of transport along with fuel and maintenance of the same to which we must add labor (Saminef 2020).

Route Programming

The main objective of the programming of a route is to reduce expenses as well as the time factor, intervening stops, arrivals and destination. However, route optimization includes factors such as schedules, time constraints, road restrictions, weight capacity among others (Saminef 2020).

2.7 Objecives

General Objecives

Develop a route planner for the collection of solid waste in the district of Huanuco using Genetic algorithms.

Specific Objectives

  • Determine the problem of solid waste collection in the Huanuco district.

  • Design the genetic algorithm.

  • Design the optimal route plan for the Huanuco district.

  • Conduct tests of the planner for the collection of solid waste in the district of Huanuco.

3 Methodology

The study carried out is of a complementary type because it uses qualitative techniques (Observation Guide) and quantitative techniques (Development of an algorithm to define an optimal route plan). Therefore the approach is complementary.

In itself, the design is experimental of the quasi-experimental subtype, because a stimulus is used through the route planner and determines the optimal route, in a set of routes established by the researchers.

The technique for collecting the information was the observation guide in order to obtain the data that, in advance, have been defined as of interest for the investigation. According to Sampieri, the population defines it as: “A set of all cases that meet certain specifications”, which is equivalent to 12 vehicle units in charge of collecting garbage in the study area.

The sample “Subgroup of the universe or population from which the data are collected and which must be representative of it”. For the study the sample is made up of 4 vehicle units in charge of collecting garbage in the city.

The study sampling was established as a non-probability sampling for the convenience of the researchers.

4 Results

The main results obtained are defined according to the objectives indicated in this study:

According to the objective of Determining the problem of solid waste collection in the Huanuco district, the problem was defined through an Observation Guide, whose objective was to collect information on the routes of solid waste collection in the city of Huánuco, The problem found was the inadequate solid waste collection management in the Huánuco district, the observation area was carried out in the streets of the city of Huánuco and strategic places, the observation time was carried out in 3 h a day for 3 days, the observation guide was structured according to 5 dimensions of web platform analysis, operation, test, restrictions and planning, through a nominal scale with a yes and no answer, reporting through the instrument used, that the management of the authorities is terrible, residents accumulate their waste next to their houses or in places accumulated by neighbors, recent accumulations were observed in The places where waste accumulates, uniformed collectors were also observed carrying safety tools (helmet and gloves), few places were observed to deposit their waste, garbage bags were located around the places where the collection trucks pass.

According to the objective of Designing the genetic algorithm, it was established that genetic algorithms are particularly appropriate to solve real route optimization problems due to their robustness and flexibility to adapt to changing environments, and complies with a structure defined as:

  • Genetic architecture.

  • Populations and their size.

  • Initial population.

  • Evaluation.

  • Selection.

  • Crossing.

  • Mutation.

The operation of the genetic algorithm follows the following process:

  1. 1.

    Initialization of the population.

  2. 2.

    Repair function.

  3. 3.

    Fitness assessment.

  4. 4.

    Repeat the process.

  5. 5.

    Selection of survival, elitist strategy.

  6. 6.

    Cross operation.

  7. 7.

    Selection of parents, selection by tournament.

  8. 8.

    Mutation operation.

  9. 9.

    Repair function.

  10. 10.

    Assessment of aptitude.

  11. 11.

    Until meeting a convergence criterion.

  12. 12.

    Decode the best solution.

Genetic Algorithm Application Model

The case study presented in this section corresponds to the cleaning and collection of solid waste needs in the city of Huánuco.

For which the model was then started, with a set of classes (initial population, route and final vertex), which have associated their distances from vertex to vertex and costs, divided, the routes are divided into vertices, usually the distance -from one vertex to another is different, we have 4 trucks available, 2 trucks for garbage collection during the day shift hours and 2 trucks for garbage collection during the night shift hours, for this, 4 optimal routes were generated.

We define then: A route of 4 assignments, one for each collection truck. The routes were subjected to multiple restrictions, greater number of vertices and the schedule, no route was accepted if it did not comply with all the established restrictions.

Variables Involved

  1. a)

    Path length: The maximum size of an individual

  2. b)

    Start vertex: The beginning of the route

  3. c)

    Final vertex: It is the end of the tour

  4. d)

    Maximum length

  5. e)

    Generation: Initialization of the Initial population

  6. f)

    Temporary population

  7. g)

    Population size

  8. h)

    Elitism: 2 Individuals

  9. i)

    Selection operation: Selection by tournament

  10. j)

    Crossing Operator: 1 point

  11. k)

    Crossover rate: 0.80%

  12. l)

    Mutation rate: 0.1%

According to the objective of designing the optimal route plan for the Huanuco district, the most suitable route plan was established.

Graphic Representation of a Route

It must be taken into account that the vertices assigned in a chromosome are generated randomly, “but not so random”, this because it can randomly repeat the vertices; therefore, it is considered invalid vertex, which is considered in the creation of valid chromosome. Authors’ elaboration.

And it fulfills the following structure: Chromosome = [\({vertex}_{1}\), \({vertex}_{2}\), \({vertex}_{3}\), \({vertex}_{4}\),… \({vertex}_{n}\)].

ó chromosome = [\(route_{1 } ,\,route_{2 } ,\,route_{3 } ,\,route_{4 } , \ldots \,route_{n}\)] (Fig. 1).

Fig. 1.
figure 1

Representation of the assigned vertices.

Full size image

Analyzing the structure of the chromosome, it is indicated that one of the possible optimal pathways is the vertex 1, followed by \({vertex}_{2}\)… until the vertex n. This reflects the distance of the \({vertex}_{1}\) a \({vertex}_{2}\), plus the distance of \({vertex}_{2}\) a \({vertex}_{3}\), so keep adding up to the distance of \({vertex}_{n-1}\) until \({vertex}_{n}\).

Fitness: It is the adaptation value of each chromosome, which allows to corroborate which chromosome is more suitable among the population. This is reflected by the following equation:

Fitness = 1−distance/maximum distance * tam Chromosome).

Coding an Individual According to the Structure Described

The figure shows the representation of the route of the collection trucks, represented by the location points of the area under study and its vertices. Obtained through the online server Google Maps (Fig. 2).

Fig. 2.
figure 2

Coding an individual according to the structure described

Full size image

Representation of a Vertex

The code for a vertex consists of (3) characters. The vertex codes can be coded from V1 to V99 (See Fig. 3).

Fig. 3.
figure 3

Representation of a vertex.

Full size image

The figure shows the representation of a vertex. Example V8.

Representation of a Route.

The most optimal route for the collection trucks is represented (See Fig. 4).

Fig. 4.
figure 4

Representation of a route, image obtained through the online server Google Maps.

Full size image

Representation of a Collection Truck

They are made up of (4) alphanumeric characters that are the first two characters of the truck and the last two of the truck schedule. Characters can be from C1D1 to C4D2 (Table 1).

Table 1. Representation of a collection truck
Full size table

Distance Representation

It is formed by two vertices, the distance codes can be alphanumeric of (3) digits. The distance codes can be from D01 to D99.

  • Conduct tests of the planner for the collection of solid waste in the district of Huanuco.

  • Develop a route planner for solid waste collection in the Huanuco district using Genetic algorithms (Fig. 5).

Fig. 5.
figure 5

Distance representation.

Full size image

The figure shows how to represent the distance between two vertices. Image obtained through the online server Google Maps.

Representation of a Day

The code for a day consists of one (1) digit. Day codes can be encoded from 1 to 3.

Table 2. Representation of a day
Full size table

Nota. The table shows the way of the representation of a day, where the collection truck only passes through the route three times a week. The days of the week will be Tuesday, Thursday and Saturday.

Data Set Preparation

To obtain the georeferential points, it begins with obtaining the georeferenced points (latitude and longitude) by the “Google Maps” map application server, on the map of the city of Huánuco, to later convert those points into a weighted directed graph. The georeferenced points to take into account will be obtained at random. The georeferenced points are obtained in this manual way according to the investigations of (Zhang, Chen, & Li, 2015).

Based on the information obtained from the map server Google Maps, we obtain the summary of the data of each simulated route.

Fig. 6.
figure 6

Simulated routes.

Full size image

The figure represents the vertices, latitude, longitude and place of the Huanu-co district, which have been considered in the simulation with Google Maps.

The data previously produced in Fig. 6 were obtained from the representation of the map of the city of Huánuco, making use of the “Google earth” map application server as indicated in the following figure (Fig. 7).

Fig. 7.
figure 7

Simulated routes obtained on the map server “Google Maps”.

Full size image

It is important to mention that in Fig. 4 the projected trajectory is not the optimal route, but is the trajectory automatically produced by the “Google Maps” application when placing various points on the map.

Convert Georeferenced Points to Graphs

Launch the Problema

The solid waste collection truck must travel at the infectious focus points set by the user, so how to determine an optimal path for the solid waste collection truck so that the length traveled is the shortest, taking into account the direction of the streets.

Modeling the Problem

From the point where the truck is to the points of infectious foci, a graph must be originated, now both the truck and the infectious foci from now on will be called vertices. Where the starting vertex of the truck will be called v 0, the rest of the vertices are the infectious foci, which will be “v1,2”, and the routes between them will be called edges. The modeling is carried out in this way because the map application server “Google earth”, although it can save the information of a part of the map that the user selects automatically, the format of that information is a list of coordinates (latitude and longitude), which does not show the relationship of a coordinate with another coordinate (adjacent vertices), nor the direction of the streets, nor the value of the distance (cost) of a coordinate with another coordinate The graph presents a Starting Point: V1 End Point: V57 (Fig. 8)

Fig. 8.
figure 8

Weighted directed graph of the solid waste collection network. Obtained from Google Earth. Authors’ elaboration.

Full size image

Problem Solution

The solid waste collection network is abstracted as follows, “v0” the vertex where the truck is located, and the other vertices are the infectious foci, the weight of the edge between the vertices is the length of the route interpreted in meters (m).

The procedure to carry out the adjacency matrix is summarized in abstracting the distance between a pair of vertices that are associated and in turn accessible, from the directed graph of Fig. 14, see Table 2.

It is necessary to refer to some conclusions in the development of the planning of routes established in this aspect, under the evolutionary model, the shortest route of n vertices can be found and it does not present complications due to the number of vertices to be evaluated, considering that it was tested with “n” nodes and we predict that it will be in seconds.

The genetic algorithm that is developed calculates optimal routes based on distance, time, taking into account random events such as distances, vertices and the time of, while the GoogleMaps algorithm has an average error of 24%, therefore, With the proposed genetic algorithm, the accuracy of route calculation is improved compared to GoogleMaps.

From the tests it is necessary to highlight the importance of the initial vertex of the route because any additional deviation affects the trajectory considerably (Fig. 9).

Application of the Genetic Algorithm on the Graph

Flow Chart Design

Fig. 9.
figure 9

Flow diagram of the algorithm for route planning, designed in the PsInt tool. Prepared by the authors.

Full size image

5 Discussion

Having concluded with the results of the present investigation, in this chapter it is intended to approach the discussion of results, considering the results obtained, the theories that support the investigation and the antecedents, as José Jaime Ruz says, the application that helps to obtain the most optimal, it reduces costs for our entities, which is a good option. You use genetic programming to carry out these types of projects. On the other hand, Jorge Andrés Quintero tells us that the world of transport has very serious problems causing many losses and for this, using technology is a good option to combat these deficiencies, he also tells us that the most important thing for this type of implementation is the Planning is for this reason that in our project we first saw the part of the guide in order to see the deficiencies that transport has for waste collectors, after that we plan the type of language that we will use and how we intend to solve this problem, for this we use a page that is known to all or the vast majority called Google Maps. This page helped to collect real data for our project; Medina tells us that there are eight basic elements to design genetic algorithms.This heuristic technique originally developed to solve TSP has been modified to satisfactorily solve CVRP and SCVRP and this helped us to design the genetic algorithm of the routes for waste collection. And finally we designed this genetic algorithm in a small city called Huánuco, because we saw that the management of the garbage collectors’ routes was not good and with all the data collected we started to implement this project, the An explanation of our project is in the annexes, in more detail but here we will explain in a summarized way, it is an app where it will ask you for the number of streets, the transition if it is a lot or this street is empty and then ask if they are two-way or No, and with all these data our algorithm will identify which is the most optimal route, but first we have to make some adjustments because we know, or at least those who live in Huánuco, that the streets of Huánuco are not square, for this are the adjustments before of the search, and the result will come out of a nomenclature elaborated by us, the first letter identifies the column and the first number the number of the column then it will find another l This will be the row and the row number in order to arrive at the optimal route.

Conclusions

The graph was constructed by gathering information from the streets and/or avenues of the Huánuco district such as addresses, coordinates, street intersections, through the Google Maps map provider through an Adjacency matrix, to later execute the Genetic Algorithm.

The procedure to find the best route between several infectious foci causes the genetic algorithm to be used twice to find the best solution. The first place, when entering the initial point and the infectious foci, evaluates the most optimal route in the order from which the collection truck should pick up, and secondly, constructing the shortest route between each pair of vertices to arrive from the truck to the first infectious focus, and from the infectious focus to the next if there is one, and so on progressively.

The execution time of the genetic algorithm to find an optimal solution can be decreased, reducing the population size, but it is observed that, for complex routes, the precision of the genetic algorithm decreases as the population size is reduced.

Recommendations

Municipalities or public or private companies in the town of Huánuco are recommended to implement a route planning software using the genetic algorithm, since it provides you with a more optimal solution to find a route from an initial point to an end point.

Future researchers are recommended to modify the genetic algorithm developed to a multiobjective algorithm, where it can take into account information on traffic, route through main roads, etc. Converting the proposed genetic or algorithm into an intelligent route planning system.