Premium
A matheuristic algorithm for the mixed capacitated general routing problem
Author(s) -
Bosco Adamo,
Laganà Demetrio,
Musmanno Roberto,
Vocaturo Francesca
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21574
Subject(s) - mathematical optimization , iterated local search , computer science , vehicle routing problem , benchmark (surveying) , arc routing , routing (electronic design automation) , mathematics , graph , heuristic , local search (optimization) , theoretical computer science , computer network , geodesy , geography
We study the general routing problem defined on a mixed graph and subject to capacity constraints. Such a problem aims to find the set of routes of minimum overall cost servicing a subset of required elements like vertices, arcs, and edges, without exceeding the capacity of a fleet of homogeneous vehicles based at the same depot. The problem is a generalization of a large variety of node and arc routing problems. It belongs to the family of NP‐hard combinatorial problems. Instances with a small number of vehicles and required elements can be effectively solved by means of exact methods. Heuristic approaches are helpful to obtain feasible solutions for medium to large size instances. In this article, we present a matheuristic approach to the problem, in which a set of neighborhood structures is iteratively searched and a branch‐and‐cut algorithm is used to improve the quality of the solutions found during the search. The search is iterated within a defined global number of steps, in which the solution space is explored. We demonstrate the effectiveness of this approach through an extensive computational study on several benchmark instances. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(4), 262–281 2014