The paper tackles 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.

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

NONATO, Maddalena
Ultimo
2018

Abstract

The paper tackles 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.
2018
Aringhieri, Roberto; Bruglieri, Maurizio; Malucelli, Federico; Nonato, Maddalena
File in questo prodotto:
File Dimensione Formato  
00-gesenu-mainrevised.pdf

accesso aperto

Descrizione: preprint
Tipologia: Pre-print
Licenza: PUBBLICO - Pubblico con Copyright
Dimensione 625.81 kB
Formato Adobe PDF
625.81 kB Adobe PDF Visualizza/Apri
11392_2370011_FULL_Nonato.pdf

solo gestori archivio

Tipologia: Full text (versione editoriale)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 669.73 kB
Formato Adobe PDF
669.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in SFERA 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/11392/2370011
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 15
social impact