Routing-problem approaches to the design of a system for urban waste collection

Résumé

A routing problem arises when there is a set of demand points that have to be served by finding the "best" routes in order to provide the required service. Finding these "best" routes consists of optimizing one or several objective functions associated to these routes. This Ph.D. thesis is motivated by a real-world routing problem. Specifically, we focus on the waste collection problem in the city of Seville and its resolution by using approximate algorithms. Waste collection is an interesting routing problem not only due to its high practical relevance, but also because it constitutes one of the most difficult operational problems faced by local authorities in any large city. Seville has a population of 703,021 inhabitants (according to official statistics of 2011) and is ranked as the fourth largest city of Spain. Urban waste is collected every single day of the year, i.e., seven days a week. The road network of Seville can be represented by a directed graph with 99,427 points that correspond to street crossings and dead-end streets, 224,638 fragments of streets delimited by two points and 1,642 streets where there are containers placed. According to the local authority responsible for the waste collection in the city (February, 2012), 20 vehicles currently collect the waste of 2,821 containers placed at different locations all over the city. The annual waste generated amounts to approximately 23.2 litres per inhabitant. This extremely tough problem can be described as follows. The waste generated in the city is the responsibility of the local authorities. Citizens deposit their refuse in containers along the streets and these containers must all be collected every day by a fleet of vehicles whose capacity cannot be exceeded. Each vehicle must travel along a route that is defined as a sequence of two or more trips due to the relatively small capacity of each vehicle, and the length of the working day must be satisfied. In the initial trip or open trip, vehicles leave the depot and start to collect refuse and once their capacity is full then go to the landfill. When vehicles have emptied the refuse into the landfill, they then begin as many closed trips as necessary without exceeding the working day. In the closed trips, vehicles start their trajectory from the landfill and return back to it when their capacity is full again. In closing, once vehicles have deposited the last load of refuse in the landfill they all return to the depot. This Ph.D. thesis is organized as follows. In Chapter 1, a survey of routing problems and its variants is presented. We draw a distinction between vehicle (node) routing problems and arc routing problems. Furthermore, in order to equalize the two classes of problems, we describe well-known transformations and we propose a new and general transformation. This transformation can be seen as a generalization of the transformations that have been proposed in the literature so far. In Chapter 2, background information on well-known solution methods is provided. In particular, a quick outline is drawn of the most popular, exact and approximate methods used to solve routing problems. Furthermore, a parallel is drawn between single-objective optimization problems, which find optimal or feasible solutions, and multi-objective optimization problems, which provide non-dominated or Pareto optimal solutions. We then describe performance metrics, which enables the quality of the solutions obtained to be measured. The main contribution of this chapter is that two versions of routing problems are solved by using new metaheuristics. Specifically, a new algorithm is designed to solve single-objective routing problems, in which the objective is to minimize the total routing cost, and four algorithms are designed to solve multi-objective routing problems, in which we do not only minimize the total routing cost but also balance the routes. In particular, the proposed algorithms combine two metaheuristics: Greedy Randomized Adaptive Search Procedure and Variable Neighborhood Descent. In Chapter 3, the current waste collection problem in Seville is presented progressively. First, we focus on describing and modelling the waste collection in this city. The real-world problem cannot be solved by using exact methods, and hence the validity of the formulation is proved by using a number of small and medium-sized literature problems. The limitation imposed on the solution of these problems by using exact methods leads us to use approximate methods to solve the real-world problem. The proposed algorithms presented in Chapter 2 are therefore adapted to solve the real-world problem. Again, both approaches are taken into account: the single-objective problem, in which the objective is to minimize the total distance travelled by all the vehicles; and the multi-objective problem, in which the objectives include the minimization of the total distance as well as a balance across the working day of the workers in each route. This dissertation draws to a close with conclusions being reached and future research being proposed.