A heuristic solution method for node routing based solid waste collection problems

Hemmelmayr, Vera and Doerner, Karl and Hartl, Richard F. and Rath, Stefan (2013) A heuristic solution method for node routing based solid waste collection problems. Journal of Heuristics, 19 (2). pp. 129-156. ISSN 1572-9397

Available under License Creative Commons: Attribution-NonCommercial 4.0 International (CC BY-NC 4.0).

Download (802kB)


This paper considers a real world waste collection problem in which glass, metal, plastics, or paper is brought to certain waste collection points by the citizens of a certain region. The collection of this waste from the collection points is therefore a node routing problem. The waste is delivered to special sites, so called intermediate facilities (IF), that are typically not identical with the vehicle depot. Since most waste collection points need not be visited every day, a planning period of several days has to be considered. In this context three related planning problems are considered. First, the periodic vehicle routing problem with intermediate facilities (PVRP-IF) is considered and an exact problem formulation is proposed. A set of benchmark instances is developed and an efficient hybrid solution method based on variable neighborhood search and dynamic programming is presented. Second, in a real world application the PVRP-IF is modified by permitting the return of partly loaded vehicles to the depots and by considering capacity limits at the IF. An average improvement of 25% in the routing cost is obtained compared to the current solution. Finally, a different but related problem, the so called multi-depot vehicle routing problem with inter-depot routes (MDVRPI) is considered. In this problem class just a single day is considered and the depots can act as an intermediate facility only at the end of a tour. For this problem several instances and benchmark solutions are available. It is shown that the algorithm outperforms all previously published metaheuristics for this problem class and finds the best solutions for all available benchmark instances.

Item Type: Article
Additional Information: This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Keywords: reverse logistics / metaheuristics / solid waste collection / periodic vehicle routing problems / multi-depot vehicle routing problems
Divisions: Departments > Welthandel > Transportwirtschaft und Logistik > Wakolbinger
Version of the Document: Published
Variance from Published Version: None
Depositing User: Elena Simukovic
Date Deposited: 18 Apr 2017 16:46
Last Modified: 24 Jul 2020 14:40
Related URLs:
FIDES Link: https://bach.wu.ac.at/d/research/results/56821/
URI: https://epub.wu.ac.at/id/eprint/5519


View Item View Item


Downloads per month over past year

View more statistics