To main content

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


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 (GRP). 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 datasets, and good results on four well-known CVRP benchmarks.


Academic lecture


  • Research Council of Norway (RCN) / 227071
  • Research Council of Norway (RCN) / 205298
  • Research Council of Norway (RCN) / 217108




  • Mauro Dell'Amico
  • Jose Carlos Diaz Diaz
  • Geir Hasle
  • Manuel Iori


  • University of Modena and Reggio Emilia
  • SINTEF Digital / Mathematics and Cybernetics

Presented at

The third meeting of the EURO Working Group on Vehicle Routing and Logistics Optimization (VeRoLog 2014)




22.06.2014 - 25.06.2014


SINTEF, Høgskolen i Molde, NTNU, NHH



View this publication at Cristin