To main content

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

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 (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.
Oppdragsgiver: Norges forskningsråd / eVita
Read publication

Category

Report

Client

  • SINTEF AS / 102002202

Language

English

Author(s)

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

Affiliation

  • Unknown
  • SINTEF Digital / Mathematics and Cybernetics

Year

2014

Publisher

SINTEF

Issue

A26278

ISBN

978-82-14-05361-6

View this publication at Cristin