We study the general routing problem defined on a mixedgraph 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.

A Matheuristic Algorithm for the Mixed Capacitated General Routing Problem

Lagana' D;Musmanno R;Vocaturo F
2014

Abstract

We study the general routing problem defined on a mixedgraph 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.
routing problem; mixed graph; neighborhood search; branch-and-cut
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/137354
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 14
social impact