Solving the Team Orienteering Problem: Developing a Solution Tool Using a Genetic Algorithm Approach
Nowadays, the collection of separated solid waste for recycling is still an expensive process, specially when performed in large-scale. One main problem resides in fleet-management, since the currently applied strategies usually have low efficiency. The w
- PDF / 461,067 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 80 Downloads / 196 Views
Abstract Nowadays, the collection of separated solid waste for recycling is still an expensive process, specially when performed in large-scale. One main problem resides in fleet-management, since the currently applied strategies usually have low efficiency. The waste collection process can be modelled as a vehicle routing problem, in particular as a Team Orienteering Problem (TOP). In the TOP, a vehicle fleet is assigned to visit a set of customers, while executing optimized routes that maximize total profit and minimize resources needed. The objective of this work is to optimize the waste collection process while addressing the specific issues around fleet-management. This should be achieved by developing a software tool that implements a genetic algorithm to solve the TOP. We were able to accomplish the proposed task, as our computational tests have produced some challenging results in comparison to previous work around this subject of study. Specifically, our results attained 60% of the best known scores in a selection of 24 TOP benchmark instances, with an average error of 18.7 in the remaining instances. The usage of a genetic algorithm to solve the TOP proved to be an efficient method by outputting good results in an acceptable time.
J. Ferreira (&) J. A. Oliveira G. A. B. Pereira L. Dias Centre Algoritmi, Universidade do Minho, Braga, Portugal e-mail: [email protected] J. A. Oliveira e-mail: [email protected] G. A. B. Pereira e-mail: [email protected] L. Dias e-mail: [email protected] A. Quintas Graduation in Informatics Engineering, Universidade do Minho, Braga, Portugal e-mail: [email protected]
V. Snášel et al. (eds.), Soft Computing in Industrial Applications, Advances in Intelligent Systems and Computing 223, DOI: 10.1007/978-3-319-00930-8_32, Springer International Publishing Switzerland 2014
365
366
J. Ferreira et al.
1 Introduction In nature, there is no other living creature that endangers more the environment than us humans. Our way of living and eating habits represent the major source of solid waste production, along with the level of technology consumption. In order to manage and control this continuous waste generation, some decisions were taken. Giving a better and useful utilization to waste materials (recycling) is one of them, along with the corresponding reduction of the total amount of waste produced. In this case, waste separation is critical in order to generate a special stream of solid waste aside from the common waste. Therefore, a new collection system was developed and different collection points were made available to the population. There are companies specially dedicated to the separated waste collection for recycling, and that task is usually performed using a vehicle fleet, with fixed routes and schedules. The real problem lies, not on designing an easily accessible network of collection points, but yet on the development of efficient methods for performing waste collection, where constant resource management is vital. One issue that often arises is
Data Loading...
