Tactical waste collection: column generation and mixed integer programming based heuristics
- PDF / 1,378,140 Bytes
- 38 Pages / 439.37 x 666.142 pts Page_size
- 11 Downloads / 194 Views
Tactical waste collection: column generation and mixed integer programming based heuristics Jens Van Engeland1 · Jeroen Beliën2,3 Received: 28 December 2018 / Accepted: 6 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Environmental considerations and corresponding legislation cause a shift from waste management to materials management, requiring efficient collection of these flows. This paper develops a model for building tactical waste collection schemes in which a set of capacitated vehicles visits a set of customers during a given time period. Each vehicle must visit the disposal facility to discharge the waste after each customer visit. This is motivated by the fact that the waste of each customer has to be weighed at the disposal facility. The goal is to find a set of routes for each vehicle that satisfy both the demand and the frequency constraints and minimize the total cost. Since a state-of-the-art solver could not find a solution with a reasonable gap within an acceptable time limit, a column generation and a mixed integer programming-based heuristic are proposed. While the mixed integer programming-based heuristic outperforms the column generation heuristic in terms of solution quality, the lower bound provided by column generation allows to prove the small optimality gaps of the solutions obtained. Moreover, by applying both heuristics on instances derived from real-life data, they proved to be capable of finding good quality solutions in small computation times. Keywords OR in service industries · Waste collection · Mixed integer programming · Column generation · Tactical level planning
* Jeroen Beliën [email protected] Jens Van Engeland [email protected] 1
Center for Economics and Corporate Sustainability, Faculty of Economics and Business, KU Leuven, Campus Brussels, Warmoesberg 26, 1000 Brussels, Belgium
2
Center for Information Management, Modeling and Simulation, Faculty of Economics and Business, KU Leuven, Campus Brussels, Warmoesberg 26, 1000 Brussels, Belgium
3
Research Centre for Operations Management, Faculty of Economics and Business, KU Leuven, Campus Leuven, Naamsestraat 69, 3000 Leuven, Belgium
13
Vol.:(0123456789)
J. Van Engeland, J. Beliën
1 Introduction Due to environmental awareness and corresponding legislation [see, e.g., the EU circular economy strategy (European Commission 2017)], attention is shifting from waste management to materials management. The “EU revised legislative proposals on waste” set ambitious goals: a common EU target of 65% and 75% for recycling municipal and packaging waste, respectively, by 2030. The focus on separate waste and material flows will have an undeniable impact on efficient collection schemes. This research was inspired by a real-life problem in the context of collecting municipal solid waste, and hence a customer can be seen as a neighborhood (sequence of streets), or even an entire municipal district, borough, municipality or suburb. The model is generic, though, and is also applicab
Data Loading...
