We address a particular pick-up 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 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 VRP 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 which 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 MILP 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.

A special VRP arising in the optimization of waste disposal: a real case

ARINGHIERI, ROBERTO;
2018-01-01

Abstract

We address a particular pick-up 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 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 VRP 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 which 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 MILP 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.
2018
52
2
277
299
http://pubsonline.informs.org/doi/full/10.1287/trsc.2016.0731
Aringhieri, Roberto; Bruglieri, Maurizio; Malucelli, Federico; Nonato, Maddalena
File in questo prodotto:
File Dimensione Formato  
2017-TranspSci-online.pdf

Accesso riservato

Descrizione: PDF editoriale (online version)
Tipo di file: PDF EDITORIALE
Dimensione 422.73 kB
Formato Adobe PDF
422.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2017-TranspSci-postprint.pdf

Open Access dal 08/04/2018

Descrizione: post print
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 944.05 kB
Formato Adobe PDF
944.05 kB Adobe PDF Visualizza/Apri
2018-TranspSci-published.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 669.73 kB
Formato Adobe PDF
669.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1596992
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 14
social impact