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.
2017
978-3-319-67307-3
978-3-319-67308-0
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11567/998671
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact