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. ; acceptedVersion


    Access

    Download


    Export, share and cite



    Title :

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


    Contributors:

    Publication date :

    2016-01-01


    Remarks:

    cristin:1352810
    1223-1238 ; 50 ; Transportation Science ; 4



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629




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

    Dell Amico, Mauro / Díaz, José Carlos Díaz / Hasle, Geir et al. | British Library Online Contents | 2016


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

    DELL'AMICO, Mauro / DIAZ DIAZ, Jose Carlos / IORI, MANUEL et al. | BASE | 2016

    Free access


    Memetic algorithm with adaptive local search for Capacitated Arc Routing Problem

    Yao, Tingting / Yao, Xin / Han, Shuangshuang et al. | IEEE | 2017


    An iterated local search algorithm for the single-vehicle cyclic inventory routing problem

    Vansteenwegen, Pieter / Mateo Doll, Manuel | BASE | 2014

    Free access