Collection of Waste with Single Load Trucks: A Real Case

In this paper we consider a real case problem of waste collection in the county of Brescia, in the North of Italy, which we call the 1-Skip Collection Problem (1-SCP). This is a problem where a fleet of vehicles must collect a number of skips containing waste and transport them to one among different plants chosen on the basis of the kind of waste contained in the skip. Each vehicle has a capacity of one skip and it starts and ends its tour at the depot. Each time a vehicle collects a skip, it has to go to a plant and empty it. A number of constraints and problem characteristics have to be considered, as time windows for the customers and the plants, shift-time, different kinds of skips, number of drivers available to carry out the service and priorities assigned to the customers that have to be served. The objective is to minimize the total cost of the service given by the sum of the cost of the drivers engaged to carry out the service, the cost of the extra time and the penalty cost paid if a customer is not served. A heuristic algorithm to solve the real case problem is presented. The algorithm first constructs a feasible solution by means of the nearest neighbor algorithm and then improves it. The computational results show that the solution of the algorithm is much better than the solution applied by the firm which carries out the service since it serves a larger number of skips with a smaller number of drivers.