Keywords: genetic algorithm, optimization, real-value coding, traveling salesman problem, large-scale example, solid waste routing.

Solid waste management is concerned with the control of generation, storage, collection, transportation, processing and disposal of waste according to the principles of public health, economic and other environmental consideration. The routing is one of the main components of solid waste management in the cities where the collection takes more than 85% of the solid waste system cost. The objective of this research paper is to find the optimal routes with the least cost for solid waste collection in the cities taking Irbid City in Jordan as a case study. The routing problem in Irbid is a node routing or traveling salesman problem (TSP). A set of 15 nodes with 1 or 2 waste containers at each node were in service by vehicles. Our problem has been the construction of a tour through n points with a minimum distance.

The traveling salesman problem (TSP) is one of the most widely studied and most often cited problems in operations research. For over fifty years the study of the TSP has led to improve solution methods for wide range of practical problems. Those studies based mainly on several modeling approaches such as linear and dynamic programming techniques and also heuristic techniques. Genetic algorithms have also been used successfully to solve this NP-problem. However, in many of such works, a little effort was made to handle the problem of routing solid waste collection.

Previous to this case study the authors [1] applied their own research work for modeling techniques of Monte Carlo Simulation and Heuristic Algorithms which concluded that the shortest tour was by Monte Carlo Simulation 6715 m and by modified heuristic algorithm was 7945m.

The present work is completing the above mentioned research by using linear and dynamic programming techniques which revealed that the mathematical modeling has limited success with the TSP, with a limited number of nodes and with the need to formulate a large number of constraints. For problems like ours this can take a long time.

Moreover, a new genetic algorithm methodology for optimal solving the TSP has been applied. This methodology takes by real representation with any code (binary, integer, real, name), whether individual or combined, without any need to changer from one to another, i.e. our GA, using the chromosome as a unit, works equally well with integer and non-integer decision variables. This is a specific behaviour distinguishes our real-coding GA from other binary-coding or Gray-coding GA. In our example we work with one chromosome of 14 genes to represent a solid waste routing design for the studied network consisting of 15 nodes.

The parameters used for implementing our GA were the population size of 40 with fully efficient genetic operators probabilities of 0.8 for crossover and 0.4 for mutation. The optimization was carried out over 80 generations. The GA found a solution which led to the shortest - distance (lowest cost) of 6585m with 2060 simulations (evaluations) for collection vehicles routing in Irbid. Figure 1 shows a plot of the distance of the best solution in each generation. The results of our study, in comparison with the other applied optimization methods (linear, dynamic, Monte Carlo and heuristic search method), indicated that the real GA through its specific behavior produces significantly the lowest distance (cost) solution. Accordingly, it is concluded that the real GA approach is robust, represents an efficient search method and is easily applied to nonlinear and complex system of the well-known TSP in the field of solid waste routing system in the large cities.

1

A.R. Awad, M.T. Aboul-Ela and R. Abu-Hassan, "Development of a Simplified Procedure for Routing Solid Waste Collection", International Journal for Science and Technology (Scientia Iranica), 8(1), 71-75, 2001.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £105 +P&P)