Integrating a heterogeneous fixed fleet and a exible assignment of destination depots in the waste collection VRP with intermediate facilities

Markov, Iliya (Haute école de gestion de Genève, HES-SO // Haute Ecole Spécialisée de Suisse Occidentale) ; Varone, Sacha (Haute école de gestion de Genève, HES-SO // Haute Ecole Spécialisée de Suisse Occidentale) ; Bierlaire, Michel (Transport and Mobility Laboratory School of Architecture, Civil and Environmental Engineering Ecole Polytechnique Fédérale de Lausanne Station 18, 1015 Lausanne, Switzerland)

We consider a complex recyclable waste collection problem that extends the class of vehicle routing problems with intermediate facilities by integrating a heterogeneous fixed fleet and a flexible assignment of destination depots. Several additional side constraints, such as a mandated break period contingent on tour start time, multiple vehicle capacities, and site dependencies are also included. This specific problem was inspired by a real-world application and does not appear in the literature. It is modeled as an MILP which is enhanced with several valid inequalities. Due to the rich nature of the problem, state-of-the-art solvers are only able to tackle instances of small to medium size. To solve realistic instances, we propose a multiple neighborhood search heuristic capable of systematically treating all problem features and general enough to respond to the varying characteristics of the case study regions for which it is intended. The results show that the heuristic achieves optimality on small instances, exhibits competitive performance in comparison to state-of-the-art solution methods for special cases of our problem, and leads to important savings in the state of practice. Moreover, it highlights and quantifies the savings from allowing a flexible depot assignment. The data from the state of practice comes from a company in the waste collection industry in Geneva, Switzerland.

Article Type:
Economie et Services
HEG - Genève
CRAG - Centre de Recherche Appliquée en Gestion
Published in:
Transportation research part B: methodological
Numeration (vol. no.):
February 2016, vol. 85, pp. 256-273
Appears in Collection:

 Record created 2016-05-26, last modified 2020-10-27

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)