The close-enough arc routing problem is a generalization of the classic arc routing problem and it has many interesting real-life applications. In this paper, we propose some techniques to reduce the size of the input graph and a new effective mixed integer programming formulation for the problem. Our experiments on directed graphs show the effectiveness of our reduction techniques. Computational results obtained by comparing our MIP model with the existing exact methods show that our algorithm is really effective in practice.
A Flow Formulation for the Close-Enough Arc Routing Problem
Cerrone C.;
2017-01-01
Abstract
The close-enough arc routing problem is a generalization of the classic arc routing problem and it has many interesting real-life applications. In this paper, we propose some techniques to reduce the size of the input graph and a new effective mixed integer programming formulation for the problem. Our experiments on directed graphs show the effectiveness of our reduction techniques. Computational results obtained by comparing our MIP model with the existing exact methods show that our algorithm is really effective in practice.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Cerrone2017_Chapter_AFlowFormulationForTheClose-En.pdf
accesso chiuso
Tipologia:
Documento in versione editoriale
Dimensione
261.79 kB
Formato
Adobe PDF
|
261.79 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
