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

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

0.00 Avg rating0 Votes
Article ID: iaor20164864
Volume: 50
Issue: 4
Start Page Number: 1223
End Page Number: 1238
Publication Date: Nov 2016
Journal: Transportation Science
Authors: , , ,
Keywords: combinatorial optimization, heuristics: local search, graphs
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.

Reviews

Required fields are marked *. Your email address will not be published.