We study the mixed capacitated general routing problem (MCGRP) in which a fleet of capacitated vehicles has to serve a set of requests by traversing a mixed weighted graph. The requests may be located on nodes, edges, and arcs. The problem has theoretical interest because it is a generalization of the capacitated vehicle routing problem (CVRP), the capacitated arc routing problem (CARP), and the general routing problem. It is also of great practical interest since it is often a more accurate model for real-world cases than its widely studied specializations, particularly for so-called street routing applications. Examples are urban waste collection, snow removal, and newspaper delivery. We propose a new iterated local search metaheuristic for the problem that also includes vital mechanisms from adaptive large neighborhood search combined with further intensification through local search. The method utilizes selected, tailored, and novel local search and large neighborhood search operators, as well as a new local search strategy. Computational experiments show that the proposed metaheuristic is highly effective on five published benchmarks for the MCGRP. The metaheuristic yields excellent results also on seven standard CARP data sets, and good results on four well-known CVRP benchmarks, including improvement of the best known upper bound for one instance.

An Adaptive Iterated Local Search for the Mixed Capacitated General Routing Problem / Dell'Amico, Mauro; Diaz Diaz, Jose Carlos; Hasle, Geir; Iori, Manuel. - In: TRANSPORTATION SCIENCE. - ISSN 0041-1655. - STAMPA. - 50:4(2016), pp. 1223-1238. [10.1287/trsc.2015.0660]

An Adaptive Iterated Local Search for the Mixed Capacitated General Routing Problem

DELL'AMICO, Mauro;DIAZ DIAZ, Jose Carlos;IORI, MANUEL
2016

Abstract

We study the mixed capacitated general routing problem (MCGRP) in which a fleet of capacitated vehicles has to serve a set of requests by traversing a mixed weighted graph. The requests may be located on nodes, edges, and arcs. The problem has theoretical interest because it is a generalization of the capacitated vehicle routing problem (CVRP), the capacitated arc routing problem (CARP), and the general routing problem. It is also of great practical interest since it is often a more accurate model for real-world cases than its widely studied specializations, particularly for so-called street routing applications. Examples are urban waste collection, snow removal, and newspaper delivery. We propose a new iterated local search metaheuristic for the problem that also includes vital mechanisms from adaptive large neighborhood search combined with further intensification through local search. The method utilizes selected, tailored, and novel local search and large neighborhood search operators, as well as a new local search strategy. Computational experiments show that the proposed metaheuristic is highly effective on five published benchmarks for the MCGRP. The metaheuristic yields excellent results also on seven standard CARP data sets, and good results on four well-known CVRP benchmarks, including improvement of the best known upper bound for one instance.
50
4
1223
1238
An Adaptive Iterated Local Search for the Mixed Capacitated General Routing Problem / Dell'Amico, Mauro; Diaz Diaz, Jose Carlos; Hasle, Geir; Iori, Manuel. - In: TRANSPORTATION SCIENCE. - ISSN 0041-1655. - STAMPA. - 50:4(2016), pp. 1223-1238. [10.1287/trsc.2015.0660]
Dell'Amico, Mauro; Diaz Diaz, Jose Carlos; Hasle, Geir; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
DellAmico-DiazDiaz-Hasle-Iori-2016-Editorial.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 399.28 kB
Formato Adobe PDF
399.28 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
DellAmico-DiazDiaz-Hasle-Iori-2016-Supplementary.pdf

accesso aperto

Descrizione: Supplemento on-line
Tipologia: Altro materiale allegato
Dimensione 91.94 kB
Formato Adobe PDF
91.94 kB Adobe PDF Visualizza/Apri
DellAmico-DiazDiaz-Hasle-Iori-2016-postprint.pdf

accesso aperto

Descrizione: Versione post-print
Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 360.25 kB
Formato Adobe PDF
360.25 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

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