A Special Vehicle Routing Problem Arising in the Optimization of Waste Disposal: A Real Case

Roberto Aringhieri (), Maurizio Bruglieri (), Federico Malucelli () and Maddalena Nonato ()
Additional contact information
Roberto Aringhieri: Dipartimento di Informatica, Università degli Studi di Torino, 10124 Torino, Italy
Maurizio Bruglieri: Dipartimento di Design, Politecnico di Milano, 20133 Milano, Italy
Federico Malucelli: Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, 20133 Milano, Italy
Maddalena Nonato: Dipartimento di Ingegneria, Università degli Studi di Ferrara, 44122 Ferrara, Italy

Transportation Science, 2018, vol. 52, issue 2, 277-299

Abstract: We address a particular pickup and delivery vehicle routing problem arising in the collection and disposal of bulky recyclable waste. Containers of different types, used to collect different waste materials, once full, must be picked up to be emptied at suitable disposal plants and replaced by empty containers alike. All requests must be served, and routes are subject to a maximum duration constraint. Minimizing the number of vehicles is the main objective, while minimizing the total route duration is a secondary objective. The problem belongs to the class of rollon–rolloff vehicle routing problems (RR-VRPs), though some characteristics of the case study, such as the free circulation of containers and the limited availability of spare containers, allow us to exploit them in the solution approach. We formalize the problem as a special vehicle routing problem on a bipartite graph, we analyze its structure, and we compare it to similar problems emphasizing the impact of limited spare containers. Moreover, we propose a neighborhood-based metaheuristic that alternatively switches from one objective to the other along the search path and periodically destroys and rebuilds parts of the solution. The main algorithm components are experimentally evaluated on real and realistic instances, the largest of which fail to be solved by a mixed-integer linear programming solver. We are increasingly competitive with the solver as the instance size increases, especially regarding fleet size. In addition, the algorithm is applied to the benchmark instances for the RR-VRP.

Keywords: waste management; rollon–rolloff VRP; distance-constrained VRP; hierarchical neighborhood search; spare containers (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/trsc.2016.0731 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:52:y:2018:i:2:p:277-299

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().