Computational & Technology Resources
an online resource for computational,
engineering & technology publications 

CivilComp Proceedings
ISSN 17593433 CCP: 84
PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON ENGINEERING COMPUTATIONAL TECHNOLOGY Edited by: B.H.V. Topping, G. Montero and R. Montenegro
Paper 57
The Solution of the Traveling Salesman Problem of Solid Waste Routing in Cities Using Real Genetic Algorithms A.R. Awad^{1}, I. Von Poser^{2} and M.T. AboulEla^{3}
^{1}Department of Environmental Engineering, Tishreen University, Lattakia, Syria
A.R. Awad, I. Von Poser, M.T. AboulEla, "The Solution of the Traveling Salesman Problem of Solid Waste Routing in Cities Using Real Genetic Algorithms", in B.H.V. Topping, G. Montero, R. Montenegro, (Editors), "Proceedings of the Fifth International Conference on Engineering Computational Technology", CivilComp Press, Stirlingshire, UK, Paper 57, 2006. doi:10.4203/ccp.84.57
Keywords: genetic algorithm, optimization, realvalue coding, traveling salesman problem, largescale example, solid waste routing.
Summary
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 NPproblem. 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 noninteger decision variables. This is a specific behaviour distinguishes our realcoding GA from other binarycoding or Graycoding 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 wellknown TSP in the field of solid waste routing system in the large cities. References
purchase the fulltext of this paper (price £20)
go to the previous paper 
