Subproject OVERSYS: Optimization in waste disposal logistics

Background

In the area of disposal logistics, the planning of suitable disposal precincts and personnel deployment planning represent two central challenges. A major problem in precinct planning is to determine when the waste containers of households in a disposal area are to be emptied and by which vehicle. On the one hand, citizens should be provided with a reliable waste calendar; on the other hand, a waste disposal company must operate as efficiently as possible, i.e. with a suitable number of vehicles and personnel.

Within the framework of district planning, daily routes must be planned for each vehicle in such a way that the containers from each street section are emptied within a time window and within a daily shift of a vehicle.

In personnel deployment planning, the employees are assigned to each (recurring) daily route for a specified planning period (e.g. one year). In addition to predefined requirements for vehicle crews, additional aspects such as specific working time models and working time regulations in the waste disposal industry and, in particular, the fulfillment of vacation wishes of all waste disposal employees must be taken into account.

Procedure

As a first step, the planning processes of the waste management companies, which are involved in this project, were analyzed in the areas of precinct and personnel scheduling. The aim was to filter out the decisive factors for the successful scheduling of vehicles and personnel.

In a second step, mathematical models for the scheduling of vehicles and personnel were created, which take into account all the previously identified factors. Due to their enormous complexity, the constructed mixed-integer mathematical optimization models required the development of new powerful methods of mathematical optimization in order to cover the specific requirements of waste management logistics and to solve the planning problem in a reasonable time.

Targeted results

In the area of both precinct planning and personnel planning, multi-level solution approaches were developed and implemented, which combine both heuristic and exact mathematical optimization approaches (e.g. decomposition approaches, column generation, resource-constrained shortest-path algorithms, Lagrange relaxation, subgradient optimization, and savings methods). The developed mathematical optimization methods are able to support a dispatcher in the later use of both precinct planning and personnel scheduling. They offer him a high degree of user interaction and influence on the planning results via a large number of possible parameter settings.

Contact: Prof. Dr.-Ing. Uwe Clausen

Funding and partners