Groupe d’études et de recherche en analyse des décisions

# An Ant Colony Optimization Metaheuristic for the Undirected Rural Postman Problem

## Demetrio Laganà, Gilbert Laporte, Francesco Mari, Roberto Musmanno et Ornella Pisacane

This paper describes a new heuristic for the well-known Undirected Rural Postman Problem. It consists of two steps: it first constructs a partial solution using the Ant Colony Optimization metaheuristic, and the remaining required edges are then gradually inserted. Computational results on a set of benchmark instances are presented and comparisons with alternative heuristics are performed. The optimality gap is also computed by running a branch-and-cut algorithm.

, 22 pages