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




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.


Press 'enter' for creating the tag

Publication's profile

Status of publication Published
Affiliation WU
Type of publication Journal article
Journal Journal of Heuristics
Citation Index SCI
WU Journalrating 2009 A
WU-Journal-Rating new FIN-A, INF-A, STRAT-B, WH-B
Language English
Title A heuristic solution method for node routing based solid waste collection problems
Volume 19
Number 2
Year 2013
Page from 129
Page to 156
Reviewed? Y
URL http://link.springer.com/article/10.1007%2Fs10732-011-9188-9
DOI http://dx.doi.org/10.1007/s10732-011-9188-9


Hemmelmayr, Vera (Details)
Doerner, Karl F.
Hartl, Richard F.
Rath, Stefan
Institute for Transport and Logistics Management (Details)
Google Scholar: Search